Vai alla Home Page About me Courseware Federica Living Library Federica Federica Podstudio Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica La Corte in Rete
 
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

Stefano Russo » 26.Esercitazione - Mutua Esclusione Distribuita


Sommario

La mutua esclusione distribuita (richiami)
L’algoritmo di Ricart-Agrawala
Implementazione dell’algoritmo utilizzando DAJ

Ipotesi

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.

Requisiti

I requisiti che devono essere soddisfatti da un algoritmo di mutua esclusione distribuita in ogni sua esecuzione sono:

  • ME1 (safety): al più un processo alla volta può trovarsi nella sezione critica
  • ME2 (liveness): le richieste di ingresso e uscita dalla sezione critica devono prima o poi essere soddisfatte
  • ME3 (ordering): se la richiesta x è in relazione HB con la richiesta y (x → y), l’accesso alla sezione critica da parte di x deve avvenire prima dell’accesso di y

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à.

Protocollo applicativo

enter() – richiesta di ingresso in sezione critica
resourceAccess() – accesso alla risorsa nella sezione critica
exit() – uscita dalla sezione critica

Algoritmo di Ricart e Agrawala


Algoritmo di Ricart e Agrawala

Ogni processo ha una variabile stato con i possibili valori:

  • Fuori: il processo è all’esterno della sezione critica
  • Dentro: il processo è nella sezione critica
  • inAttesa: il processo vuole accedere alla sezione critica

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.

Algoritmo di Ricart e Agrawala


Implementazione in DAJ

Class RicartAgrawala extends Application
Ridefinire il metodo construct per costruire un sistema di N processi completamente connessi (come richiesto dai requisiti dell’algoritmo).

Implementazione in DAJ

 Class RicartAgrawalaProg extends Program

Implementare tale classe in maniera da:

  • memorizzare lo stato del nodo (WANTED, HELD, RELASED)
  • memorizzare il TImestamp dell’ultimo messaggio di richiesta inviato
  • memorizzare tutti i messaggi di richiesta ai quali non si è ancora inviato un reply

Implementare il behavior dinamico di tale classe:

  • invio in Broadcast dei messaggi REQUEST
  • ricezione dei messaggi request (confronto tra i timestamp dei messaggi, ed in caso di timestamp uguali, confrontare gli id dei processi)
    • assegnare ad ogni processo un indice intero come attributo della classe RicartAgrawalaProg

Acquisizione della regione critica

Rilascio della regione critica

Implementazione in DAJ

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 in DAJ

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).

Codice

Scarica i codici in DAJ.

Classe RicartAgrawalaProcess

Class RicartAgrawalaProcess

Rappresenta i processi del sistema che eseguono l’algoritmo di RicartAgrawala.

Il loro comportamento è implementato nel metodo void run():

  • Controllano la presenza di messaggi nei canali in ingresso e eseguono i metodi onReceiveRequestMessage e onReceiveReplyMessage associati rispettivamente ai due eventi di ricezione dei messaggi.
  • Probabilisticamente possono tentare di accedere alla sezione critica.
  • Possiede i metodi enter, resourceAccess, exit.

Codice implementazione Java

Scarica i codici .java

I materiali di supporto della lezione

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

Codice DAJ

Scarica i codici .java

  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion