Marco Lapegna » 16.I Sistemi Operativi distribuiti - parte terza

Bilanciamento del carico

Un obiettivo generale in tutti i sistemi con molte CPU è il bilanciamento del carico:

• distribuire equamente il carico dei processi su tutte le CPU, in maniera che nessuna di esse rimanga inutilizzata mentre le altre sono sovraccariche;
• riduce il tempo medio di risposta dei processi.

Due tipi

1. bilanciamento statico;
2. bilanciamento dinamico.

Bilanciamento statico

Una applicazione viene assegnata ad un gruppo di CPU e vi rimane per tutta l’esecuzione

Basso sovraccarico.

Non tiene conto delle variazioni del numero e del tipi di processi di una applicazione.

Utile quando l’applicazione ha un comportamento predicibile e noto prima dell’esecuzione (es sistemi con esigenze real time).

Bilanciamento dinamico

Il sistema misura il carico di lavoro di ogni processore.

Quando il carico tra i nodi è sbilanciato il sistema trasferisce i processi dai nodi sovraccarichi a quelli scarichi (migrazione dei processi).

Utile in applicazioni dove le comunicazioni tra i nodi non sono costanti e quando i processi hanno un tempo di esecuzione non predicibile.

Problemi

• Bilanciare il costo della migrazione con il vantaggio che ne può derivare (funzione di costo).
• Migrazione su nodi molto lontani può essere dispendiosa.
• Carico delle cpu può variare nel tempo e rendere inutile la migrazione.

Soluzione

• Comunicazione solo tra nodi vicini.
• Diffusione del carico attraverso il sistema.

Problema

Quando iniziare la migrazione dei processi?

Due politiche
1. Iniziata dal sender:

• la migrazione ha luogo quando il sistema registra un nodo sovraccarico;
• utile per sistemi generalmente scarichi (ci saranno pochi mittenti).

2. Iniziata dal receiver:

• la migrazione ha luogo quando il sistema registra un nodo scarico;
• utile per sistemi generalmente carichi (ci saranno pochi destinatari).

Possibili soluzioni ibride.

Algoritmo ad offerta

Esempio di migrazione iniziata dal sender.

I processori con carico di lavoro elevato cercano un numero fissato (ad es. 10) di processori che hanno un carico basso, partendo dai nodi vicini.

Un processore che ha un carico di lavoro basso, segnala la sua disponibilità pubblicando una “offerta”.

Il valore dell’offerta è calcolata in base alla differenza di carico tra i due processori e in base alla distanza tra i nodi.

Il sender invia il processo al processore che ha offerto di più.

Algoritmo drafting

Esempio di migrazione iniziata dal receiver.

Ogni processore mantiene informazioni del carico degli altri processori in apposite tabelle.

Al variare del carico, le informazioni sono fatte scorrere attraverso la rete, ed ogni processore aggiorna le proprie tabelle.

I processori sottoutilizzati possono richiedere processi ai processori sovraccarichi.

Motivazioni della migrazione dei processi

Il bilanciamento dinamico del carico è basato sulla migrazione di processi tra le CPU.
Oltre a ciò sussistono altri aspetti che richiedono la migrazione dei processi:

• se un nodo si guasta, il lavoro svolto si perde;
• comunicazone tra processi su CPU distanti;
• uso di risorse di nodi distanti.

Benefici

• Miglioramento della tolleranza ai guasti.
• Bilanciamento del carico.
• Riduzione dei costi di comunicazione.
• Condivisione delle risorse.

Migrazione freezing e restarting

Cosa migra (lo stato del processo)

• Pagine del processo nella memoria virtuale.
• Contenuto dei registri della CPU.
• Stato dei file aperti.

Come migra una volta che i processi sorgente e destinatario si accordano per la migrazione

• Il sorgente sospende il processo che deve migrare.
• Il sorgente crea una coda per i messaggi diretti al ricevente.
• Il sorgente trasmette lo stato del processo ad un processo “vuoto” creato dal destinatario destinatario.
• Il sorgente e il destinatario comunicano a tutti gli altri nodi la nuova posizione del processo.
• Il sorgente elimina l’istanza locale del processo.

Un buon meccanismo di migrazione

Trasparenza: altri processi cooperanti non dovrebbero notare se un processo è migrato.

Minima dipendenza residua: il processo migrato non dovrebbe più usare informazioni sulla vecchia CPU (info sulla paginazione, comunicazione con processi sul vecchio nodo).

Efficienza: minimo tempo di trasferimento e minimo costo di rilocazione.

Costo della migrazione

In generale la migrazione freezing e restarting è un meccanismo semplice da implementare ma costoso e poco efficiente.

Contesto (registri, program counter) pochi KB.
Spazio di indirizzamento (pagine della memoria) molti MB.

Una soluzione: migrazione pigra

• Viene trasferito solo il contesto.
• Le pagine della memoria vengono trasferite al momento del riferimento.
• Basso overhead ma alta dipendenza residua.

Meccanismi alternativi

Migrazione sporca

• Viene trasferito il contesto e le pagine modificate (sporche).
• Le pagine non modificate risiedono su un disco comune ai due processori.
• Overhead maggiore ma minore dipendenza residua.

Migrazione flushing

• Viene trasferito solo il contesto.
• le pagine sporche in memoria vengono salvate su un disco comune Basso overhead ma molti page fault in seguito.

Migrazione con precopia

• Si trasferiscono le pagine sporche prima della sospensione del processo, sovrapponendo esecuzione e migrazione.
• Pagine trasferite ed eventualmente modificate vengono ritrasmesse.
• Ottimale se durante il trasferimento delle pagine vengono modificate poche pagine.

La gestione della memoria

Un sistema multiprocessore è composto da più CPU che condividono un’unica memoria.

Problema della sincronizzazione degli accessi (mutua esclusione).

Le tecniche per sistemi monoprocessori non sono sempre utilizzabili:

• disabilitazione delle interruzioni ( non garantisce mutua esclusione);
• test and set (saturazione del buffer se molte CPU testano la variabile lock).

Possibili soluzioni

Lock pausa risveglio
Simile alle condizioni basate su attesa attiva ma con minor spreco di cicli di CPU e minor traffico sul bus:

• il primo processo che chiede una risorsa protetta ottiene il lock;
• processi successivi che richiedono la risorsa e non la ricevono si pongono in attesa;
• il processo che rilascia la risorsa sveglia anche il processo in attesa.

Non esclude la race condition.

Lock read/write
Obiettivo: rilassare le condizioni di accesso.
Basato sul protocollo di sincronizzazione lettori/scrittori.

• Una CPU alla volta può accedere alla memoria condivisa se deve scrivere;
• Molte CPU possono leggere contemporaneamente.

Esempio

Necessita' di un protocollo di coerenza.

Protocollo write through

In caso di successivi riferimenti si preleva nuovamente il dato (aggiornato) dalla memoria.