29/10/14
1
CdL MAGISTRALE in INFORMATICA
A.A. 2014-2015
corso di “Sistemi Distribuiti”
3. La concorrenza tra processi remoti nei sistemi distribuiti
Prof. S.Pizzutilo
Riferimenti: • A.Tanenbaum,M.Van Steen “Sistemi distribuiti” Pearson
Prentice Hall 2007 ) • A.A. Garganico 197474 CdLS Ingegneria Informatica
(0234) Reti di Calcolatori LS a.a. 2006/2007 • Wikipedia http://en.wikipedia.org/wiki/Publish/subscribe • De Leonardis Salvatore Seminari : 1) La mutua esclusione
nei sist. Distr. 2) Algoritmo di Bully • Siciliano Giulia Matricola seminario : Dai sistemi
concorrenti a quelli distribuiti: il problema della mutua esclusione
Concorrenza fra processi remoti
Interazioni fra processi remoti: 1. Indesiderate e (spesso) impreviste
• I processi competono per le risorse al fine di poter completare la propria esecuzione, causando condizioni di attesa ed eventualmente problemi quali blocco critico o starvation.
2. Desiderate e previste
• I processi cooperano al fine di giungere alla soluzione di un problema complesso
(Architetture client-server, in cui un processo richiede un servizio ad un altro e attende da esso la risposta)
29/10/14
2
Mutua esclusione distribuita
Nel caso di accesso simultaneo ad una risorsa, occorre garantirsi che tale accesso non corrompa la risorsa o la renda inconsistente.
ü Quando si hanno processi concorrenti che accedono ad un risorsa condivisa nasce il bisogno di sincronizzarli in modo tale che tale risorsa sia assegnata ad un processo alla volta (mutua esclusione).
Dal punto di vista astratto il problema puo’ essere formulato come segue. Ci sono N processi ognuno dei quali ripete la seguente sequenza di passi di programma : • <non in sezione critica> • <trying protocol> • sezione critica • <exit protocol> • <non in sezione critica> In un sistema concorrente esiste uno “scheduler” centralizzato che permette ad un solo processo alla volta di entrare in esecuzione e quindi di evolvere secondo il suo codice. Di fatto quindi lo scheduler esegue una linearizzazione di tutte le istruzioni elementari effettuate dai vari processi. CdL in Informatica- Magistrale Università di Bari
Sistemi Distribuiti -
Il modello di Dijkstra
La Mutua Esclusione
o Evitare interferenze e stati di inconsistenza o Deadlock (2 processi si bloccano perché aspettano uno la
risposta dell’altro) o Starvation (attesa indefinita della risorsa)
Ø Algoritmi basati su autorizzazione Ø Algoritmi basati su token
Ø Algoritmi di tipo probabilistico
Ø Algoritmi di tipo deterministico
ü centralizzati ü decentralizzati
ü distribuiti ü basati su token
29/10/14
3
Mutua esclusione distribuita
q Soluzioni basate su autorizzazioni (un processo che intende usare la risorsa, prima richiede l’autorizzazione ad altri). ü Algoritmo centralizzato ü Algoritmo decentralizzato ü Algoritmo distribuito
In questa tipologia di algoritmi esistono diverse tecniche per coordinare la comunicazione : • quorum (o votazione): si richiede il permesso di accedere ad una risorsa condivisa ad un sottoinsieme di processi (algoritmo di Maekawa). • elezione: un processo si trasforma in coordinatore (l’algoritmo bully, algoritmo ad anello e super-peer )
q Soluzioni basate su token (messaggio speciale tra processi che realizza la mutua esclusione, consentendo solo al processo detentore del token la possibilità di utilizzare la risorsa. (Algoritmo token ring)
Un’altra classificazione o un modo diverso di organizzare la stessa classificazione ?
Server che gestisce una mutua esclusione mediante token
CdL in Informatica- Magistrale Università di Bari Sistemi Distribuiti -
Server
1. Requesttoken
Queue ofrequests
2. Releasetoken
3. Granttoken
4
2
p4
p3p
2
p1
29/10/14
4
Un anello di processi che si scambiano un token mutualmente esclusivo
CdL in Informatica- Magistrale Università di Bari Sistemi Distribuiti
pn
p2
p3
p4
Token
p1
a) Un gruppo di processi non ordinati su una rete b) Un anello logico costruito via software
Trasmissione del token sull’anello (logico) e suo possesso per poter utilizzare una risorsa
o I processi devono essere ordinati in modo da formare un anello logico.
o Ogni processo deve conoscere il processo che si trova dopo di lui.
o Per ogni risorsa deve essere creato un token. o Il token circola nell’anello. o Con il token si gestisce l’accesso alla risorsa.
Algoritmo basato su autorizzazione
CdL in Informatica- Magistrale Università di Bari Sistemi Distribuiti -
p5
p4
p2
p1
p0 p3
processo coodinatore
p2 p0 p5 p4 P1
a) richiesta
b) OK
c) rilascio
d) OK
d)
29/10/14
5
Mutua esclusione con autorizzazione: un algoritmo centralizzato
a) Il processo 1 chiede al coordinatore il permesso per entrare in una regione critica. Il permesso è dato.
b) Il processo 2 allora chiede il permesso di accedere alla stessa risorsa. Il coordinatore NON risponde.
c) Quando il processo 1 esce dalla regione critica, lo dice al coordinatore che può finalmente rispondere al processo 2.
In totale 3 messaggi con 2 messaggi prima di poter usare una risorsa (ritardo). La soluzione centralizzata evita la starvation ma pone problemi sulla criticità del coordinatore.
Algoritmo centralizzato
q Un processo deve essere anche il coordinatore. q Quando un processo intende utilizzare una risorsa deve inviare una
richiesta al coordinatore. q Il coordinatore gestisce l’accesso alle risorse.
29/10/14
6
Algoritmo centralizzato
Mutua esclusione con autorizzazione: Un algoritmo decentralizzato
La soluzione decentrata (basata su quorum) estende il numero dei coordinatori alle n duplicazioni delle risorse disponibili (Lin et al.2004 basato su DHT).
q Si suppone che le risorse siano replicate n volte ed ogni replica ha il suo coordinatore.
q Ciascun coordinatore controlla l’accesso ad ogni singola risorsa da parte di processi concorrenti.
q La richiesta di una risorsa avviene come nell’algoritmo centralizzato. q Un processo, per poter accedere ad una risorsa, dovrà ottenere un voto di
maggioranza da m > n/2 coordinatori. q Quando un coordinatore vuole negare l’accesso ad un processo (perché lo ha
già dato ad un altro processo), deve comunicarlo al processo richiedente.
N. di messaggi necessari = 3mk (k=1,2,3,…tentativi) e ritardo pari a 2m
E’ ridotto al minimo il problema del crash del coordinatore, ma è possibile la starvation quando un processo non riesce ad ottenere mai la maggioranza.
29/10/14
7
0 5 6
Processi che chiedono la risorsa 9
request replay
Algoritmo decentralizzato
§ Ogni risorsa viene replicata n volte. § Ogni replica deve avere il proprio coordinatore. § La richiesta di una risorsa avviene come nell’algoritmo centralizzato. § Riduce al minimo il problema del crash da parte del coordinatore. § Per accedere ad una risorsa il processo deve ricevere almeno n/2 autorizzazioni.
Mutua esclusione con autorizzazione: un algoritmo distribuito
a) 2 processi (0 e 2) vogliono entrare nella stessa regione critica nello stesso momento. b) Il processo 0 ha il timestamp (8) più basso, perciò vince. c) Quando il processo 0 finisce, invia un OK, in modo che il processo 2 possa entrare
nella regione critica.
N messaggi = 3(n-1), ritardo = 2(n-1)
CdL in Informatica- Magistrale Università di Bari Sistemi Distribuiti
L’algoritmo di Lamport 1978 richiede che tutti gli eventi dispongano di un clock logico di sincronizzazione scalare e che ciascun processo gestisca una coda di richieste di accesso ad una regione critica. L’ algoritmo di Ricart e Agrawala (1981) richiede che ci sia un ordinamento totale di tutti gli eventi del sistema basato sui timestamp di Lamport. Quando un processo vuole accedere ad una risorsa, costruisce un messaggio contenente il nome della risorsa richiesta, il numero del processo richiedente (0,1,2) e il suo timestamp corrente. Il messaggio viene inviato a tutti i processi (compreso se stesso). L’accesso alla regione critica è consentita solo al processo in coda con timestamp minore.
29/10/14
8
Algoritmo di Ricart e Agrawala (1981)
CdL in Informatica- Magistrale Università di Bari Sistemi Distribuiti -
On initialization state := RELEASED;
To enter the section state := WANTED; Multicast request to all processes; request processing deferred here T := request’s timestamp; Wait until (number of replies received = (N – 1)); state := HELD;
On receipt of a request <Ti, pi> at pj (i ≠ j) if (state = HELD or (state = WANTED and (T, pj) < (Ti, pi))) then queue request from pi without replying; else reply immediately to pi; end if
To exit the critical section state := RELEASED; reply to any queued requests;
• Il processo che vuole accedere ad una sezione critica manda un messaggio di richiesta a tutti, incluso se stesso, contenente: il nome della sezione critica, il proprio identificatore ed il timestamp locale e si pone in attesa della risposta da tutti.
• Ottenuti tutti gli OK, entra nella sezione critica ed all’uscita da essa manda OK a tutti i processi in coda.
• Il processo che riceve può non essere nella sezione critica e non vuole accedervi, pertanto manda OK al mittente; oppure si trova nella sezione critica e non risponde mettendo in coda locale il messaggio.
• Per poter accedere alla sezione critica confronta il timestamp e vince se possiede quello più basso.
• Quindi se il processo che possiede il timestamp più basso è un altro allora invia OK, altrimenti non risponde e pone il messaggio in coda.
Algoritmo di Ricart e Agrawala (1981)
29/10/14
9
Esempio di algoritmo distribuito di Ricart e Agrawala
Confronto tra i metodi
CdL in Informatica- Magistrale Università di Bari Sistemi Distribuiti
Algorithm Messages per entry/exit
Delay before entry (in message times)
Problems
Centralized 3 2 Coordinator crash
Distributed 2 ( n – 1 ) 2 ( n – 1 ) Crash of any process
Token ring 1 to ∞ 0 to n – 1 Lost token, process crash
Decentralized 3mk (k=1,2,3,…) 2m Starvation, lower efficiency
n = numero di processi m= numero di coordinatori k= tentativi di trasmissione
29/10/14
10
Algoritmi di elezione del coordinatore
L’elezione serve per scegliere il processo che dovrà agire da coordinatore (o da iniziatore) e su cui concordano tutti gli altri.
q Algoritmo di LeLann e di Chang-Roberts (ad anello) q Algoritmo “bully” (Gracia-Molina 1982) q Elezione in ambienti mobili
Elezione del coordinatore: Algoritmo ad anello (1)
ü Processi ordinati in maniera logica; ü Il processo che intende incominciare una
elezione invia un messaggio col proprio identificativo lungo l’anello;
ü Il processo con l’identificativo più alto vince.
29/10/14
11
Elezione del coordinatore: Ring Algorithm (2)
Election algorithm using a ring.
CdL in Informatica- Magistrale Università di Bari Sistemi Distribuiti -
a) Il processo 5 avvia una elezione ed invia al processo successivo (6) il suo identificativo.
b) Il processo 6 invia il messaggio ricevuto al successivo (7) dal quale non riceve risposta
c)Il processo 6 invia il messaggio ricevuto (aggiungendo il suo identificativo ( 5 e 6 )) al processo successivo (0)
e)… e così via finchè il messaggio con tutti gli identificativi ritorna al processo 5 che riconosce il suo identificativo e lancia sull’anello un messaggio dichiarando coordinatore il processo con identificativo più alto (il 6).
d) Il processo 0 invia il messaggio ricevuto (aggiungendo il suo identificativo) al processo successivo (1)
Algoritmo ad anello (di LeLann e di Chang-Roberts)
Ø Ogni processo deve avere un identificativo univoco Ø I processi formano una anello logico Ø Il processo che intende incominciare una elezione invia un messaggio al
processo successivo contenente il proprio identificativo Ø Il processo con l’identificativo maggiore vince l’elezione
29/10/14
12
Elezione del coordinatore: algoritmo Bully
Supponiamo che un qualunque processo pi invii una richiesta al coordinatore. Se dopo un tempo T la richiesta non è ancora stata soddisfatta, pi suppone che il coordinatore sia fallito, perciò indice l'elezione : a) pi invia un messaggio di elezione a tutti i processi con maggior numero di
priorità; pi aspetta un tempo T per avere risposta; b) se non arrivano risposte nel tempo T, pi suppone che tutti i processi (con
priorità maggiore della sua) siano falliti. Perciò pi si nomina nuovo coordinatore e avvisa tutti i processi della rete del cambiamento avvenuto. La coda e le richieste precedenti sono perse;
c) se riceve almeno una risposta entro il tempo T, il suo ruolo nell'elezione è terminato.
In qualunque momento, un processo può ricevere un messaggio di tipo ELEZIONE da uno dei suoi colleghi con numero più basso. All’arrivo di tale messaggio, il destinatario ri-sponde con un messaggio di tipo OK al mittente, per indicare che è attivo e prende il con-trollo. Il destinatario organizza un’elezione, a meno che non lo stia già facendo. Alla fine tutti i processi rinunceranno tranne uno che sarà il nuovo coordinatore. Esso annuncia la sua vittoria inviando a tutti i processi un messaggio, comunicando loro che è il nuovo coordinatore con decorrenza immediata.
elezione del coordinatore: Bully Algorithm
a) Il processo 4 indice una Elezione tra i processi 5, 6, 7 (con identificativo maggiore) ,
b) I processi 5 e 6 rispondono con OK, spingendo 4 a fermarsi c) 5 e 6 indicono una nuova Elezione CdL in Informatica- Magistrale Università di Bari
Sistemi Distribuiti
29/10/14
13
Algoritmo bully
① Ogni processo ha un proprio identificativo (da 0 a 7 nell’esempio a lato)
② Il processo che intende incominciare una elezione invia un messaggio a tutti i processi con l’identificativo superiore al suo (il processo 4 invia un messaggio al 5, 6 e 7 in fig. a)
③ Se non riceve risposta vince l’elezione ed avvisa tutti che lui è stato eletto coordinatore fig. d)
④ Se riceve anche un solo messaggio termina il proprio compito (4 riceve un messaggio di ack solo da 5 e 6)
⑤ Salta a (2) (il processo 5 ricomincia l’elezione in fig.b)
(a) (b)
(c) (d)
Elezione del coordinatore in ambienti wireless
Reti mobili ad hoc Si costruisce un albero per l’elezione del nodo coordinatore, partendo dalla topologia iniziale
della rete. u Un nodo qualsiasi può iniziare una elezione inviando un messaggio di elezione ai vicini, u Quando un nodo riceve per la prima volta un messaggio di elezione, nomina il padre
come mittente ed invia il messaggio di elezione ai vicini, escluso il padre. u Quando un nodo riceve un messaggio di elezione da un nodo che non sia il padre,
semplicemente invia un messaggio di avvenuta ricezione.
Nel contesto delle reti mobili (ad hoc), il problema classico dell’elezione del coordinatore richiede due importanti requisiti aggiuntivi: • l’elezione deve tollerare cambiamenti topologici arbitrari e concorrenti e terminare eleggendo un coordinatore unico; • il coodinatore eletto dovrebbe essere il “most-valued” fra tutti i nodi all'interno del sistema, dove il valore di un nodo è determinato da caratteristiche come la carica residua della batteria, la distanza media minima con gli altri nodi, le capacità di calcolo, ecc.
29/10/14
14
Esempio di MANET
Università di Bari Aldo Moro -
Elezione in ambienti senza fili
Nodo Capacità
Capacità
Nodo
29/10/14
15
Assunzioni algoritmo
La rete ad hoc è modellata come un grafo non orientato che cambia nel tempo, quando i nodi si spostano.
Il grafo può diventare disconnesso se la rete si divide a causa di un movimento di nodo.
Sono necessarie le seguente assunzioni sui nodi e architeIura di sistema: Valore del nodo: valore di " capacità” (durata baIeria,….) come coordinatore
della rete; ID nodo univoco: gli ID devono essere ordinabili in modo da risolvere il
problema di scelta Collegamen4: i collegamenS sono bidirezionali; Comportamento nodo: ogni nodo mobile può portare modifiche della
topologia di rete; Comunicazione da nodo a nodo: la comunicazione è garanSta solo quando il
miIente e il desSnatario rimangono collegaS per tuIa la durata del trasferimento del messaggio.
Algoritmo di Vasudevan(2004)
Tratto da :Paolo Tomeo e Vito Rocco Albano:Algoritmo di elezione del coordinatore nei sistemi distribuiti mobile. Seminario Sis.Dis 2011-12
L'algoritmo uSlizza tre Spi di messaggi: Elezione: uSlizzato per la fase di "crescita" dello spanning tree. Il nodo
sorgente invia un messaggio ELEZIONE a tuZ i suoi vicini che a loro volta trasmeIono ai loro vicini e cosi via.
Ack: uSlizzato per la fase "restringimento" dello spanning tree. ConSene un idenSficatore (ID) e il relaSvo valore (di capacità). Ogni nodo padre confronta i messaggi ACK ricevuS, scegliendo l'idenSficatore del nodo con il valore di capacità più alto, e resStuisce al suo nodo padre un messaggio. Il nodo sorgente ha infine informazioni sufficienS per determinare il nodo col maggior valore di tuIa la rete.
Leader. Una volta che il nodo sorgente determina l’idenStà del coordinatore dai messaggi ACK ricevuS, trasmeIe un messaggio LEADER contenente tale idenStà a tuZ i nodi.
Algoritmo di Vasudevan(2004)
Tratto da :Paolo Tomeo e Vito Rocco Albano:Algoritmo di elezione del coordinatore nei sistemi distribuiti mobile. Seminario Sis.Dis 2011-12