Algoritmi Paraleli și Distribuiți - Terminarea programelor distribuite - PDF

Algoritmi Paraleli și Distribuiți Terminarea programelor distribuite Prof. Ciprian Dobre [email protected]  Terminarea programelor distribuite Problema: detecția terminării Algoritmi paraleli:  toate procesele se termină ▪ cicluri in...

Algoritmi Paraleli și Distribuiți Terminarea programelor distribuite Prof. Ciprian Dobre [email protected]  Terminarea programelor distribuite Problema: detecția terminării Algoritmi paraleli:  toate procesele se termină ▪ cicluri infinite?  procese terminate sau blocate și nu există I/E în curs  simplu pentru un singur procesor - coada ready goală Algoritmi distribuiți:  fiecare proces să fie liber ▪ a terminat execuția sau ▪ se află în aşteptarea unui mesaj (receive)  pe canale să nu existe mesaje în tranzit  Procese organizate în inel P(1) incepe executia P(1) M P(1) M P(6) P(2) P(6) P(2) M P(5) P(3) P(5) P(3) P(4) M P(4) M  Procese organizate în inel P(1) initiaza terminarea termina? P(1) P(1) jeton jeton jeton P(6) P(2) P(6) P(2) jeton jeton P(5) P(3) P(5) P(3) jeton jeton P(4) P(4) inainte de a primi jeton, P(1) poate fi reactivat de un mesaj de la P(6)! Procese organizate în inel (tehnica jetoanelor) (1) ▪Inițiatorul terminării este procesul P ▪acțiunile lui P cînd devine liber prima dată: culoare = albastru; jeton = 0; send ch(jeton); ▪acțiunile lui P[i=1 to N] la recepția unui mesaj obişnuit: culoare[i] = roșu;  Tehnica jetoanelor (2) acțiunile lui P[i=2 to N] la primirea unui jeton (și după ce devine liber): culoare[i] = albastru; jeton = jeton +1; send ch[(i + 1) mod n](jeton); acțiunile lui P(1) la recepția jetonului: if (culoare == albastru) { anunță terminarea; stop } culoare = albastru; jeton = 0; send ch(jeton);  Tehnica jetoanelor (3) 1 Jeton 0 4 3 2 1 5 2 STOP 3 4 Terminarea în cazul general (tehnica jetoanelor)(1) topologie generală de graf c un ciclu care include toate arcele grafului; fie nc lungimea lui Terminarea în cazul general (tehnica jetoanelor)(2) un jeton care se transmite după mesajele de date are inițial valoarea 0 acțiunile lui P[i=1 to N] la primirea unui mesaj uzual: culoare[i] = roșu; acțiunile lui P[i=1 to N] la recepția jetonului: if (jeton == nc) { if (culoare[i] == albastru) { anunță terminarea; stop } else if (culoare[i] == roșu) { culoare[i] = albastru; jeton = 0; } } else if (culoare[i] == albastru) jeton = jeton +1; setează j la canalul următor din ciclul c; send ch[j](jeton); Terminarea în cazul general (tehnica jetoanelor)(3) J D J Jeton 1 2 3 5 4 1 0 2 STOP DJ 5 3 J 4 J nc = 5  Terminare (topologii arbore) - Tehnica confirmarii mesajelor -  Terminarea in topologii arbore Când un proces frunză se termină, el anunţă părintele său. Când un nod oarecare al arborelui se termină, el aşteaptă notificarea terminării de la toţi fiii săi şi apoi îşi anunţă părintele. Notificările se propagă astfel pînă la procesul sursa, aflat în rădăcina arborelui. mesaj 1 notificare 2 3 4 5 6 7 8  Confirmarea mesajelor (1) Funcția de determinare a stării canalelor se poate împărți între procesele programului: fiecare proces verifică canalele pe care a trimis mesaje de date altor procese ( canalele sale de ieşire ). Pe un canal  se trimit mesaje de date și se primesc semnale de confirmare sau  se primesc mesaje de date și se trimit semnale de confirmare Confirmarea mesajelor: dacă pentru fiecare mesaj de date transmis pe un canal procesul primeşte de la receptor un semnal de confirmare, atunci canalul respectiv este gol. Presupune existența unui proces sursă:  care nu are legături de intrare şi  poate accesa orice alt proces pe o cale oarecare din graf  Confirmarea mesajelor (2) Exemplu:  Procesul sursă: 1  Arbore de acoperire 1 2 4 3 Algoritmul Dijkstra-Scholten (1) Dijkstra, Edsger W., and Carel S. Scholten. "Termination detection for diffusing computations." Information Processing Letters 11.1 (1980): 1-4.  Algoritmul Dijkstra-Scholten (1) Bazat pe transmiterea unor semnale de confirmare Cazul unei rețele cu topologie arborescentă:  Când un proces frunză se termină, el îl anunță pe părintele său.  Când un nod oarecare al arborelui termină, el aşteaptă notificarea terminării de la toți fiii săi și apoi își anunță părintele.  Notificările se propagă până la procesul sursă. Cazul unui graf dirijat aciclic de procese  Deficitul unei legături = diferența dintre numărul de mesaje de date transmise şi numărul de semnale de confirmare primite pe acea legătură  Când un nod doreşte să termine: ▪ aşteaptă primirea unor semnale pe legăturile de ieşire a datelor, semnale care reduc deficitele la zero (pe acele legături). ▪ trimite pe fiecare legătură de intrare a datelor un număr de semnale egal cu deficitul (legăturii respective).  Algoritmul Dijkstra-Scholten (2) Cazul general: cicluri în graful proceselor Rezolvare: generare arbore de acoperire:  fiecare legătură generată la prima recepție (adică prima legătură de intrare, numită prim – de la părinte) Pentru terminare:  trimitere semnale pentru toate legăturile de intrare, mai puțin prim  recepție semnale pentru toate legăturile de ieşire  trimitere semnale spre prim. Schema de semnalare este separată și suplimentară față de prelucrarea propriu-zisă Algoritmul Dijkstra-Scholten termina 1 2 3 4 5 6 7 8  Algoritmul Dijkstra-Scholten (3) LORDUL SERVITORUL Algoritmul Dijkstra-Scholten (4) Comunică doar cu alți lorzi și cu propriul servitor Comunică cu lorzii prin scrisori (prin poștă) și cu servitorul prin semnale de comunicare (la telefon) Își anunță servitorul când trimite/primește o scrisoare (spunându-i și destinația/sursa) După ce se plictisește întreabă servitorul dacă a terminat treaba ca să poată merge la vânătoare Comunică doar cu alți servitori și cu propriul lord Comunică doar prin semnale (la telefon) Trimite semnale de confirmare pentru scrisorile primite și așteaptă semnale de confirmare pentru scrisorile trimise  Scrisoarea primită de la lorduli se confirmă servitoruluii Răspunde afirmativ doar dacă a primit și trimis toate confirmările pentru mesajele trimise și primite, altfel îl roagă pe lord să aștepte  Algoritmul Dijkstra-Scholten (5) În continuare Lord = Prelucrare (prelucrează mesaje de date) Servitor = Nod (gestionează semnalele de confirmare cu alte noduri și semnalele de comunicare cu Prelucrare) Canalul poștal = canalul chm  chmi este „adresa” lui Prelucrarei  Prelucrarei primește mesaje pe chmi și îi trimite lui Prelucrarej mesaje pe chmj Canalul telefon pentru Nod = canalul chs  chsi este „numărul de telefon” al lui Nodi  Nodi primește semnale pe chsi (de la alte noduri sau de la Prelucrarei) și trimite semnale de confirmare lui Nodj pe chsj Canalul telefon pentru Prelucrare = canalul stop  stopi este „numărul de telefon” al lui Prelucrarei  Prelucrarei primește semnale de comunicare (da/nu) pe stopi de la Nodi  Algoritmul Dijkstra-Scholten (6) Prelucrare[k] chm[i] Prelucrare[i] chm[j] Prelucrare[j] Nod[k] Nod[j] stop[i] chs[i] chs[k] Nod[i]  Algoritmul Dijkstra-Scholten (7) enum fel{semnal, transmitere, receptie, terminare}; typedef struct {bool există; int deficit} arc; chan chs[1:N](fel op, int id); chan chm[1:N](int id, tip_date date); chan stop[1:N](bool); process Prelucrare[i=1 to N]{ tip_date data; int id; bool term; inițializări; term = false; while (NOT term) { receive chm[i](id, data); send chs[i](recepție, id); realizează prelucrare.... send chm[j](i, data); send chs[i](transmitere, j);... if (decizie de terminare) term = true; } term =false; while (NOT term) { send chs[i](terminare, i); receive stop[i](term); } stop;  Algoritmul Dijkstra-Scholten (8) process Nod[i=1 to N] { arc in[1:N]; int nsemnale = 0; int prim = 0; var id: int; fel k; semnal de la Prelucrare: a primit un mesaj while (true) { receive chs[i](k, id); semnal de la Prelucrare: a trimis un mesaj if (k == recepție) { if (prim == 0) prim = id fi; semnal de confirmare de la alt nod in[id].deficit = in[id].deficit + 1; } else if (k == transmitere) nsemnale = nsemnale+1; else if (k == semnal) nsemnale = nsemnale-1; Prelucrare dorește terminarea else if (k == terminare){ for [j = 1 to N st (in[j].există AND (j prim))] while (in[j].deficit > 0) { send chs[j](semnal, i); in[j].deficit = in[i].deficit - 1; } } if (nsemnale 0) send stop[i](false); else if (nsemnale == 0) { if ((i sursa) AND (prim 0)) { while (in[prim].deficit > 0) { send chs[prim](semnal, i); in[prim].deficit = in[prim].deficit - 1; } } send stop[i](true); }} } Detecția terminării folosind marcaje Misra, Jayadev. "Detecting termination of distributed computations using markers." Proceedings of the second annual ACM symposium on Principles of distributed computing. ACM, 1983.  Detecția terminării folosind marcaje (1) Procesele transmit mesaje de marcaj la sfârşitului comunicației. Procesele primesc semnale de confirmare doar pentru marcaje. Pentru terminare:  aşteaptă marcaje pe legăturile de intrare ▪ (să termine cei de la care a primit mesaje)  transmite marcaje pe legăturile de ieşire ▪ (anunță propria terminare celor cărora le-a trimis mesaje)  transmite semnale pe legăturile de intrare (mai puțin prim) ▪ (confirmă marcajele primite) prim  aşteaptă semnale pe legăturile ieşire ▪ (așteaptă confirmări pentru marcajele trimise)  transmite semnal pentru prim Proces  Detecția terminării folosind marcaje (2) Pentru fiecare arc se țin două atribute: activ și marcaj. Pentru fiecare arc de intrare, se înregistrează 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). Pentru fiecare arc de ieşire, se înregistrează dacă:  s-a transmis un mesaj (se pune activ pe true);  s-a transmis un marcaj (se pune marcaj pe true);  s-a primit un semnal de confirmare (se pun ambele pe false).  Detecția terminării folosind marcaje (3) const marcaj = mesaj-special-de-marcaj-sfârșit-date; typedef enum {semnal, transmitere, recepție, recepție-marcaj, terminare} fel; typedef struct {bool există; bool activ; bool marcaj} arc; chan chs[1:N](fel op, int id); chan chm[1:N](id:int, tip_date date); chan stop[1:N](bool); process Nod[i=1 to N]{ bool term = false; arc in[1:N], out[1:N]; int nsemnale = 0; int prim = 0; int nmarcaje; int id; fel k;  Detecția terminării folosind marcaje (4) while (true) { receive chs[i](k, id); semnal de la Prelucrare: a primit un mesaj if (k == recepție) { if (prim == 0) prim = id; if (NOT in[id].activ) { in[id].activ = true; nmarcaje = nmarcaje + 1; } semnal de la Prelucrare: a primit un marcaj else if (k == recepție-marcaj) { in[id].marcaj = true; nmarcaje = nmarcaje - 1; if (id == prim) term = true; } else if (k == transmitere) { semnal de la Prelucrare: a trimis un mesaj if (NOT out[id].activ) { out[id].activ = true; nsemnale = nsemnale + 1; } else if (k == semnal) { semnal de confirmare de la alt nod out[id].activ = false; out[id].marcaj = false; nsemnale = nsemnale - 1; }  Detecția terminării folosind marcaje (5) else if (k == terminare) { if (NOT term) send stop[i](false); else if (term) { for [j = 1 to N st (j prim AND out[j].activ AND NOT out[j].marcaj)] { send chm[j](i, marcaj); out[j].marcaj = true; } if (nmarcaje 0) send stop[i](false); else if (nmarcaje == 0) { for [j = 1 to n st (in[j].există AND (jprim) AND in[j].activ)] { send chs[j](semnal, i); in[j].activ = false; in[j].marcaj = false; } if (nsemnale 0) send stop[i](false); else if (nsemnale == 0) { if ((i sursa) AND (prim 0)) { send chs[prim](semnal, i); in[prim].activ = false; in[prim].marcaj = false; } send stop[i](true); } } } }  Detecția terminării folosind marcaje (6) process Prelucrare[i=1 to N] { tip_date data; int id; bool term; initializari; term = false; while (NOT term) { receive chm[i](id, data); if (data==marcaj) send chs[i](receptie-marcaj,id); else if (datamarcaj) { send chs[i](receptie, id); realizează prelucrare.... send chm[j](i, data); send chs[i](transmitere, j);... if (decizie de terminare) term = true; } } term =false; while (NOT term) { send chs[i](terminare, i); receive stop[i](term); } stop;  Algoritmul lui Huang Huang, S-T. "Detecting termination of distributed computations by external agents." Proceedings. The 9th International Conference on Distributed Computing Systems. IEEE, 1989.  Algoritmul lui Huang (1) Modelul se bazează pe următoarele:  procesele pot fi active sau libere (idle)  doar procesele active transmit mesaje  procesele libere pot deveni active la recepția unui mesaj de calcul  procesele active pot deveni libere în orice moment  terminarea: toate procesele sunt libere şi nu există mesaje de date în tranzit  topologia este un graf conex  Algoritmul lui Huang (2) Ideea:  Un agent de control are inițial ponderea 1.  Toate celelalte procese sunt libere și au inițial ponderea 0.  Calculul porneşte atunci când agentul de control trimite un mesaj de date unui proces.  Un proces liber devine activ la recepția unui mesaj de date. Notații:  B(DW) ▪ Mesaj de date cu ponderea DW ▪ Trimis doar de agentul de control sau de un proces activ  C(DW) ▪ Mesaj de control cu ponderea DW ▪ Trimis de un proces activ agentului de control când devine liber  W ▪ Ponderea curentă a unui proces  Algoritmul lui Huang (3) 1. Send B(DW):  Găseşte W1, W2 astfel încât W1 > 0, W2 > 0, W1 + W2 = W  Pune W = W1 şi transmite B(DW = W2) 2. Receive B(DW):  W = W + DW  if liber -> devine activ fi 3. Send C(DW):  send C(DW = W) agentului de control  devine liber 4. Receive C(DW) (doar agentul de control):  W = W + DW  if W = 1 -> declară “terminarea” fi  Algoritmul lui Huang (4) 0 4 5 0 1 A 3 0 Sursă Destinație Mesaj A 3 B(DW=0.5) 0 1 2 0 TIMP 0  Algoritmul lui Huang (4) 0 4 5 0 0.5 A 3 0.5 Sursă Destinație Mesaj A 2 B(DW=0.25) 3 4 B(DW=0.25) 0 1 2 0 TIMP 1  Algoritmul lui Huang (4) 0.25 4 5 0 0.25 A 3 0.25 Sursă Destinație Mesaj 4 1 B(DW=0.125) 3 A C(DW=0.25) 2 5 B(DW=0.125) 0 1 2 0.25 TIMP 2  Algoritmul lui Huang (4) 0.125 4 5 0.125 0.5 A 3 0 Sursă Destinație Mesaj 4 1 B(DW=0.0625) 2 A C(DW=0.125) 1 3 B(DW=0.0625) 0.125 1 2 0.125 5 1 B(DW=0.0625) TIMP 3  Algoritmul lui Huang (4) 0.0625 4 5 0.0625 0.625 A 3 0.0625 Sursă Destinație Mesaj 1 A C(DW=0.1875) 3 A C(DW=0.0625) 4 A C(DW=0.0625) 0.1875 1 2 0 5 A C(DW=0.0625) TIMP 4  Algoritmul lui Huang (4) 0 4 5 0 1 A 3 0 Sursă Destinație Mesaj 0 1 2 0 TIMP 5  Sumar ▪Problematica terminării programelor distribuite ▪Cazul proceselor organizate în inel ▪Tehnica jetoanelor pentru cazul general ▪Confirmarea mesajelor ▪Algoritmul Dijkstra-Scholten ▪Detecția terminării folosind marcaje ▪Algoritmul lui Huang