La mutua esclusione distribuita (richiami)
L’algoritmo di Ricart-Agrawala
Implementazione dell’algoritmo utilizzando DAJ
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).
L’ordering è un’ulteriore requisito di imparzialità.
enter() – richiesta di ingresso in sezione critica
resourceAccess() – accesso alla risorsa nella sezione critica
exit() – uscita dalla sezione critica
Ogni processo ha una variabile stato con i possibili valori:
Un processo nello stato inAttesa invia in multicast la richiesta <T, pi>, ed attende di raccogliere N-1 risposte.
Un processo nello stato Fuori risponde immediatamente alle richieste.
Il processo nello stato Dentro risponde alle richieste solo al termine della sezione critica, mettendo quindi in attesa il/i richiedente/i.
Class RicartAgrawala extends Application
Ridefinire il metodo construct per costruire un sistema di N processi completamente connessi (come richiesto dai requisiti dell’algoritmo).
Class RicartAgrawalaProg extends Program
Implementare tale classe in maniera da:
Implementare il behavior dinamico di tale classe:
Acquisizione della regione critica
Rilascio della regione critica
Class RicartAgrawalaMsg extends Message
Il messaggio è costituito da un tipo ed un timestamp.
Il tipo può essere REQUEST o REPLY
Il timestamp ha senso solo nel caso di Messaggi di tipo Request
N.B.: È possibile implementare anche due classi distinte per i messaggi di REQUEST e REPLY
Implementazione delle Assertions
Implementare le assertions per verificare che siano soddisfatti i requisiti:
ME1: Non più di un processo in ogni istante è in sezione critica.
ME2: Verifica che un processo che invia i messaggi REQUEST entra in sezione critica entro un determinato timeout.
ME3: Le richieste vengono servite secondo l’ordinamento happened-before con il quale pervengono (in altre parole se un processo che ha effettuato la richiesta con timestamp Ti è in regione critica, non può esistere alcun altro processo in attesa con timestamp Tj<Ti).
Le asserzioni devono essere verificate ogni qualvolta un nodo viene schedulato per l’esecuzione (ovvero ad ogni iterazione del ciclo che va inserito nel metodo main della classe RicartAgrawalaProg).
Scarica i codici in DAJ.
Class RicartAgrawalaProcess
Rappresenta i processi del sistema che eseguono l’algoritmo di RicartAgrawala.
Il loro comportamento è implementato nel metodo void run():
Scarica i codici .java
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, 3° ed., pp. 423-431
G.Ricart, A. Agrawala: An Optimal Algorithm for Mutual Exclusion in Computer Networks, Communications of the ACM, Volume 24, Issue1, Gennaio 1981