88

6.3. Procese egale. Stabilirea topologiei 6.3.1 Difuzarea mesajelor folosind sondaje În rezolvările multor probleme paralele, procesele realizează aceleaşi prelucrări, cooperând de pe poziţii egale pentru îndeplinirea unei funcţii. Ca exemplu, vom considera problema difuzării mesajelor folosind sondaje. Fie i nodul sursă al informaţiei care se difuzează. O posibilă soluţie este utilizarea arborelui de acoperire T pentru a stabili căile de comunicare a informaţiei de la i la toate celelalte noduri. Astfel nodul i transmite informaţia împreună cu T vecinilor săi. Fiecare vecin inspectează T şi transmite informaţia împreună cu T fiilor săi din T, s.a.m.d. Deoarece T este arbore de acoperire, informaţia va ajunge la fiecare nod, o singură dată ( comunicată de tatăl din T al nodului respectiv). Algoritmul este următorul: type tip_arb = array [1:N,1:N] of int; chan sondaj[1:N](tip_arb,tip_mesaj); Nod(p:1..N):: var arb:tip_arb, m : tip_mesaj; receive sondaj[p](arb,m); fa q:=1 to N st q este fiul lui p in arb -> send sondaj[q](arb,m) af Initiator:: var i: int := indexul nodului initiator; var top: array[1:N,1:N] of bool; var T : tip_arb, m : tip_mesaj; calculeaza T pe baza top; m := mesaj_de_transmis; send sondaj[i](T,m); Mesajul este pregătit de un proces Iniţiator situat în nodul i şi este comunicat procesului Nod(i). Aceasta permite descrierea întregii reţele de difuzare ca o colecţie de procese egale. Soluţia presupune că procesul Iniţiator cunoaşte topologia reţelei, din care derivează arborele de acoperire T. În cazul în care nodul iniţiator nu cunoaşte topologia, iar fiecare nod cunoaşte doar vecinii, difuzarea mesajului se poate face dacă fiecare nod retransmite mesajul primit

89

tuturor vecinilor săi, ignorând copiile acestuia. Pentru a furniza o soluţie complet simetrică, adoptăm convenţia că primul mesaj care se difuzează este retransmis chiar şi nodului de la care provine. În acest mod, fiecare nod cunoaşte precis numărul nodurilor de la care primeşte sau cărora le transmite mesajul. Soluţia are descrierea următoare: chan sondaj[1:n](tip_mesaj); Nod(p:1..n):: var leg: array [1:n] of bool := vecinii_lui_p; var num: int := numarul_vecinilor; var m: tip_mesaj; receive sondaj[p](m); fa q := 1 to n st leg[q] -> send sondaj[q](m); af; fa q := 1 to num-1 -> receive sondaj[p](m); af; Initiator:: var i:int := indexul_nodului_initiator; var m: tip_mesaj; m := mesaj_de_transmis; send sondaj[i](m); Comparând cele două soluţii, putem remarca următoarele: - numărul de mesaje transmise de primul algoritm este n-1, în timp ce,în al doilea caz, este 2m, unde m este numărul de legături din reţea; - mesajele transmise de al doilea algoritm sunt mai simple şi mai scurte, deoarece nu includ arborele de acoperire T. În esenţă, arborele de acoperire este construit dinamic, el constând din legăturile pe care sunt primite primele mesaje de către noduri. 6.3.2. Stabilirea topologiei unei reţele de procese Ca un alt exemplu, vom considera problema stabilirii topologiei unei reţele. Fiecare nod al reţelei este reprezentat de un proces, iar legăturile dintre noduri sunt realizate prin canale. Fiecare nod poate comunica doar cu vecinii săi, cu care are canale directe de legătura. Iniţial, fiecare nod cunoaşte aceste canale şi, implicit, vecinii. Problema este ca fiecare nod să determine topologia întregii reţele. Aceasta informaţie ar putea fi folosită în dirijarea mesajelor între noduri neadiacente. Vom reprezenta fiecare nod printr-un proces Nod(p:1..N). Un tablou de legături, leg[1:N], local fiecarui proces, va preciza vecinii nodului p: pentru p, leg[q]=TRUE daca q este vecin cu p, altfel leg[q]=FALSE.

90

Relaţia de vecinătate este simetrică, astfel că pentru p, leg[q]=TRUE <=> pentru q, leg[p]=TRUE. Topologia care trebuie calculată este reprezentată în fiecare nod prin matricea de adiacenţă top, având elementele :

top[i,j]=TRUE , dacă i este vecin cu j top[i,j]=FALSE , în caz contrar.

Evident, top se calculează folosind valorile cunoscute leg ale fiecărui proces p, astfel că, la terminarea calcului, următorul predicat este satisfacut: TOPOLOGIE: ( pentru orice p,q: 1<=p,q<=N : top[p,q] = legp[q] ) Problema are o rezolvare foarte simplă în cazul variabilelor partajate: este suficient ca fiecare proces p sa actualizeze linia p a matricei top. Deoarece procesele folosesc elemente de matrice din linii diferite, non-interferenţa este asigurată. O altă soluţie simplă este cea centralizată: fiecare proces trimite informaţii despre vecinii săi unui proces central care alcătuieşte matricea de adiacenţă, pe care o retransmite apoi diferitelor noduri. Deoarece nu toate nodurile sunt vecine cu nodul central, rezolvarea este inevitabil asimetrică, unele noduri jucând şi rolul de intermediere a transferului de mesaje, în timp ce altele nu (prezentăm această soluţie ceva mai târziu). Algoritmul pulsaţiilor pentru stabilirea topologiei O soluţie uniformă este cea distribuită: fiecare proces calculează singur topologia, folosind informaţiile provenite de la vecini. Dacă fiecare nod transmite vecinilor informaţia din matricea sa de adiacenţă şi, în acelaşi timp, primeşte matricea de adiacenţă a fiecărui vecin, după un rund complet, fiecare nod va dispune de informaţii despre noduri aflate la distanţa 2 de el. După două runde complete, orice nod va avea informaţii despre noduri aflate la distanţa 3, etc. În general, dupa r runde sunt completate liniile din top corespunzătoare nodurilor q aflate la o distanţă d <= r, adică următorul predicat este satisfăcut pentru fiecare proces p: RUND: ( oricare ar fi q cu 1<=q<=N: dist(p,q) <=r => top[q,*] este completat ) unde dist(p,q) este distanţa de la p la q, adică lungimea căii celei mai scurte între cele două noduri.

91

Cunoscând diametrul D al unei reţele, putem face calculul topologiei după următorul algoritm: type tip_top=array[1:N,1:N] of bool; tip_leg = array [1 :N] of bool; chan topologie[1:N] (tip_top); Nod(p:1..N):: var leg: tip_leg := vecinii_lui_p); {initializat cu vecinii lui p} var top: tip_top := ([N*N]FALSE); top[p,1:N]:= leg; {actualizeaza linia vecinilor} var r: int := 0; var top_nou: tip_top; do r<D -> {transmite topologia curenta tuturor vecinilor} fa q :=1 to N st leg[q]-> send topologie[q](top) af fa q :=1 to N st leg[q]-> receive topologie[p](top_nou); top := top or top_nou; af r := r+1; od Algoritmul prezentat se numeşte algoritmul pulsaţiilor (inimii) - heartbeat - deoarece acţiunile fiecărui nod pot fi asemănate cu bătăile inimii: transmiterea informaţiilor către vecini este asemănătoare dilatării, în timp ce culegerea informaţiilor de la vecini este asemănătoare unei contracţii. Algoritmul are două neajunsuri: unul este faptul că, în general, D nu este cunoscut; cel de al doilea este traficul inutil, anumite noduri primind mesaje chiar după actualizarea completă a tabloului top local. Pentru a ocoli aceste neajunsuri, trebuie să observăm că, deoarece reţeaua este conexă, putem considera că un nod cunoaşte întreaga topologie dacă fiecare linie top are cel puţin un element TRUE. În acest moment, procesul p trebuie să mai execute un singur rund, după care se poate termina. Acest ultim rund este necesar pentru a transmite vecinilor informaţiile recente primite, eventual, la rundul precedent. Totodată, procesul poate culege ultimele mesaje care îi sunt transmise, evitând abandonarea mesajelor în canale. Deoarece un nod poate termina cu un rund înainte sau după vecinii săi, sunt necesare măsuri suplimentare de evitare a blocării

92

definitive: un proces transmite mesaje doar vecinilor care nu s-au terminat şi preia doar mesajele pe care aceştia le trimit. Aceste elemente sunt surprinse în descrierea următoare: type tip_top=array[1:N,1:N] of bool; tip_leg = array [1 :N] of bool; chan topologie[1:N](transm: int, gata : bool, top: tip_top); Nod(p:1..N):: var leg: tip_leg := (vecinii_lui_p); var activ: tip_leg := leg; {vecinii activi} var top: tip_top := ([N*N]FALSE); var gata: bool := FALSE; var transm: int, qgata: bool, top_nou: tip-top; top[p,1:N] := leg; {actualizeaza vecinii lui p} do not gata -> {transmite topologia curenta tuturor vecinilor} fa q :=1 to N st leg[q]-> send topologie[q](p,FALSE,top) af {receptioneaza topologiile de la vecini} fa q :=1 to N st leg[q]-> receive topologie[p](transm,qgata,top_nou); top := top or top_nou; if qgata -> activ[transm]:=FALSE fi af if toate liniile din top au un element TRUE -> gata := TRUE fi od {transmite top vecinilor activi in ultimul rund} fa q :=1 to N st activ[q]-> send topologie[q](p,TRUE,top) af fa q :=1 to N st activ[q]-> receive topologie[p](transm,qgata,top_nou); af Trebuie observat că primul ciclu se termină deoarece, reţeaua fiind conexă, informaţiile despre un nod se propagă la fiecare rund. Ca urmare, la un moment dat, toate liniile matricei top vor fi actualizate şi gata devine TRUE. Pentru algoritmii distribuiţi, o măsură importantă de complexitate este numărul de mesaje comunicate între procese. În varianta centralizată, menţionată la începutul

93

secţiunii, se transmit 2*N mesaje: unul de la fiecare nod la serverul central şi câte unul de răspuns, de la server la fiecare nod. De data aceasta, numărul mesajelor este mai mare, dar mesajele se transmit doar între vecini. Dacă diametrul reţelei este D, iar gradul fiecărui nod nu depăşeşte valoarea m , numărul mesajelor este limitat superior de 2m*N*(D+1). Justificarea este că se execută D+1 runde, în care fiecare nod schimbă cu fiecare vecin două mesaje. Stabilirea topologiei unei reţele are şi alte soluţii. Unele se bazează pe mesajele de sondaj cu ecou, la care ne referim în cele ce urmează. Ea foloseşte mesajele de sondaj pentru a difuza informaţia într-o reţea. Stabilirea topologiei folosind mesaje de sondaj cu ecou Rezolvarea bazată pe mesajele de sondaj cu ecou are următoarele etape: un iniţiator colectează informaţii despre topologia locală a tuturor celorlalte noduri, determină topologia întregii reţele şi o difuzează nodurilor. Colectarea se poate face în două faze: mai întîi, fiecare nod transmite cîte un mesaj de sondaj vecinilor şi recepţionează topologii ca ecouri; apoi, fiecare nod trimite topologia locală actualizată cu ecourile, nodului de la care a primit primul mesaj de sondaj. Iniţiatorul mesajului de sondaj primeşte informaţiile cumulate prin ecouri de la toate celelalte noduri. Ca urmare, el poate calcula topologia întregii reţele, pe care o transmite apoi prin legăturile arborelui de acoperire. Pentru început, să presupunem că reţeaua este un graf aciclic, mai precis un arbore şi că nodul iniţiator i este rădăcina acestuia. Nodul i trimite un mesaj de sondaj tuturor vecinilor (fiilor). Ca urmare, mesajele se propagă spre frunze. Deoarece acestea nu au alţi vecini, ele încep faza de transmitere a ecourilor. Fiecare frunză trimite un mesaj cu topologia vecinilor săi, către părinte. După adunarea mesajelor ecou de la fii, un nod le combină cu propria sa informaţie şi transmite rezultatul părintelui său. Rădăcina va primi informaţii de la toate celelalte noduri, obţinînd prin reuniune topologia reţelei. const sursa=i; type tip_leg = array [1:n] of bool; tip_top = array [1:n, 1:n] of bool; chan sondaj[1:n](transm: int); chan ecou[1:n](top: tip_top); chan ecou_final(top: tip_top);

94

Nod(p:1..n):: var leg: tip_leg := vecnii_lui_p; var top: tip_top := ([n*n] false); top[p, 1..n] := leg; var top_nou: tip_top; var parinte: int; receive sondaj[p](parinte); {transmite sondaje celorlalte noduri vecine, copiii lui p} fa q := 1 to n st leg[q] and (q<>parinte) -> send sondaj[q](p); af; {primeste ecourile si fa reuniunea lor} fa q := 1 to n st leg[q] and (q<> parinte) -> receive ecou[p](top_nou); top := top or top_nou; af; if p=sursa -> send ecou_final(top); [] p<>sursa -> send ecou[parinte](top); fi; Initiator:: var top: tip_top; send sondaj[sursa](sursa); receive ecou_final (top); În cazul general, adoptăm următoarele măsuri: - ca şi mai înainte, după ce primeşte un mesaj de sondaj, un nod îl trimite tuturor celorlalţi vecini, după care aşteaptă ecouri de la ei; - datorită existenţei ciclurilor, două noduri îşi pot trimite reciproc sondaje; pentru toate sondajele în afara primului, se transmite un ecou cu o topologie nulă; topologia locală va fi transmisă doar ca ecou la primul sondaj; - pentru recepţia eventualelor sondaje primite pe durata aşteptării ecourilor, cele două tipuri de mesaje sunt recepţionate pe un acelaşi canal. const sursa=i; {index initiator} type fel = enum(sonda, ecou); type tip_leg = array [1:n] of bool; tip_top = array [1:n, 1:n] of bool; chan sonda-ecou[1:n](fel, transm: int, top:tip_top); chan ecou_final(top: tip_top); Nod(p:1..n):: var leg: tip_leg := vecinii_lui_p; var top: tip_top := ([n*n] false); top[p, 1:n] := leg;

95

var top_nou: tip_top; var prim: int; {nodul de la care s-a primit prima sonda} var k:fel, transm:int; var nr_ecouri: int := numar_vecini - 1; receive sonda-ecou[p](k, prim, top_nou); {transmite sondaje celorlalte noduri vecine, copiii lui p} fa q := 1 to n st leg[q] and (q<>prim) -> send sonda-ecou[q](sonda, p, O); {topologie nula} af; {primeste ecourile si fa reuniunea lor, sau sonde si ignora} do nr_ecouri>0 -> receive sonda-ecou[p](k, transm, top_nou); if k=sonda -> send sonda-ecou[transm](ecou, p, O); [] k=ecou -> top := top or top_nou; nr_ecouri := nr_ecouri-1; fi od; if p=sursa -> send ecou_final(top); [] p<>sursa -> send sonda-ecou[prim](ecou, p, top); fi; Initiator:: var top: tip_top; send sonda-ecou[sursa](sonda, sursa, O); receive ecou_final (top); Procesul Nod(p) transmite un mesaj de sondaj vecinilor, aşteptând apoi ecourile. Ciclul de aşteptare se încheie cînd toţi vecinii au transmis ecourile (în algoritm se face doar contorizarea ecourilor). În acest moment, canalul sonda-ecou[p] nu mai conţine nici un mesaj, deoarece orice proces q transmite un eventual mesaj de sondaj înainte de ecou, sondaj ce este prelucrat înaintea ecoului (ciclul de transmitere a sondajelor precede ciclul de transmitere a ecourilor). În privinţa numărului de mesaje, prezentul algoritm foloseşte un număr mai mic de mesaje decît algoritmul pulsaţiilor: fiecare legătură (aparţinând arborelui de acoperire) corespunzătoare primei sonde poartă două mesaje (sonda şi ecoul), iar celelalte cîte patru (două sonde şi două ecouri). Transmiterea topologiei de la iniţiator la noduri necesită alte n mesaje. Ca şi la difuzarea mesajelor folosind listele vecinilor, şi aici arborele de acoperire este stabilit dinamic, constînd din legăturile de la fiecare nod la nodul prim, de la care acesta a recepţionat primul mesaj de sondaj.

96

Exerciţii 1) Problema mariajului stabil. Fie două tablouri a câte n procese, B (bărbaţi) şi F (femei). Fiecare bărbat clasifică femeile de la 1 la n şi fiecare femeie clasifică bărbaţii de la 1 la n. Un mariaj este o corespondenţă unu-la-unu B-F. O împerechere este stabilă dacă pentru oricare doi bărbaţi b1, b2 şi pentru corespondentele lor f1 şi f2 sunt satisfăcute condiţiile următoare: - b1 clasifică f1 mai sus decat f2 sau f2 clasifică b2 mai sus decat b1; şi - b2 clasifică f2 mai sus decat f1 sau f1 clasifică b1 mai sus decat b2. Altfel spus, un mariaj este instabil dacă există un bărbat şi o femeie care preferă fiecare perechea celuilalt. O soluţie a problemei este o mulţime de n perechi b-f, toate stabile.Scrieţi un program de rezolvare a problemei mariajului stabil, în care procesele comunică doar prin mesaje asincrone. 2) Imperechere distribuită. Sunt date n procese, fiecare corespunzând unui nod dintr-un graf. Fiecare nod poate comunica doar cu vecinii săi. Fiecare proces încearcă să se împerecheze cu un vecin. La terminarea împerecherii, fiecare proces trebuie să fie împerecheat sau singur, dar nu trebuie să existe două procese care sunt vecine şi sunt ambele neîmperecheate. 3) Arbore de acoperire. Sunt date n procese, fiecare corespunzând unui nod dintr-un graf. Fiecare nod poate comunica doar cu vecinii săi. Scrieţi un program pentru construirea arborelui de acoperire, fără a afla mai înainte topologia. Deci, fiecare proces va decide împreună cu vecinii săi care legături să fie puse în arbore şi care nu. 4) Se dau trei procese, fiecare avand o secvenţă de numere întregi ordonată crescător. Există cel puţin o valoare comună celor trei secvenţe. Scrieţi programul care găseşte cea mai mică valoare comună.