APD - Note Curs - 11 Terminarea

8/8/2019 APD - Note Curs - 11 Terminarea

1/12

88

6.7. Terminarea programelor distribuite

Tehnica jetonului poate fi folosit cu succes la detectarea terminrii proceselor ntr-un program paralel. Un program paralel se termin dac toate procesele sale setermin. Exist ns situaii n care procesele ce compun un program paralel conincicluri infinite. Definiia anterioar nu este aplicabil n astfel de situaii, fiindnecesar adoptarea unei variante mai cuprinztoare. Astfel, considerm c un programeste terminat dac fiecare proces este blocat sau terminat i nu exist nici o cerere deintrare/ieire n curs de execuie. Detecia terminrii se poate face simplu n cazul cndtoate procesele se execut pe acelai procesor: coada proceselor pregtite pentruexecuie este goal.

n cazul unui algoritm distribuit detectarea terminrii este mai dificil, deoarece nuexist nici o cale de a "capta" starea instantanee a tuturor proceselor. Deci, chiar dac,la un moment dat, un proces termin prelucrarea, el poate fi reactivat ulterior de unmesaj primit de la un alt proces al programului. Din acest motiv, stabilirea terminriiunui program necesit comunicarea unor mesaje de control suplimentare ntre

procesele sale.

Terminarea proceselor organizate ntr-un inel (tehnica jetoanelor)

Pentru nceput vom analiza o variant mai simpl, n care procesele comunic ntreele prin canale formnd un inel: P(1) trimite mesaje doar lui P(2), P(2) doar lui P(3) i

aa mai departe. n general, procesul P(i) primete mesaje pe canalul ch[i] i trimitemesaje pe canalul ch[(i mod n) + 1].

Condiia de terminare a coleciei de procese este ca fiecare proces s fie liberi pecanale s nu existe mesaje n tranzit. Un proces se consider liber dac a terminatexecuia sau dac se afl n ateptarea unui mesaj (receive). Un mesaj este n tranzitdac a fost transmis dar nu a fost nc recepionat.

Pentru a detecta terminarea folosim un jeton pe care procesele i-l trimit pe aceleaicanale pe care le folosesc pentru mesajele uzuale. Cnd procesul care deine jetonul laun moment dat se termin, el trimite jetonul mai departe, procesului urmtor. Fiecaredintre procesele urmtoare particip la transmiterea jetonului n continuare (convenim

ca un proces s participe la transmiterea jetonului n algoritmul de stabilire aterminrii ntregului program, chiar dac el nu mai particip la calcule). Ca urmare, la


2/12

89

un moment dat, jetonul va ajunge napoi la iniiatorul aciunii de terminare. Poate

acesta decide c programul s-a terminat?

La prima vedere, da! Dar, nu trebuie uitat c iniiatorul poate primi mesaje obinuitefiind reactivat, nainte de primirea jetonului napoi. Ca urmare, pentru a decideterminarea, este nevoie de o condiie suplimentar: dup generarea jetonului determinare, iniiatorul s nu mai primeasc alte mesaje. Pentru a putea face aceastverificare, marcm starea procesului, la transmiterea jetonului, cu albastru i ischimbm culoarea n rou dac primete un mesaj obinuit i face calcule. Dac

procesul primete jetonul napoi i culoarea sa a rmas albastru atunci el poate decideterminarea programului paralel.

Aceste elemente sunt cuprinse n regulile ce urmeaz, n care, pentru exprimareapredicatului RING, s-a asociat jetonului o variabil auxiliar, care numr canalelegoale. Se presupune c iniiatorul terminrii este procesul P(1).

{RING: P(1) este albastru => P(1),...,P(jeton+1) sunt albastre i ch[2],...,ch[(jetonmod n) + 1] sunt goale}

aciunile lui P(1) cnd devine liber prima dat:culoare[1] := albastru;jeton := 0;send ch[2](jeton);

aciunile lui P(i:1..n) la recepia unui mesaj obinuit:

culoare[i] := rosu;

aciunile lui P(i:2..n) la primirea unui jeton:culoare[i] := albastru;jeton := jeton +1;send ch[(i mod n) + 1](jeton);

aciunile lui P(1) la recepia jetonului:if culoare[1] = albastru -> anun terminarea i stop ficuloare[1] := albastru;jeton := 0;send ch[2](jeton);

Terminarea n cazul general (tehnica jetoanelor)


3/12

90

Algoritmul se complic dac topologia reelei de procesoare este diferit de un inel.

Deoarece canalele utilizate de procesele unui program paralel sunt entiti globale, otopologie de graf complet, n care fiecare proces poate comunica mesaje tuturorcelorlalte, nu este exclus.

Cheia algoritmului pentru topologia inel este c jetonul parcurge toate legturile posibile ntre procese, golind canalele de comunicare de mesajele uzuale. Putemextinde aceast metod la noua topologie, cernd ca jetonul s parcurg fiecare arc algrafului. Aceasta nseamn c fiecare proces este vizitat de mai multe ori. Dac lafiecare vizitare procesul se menine liber, putem decide terminarea ntregii colecii de

procese.

Fie c un ciclu care include toate arcele grafului i fie nc lungimea lui. Proceselepstreaz o urm a acestui ciclu, astfel c la fiecare vizitare ele aleg urmtoarealegtur pe care transmit jetonul. Ca i mai nainte, jetonul poart numrul de legturigsite libere. Spre deosebire de cazul precedent, nu este sigur c dac la captulciclului jetonul gsete procesul iniiator la culoarea de start, celelalte procese nu auschimbat mesaje ntre ele. Ca urmare, de data aceasta este nevoie de o regul diferitde pasare a jetonului i de o condiie diferit de decidere a terminrii.

Jetonul pornete de la orice proces i are iniial valoarea 0. Cnd procesul devine liberpentru prima dat, se coloreaz n albastru i transmite jetonul prin prima legtur aciclului c. La recepia unui jeton, un proces face urmtoarele aciuni:{GRAF: jetonul are valoarea T => ultimele T canale vizitate de jeton erau goale i

toate P(i) care au transmis jetonul erau albastre cnd au transmis jetonul}aciunile lui P(i:1..n) la primirea unui mesaj uzual:

culoare[i] := rosu;

aciunile lui P(i:1..n) la recepia jetonului:if jeton = nc -> anun terminarea i stop fi;if culoare[i] = rosu -> culoare[i] := albastru;

jeton := 0[] culoare[i] = albastru -> jeton := jeton +1fi;seteaz j la canalul urmtor din ciclul c;send ch[j](jeton);

Regulile enunate asigur c GRAF este un invariant global. ndat ce jetonul atingevaloarea nc, se poate decide c toate procesele sunt libere i toate canalele sunt goale.


4/12

91

n fapt, jetonul parcurge ciclul de dou ori pentru a decide terminarea: o dat pentru a

pune procesele la culoarea albastru i a doua oar pentru a verifica pstrarea culorii dela ultima modificare.

Exerciiu

Extindei rezolvarea deteciei terminrii prin jetoane, de la cazul unui graf complet lacel al unui graf oarecare.


5/12

92

Detecia terminrii folosind confirmrile mesajelor

Reamintim c terminarea unui program distribuit este detectat atunci cnd toateprocesele sunt libere i toate canalele sunt goale. n soluiile prezentate, se foloseteun singur jeton, care culege informaii despre starea tuturor canalelor folosite de

program. Funcia de determinare a strii canalelor se poate mpri ntre procesele programului: fiecare proces verific acele canale pe care a transmis mesaje altorprocese i care constituie, deci, canalele sale de ieire.

Pentru a determina starea canalelor se folosesc dou variante. Prima este cea aconfirmrilor: dac pentru fiecare mesaj transmis pe un canal, procesul primete dela receptor un semnal de confirmare, atunci canalul respectiv este gol. A doua variantfolosete mesaje de marcaj, transmise pe aceleai canale cu mesajele de date. Un

proces transmite un mesaj de marcaj, dup ultimul mesaj de date transmis pe olegtur. Doar marcajele sunt confirmate. Dac procesul nu transmite alte mesajedup marcaj i primete confirmarea acestuia, atunci canalul respectiv este gol.

n continuare sunt prezentate dou soluii ce folosesc aceste variante pentru deteciaterminrii unei reele de procese, ale cror legturi de comunicare a datelor alctuiescun graf oarecare. Ambele presupun existena unui proces sursa, care nu are legturi deintrare i de la care orice alt proces este accesibil pe o cale oarecare din graf (vezifigura 6.4), n care legturile arborelui de acoperire sunt marcate cu linie dubl.

+---+ +---+ +---+| 1 |============>| 2 |===============>| 4 |

+---+ +---+ +---+| || ^ || || | || \/ | || +---+ |+-------------->| 3 |


6/12

93

Algoritmul Dijkstra-Scholten se bazeaz pe transmiterea ntre procese a unor

semnale de confirmare. Schema de semnalare a terminrii este separat isuplimentar fa de prelucrarea propriu-zis pe care o realizeaz procesul. Eaurmrete informarea sursei despre terminarea coleciei de procese. Procesele potrecepiona i transmite semnalele, chiar i atunci cnd sunt libere, deci au terminat

prelucrarea caracteristic a datelor. Semnalele se transmit, evident, n sens inversdatelor, reprezentnd confirmri ale prelurii acestora de ctre destinatar.

Dac procesele ar fi organizate ntr-o reea cu topologie arborescent, algoritmul desemnalare ar fi simplu: cnd un proces frunz se termin, el anun printele su. Cndun nod oarecare al arborelui se termin, el ateapt notificarea terminrii de la toi fiiisi i apoi i anun printele. Notificrile se propag astfel pn la procesul sursa,aflat n rdcina arborelui.

Acest algoritm poate fi extins la un graf dirijat aciclic de procese. Fiecrei legturi ise asociaz un numr, reprezentnd diferena dintre numrul de mesaje de datetransmise i numrul de semnale de confirmare primite pe acea legtur. Numimdeficit aceast diferen. Cnd un nod dorete s termine, el ateapt primirea pelegturile de ieire a datelor, a unor semnale care reduc deficitele la zero, dup caretrimite pe fiecare legtur de intrare a datelor un numr de semnale egal cu deficitul.

Algoritmul Dijkstra-Scholten rezolv problema n cazul general, n care suntpermise cicluri n graful proceselor. Rezolvarea se face prin generarea unui arbore deacoperire, pe parcursul transferului mesajelor de date: fiecare proces pstreaz o

variabilprim a crei valoare este egal cu identificatorul procesului de la care s-arecepionat primul mesaj de date.

Rezolvarea implic trei faze:- trimiterea semnalelor pe toate legturile de intrare, cu excepia celei de la prim;- recepia semnalelor pe toate legturile de ieire;- transmiterea semnalelor spre prim.

Pentru recepia semnalelor pe legturile de ieire, se poate ine o eviden global,deoarece este important ca deficitele legturilor de ieire s se anuleze, neavndimportan identitatea legturilor pe care se primesc semnale. Ca urmare, o singurvariabil nsemnale care s in minte suma deficitelor legturilor de ieire este

suficient.


7/12

94

Algoritmul fiecrui nod este repartizat n dou procese: Prelucrare(i) realizeaz

transformarea datelor; Nod(i) realizeaz gestiunea mesajelor i a semnalelorschimbate cu celelalte noduri. Prelucrare(i) are un canal chm[i] prin care primetemesajele de date. Nod(i) are un canal chs[i] prin care primete semnale de la celelalte

procese, anunuri de transmitere/recepie de mesaje de date i cereri de terminare de laPrelucrare(i). Rspunsul la cererile de terminare este dat pe canalele stop[i].

chm[i] +-------------+ chm[j]--> ]]]]]]-->-|Prelucrare[i]| -----> ]]]]]]---> Prelucrare[j]

+-------------+| |


8/12

95

type fel = enum(semnal, transmitere, receptie, terminare);type arc = rec (exista: bool;

deficit: int;);chan chs[1:n](op: fel, id: int);chan chm[1:n](id:int, date: tip_date);chan stop[1:n](bool);

Nod(i:1..n)::var in: array[1:n] of arc;var nsemnale: int :=0;var prim: int :=0;var id: int, k: fel;

do true ->

receive chs[i](k, id);if k = receptie ->if prim = 0 -> prim := id fi;in[id].deficit := in[id].deficit+1;

[] k = transmitere ->nsemnale := nsemnale+1;

[] k = semnal ->nsemnale := nsemnale-1;

[] k = terminare ->fa j := 1 to n st in[j].exista and (jprim) ->

do in[j].deficit>0 ->send chs[j](semnal, i);in[j].deficit := in[i].deficit-1;

od

af;if nsemnale0 -> send stop[i](false);[] nsemnale=0 ->

if (isursa) and (prim0) ->do in[prim].deficit>0 ->

send chs[prim](semnal, i);in[prim].deficit := in[prim].deficit-1;

od;fi

send stop[i](true);fi

od;

Prelucrare(i:1..n)::var data: tip_date, id: int, term: bool;

initializari;term := false;donot term ->


9/12

96

receive chm[i](id, data);

send chs[i](receptie, id);realizeaza prelucrare....send chm[j](i, data);send chs[i](transmitere, j);...if decizie de terminare -> term := true; fi

od;term :=false;donot term ->

send chs[i](terminare, i);receive stop[i](term);

od;stop;

De notat c dacnsemnale0, nu se ateapt primirea semnalelor nerezolvate i setransmite procesului de prelucrare un rspuns negativ. n varianta prezentat, procesulde prelucrare rencearc terminarea pn cnd aceasta reuete, dar, n cazul general,el poate primi mesaje care s-l repun n execuie (codul trebuie modificatcorespunztor). Starea final a actualului algoritm este cea n care procesul sursraporteaz terminarea, iar n celelalte noduri, procesele au terminat prelucrrile.

Detecia terminrii folosind marcaje

n cea de a doua variant, procesele transmit mesaje de marcaj al sfrituluicomunicaiei, urmnd s primeasc o confirmare doar pentru aceste mesaje, nu i

pentru cele de date. Cnd un proces decide terminarea, el ateapt marcaje pe toatelegturile de intrare i transmite un marcaj pe fiecare legtur de ieire. ndat ce procesul a primit marcaje, el trimite confirmri pe legturile de intrarecorespunztoare, mai puin pe prima legtur. Apoi, el ateapt semnale pe legturilede ieire. Cnd le primete, transmite un semnal pe prima legtur.

Structurile utilizate pentru cele dou categorii de arce au aceeai sintax. Ele conincmpurile exista, activ i marcaj. De data aceasta, fiecare arc de intrarenregistreaz dac:- s-a primit un mesaj (se pune activ pe true);- s-a primit un marcaj (se pune marcaj pe true);- s-a transmis un semnal de confirmare (se pun ambele pe false).

Similar, pentru fiecare arc de ieire, se nregistreaz dac:- s-a transmis un mesaj (se pune activ pe true);


10/12

97

- s-a transmis un marcaj (se pune marcaj pe true);

- s-a primit un semnal de confirmare (se pun ambele pe false).

const marcaj = mesaj-special-de-marcaj-sfirsit-date;type fel = enum(semnal, transmitere, receptie,

receptie-marcaj, terminare);type arc = rec (exista: bool;

activ: bool; {initial false}marcaj: bool;); {initial false}

chan chs[1:n](op: fel, id: int);chan chm[1:n](id:int, date: tip_date);chan stop[1:n](bool);

Nod(i:1..n)::var term: bool := false;

var in, out: array[1:n] of arc;var nsemnale: int :=0; {numar semnale asteptate pe out}var prim: int :=0;var nmarcaje: int; {numar marcaje asteptate pe in}var id: int, k: fel;

do true ->receive chs[i](k, id);if k = receptie ->if prim = 0 -> prim := id fi;if not in[id].activ -> in[id].activ := true;

nmarcaje := nmarcaje+1;fi;

[] k = receptie-marcaj ->

in[id].marcaj :=true; nmarcaje := nmarcaje-1;if id=prim -> term := true fi;

[] k = transmitere ->if not out[id].activ -> out[id].activ := true;

nsemnale := nsemnale+1;fi

[] k = semnal ->out[id].activ := false; out[id].marcaj := false;nsemnale := nsemnale-1;

[] k = terminare ->ifnot term -> send stop[i](false);[] term ->

fa j := 1 to n st jprim and out[j].activ andnot out[j].marcaj ->

send chm[j](i, marcaj); out[j].marcaj := true;af;if nmarcaje 0 -> send stop[i](false);[] nmarcaje = 0 ->


11/12

98

fa j := 1 to n st in[j].exista and (jprim)

and in[j].activ ->send chs[j](semnal, i);in[j].activ := false; in[j].marcaj := false;

af

if nsemnale0 -> send stop[i](false);[] nsemnale=0 ->

if (isursa) and (prim0) ->send chs[prim](semnal, i);in[prim].activ := false;in[prim].marcaj := false;

fi;send stop[i](true);

fi

fi

fi

fi

od;

Prelucrare(i:1..n)::var data: tip_date, id: int, term: bool;initializari;term := false;donot term ->

receive chm[i](id, data);if data=marcaj -> send chs[i](receptie-marcaj,id);[] datamarcaj ->

send chs[i](receptie, id);realizeaza prelucrare....

send chm[j](i, data);send chs[i](transmitere, j);...if decizie de terminare -> term := true;

fi

od;term :=false;do not term ->

send chs[i](terminare, i);receive stop[i](term);

od;stop;


12/12

99

Termination Detection

Model

processes can be active or idle only active processes send messages idle process can become active onreceiving an computation message active process can become idle at any time termination: all processes are idle and no computation message are in transit Can use global snapshot to detect termination also

Huangs Algorithm

One controlling agent, has weight 1 initially All other processes are idle initially and have weight 0 Computation starts when controlling agent sends a computation message to a process An idle process becomes active on receiving a computation message B(DW) computation message with weight DW. Can be sent only by the controlling agentor an active process C(DW) control message with weight DW, sent by active processes to controlling agentwhen they are about to become idleLet current weight at process = W

1. Send of B(DW): Find W1, W2 such that W1 > 0, W2> 0, W1 + W2 = W Set W = W1 and send B(W2)

2. Receive of B(DW): W += DW; if idle, become active

3. Send of C(DW): send C(W) to controlling agent Become idle

4. Receive of C(DW): W += DW

if W = 1, declare termination

APD - Note Curs - 11 Terminarea

Documents

Transcript of APD - Note Curs - 11 Terminarea