Informalmente, il problema della mutua esclusione distribuita consiste nel far sì che un insieme di processi distribuiti che condividono una risorsa (o una collezione di risorse) possano accedervi senza interferenze e senza determinarne stati inconsistenti.
Spesso le risorse sono gestite (e incapsulate) da processi server, che possono offrire meccanismi di accesso in mutua esclusione. In tal caso si applicano gli algoritmi di mutua esclusione (non distribuita) noti dalla teoria dei sistemi operativi.
Nella teoria dei sistemi distribuiti, il caso di interesse è quello in cui la risorsa non è gestita da un singolo server locale, e un insieme di processi (peers) devono coordinare gli accessi alle risorse tra essi condivise.
Due esempi applicativi:
Si considera un sistema con N processi pi, i = 1, …, N.
I processi non hanno variabili condivise, ed accedono alle risorse comuni in una sezione critica.
Esiste un’unica sezione critica.
Il sistema è asincrono.
I processi non sono soggetti a fallimenti.
I canali sono affidabili, e i messaggi prima o poi sono consegnati intatti una e una sola volta.
I processi trascorrono un tempo finito nella sezione critica, rilasciando quindi le risorse comuni dopo un tempo limitato.
I requisiti che devono essere soddisfatti da un algoritmo di mutua esclusione distribuita in ogni sua esecuzione sono:
La liveness garantisce l’assenza di deadlock e starvation.
L’assenza di starvation è una condizione di imparzialità (fairness). Spesso è richiesto l’ulteriore requisito di imparzialità:
Gli algoritmi di mutua esclusione distribuita possono essere valutati in base ai seguenti criteri:
A.banda di rete (network bandwidth) consumata, proporzionale al numero di messaggi inviati per l’ingresso e l’uscita dalla sezione critica;
B.ritardo di un processo (client delay) in ingresso e uscita dalla sezione critica;
C.ritardo di sincronizzazione (synchronization delay) tra due processi che si succedono nella sezione critica: è una misura dell’effetto dell’algoritmo sulla produttività (throughput) del sistema; quest’ultima determina il numero massimo di processi che complessivamente possono accedere alla sezione critica nell’unità di tempo.
Una soluzione distribuita basata su controllo centralizzato è quella di prevedere un server centrale (lock server) cui i processi inviano le richieste d’accesso alla risorsa condivisa.
Questa soluzione presenta diversi svantaggi:
Per entrare nella sezione critica, un processo invia un messaggio a un apposito server ed attende finché ottiene in risposta il permesso.
A. Il numero dei messaggi è proporzionale alle richieste di accesso alla sezione critica. L’algoritmo non consuma banda di rete quando nessun processo richiede l’accesso alle risorse comuni.
B. In ingresso nella sezione critica, il client delay è di 2 messaggi (request, grant). In uscita dalla sezione critica, il client delay è di un solo messaggio (release).
C. Il ritardo di sincronizzazione tra il processo uscente e un processo entrante è di 2 messaggi (release, poi grant al successivo).
Si potrebbe immaginare una soluzione ispirata all’algoritmo del server centrale, ma completamente decentralizzata, replicando in ciascun processo lo stato del lock server: per richiedere la risorsa, un processo dovrebbe inviare la richiesta di lock a tutti gli altri, e attendere i relativi lock grant.
Naturalmente tale soluzione sarebbe inadeguata.
Si supponga di avere 4 processi:
Inoltre l’algoritmo causerebbe un deadlock, perchè p1 e p2 non solo non otterrebbero il lock, ma impedirebbero ad altri di ottenerlo.
I problemi di tale soluzione decentralizzata possono essere risolti:
In quest’ultimo caso (Lamport, 1978), tutti i messaggi vanno marcati temporalmente con l’orologio logico del mittente. Le richieste ricevute sono immesse da ciascun processo in una coda, ordinata secondo la loro marcatura temporale.
Alla ricezione di una richiesta, viene inviato un ACK a tutti gli altri processi. Quando una richiesta ha ricevuto ACK da tutti i processi, viene marcata come stabile.
Un processo entra nella sezione critica quando:
All’uscita dalla sezione critica si inviano messaggi di release.
Non è necessario inviare messaggi di lock grant.
I processi sono organizzati logicamente ad anello: il processo pi ha un canale di comunicazione con il successivo p(i+1)mod N
I processi si scambiano un gettone (token), che ruota sempre nella stessa direzione.
Il possesso del token dà diritto ad entrare nella sezione critica.
Sono soddisfatti i requisiti ME1, ME2.
Il requisito ME3 non è soddisfatto (i processi si scambiano messaggi applicativi indipendentemente dalla rotazione del token).
A. Il token ruota in continuazione, tranne quando un processo è nella sezione critica, perciò l’algoritmo consuma banda di rete, anche quando nessun processo richiede l’accesso alle risorse comuni.
B. In ingresso nella sezione critica, il client delay varia da 0 (se ha appena ricevuto il token) a N messaggi (se l’ha appena ceduto). In uscita dalla sezione critica, il client delay è di un solo messaggio.
C. Il ritardo di sincronizzazione tra il processo uscente e un processo entrante varia da 1 a N-1 messaggi.
È un algoritmo basato su multicast e orologi logici (1981).
Un processo che vuole entrare nella sezione critica invia in multicast una richiesta, ed accede effettivamente alla risorsa solo dopo aver ricevuto risposta da tutti gli altri processi.
I processi hanno identificativi univoci numerici interi pi, e possiedono ciascuno un orologio logico di Lamport.
I messaggi di richiesta sono nella forma < T, pi > , dove T è la marcatura temporale (timestamp) di Lamport.
Le condizioni in base alle quali i processi rispondono garantiscono il soddisfacimento dei requisiti ME1, ME2, ME3.
Ogni processo ha una variabile state con i possibili valori:
Un processo nello stato Wanted invia in multicast la richiesta < T, pi > , ed attende di raccogliere N-1 risposte.
Un processo nello stato Relesead risponde immediatamente alle richieste.
Il processo nello stato Held risponde alle richieste solo al termine della sezione critica, mettendo quindi in attesa il/i richiedente/i.
Se un solo processo è nello stato inAttesa e gli altri nello stato Fuori, il richiedente riceve subito N-1 risposte ed entra nella sezione critica.
Se un solo processo è nello stato inAttesa ed un processo è nello stato Dentro, allora N-2 processi sono nello stato Fuori, il richiedente riceve subito N-2 risposte, ed entra nella sezione critica appena il processo Dentro rilascia la risorsa.
Se due o più processi sono nello stato inAttesa, il primo a raccogliere N-1 repliche è il processo la cui richiesta ha il timestamp minore. A parità di timestamp logico, ha la precedenza il processo con l’identificativo minore.
È essenziale che nella fase di invio della richiesta ciascun processo sospenda l’elaborazione delle richieste altrui.
L’algoritmo di Ricart e Agrawala può essere riguardato come una ottimizzazione dell’algoritmo di Lamport, basata sull’osservazione che un processo non può entrare nella sezione critica se la sua richiesta non è stabile, cioè non ha avuto N-1 grant.
Pertanto è possibile risparmiare i messaggi espliciti di release, se il processo che detiene la risorsa differisce l’invio degli ACK al termine della sezione critica.
A. L’ingresso nella sezione critica comporta 2(N-1) messaggi: N-1 per il multicast della richiesta, e N-1 repliche. Se il multicast è supportato in hardware, occorrono N messaggi.
L’algoritmo non consuma banda di rete quando nessun processo richiede l’accesso alle risorse comuni.
B. Se il multicast è in hardware, in ingresso il client delay è di due tempi di trasmissione di messaggi (richiesta in multicast, e risposta dal processo uscente).
In uscita dalla sezione critica, il client delay è pari al numero di processi in attesa. Se il multicast è in hardware, il client delay è di un solo messaggio.
C. Il ritardo di sincronizzazione tra il processo uscente e un processo entrante è di un solo messaggio.
Si tratta di un algoritmo basato sull’osservazione che, affinché un processo possa entrare nella sezione critica, non è necessario che attenda il permesso di tutti gli altri: è sufficiente che ciascuno attenda e riceva il permesso da sottoinsiemi dei suoi pari, a condizione che i sottoinsiemi di due qualsiasi processi non siano disgiunti.
Si può pensare a tale algoritmo come a una votazione distribuita: i processi votano per entrare nella sezione critica, e per entrarvi un candidato deve raccogliere un numero sufficiente di voti.
I processi comuni a due sottoinsiemi garantiscono il requisito di safety ME1, in quanto sono potenziali elettori di più processi, ma devono votare per uno solo di essi.
Ogni processo ha una variabile state ε {Relesead, Wanted, Held} e una var. booleana voted, inizialmente pari a Relesead e False, rispettivamente.
L’algoritmo base soddisfa i requisito di safety ME1, ma non quello di liveness ME2: è infatti possibile che si verifichi un deadlock.
Se infatti tre processi p1, p2, p3 richiedono concorrentemente l’accesso, e V1= {p1, p2}, V2 = {p2, p3}, V3 = {p3, p1}, è possibile che ogni processo replichi a sé stesso e tenga fuori l’altro: ogni processo riceverebbe una replica su due, e nessuno può procedere oltre.
L’algoritmo può essere adattato in modo da soddisfare ME2 (Saunders, 1987). L’adattamento di Saunders si basa sull’uso di orologi logici, e sull’accodamento delle richieste secondo l’ordinamento happened-before; in questo modo anche il requisito ME3 è soddisfatto.
A. Se il multicast non è supportato in hardware, l’ingresso nella sezione critica comporta 2 √N messaggi, e l’uscita comporta √N messaggi. Per quanto riguarda il consumo di banda, il totale dei messaggi scambiati è 3 √N.
Se N > 4, 3 √N > 2(N-1), e il consumo di banda è migliore di quello dell’algoritmo di Ricart e Agrawala.
B. Il client delay è lo stesso dell’algoritmo di Ricart e Agrawala.
C. Il ritardo di sincronizzazione tra il processo uscente e un processo entrante è di due messaggi, peggiore di quello di Ricart e Agrawala.
1. Caratterizzazione dei sistemi distribuiti
2. Modelli di sistemi distribuiti
3. Tempo e sincronizzazione nei Sistemi Distribuiti
4. Stato globale nei Sistemi Distribuiti
5. Problemi di consenso nei sistemi distribuiti
7. Algoritmi di mutua esclusione nei sistemi distribuiti
8. Algoritmi di elezione nei sistemi distribuiti
10. Il Network File System di SUN Microsystems
11. AFS (Andrew File System) e GFS (Google File System)
12. Transazioni e controllo di concorrenza
13. Transazioni
15. Affidabilità (dependability) dei sistemi software distribuiti
16. Affidabilità dei sistemi software distribuiti
17. Software Faults
18. Classificazione e analisi dei difetti software
G. Coulouris et al.: Distributed Systems: Concepts and Design
(Cap. XII §2), IV ed., 2005.