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
 
I corsi di Ingegneria
 
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