Concorrenza fra processi remoti - Dipartimento di …disys/sidys3concorrenzaSD14.pdf29/10/14 1 CdL...

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


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)


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)


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


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.


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

29/10/14

16

Esempio: Algoritmo di Vasudevan

Concorrenza fra processi remoti - Dipartimento di …disys/sidys3concorrenzaSD14.pdf29/10/14 1 CdL...

Documents

Transcript of Concorrenza fra processi remoti - Dipartimento di …disys/sidys3concorrenzaSD14.pdf29/10/14 1 CdL...