Marco Lapegna » 17.I Sistemi Operativi distribuiti - parte quarta

Ordinamento degli eventi

Un sistema monoprocessore:

• unico clock;
• unica memoria.

Possibile stabilire un ordinamento degli eventi

Un sistema multicomputer/distribuito:

• non ha memoria comune;
• non ha unico clock.

Impossibile stabilire un ordinamento completo degli eventi

Relazione “verificato prima”

Denotata con →

Definizione: A si e’ verificato prima di B se (A → B )

A e B sono eventi dello stesso processo e A è stato eseguito prima di B.
A è l’evento di inviare un messaggio da un processo e B è l’evento di ricevere lo stesso messaggio da un altro processo.
A → C e C → B (proprietà transitiva).
Se non è possibile stabilire una relazione di “verificato prima” tra due eventi A e B, allora i due eventi devono essere considerati concorrenti.

Esempio

Implementazione di →

Si associa una marca temporale ad ogni evento del sistema e si richiede che per ogni coppia di eventi A e B, se A → B, allora la marca temporale di A deve essere minore della marca temporale di B.

In ogni processo P_i la marca temporale è realizzata mediante il valore di un orologio logico LC_i. L’orologio logico è un contatore che viene incrementato ad ogni evento all’interno del sistema.

Se un processo riceve un messaggio con marca temporale minore, esso sincronizza il suo orologio logico.

Esempio

Mutua esclusione distribuita (DME)

Il problema della mutua esclusione è un altro problema che richiede un coordinamento con decisioni che devono essere prese in maniera distribuita.

Assunzioni

• Il sistema ha n processi; ogni processo risiede in un differente processore.
• Ogni processo ha una sezione critica che richiede la mutua esclusione.

Richieste
Se P_i è dentro la propria sezione critica allora nessun altro processo deve essere dentro la propria sezione critica.

Algoritmo centralizzato

Uno dei processi nel sistema è scelto come coordinatore.

• Un processo che vuole entrare nella sezione critica manda un messaggio di richiesta al coordinatore.
• Il coordinatore decide se può entrare, in caso affermativo risponde con un messaggio, altrimenti mette in attesa il processo richiedente.
• Quando il processo esce dalla sezione critica, manda un messaggio di rilascio al coordinatore e procede con la sua esecuzione.

Lo schema garantisce la mutua esclusione e evita l’attesa indefinita.

Richiede 3 comunicazioni per ogni accesso alla sezione critica.

Approccio distribuito

Basato sul concetto di marca temporale.
Quando un processo P_i vuole entrare nella sezione critica genera una nuova marca temporale TS, e manda un messaggio di richiesta (P_i ,TS) a tutti gli altri processi del sistema.
Quando un processo P_j riceve un messaggio di richiesta può:

• rispondere immediatamente;
• differire la risposta.

Quando il processo P_i riceve la risposta da tutti gli altri processi, può entrare nella sezione critica e differisce tutte le eventuali richieste in arrivo.
All’uscita dalla sezione critica il processo risponde a tutte le richieste sospese.

Algoritmo di Agrawala e Ricart per la mutua esclusione.

Esempio: 3 processi P1, P2 e P3

Algoritmo di Agrawala e Ricart

Aspetti positivi

• Garantita l’assenza di deadlock.
• Garantita l’assenza di starvation (si entra secondo le TS).
• Numero di messaggi per entrare nella sezione critica =  2 x (n – 1).

Aspetti negativi

• Necessità di conoscere l’identità di tutti gli altri processi e comunicazioni globali.
• Se un nodo cade tutto lo schema fallisce.
• Processi che non devono entrare nella sezione critica sono interrotti frequentemente e inutilmente → adatto a pochi processi.

Metodo con passaggio del contrassegno

I processi sono organizzati logicamente in una struttura ad anello.

Uno speciale messaggio, il contrassegno, viene fatto circolare lungo l’anello: chi lo possiede può entrare nella sezione critica e trattiene il contrassegno.

Quando il processo esce, il contrassegno viene rimesso in circolazione.

Se il processo non vuole entrare nella sezione critica, lo passa al successivo.

Se l’anello è unidirezionale non vi sono situazioni di attesa indefinita.

Prevenzione dei deadlock

Alcuni approcci per la prevenzione dei deadlock nei sistemi monoprocessori possono essere utilizzati nei sistemi multicomputer/distribuiti.

Ordinamento globale delle risorse

• Si assegna un unico identificativo alle risorse.
• Un processo può acquisire la risorse numero i solo se non è già in possesso di una risorsa j con i > j.
• Semplice da implementare e con basso overhead.

Algoritmo del banchiere

• Si designa uno dei processi come banchiere, che mantiene le strutture dati (approccio centr.).
• Gli altri processi contattano il banchiere per sapere se possono acquisire le risorse.
• Anche implementato facilmente ma richiede un maggiore overhead.

Rilevazione dello stallo

Il problema principale in un sistema distribuito è decidere come e dove mantenere il grafo di attesa.

Usualmente si mantiene in ogni sito un grafo di attesa locale.

I nodi del grafo corrispondono a tutti i processi (anche di altri siti) ai quali è stata allocata una risorsa locale.

Non è sufficiente verificare l’assenza di cicli all’interno dei singoli grafi locali.

Approccio centralizzato

L’unione di tutti i grafi è mantenuta da un singolo processo: il coordinatore per il rilevamento.

Differenti opzioni per la costruzione del grafo di attesa :

1. ogni volta che si inserisce o si rimuove un arco in uno dei grafi locali (dispendioso);
2. periodicamente, ad es. quando un numero minimo di cambi sono stati fatti nei grafi locali;
3. solo quando il coordinatore decide di verificare la presenza di un deadlock.

Un problema: falsi cicli di deadlock (deadlock fantasma).

Approccio distribuito

Tutti i siti condividono la responsabilità di rilevare lo stallo.
Ogni sito costruisce un grafo di attesa locale che è parte del grafo globale.

Ad ogni grafo locale si aggiunge un nodo P_ex per fare riferimento a risorse di altri siti.

• Se un grafo locale contiene un ciclo che non involve P_ex, allora il sistema è in uno stato di deadlock (lo stallo è interno al sito).
• Se un grafo locale contiene un ciclo che involve P_ex allora c’è possibilità di deadlock.

Problema

Come fare a vedere se c’è effettivamente uno stallo?

Se S1 trova un ciclo che coinvolge P_ex nel sito S2 allora manda le informazioni del proprio grafo a S2, che aggiorna il proprio grafo con le nuove informazioni.

Ciclo che non coinvolge P_ex allora c’è deadlock.

Nel caso di più siti puo’ essere necessario passare le informazioni da sito a sito.

In un numero di passi al più pari al numero di siti viene rilevato lo stallo.

Algoritmi di elezione (leader election)

Molti algoritmi alla base dei sistemi operativi distribuiti richiedono un coordinatore (o master, leader):

• Per la mutua esclusione;
• Per mantenere grafi globali;
• Controllo di dispositivi di I/O.

In caso di caduta del processo o di interruzione della comunicazione è necessario eleggere un nuovo coordinatore.

Algoritmi basati sul concetto di priorità (per semplicita’ priorita’ di Pi = i).
Il coordinatore e’ il processo con priorità maggiore.
Si assume nel seguito una corrispondenza 1-1 tra processi e siti.

Algoritmo dello spaccone

Se un processo Pi invia una richiesta e il coordinatore non risponde in un intervallo di tempo T, allora Pi assume che il coordinatore non è più attivo e cerca di eleggere se stesso come nuovo coordinatore:

Pi invia un messaggio a ogni processo Pj con un numero di priorità più alto (j > i) ed aspetta per un tempo T’ la risposta da tutti gli altri processi.

• Se non riceve risposta, Pi assume che tutti i processi Pj non sono attivi ed elegge se stesso come coordinatore. Pi fa partire una copia del coordinatore e manda un messaggio a tutti i processi con priorità minore di i, informandoli che lui è il nuovo coordinatore.
• Se riceve una risposta, Pi aspetta di ricevere un messaggio che lo informi quale processo con priorità più alta della sua è stato eletto.

Algoritmo dello spaccone (segue)

Un processo Pi in ogni istante può ricevere un messaggio da Pj del tipo:

• Pj è il nuovo coordinatore (j > i). Pi registra tale informazione
• Pj ha iniziato l’elezione di un nuovo coordinatore (j < i). Pi manda una risposta a Pj e inizia il suo algoritmo di elezione

Quando un processo caduto viene ripristinato, inizia immediatamente l’algoritmo di elezione.

Se non ci sono processi attivi con priorità maggiore, il processo ripristinato si impone come coordinatore, anche se già in esecuzione un altro coordinatore.

Richiede al più n² messaggi per l’elezione.