2. Sincronizarea n sisteme distribuiteAm artat mai sus c una dintre cele mai mari probleme ale algoritmilor distribuii e aceea c pe

fiecare nod al sistemului, ceasul fizic local poate fi desincronizat de celelalte ceasuri fizice. De aceea, nmulte aplicaii de timp real n care ordinea n care se proceseaz evenimentele conteaz, este necesarsincronizarea nodurilor.2.1. Sincronizarea ceasurilor fizice. Algoritmul Cristian

Vom discuta mai nti despre ceasurile fizice aflate pe fiecare main de calcul. Problemamsurrii timpului este mai complicat dect pare, mai ales n cazurile n care este necesar o mareprecizie. n trecut, timpul se msura raportndu-se la micarea solar. Intervalul de timp dintremomentele cnd soarele este la punctul su maxim pe cer se numete zi. O zi conine 24 de ore, fiecareor conine 3600 de secunde, deci 1 secund solar este reprezint a 1/86400 a parte dintr-o zi solar. n1940 s-a constatat c perioada de rotaie a Pamantului n jurul Soarelui nu este constant. Oamenii detiin susineau c, n urm cu 300 milioane de ani n urm, un an solar dura cu aproximaie 400 zile.Pentru a compensa durata variabil a unei zile solare, s-a introdus conceptul de secund medie solar.Astfel astronomii au luat duratele mai multor zile solare de-a lungul timpului, au fcut media lor, iapoi 1/86400 din rezultatul obinut a fost aa numita secund medie solar.

n 1948 a aprul ceasul atomic. Inventarea ceasului atomic a permis msurarea timpului cu oprecizie mult mai mare. S-a definit, de ctre fizicieni de data aceasta, c durata unei secunde esteintervalul de timp n care atomul de cesiu 133 face exact 9 192 631 770 de tranziii. S-a ales aceastvaloare pentru ca rezultatul s coincid cu valoarea secundei medii solare calculat de astronimi la aceadat. La ora actual n lume exist aproximativ 50 de laboratoare care dein ceasuri cu atomi decesiu133. Periodic toate cele 50 de laboratoare raporteaz cte secunde a numrat ceasul de cesiu de lapunerea sa n funciune. Prin medierea celor 50 de rezultate, se poate obine cu cea mai mare precizie,cte secunde au trecut de la 1 Ianuarie 1958, data la care a intrat n funciune primul ceas atomic.

Metoda ceasurilor cu atomi de cesiu are ns o problem. Dup cum am spus n rndurile de maisus, o zi solar are o durat de timp variabil.Dac s-ar folosi ceasurile cu cesiu pentru raportareatimpului, cum ele msoar secundele cu precizie mare, i cum durata unei zile solare este n scdere,atunci de exemplu ora 12:00 ar fi din ce n ce mai aproape de zorii zilei dac ne raportm la momentulcnd rsare soarele. De aceea, la timpul msurat cu ceasul atomic, s-au mai adugat nite corecii. Aufost introduse nite aa numite secunde scurte. O secund scurt este mai scurt dect o secundraportat de ceasul atomic. Rostul secundelor scurte este acela de a face, n mod controlat ca ceasulatomic s raporteze un timp sincronizat cu poziia soarelui. Acest mod de a msura timpul se numetetimp UTC (Universal Coordinated Time).

Pentru a raporta timpul UTC echipamentelor care necesit precizie ridicat n msurareatimpului se folosesc unde scurte radio. n Fort Collins Colorado, dar i n alte pri ale lumii exist staiiradio care la fiecare secund UTC, trimit un semnal radio ctre toate receptoarele. Totui din cauzamediului de transmisiune, acest semnal poate ajunge la receptoare cu o variaie de pn la 10 ms. Deasemenea, o alternativ la staiile radio pot fi si sateliii geo-staionari.

n concluzie putem spune c sincronizarea unui echipament la timpul UTC este destul dedificil. Este nevoie de un receptor radio care s recepioneze semnalul de la o staie cum e cea din FortCollins sau cum sunt sateliii geo-staionari. De asemenea, chiar dac echipamentul respectiv va aveaun receptor de acest fel, el va putea menine ceasul UTC cu o precizie de 10 ms.

Dup cum am vzut mai sus, exist foarte puine ceasuri atomice n lume, i acestea sunt foartescumpe. Pentru a face accesibil ceasul UTC la toat lumea, s-au folosit staii care emit periodic oraexact. Chiar i aa, costul unui receptor WWV pentru ceasul UTC este destul de ridicat. De aceea, seprefer ca ntr-un sistem distribuit o singur main s dein receptorul WWV, iar celelalte s i

2sincronizeze ceasurile fizice dup aceast main. n continuare, vom discuta nite exemple dealgoritmi folosii pentru sincronizarea ceasurilor fizice.

Dup cum am spus mai sus, pentru meninerea ceasurilor fizice, se folosesc cristale de quartz.Cnd sunt puse sub tensiune, cristalele oscileaz pe o anumit frecven care depinde de proprietilefizice ale cristalului de quartz i de valoarea tensiunii la care este supus. Pe lnga cristalul de quartz, semai folosesc i doi regitrii, un numrtor i un registru n care se stocheaz valoarea iniial anumratorului. La fiecare oscilaie a cristalului, numrtorul se decrementeaz. Cnd numrtorulajunge la valoarea 0, se genereaz o ntrerupere i numrtorul se va ncrca cu valoarea reinut deregistrul cu valoarea iniial, i procesul se reia. Astfel, prin alegerea cristalului i prin reglareatensiunii la care este supus, se poate face astfel nct sistemul s genereze ntreruperi cu o rat de 60 deori pe secund, sau orice alt frecven dorit. Fiecare ntrerupere generat poate fi considerat un tactde ceas fizic. Cnd s-au realizat 60 de ntreruperi, se incrementeaz cu 1 registrul care ine ceasul afiatutilizatorului. S notm cu C aceast valoare i cu t timpul real. n cazul ideal, ceasul afiat deechipament este identic cu ceasul UTC, deci dC / dt = 1. n realitate, din cauza imperfeciunilorcristalelor de quartz, din cauza variaei frecvenei de oscilaie a cristalelor de quartz cu temperatura, nutoate mainile de calcul vor avea exact 60 de ntreruperi pe secund. De aceea, vor fi maini cu ceasurimai rapide dect ceasul ideal, sau cu ceasuri fizice mai lente dect ceasul ideal. Aceste cazuri suntafiate n figura de mai jos.

Fig 2.1 Ceas fizic ideal n comparaie cu ceasuri realeDin figura de mai sus se observ faptul c, periodic, mainile de calcul trebuie s i actualizeze

ceasul fa de ceasul ideal de referin. Algoritmul Cristian se folosete de acest principiu. Sconsiderm un sistem distribuit n care o singur main de calcul va avea un receptor WWV. Aceamain va avea rolul de server de timp. Din cauz c celelalte maini au fenomenul de drift al ceasului,ele vor avea o deviaie fa de ceasul ideal, conform formulei

11 dtdC(2.1)

3unde este rata maxim de drift i este o constant pe care o afieaz productorul de cristale de quartz.n cazul cel mai defavorabil, putem avea un nod de sistem distribuit care va avea un ceas mai rapid cui altul care s aib un ceas mai ncet cu Aceasta nseamn c ntr-o perioad de timp t, va apreao diferen de 2t ntre cele dou ceasuri fizice. De obicei un proiectant de sisteme distribuite trebuies garanteze c diferena dintre dou ceasuri fizice s nu depeasc o anumit valoare. Dac notmaceast valoare cu rezult c ceasurile fizice ale nodurilor din sistemul distribuit trebuieresincronizate la fiecare //2secunde.

Avnd n vedere cele spuse n paragraful de mai sus, n algoritmul lui Cristian maina care arereceptorul WWV va fi server de timp. Celelalte maini care au un drift de maxim , la fiecare //2secunde vor iniia cte o cerere ctre serverul de timp. Serverul de timp, imediat ce primete cererea, seactiveaz o ntrerupere i raspunde cu un mesaj coninnd timpul de referin CUTC.

Fig 2.2 Algoritmul Cristian pentru sincronizarea ceasurilor fizice

Algoritmul descris mai sus are dou probleme. Prima ar fi c pot exista cazuri n care CUTC estemai mic dect ceasul local de pe maina client care face cererea. n astfel de cazuri, timpul nu are voies fie dat napoi. De aceea, se prefer ca s se ncetineasc n mod voit ceasul fizic pe maina client.Acest lucru se poate face n modul urmtor. S zicem c pe maina client, cnd cristalul de quartzgenereaz o ntrerupere, se incrementeaz ceasul fizic cu valoarea X msec. Ca s se ncetineasc ceasuln mod voit, la fiecare ntrerupere se va incrementa ceasul cu Y

4momentul n care primete rspunsul de la server, (T1 T0 ). Clientul ar trebui s mai adauge la CUTCntrzierea de la server la client. n algoritmul lui Cristian se pornete de la premiza c ntrzierea va fijumtate din intervalul de timp msurat, deci (T1 T0 )/2. Exist reele n care mesajele de cerere o iaupe alt cale dect mesajele de rspuns. n aceste sisteme, metoda Cristian de sincronizare a ceasurilorfizice nu este recomandat. Pentru a mai mbunti estimarea ntrzierii de la server la client,algoritmul Cristian mai sugereaz s se fac mai multe msurtori (T1 T0 ) i s se fac media lor.ntr-un sistem centralizat, problema sincronizrii nodurilor este mult mai simpl. Dac procesul A arenevoie s afle timpul, face o cerere la sistemul de operare central i obine o valoare. Dac la unmoment ulterior procesul B dorete s afle timpul, procesul B va obine o valoare cel puin egal cuvaloarea primit de A.2.2 Algoritmul Berkley de sincronizare a ceasurilor fiziceUn al doilea exemplu de algoritm de sincronizare a ceasurilor fizice este reprezentat n figurile de maijos.

Fig 2.3 Prima etap n algoritmul Berkley

5Fig 2.4 A doua etap n algoritmul Berkley

Fig 2.5 A treia etap n algoritmul Berkley

Algortmul Berkley de sincronizare a ceasurilor fizice este reprezentat n cele trei figuri de mai sus.Acest algoritm se potrivete mai mult pentru sistemele distribuite n care nu exist nicio main cureceptor WWV, ci se dorete doar sincronizarea tuturor ceasurilor ntre ele, fr a se dori neaprat caceasurile s se potriveasc cu UTC.Spre deosebire de algoritmul Cristian, n care serverele stteau pasive i doar rspundeau la cereri, nalgoritmul Berkley lucrurile stau pe dos. Proiectantul sistemului distribuit este liber s aleag ce serverva folosi. n prima etap, descris n primul desen din cele trei de mai sus, serverul trimite un mesajctre toate mainile n care pune valoarea ceasului fizic local, de pe propria main. n a doua etap,reprezentat n a doua figur, fiecare main client rspunde la mesajul serverului cu cte un mesaj ncare spune cu ct difer ceasul local fa de ceasul serverului. De exemplu, maina Cl 1, are ceasul local3:25 i de aceea rspunde cu un mesaj n care pune un decalaj de +25 ntre propriul ceas i ceasulserverului. Maina Cl2 are ceasul 2:50 i trimite un mesaj n care scrie un decalaj de -10 ntre ceasulpropriu i ceasul serverului.Dup ce primete toate mesajele de la toate mainile client, maina server calculeaz media tuturorceasurilor din sistem i i seteaz ceasul local la valoarea medie. Apoi procesul se reia cu etapa nti.

62.3 Ceasuri LogiceS considerm un sistem distribuit cu mai multe procese care lucreaz n paralel. Pe fiecare

proces are loc o secven de evenimente. n funcie de sistemul distribuit considerat, un evenimentpoate fi execuia unui subprogram, sau chiar execuia unei instruciuni. De asemenea, i faptul c unproces trimite sau recepioneaz un mesaj se consider tot un eveniment. La prima vedere, se poatespune ca evenimentul a s-a petrecut naintea evenimentului b dac timpul fizic asociat evenimentului aeste mai mic dect timpul fizic asociat evenimentului b. Dac se folosee aceast metod de a ordonaevenimentele, atunci trebuie ca n sistemul distribuit s se foloseasc ceasuri fizice pe toate nodurile.Am vzut n paragrafele de mai sus c n sistemele distribuite, ceasurile fizice ale nodurilor, cu trecereatimpului, se desincronizeaz. De asemenea, am vzut c metodele de sincronizare a ceasurilor fizice auunele limitri i unele dezavantaje.

Pentru a evita problemele sincronizrii ceasurilor fizice, putem s folosim un alt mod de aordona evenimentele ntr-un sistem distribuit. n 1978 Leslie Lamport, n lucrarea sa [ 1 ] a introdus oalt metod pentru a ordona evenimentele ntr-un sistem distribuit. El susine c nu e neaprat necesarca ntr-un sistem distribuit s se foloseasc ceasuri fizice, ci e suficient ca toate nodurile s cad deacord asupra ordinii n care un eveniment s-a petrecut. Pentru aceasta, Lamport a introdus relaia decauzalitate (happened before), notat cu . Relaia ntr-un sistem distribuit trebuie ssatisfac urmtoarele trei condiii: Dac a i b sunt evenimente n acelai proces al sistemului distribuit i a are loc naintea lui b,

atunci ab. Dac a reprezint evenimentul de transmitere a unui mesaj pe un anumit nod, iar b este

evenimentul de recepie a aceluiai mesaj pe nodul destinaie, atunci ab. Dac ab i bc, atunci ac.

Dou evenimente a i b sunt concurente dac ab i ba.Este mai uor de neles relaia de , dac folosim o diagram spaiu-timp pentru a reprezentasistemul distribuit.

Fig 2.6 Diagram pentru reprezentarea unui sistem distribuitLiniile orizontale reprezint nodurile sau procesele din sistemul distribuit. Timpul fizic crete de

la stnga spre dreapta. Cu bulinue sunt reprezentate evenimentele care se petrec n sistemul distribuit.Cu sgeat sunt reprezentate mesajele de la un nod la altul. Se observ c pentru un mesaj, avemeveniment i la transmiterea mesajului de ctre nodul surs, ct i la recepia mesajului la noduldestinaie.

7Avnd n vedere definiia relaiei de happened before dat de Lamport i folosind i diagramadin figura de mai sus, putem spune c evenimentul a s-a petrecut naintea evenimentului b dac pediagrama reprezentat mai sus gsim un drum de la evenimentul a la evenimentul b mergnd doar pesgeile mesajelor si mergnd doar nainte. De exemplu, primul eveniment al nodului P1, s-a petrecutnaintea evenimentului al doilea al procesului P2, pentru c gsim pe diagram un drum de la primuleveniment la al doilea. n schimb, primul eveniment al procesului P3 i al doilea eveniment alprocesului P2 , nu putem spune care s-a ntmplat mai devreme i care mai trziu.

Acum se poate defini noiunea de ceas logic. Ceasul logic este o funcie C:H->T, unde H estemulimea tuturor evenimentelor din sistemul distribuit, iar T este mulimea tuturor valorilor numericepe care le poate lua un ceas logic. Funcia C asigneaz fiecrui eveniment din H un numr din mulimeaT. Vom nota funcia cu Ci(a), unde i este identificatorul procesului pe care are loc evenimentul, a esteevenimentul. Un astfel de ceas se poate implementa printr-un registru pe fiecare nod al sistemuluidistribuit. Acest regstru, spre deosebire de ceasurile fizice, nu se va incrementa la fiecare oscilaie acristalului de quartz, ci se va incrementa dup alte reguli. Pentru a putea folosi aceast tip de ceas logicla determinarea cauzalitii, trebuie respectat urmatoarea regul

Dac ab , atunci C(a)

8o Trimite mesajul mai departe

Fig 2.7 Exemplu de sincronizare folosind ceasuri scalare

Se observ c proprietatea de consisten slab este respectat: evenimentele a i b, )()( bCaCba .

Ceasurile logice scalare pot fi folosite pentru a ordona evenimentele n sistemele distribuite.Principala problem const n faptul c dou sau mai multe evenimente de pe procese diferite pot aveatampile de timp identice. De exemplu, n figura de mai sus al treilea eveniment al procesului P1 i aldoilea proces al evenimentului P2 au ceasuri scalare identice. De aceea, este nevoie de o regul care sdefineasc care eveniment s-a petrecut mai devreme. Putem defini tampila de timp a unui evenimentca un cuplu (t,i) n care t reprezint valoarea ceasului logic, iar i reprezint identitatea procesului undes-a petrecut evenimentul. Relaia de ordonare total pentru dou evenimente x i y, avnd tampilele detimp (h,i), respectiv (k,j) este definit n modul urmtor:

khyx sau h=k i i

9logice locale proprii fiecrui proces din sistemul distribuit. Acest vector va fi ataat i la mesajele de laun proces la altul ca i tampil de timp.

Procesul Pi folosete urmtoarele dou reguli pentru a-i corecta ceasul: R1 nainte de execuia unui eveniment intern,

divtivt ii ][][(2.6)

R2 Fiecare mesaj are ataat un timestamp cu ceasul logic vectorial al procesului caretrimite. La recpia acestul mesaj, procesul pi execut urmtoarea suit de aciuni

o i actualizeaz ceasul logic vectorial1 k n, vti[k] =max (vti[k], vt[k])(2.7)

o Execut regula R1o Trimite mesajul mai departen figura de mai jos este reprezentat metoda vectorial:

Fig 2.8 Exemplu de sincronizare folosind ceasuri vectorialePentru a compara dou ceasuri vectoriale se folosesc relaiile

xvkvh : ][][ xvkxvh (2.8)xvkvh : ][][ xvkxvh (2.9)vkvhvkvh si x : ][][ xvkxvh (2.10)

)(!)(!|| vhvkivkvhvkvh (2.11)

Am scris mai sus ca relaia introduce o ordonare parial a mulimii de evenimentecare sunt produse de un sistem distribuit. Dac evenimentele dintr-un sistem distribuit suntmarcate cu tampile de timp folosind ceasuri vectoriale, avem urmtoarea proprietateinteresant. Dac dou evenimente x i y care au timestaps vh respectiv vk, atunci

vkvhyx (2.12)

10

vkvhyx |||| (2.13)

Se poate observa c exist un izomorfism ntre mulimea de evenimente parial ordonateprodus de un sistem distribuit i calculul distribuit al tampilelor de timp asociate. Aceasta esteo proprietate foarte puternic a sistemelor de ceasuri logice vectoriale.

Dac se cunoate procesul care a generat un anumit eveniment, testul pentru a comparadou tampile de timp poate fi simplificat n felul urmtor. Daca dou evenimente x i y s-aupetrecut la procesele pi respectiv pj, avnd tampilele de timp vh i vk, atunci

][][ ivkivhyx (2.14)

][][][][|| jvkjvhivkivhyx (2.15)

Sistemul cu ceasuri logice vectoriale are proprietatea de consisten puternic. Astfel,dac se examineaz tampila de timp pentru orice dou mesaje, putem determina dacevenimentele au o relaie de cauzalitate.

Folosind ceasurile logice vectoriale se poate determina numrul de evenimente carepreced un anumit eveniment cu o anumit tampil de timp. Pentru procesul pi, numrul vti[i]reprezint numrul de evenimente care s-au petrecut in cadrul procesului pi pn n acelmoment de timp. Dac un eveniment e are tampila de timp vh, vh[j] reprezint numrul deevenimente executate de ctre procesul pi care preced evenimentul e. Deci, vh[j]-1 reprezintnumrul total de evenimente care preced evenimentul e i care sunt n relaie de cauzalitate cu edin cadrul sistemului distribuit.

2.6 Metoda de sincronizare a ceasurilor logice folosind ceasuri matricialentr-un sistem distribuit cu ceasuri logice matriciale, timpul este reprezentat de o mulime de

matrici de dimensiune n x n cu elemente avnd valori ntregi ne-negative. Un proces pi reine o matricemti[1,...n,1,..n] unde:

mti[i,i] reprezint ceasul logic al procesului pi i urmrete progresul calculriiceasului logic local la procesul pi.

mti[i,j] reprezint ceea ce procesul pi tie despre valoarea ceasului local al procesuluipj.

mti[j,k] reprezint ceea ce procesul pi tie c procesul pj tie despre valoarea ceasuluilocal al procesului pk.

ntreaga matrice mti reprezint imaginea local a procesului pi asupra timpului logic global.tampila de timp care va fi ataat la un mesaj va avea ataat matricea care reprezint ceasul logic alevenimentului de pe procesul care trimite mesajul.

Procesul pi folosete urmtoarele reguli pentru a face corecie de ceas: R1 nainte de execuia unui eveniment, procesul pi face urmatoarea corecie de ceas

diimtiimt ii ],[],[ , d>0(2.16)

11

R2 Fiecare mesaj are ataat timpul logic matricial mt. Cnd procesul pi recepioneaz mesajul(m, mt) de la procesul pj, pi efectueaz urmtoarea suit de aciuni

o i incrementeaz ceasul logic astfel 1 k n : mti[i,k] = max( mti[i,k], mt[j,k] )(2.17)adic i actualizeaz rndul mti[i,*] cu rndul corespunztor procesului pj dintampila de timp a mesajului pe care l recepioneaz. 1 k, l n : mti[k,l] = max( mti[k,l], mt[k,l] )

(2.18)o Execut R1o Trimite messajul m mai departe

Ceasurile logice matriciale au toate proprietile pe care le au i ceasurile logice vectoriale. nplus, ceasurile matriciale mai au i urmtoarea proprietate

Min (mti[k,l]) t implic faptul c procesul pi tie c orice alt proces pk tie c ceasul local alprocesului pls local time a ajuns pn la valoarea t.

Fig 2.9 Exemplu de sincronizare folosind ceasuri matriciale

2.7. Algoritmul Birman Schiper Stephenson (BSS)Ceea ce este de dorit ntr-un sistem distribuit este ordonarea mesajelor dup cauzalitate. Pe scurt,aceasta nseamn c dac avem dou mesaje, M1 si M2, i timpul la care a fost transmis M1 este maimic dect timpul la care a fost transmis M2, atunci i timpul la care este recpionat M1 trebuie s fiemai mic dect M2.

dac Send(M1)Send(M2)Rec(M1)Rec(M2)(2.19)

12

Din pcate, canalele de comunicaie din sistemul distribuit nu pot oferi aceast garanie. Din cauzancrcrii reelei, sau din cauza rutelor diferite pe care le pot lua pachetele, nu se poate garanta faptul ctimpul la care va fi recepionat primul mesaj va fi mai devreme dect timpul la care este recepionat aldoilea mesaj.n figura de mai jos este reprezentat un caz n care ordonarea mesajelor dup cauzalitate este ne-respectat

Fig 2.10 Exemplu n care ordonarea mesajelor dup cauzalitate nu este respectat

n figura de mai sus se observ c mesajul M1 este trimis primul, dar din cauza canalului decomunicaie, el ajunge la nodul destinaie ultimul. ntre timp. mesajul M3, ajunge mai devreme ladestinaie. Se vede pe figur c mesajul Send(M1)Send(M2). De asemenea, Send(M2)Rec(M2).Rec(M2)Send(M3) i Send(M3)Rec(M3)Algoritmul BSS face ca ntr-un sistem distribuit, chiar dac reeaua sau canalul de comunicaie producntrzieri de mesaje, totui s se respecte ordonarea mesajelor dup cauzalitate.Totui, pe lng celelalte condiii, algoritmul BSS se poate aplica doar la mesajele de tip difuzare. Decipentru ca algoritmul s i fac efectul, trebuie ca un mesaj s fie trimis la toate celelalte noduri dinsistemul distribuit.Algoritmul BSS cere ca pasul cu care se incrementeaz ceasurile vectoriale s fie 1. n rndurileurmtoare este exemplificat algoritmul:

1. Fiecare proces Pi menine un ceas vectorial2. nainte de a difuza un mesaj m ctre toate celelalte noduri, un nod Pi i incrementeaz ceasul

vectorial local vti[i] i ataeaz noul ceas vti[i] ca o tampil de timp a mesajului. Vom notatampila de timp a mesajului m cu vtm.

3. Cnd nodul Pj recepioneaz mesajul m, nti verific urmtoarele condiii:

13

a. vtj[i]=vtm[i]-1, ceea ce nseamn c toate mesaje anterioare trimise de ctre nodul Pi aufost recepionate de ctre Pj

b. vtj[k] vtm[k], },...2,1{ nk k i, ceea ce nseamn c nodul Pj a recepionat toatecelelalte mesaje care au trecut pe la Pi (dar nu au fost emise de ctre Pi).

4. Dac una dintre cele dou condiii nu e ndeplinit, nodul Pj pune mesajul m ntr-o coad i vatesta tot aceste dou condiii mai trziu

5. Dac ambele condiii sunt ndeplinite, atunci procesul Pj difuzeaz mesajul m ctre toatecelelalte noduri din sistemul distribuit, mai puin Pi.

3.2 Specificaii ale simulatoruluin figura de mai jos este reprezentat o diagram FSM ce cuprinde arhitectura general a programului.Cnd se pornete programul, utilizatorul ajunge n fereastra cu datele pentru simulare.

TINE MINTE SA UPDATEZI SCHEMA

14

Completaremanual

nchidefereastra

nchidefereastra

nchidefereastra

nchidefereastra

Schimb tabul Schimb tabul Schimb tabul

Completaremanual

nchidefereastra

START

DateSimulare

Completarealeatorie

Scrie fiierulMatrixEventIn.txt

Calcul matrice timp

Afiarearezultatelor

Analizancrcrii

Generarerezultate

Afiarerezultate 3metode

Afiarerezultate 1metod

Comparaieceasuri fizice

Completaremanual

Completarealeatorie

Scrie fiierulMatrixEventIn.txt

Calcul farasincronizare

Calcul cusincronizare

Afiarearezultatelor

BSS datesimulare

ScrieMatrixEventInBSS.txt

Bloc calculmatrice timp

Afiarearezultatelor

Fig 3.10 Diagram FSM cuarhitectura general a programului

Calcul matriciauxiliare

15

n figura de mai sus este reprezentat ca o diagram a unei maini cu stri finite, arhitectura de baz aprogramului.n blocul Fereastr simulare utilizatorul poate selecta ce metod de sincronizare dorete s simuleze.Tot n aceeai fereastr, utilizatorul trebuie s defineasc secvena de evenimente care se vor petrece pefiecare nod al sistemului distribuit. Pentru aceasta, el va alege nti numrul de noduri din sistemuldistribuit, i apoi numrul de evenimente care vor fi simulate. Fiind alese aceste dimensiuni, n fereastrade simulare utilizatorul trebuie s dea ca date de intrare sirul evenimentelor care se vor petrece pefiecare nod al sistemului distribuit.Pentru cazul n care numrul de noduri din sistemul distribuit este mare i utilizatorul trebuie scompleteze un ir de evenimente prea vast, simulatorul va avea i opiunea de a completa aleator irulde evenimente pe fiecare nod. De acest lucru se ocupa blocul Completare aleatorie a matricei dinfigura de mai sus.Dup ce utilizatorul a completat manual sau aleator i irul de evenimente, simulatorul transfer toateaceste date ctre blocul Calcul matrice timp. Acest bloc, n funcie de metoda selectat, n funcie denumrul de noduri i de evenimente, i n funcie de irul particular de evenimente care este dat spresimulare, calculeaz valorile ceasurilor logice asociate fiecrui eveniment de pe fiecare nod i letranfer mai departe ctre urmtorul bloc.Blocul Afiare rezultate preia att valorile ceasurilor logice pentru fiecare eveniment, ct i irulevenimentelor de pe fiecare nod i afieaz pe ecran o diagram n care fiecrui eveniment din irul deevenimente i corespunde o valoare a ceasului logic calculat de blocul Calcul matrice timp. Acestevalori vor fi afiate pe ecran ntr-un mod ct mai uor de citit i de neles pentru utilizator.Simulatorul va avea i o seciune n care se va face studiul ncrcrii suplimentare a reelei datoratfolosirii fiecrei dintre cele trei metode de sincronizare a ceasurilor logice.Blocul Buton Generare rezultate se va folosi de mecanismul de generare aletorie a sevenei deevenimente pe fiecare nod i va genera aleator un numr suficient de mare de evenimente. Apoi cuajutorul unei metode din mecanismul de calcul al rezultatelor, se va msura ncrcarea suplimentarintrodus de folosirea metodei respective de sincronizare. Metodele de sincronizare a ceasurilor logicestudiate n lucrarea de fa introduc o ncrcare suplimentar a reelei prin faptul c la fiecare mesajtransmis de la un nod la altul, se ataeaz i o tampil de timp care va conine valoarea ceasului logical nodului de la emisie, la momentul trimiterii mesajului. Blocul Buton Generare rezultate vaparcurge sevena de evenimente generat aleator i va calcula o ncrcare la fiecare tact logic, i oncrcare medie.Urmtoarele dou blocuri, Generare ncrcare toate cele trei metode i Generare ncrcare o singurmetod vor prelua datele calculate de blocul anterior i vor afia pe ecran grafice cu ncrcarea reelei.n funcie de ce selecteaz utilizatorul, se poate afia pe acelai grafic o comparaie ntre ncrcareareelei datorat fiecrei dintre cele trei metode de sincronizare, sau se poate afia pe ecran un grafic carecuprinde incrcarea datorat unei singure metode, dar s fie afiate mai multe detalii, cum ar fi evoluiancrcrii la fiecare tact de timp, sau evoluia medie a ncrcrii.Dac utilizatorul trece n tabul pentru comparaie ntre situaia cu sincronizare Lamport i situaia ncare doar avem ceasuri fizice, situaia este reprezentat de blocul Comparaie ceasuri fizice. Aici esteo situaie similar cu cea prezentat n blocul Date simulare de la tabul de simulare. Utilizatorul poateda manual secvena de evenimente de pe fiecare nod al sistemului distribuit sau poate alege ca secvenade evenimente s fie completat aleator de ctre simulator. O diferen important fa de tabul desimulare este aceea c n tabul de comparaie utilizatorul nu mai poate selecta metoda scalar,vectorial sau matricial. Metoda folosit va fi implicit metoda scalar. O alt deosebire este aceea cutilizatorul va putea regla perioada ceasului fizic pe fiecare nod al sistemului distribuit.Dup ce datele date de ctre utilizator sunt scrise n fiierul text, spre deosebire de cazul din tabulpentru simulare, aici n tabul de comparaie, aceleai date de intrare sunt prelucrate de dou blocuri de

16

calcul. Blocul Calcul fr sincronizare calculeaz ceasurile scalare pentri fiecare eveniment fr afolosi algoritmul Lamport de sincronizare a ceasurilor. Ceasurile fizice pe fiecare nod vor progresadup perioada stabilit de utilizator. Blocul Calcul cu sincronizare va calcula ceasurile ataatefiecrui eveniment folosing regulile Lamport de sincronizare.Blocul Afiarea rezultatelor va afia pe ecran n paralel cele dou seturi de valori corespunztoaresecvenei de evenimente pentru care s-a realizat simularea. Rezultatele se vor afia pe o diagram astfelnct s se poat citi i nelege uor de ctre utilizator.Ultima seciune disponibil va fi implementarea algoritmului Birman-Schiper-Stephenson. BloculBSS Date simulare, ca i n cazul taburilor de comparaie si de simulare, va primi datele de intrarede la utilizator. Spre deosebire de celelalte cazuri, nu va mai exista posibilitatea ca simulatorul scompleteze automat secvena de evenimente. De asemenea, utilizatorul va putea s regleze intrzierea cu care un mesaj va ajunge la nodul destinaie. n cazul tabului BSS, utilizatorul nu vaputea schimba metoda de sincronizare, ci ea va fi setat implicit la metoda vectorial.Blocul de calcul preia datele de intrare de la blocul anterior i calculeaz ceasurile ataate fiecruieveniment i eventualele informaii suplimentare necesare afiarii datelor.Blocul Afiarea rezultatelor va prelua rezultatele calculate de blocul anterior i va afia pe ecran listaeveniementelor simulate i rezultatele ceasurilor vectoriale ataate fiecrui eveniment. De asemenea, vaafia pe ecran i dac mesajul recepionat de un nod ndeplinete condiiile impuse de algoritmulBirman-Schiper-Stephenson, i atunci este trimis mai departe, sau dac nu ndeplinete este pus ntr-ocoad.3.3. Detalierea blocurilor din arhitectura general a simulatoruluin paragraful de mai sus am spus c simulatorul va putea genera secvena de evenimente pentru fiecarenod ntr-un mod aleator.n diagrama de mai jos este prezentat algoritmul de generare aleatoare a matricei cu secvena deevenimente pentru fiecare nod al sistemului distribuit. Scopul acestui algoritm este de a genera aleatorfiecare coloan astfel nct s nu fie cazuri n care pentru un nod s existe mai multe evenimente naceeai perioad de ceas

3.3.1 Blocul de generare automat a secvenei de evenimente de la intrareGenerarea matricei se face pe coloane. Se ia prima coloan, se genereaz n numere aleatoare

pentru coloana respectiv (n fiind numrul de noduri din sistemul distribuit), iar apoi se valideaz irul.Practic, se valideaz s nu existe mesaj de la nodul i tot la nodul i. Apoi se incearc ca pentru fiecarenod, s nu existe mai multe evenimente simultane. Pentru aceasta, se folosete un ir numit dirty dedimensiune n. De fiecare dat cnd se produce un eveniment pentru un nod i, se incrementeazelementul dirty[i] . Apoi se verific dac vreun element al lui dirty este mai mare dect 1. Dac da,atunci nseamn c exist dou evenimente simultane. Dac nu, atunci nseamn c numerele aleatoarerespect validrile i se trece la urmtoarea coloan a matricei.

17.

Da

Da

Da

Da

Fig 3.11 Diagrama pentru algoritmul de generare aleatoare aMatricei de secven de evenimente

Generare a coloanei c[] cu numerealeatorii

Initializarea vectorului den elemente dirty[] cu 0

i = 0

c[i] =ev intern

dirty[i]++

c[i]= mesajde la noduln1 la n2

dirty [i]>=2

Se trece lacoloanaurmatoare

i >= n?

dirty[n1] ++dirty[n2]++

i + +

i = 0

i >= n?

i + + Re-genereazaceeai col

Fig4.2Cumpoateutilizatorul saleagametoda inumaruldeliniii decoloanealematricei

18

Fereastra care preia datele de la utilizator i fereastra care afieaz ceasurile calculate, suntdefinite pe dou fire de execuie. ntre cele dou fire de execuie am aplicat modelul de productor->consumator pentru sincronizarea lor. Firul de execuie de productor, preia datele de la utilizator i lescrie n fiierul MatrixEventIn.txt. Dup ce termin de completat fiierul, productorul i trimite unmesaj de sincronizare consumatorului care citete datele din MatrixEventIn.txt i calculeaz ceasurilelogice, apoi le afieaz pe ecran. Dup ce utilizatorul inchide fereastra n care se afieaz rezultatele,procesul de pe firul de execuie consumator ateapt de la productor un alt mesaj de sincronizare ca stie cnd s-au scris n fiierul MatrixEventIn.txt date noi.

Fig 3.12 Modelul de productor-consumator folosit

3.3.2. Blocul de calcul al ceasurilor pentru Metoda Scalarn figura de mai sus este afiat un exemplu de fiier de intrare cu metoda Scalar. Primul lucru

pe care l face blocul Calcul matrice timp este acela c se uit la al treilea numr de pe prima liniedin MatrixEventIn.txt n funcie de acest numr, va aplica diveri algoritmi pentru a calcula matricea deTimp pentru fiecare eveniment.

n continuare vom nota matricea de intrare cu evenimente mEv1[][] si matricea timp cumT1[][]. n cazul metodei scalare elementele care constituie matricea de timp vor fi scalari. Elementulde coordonate mT1[i][j] reprezint ceasul vectorial corespunztor evenimentului mEv1[i][j] dinmatricea de evenimente. Pentru a putea lucra mai uor, s-a lucrat cu matricea de evenimente si matriceade timp ambele transpuse. Astfel,

TmEvmEv 1TmTmT 1

(3.1)n cadrul blocului Calcul matrice timp vom lucra cu mT i mEv transpuse. Deci pentru mEv, pe linia1 vor fi evenimentele care au loc simultan n timpul primei perioade de ceas, pe linia 2 vor fievenimentele care au loc simultan n timpul celei de-a doua perioade de ceas, amd.

Productor Consumator

MatrixEventIn.txtScrie n Citete din

Mesaj sincronizare

19

Un alt amnunt notabil este urmtorul. Matricea de evenimente, mEv, se completeaz ncepndde la indicii i=0 i j = 0, dar matricea de ceasuri are o linie n plus. Prima linie, cea cu indicii i=0, nu vafi folosit n calcule i nici nu va fi afiat n fereastra cu afiarea rezultatelor. Deci liniile care seafieaz la sfrit pentru matricea de ceasuri sunt cele ncepnd de la indicii i=1. De aceea, n diagramade mai jos, bucla for cu care se face parcurgerea matricelor ncepe de la i = 1.

n figura de mai jos este reprezentat diagrama blocului de Calcul matrice timp. Acest blocface parte din gruparea blocurilor de pe linia de execuie Consumator discutat mai sus. De aceea,dup ce primete mesajul de sincronizare, se citesc valorile din fiierul MatrixEventIn.txt i sestocheaz n matricea mEv1[ ] [ ]. Dup cum spuneam, ca s se poat parcurge mai uor, n urmtoareaetap se transpune matricea de evenimente

TmEvmEv 1(3.2)

Dac mai sus am spus c elementul din matricea de timp mT1[i0][j0] reprezint ceasul Lamportcorespunztor evenimentului mEv1[i0][j0], aceeai proprietate se pstreaz i pentru matriciletranspuse, adic elementul din mT[i0][j0] reprezint ceasul Lamport corespunztor evenimentuluimEv[i0][j0].

n urmtorul pas se iniializeaz matricea mT cu zero.0]][[ jimT , nrColi ,0 , nrLinj ,0

(3.3)nrLin i nrCol se citesc din prima linie a fiierului MatrixEventIn.txt i reprezint numrul de linii i decoloane pentru matricea mEv1. Dar, dup cum am spus, lucrm cu matricea transpus i de aceea i, caree primul indice e de la 0 la nrCol i j, al doilea indice e de la 0 la nrLin.

Dup stabilirea limitelor se ncepe parcurgerea matricelor. Aici este foarte important faptul cmatricea mEv se parcurge ncepnd de la prima linie, cea de index i=0, pe cnd matricea mT separcurge ncepnd de la a doua linie, cea de index i=1. De aceea, n buclele for, indicele i ncepe de lavaloarea 1, pe cnd indicele j ncepe de la valoarea 0. Pentru c matricea mEv se parcurge de la linia0, din aceast cauz mEv se parcurge in bucla for cu mEv[i-1][j],iar mT cu mT[i][j].

n bucla for se ia elementul curent din mEv i se verific ce fel de eveniment este. Dac este uneveniment neutru se face urmtorul lucru. Se ia valoarea de la linia precedent din mT i se stocheaz lalinia curent. Din aceast cauz matricea mT are prima linie, cea de indice i=0, n plus fa de celelaltematrici. Pentru c n algoritmul implementat de mine n cazul evenimentului neutru, ceasul logicramne la valoarea anteriar. De aceea trebuie ca matricea mT s ia valoarea de pe linia precedent. Deaceea ncepe bucla for cu i=1, pentru ca atunci cnd iau valoarea ceasului precedent, adic cea de lalinia i-1, s gsesc valoarea de la linia i=0

20

Da

DaDa

Da

Da

Citete din MatrixEventIn.txtn mEv1[ ][ ]

mEv [ ][ ] = mEv1[ ][ ] transpus

mT[ ] [ ] =0

mEv [i-1][j]=i?

mT [i] [j] = mT[i-1][j] +stepmEv [i-1][j]=n ?

i = 1

mT[i][j]nCol

j>nLinj + +

i + +

j = 0

Urmtorul blocAfiarea Rez

Fig 3.13 Diagram calcul metodaScalar

21

for (i = 1; i

22

3.3.3 Blocul de calcul pentru Metoda VectorialPentru metoda vectorial principala diferen este datorat faptului c matricea de timp nu va mai fialctuit din scalari, ci va fi alctuit din vectori. n cazul metodei vectoriale, evenimentului de indice ii j din matricea mEv i corespunde elementul de indice i i j din matricea mTv, cu meniunea celementul de indice i i j din matricea de timp va fi un vector cu nLin elemente, unde nLin este numrulde noduri din sistemul distribuit.

Un ir de genul v[10] este usor de inchipuit, o matrice este de asemenea uor de reprezentatm[10][10], dar un sir multidimensional este puin mai greu de neles. S considerm exemplul de maijos:

i j 0 1 20 0 0 01 1 0 02 2 0 03 3 3 04 4 3 05 5 5 06 5 5 0

i j 0 1 20 0 0 01 0 0 02 0 0 03 0 1 04 0 1 05 0 2 06 0 3 0

i j 0 1 20 0 0 01 1 0 12 1 0 13 1 1 14 1 1 25 1 1 26 1 1 3

k = 0 k = 1 k = 2Fig 3.14 Exemplu de matrice mTv[][][] cu trei dimensiuni folosit la metoda Vectorial

n tabelul de mai sus este reprezentat matricea mTv aa cum este ea calculat de blocul Calculmatrice timp pentru cazul n care avem selectat metoda vectorial. Matricea de intraremEv1[][]pentru exemplul de mai sus este urmtoarea:

n i 2 i 2 nn n n n n i1 n n i n i

Fig 3.15 mEv1 pentru exemplul de mai susPrin transpunerea ei obinem matricea mEv[][]:

i j 0 1 20 n n 11 i n n2 2 n n3 i n i4 2 n n

Fig 3.16 Exemplu de matrice de intrare mEvAvnd in vedere matricea mTv[][][] cu trei dimensiuni din figura de mai sus, putem explica mai usormodul de indexare al elementelor. Pentru o matrice obinuit, cu 2 dimensiuni A[i][j], i reprezintindicele liniei, j reprezint indicele coloanei. Pentru cazul n care avem trei dimensiuni, mTv[k][i][j],putem spune ca avem k pagini, fiecare cu cte o matrice care are i linii i j coloane. Tabelul din figurade mai sus ne ajut mai uor s gasim valoare mTv[k0][i0][j0] pentru k0, i0, j0 valori particulare. Deexemplu: mTv[0][3][2] = 0, mTv[1][6][1]=3, mTv[2][6][3]=3.Folosindu-ne de conceptul de iruri multidimensionale expus mai sus, putem stoca ceasurile vectorialepentru evenimente in metoda Vectorial de sincronizare a ceasurilor logice ntr-o matrice cu treidimensiuni. Dac rulm exemplul cu matricea de intrare de mai sus in simulator i alegem metodaVectorial, vom obine rezultatele urmtoare:

23

Fig 3.17 Rezultate pentru metoda Vectorial folosite pentru a explica cum se folosete matricea multidimensionalmTv[][][]

Ceasurile vectoriale ataate fiecrui eveniment din figura de mai sus sunt stocate in matricea mTv[][][]de mai sus. Pe acest exemplu, putem face proba. De exemplu, pentru evenimentul intern de la nceputulcelei de-a doua perioade de ceas avem afiat ceasul [2 0 1] . Vom vedea de unde i ia programul desimulare datele din matricea multidimensional mTv[][][].Pentru a gsi ceasul vectorial pentru un anumit eveniment, trebuie s gsim coordonatele pentru celetrei numere.Dac lucrm cu matricile de timp i de evenimente ambele transpuse, atunci pe linia i va corespundeperioadei de ceas n care se petrece evenimentul, iar coloana j va reprezenta numrul nodului pe care sepetrece evenimentul.De asemenea, pentru matricea de timp reprezentat n figura de mai sus, se poate observa c la linia i=0toate valorile sunt 0. Linia i=0 nu este afiat la rezultate, este doar pentru iniializare i pentruuniformitatea algoritmului de calcul. Linia i=1 corespunde datelor de la prima perioad de ceas, i=2pentru datele de la a doua perioad de ceas, amd. Pe de alt parte, nu avem i coloane n plus, decitoate coloanele sunt afiate la rezultate. Coloana cu j=0 corespunde nodului 1, coloana cu j=0corespunde nodului 2, amd.Primul eveniment intern al procesului P1 se petrece n timpul celei de-a doua perioade de ceas, decii = 2. Dac este vorba de primul proces din sistemul distribuit atunci nseamn c j = 0. Am identificatcine e i, cine e j a mai rmas k. Ceasul vectorial pentru fiecare eveniment conine n numere, unde n estenumrul de noduri din sistemul distribuit. Prima valoare a ceasului vectorial se va afla la coeficientulk=0, a doua la poziia k=1 n matricea mTv[][][], iar a treia valoarea a ceasului vectorial se va afla laindicele k=2.n cazul nostru, pentru a gsi ceasul logic pentru primul eveniment intern al procesului P1, afim dinmatricea de timp valorile aflate la indicii:

1,0 nk , i = 2 (perioada de ceas la care se petrece), j = 0 (numrul nodului 1 )(3.6)

Avnd n vedere explicaiile date mai sus cu modul de folosire a matricei multidimensionale mTv[][][],algortimul de calcul al acestei matrici pentru metoda vectorial este mai uor de neles.

24

Nu

Nu

Nu

Da

Da

Da

Nu

i=1

i > nLin

mTv[k][i][jj]=max(mTv[k][i-1][jj], mTv[k][i][jj])nLinjjk ,0,

j=0

j > nCol

mEv[i-1][j]= ev int

mTv[j][i][j] ++

mEv[i-1][j]=mj

mTv[j][i][j]++

mTv[k][i][msj]=max(mTv[k][i][msj], mTv[k][i][j]nLink ,0

mTv[msj][i][msj]++

j++

i++ Fig 3.18 Diagram calculMetoda Vectorial

25

for (i = 1; i

26

n concluzie, pentru metoda Matricial, unui eveniment de coordonate i0 i j0 din matricea deEvenimente mEv[i][j], i corespund n2 valori din matricea mTm[k][i][j], unde

2,0 nk , i=i0, j=j0(3.7)

[0][0][0]=0 [1][0][0]=0 [2][0][0]=0 [3][0][0]=0 [4][0][0]=0 [5][0][0]=0 [6][0][0]=0 [7][0][0]=0 [8][0][0]=0[0][0][1]=0 [1][0][1]=0 [2][0][1]=0 [3][0][1]=0 [4][0][1]=0 [5][0][1]=0 [6][0][1]=0 [7][0][1]=0 [8][0][1]=0[0][0][2]=0 [1][0][2]=0 [2][0][2]=0 [3][0][2]=0 [4][0][2]=0 [5][0][2]=0 [6][0][2]=0 [7][0][2]=0 [8][0][2]=0[0][1][0]=0 [1][1][0]=0 [2][1][0]=0 [3][1][0]=0 [4][1][0]=0 [5][1][0]=0 [6][1][0]=0 [7][1][0]=0 [8][1][0]=0[0][1][1]=0 [1][1][1]=0 [2][1][1]=0 [3][1][1]=0 [4][1][1]=1 [5][1][1]=0 [6][1][1]=0 [7][1][1]=0 [8][1][1]=0[0][1][2]=0 [1][1][2]=0 [2][1][2]=0 [3][1][2]=0 [4][1][2]=0 [5][1][2]=0 [6][1][2]=0 [7][1][2]=0 [8][1][2]=1[0][2][0]=1 [1][2][0]=0 [2][2][0]=0 [3][2][0]=0 [4][2][0]=0 [5][2][0]=0 [6][2][0]=0 [7][2][0]=0 [8][2][0]=0[0][2][1]=0 [1][2][1]=0 [2][2][1]=0 [3][2][1]=0 [4][2][1]=1 [5][2][1]=0 [6][2][1]=0 [7][2][1]=0 [8][2][1]=0[0][2][2]=1 [1][2][2]=0 [2][2][2]=0 [3][2][2]=0 [4][2][2]=0 [5][2][2]=0 [6][2][2]=1 [7][2][2]=0 [8][2][2]=2[0][3][0]=2 [1][3][0]=2 [2][3][0]=0 [3][3][0]=0 [4][3][0]=2 [5][3][0]=0 [6][3][0]=0 [7][3][0]=0 [8][3][0]=0[0][3][1]=0 [1][3][1]=0 [2][3][1]=0 [3][3][1]=0 [4][3][1]=2 [5][3][1]=0 [6][3][1]=0 [7][3][1]=0 [8][3][1]=0[0][3][2]=1 [1][3][2]=0 [2][3][2]=0 [3][3][2]=0 [4][3][2]=0 [5][3][2]=0 [6][3][2]=1 [7][3][2]=0 [8][3][2]=3[0][4][0]=3 [1][4][0]=2 [2][4][0]=0 [3][4][0]=0 [4][4][0]=2 [5][4][0]=0 [6][4][0]=0 [7][4][0]=0 [8][4][0]=0[0][4][1]=0 [1][4][1]=0 [2][4][1]=0 [3][4][1]=0 [4][4][1]=3 [5][4][1]=0 [6][4][1]=0 [7][4][1]=0 [8][4][1]=0[0][4][2]=1 [1][4][2]=0 [2][4][2]=0 [3][4][2]=0 [4][4][2]=0 [5][4][2]=0 [6][4][2]=1 [7][4][2]=0 [8][4][2]=3[0][5][0]=4 [1][5][0]=2 [2][5][0]=4 [3][5][0]=0 [4][5][0]=2 [5][5][0]=0 [6][5][0]=1 [7][5][0]=0 [8][5][0]=4[0][5][1]=0 [1][5][1]=0 [2][5][1]=0 [3][5][1]=6 [4][5][1]=3 [5][5][1]=0 [6][5][1]=0 [7][5][1]=0 [8][5][1]=0[0][5][2]=1 [1][5][2]=0 [2][5][2]=0 [3][5][2]=0 [4][5][2]=0 [5][5][2]=0 [6][5][2]=1 [7][5][2]=0 [8][5][2]=4[0][6][0]=5 [1][6][0]=2 [2][6][0]=4 [3][6][0]=0 [4][6][0]=2 [5][6][0]=0 [6][6][0]=1 [7][6][0]=0 [8][6][0]=4[0][6][1]=0 [1][6][1]=0 [2][6][1]=0 [3][6][1]=6 [4][6][1]=3 [5][6][1]=0 [6][6][1]=0 [7][6][1]=0 [8][6][1]=0[0][6][2]=5 [1][6][2]=2 [2][6][2]=4 [3][6][2]=0 [4][6][2]=2 [5][6][2]=0 [6][6][2]=5 [7][6][2]=2 [8][6][2]=5

Fig 3.19 Exemplu de matrice de timp pentru metoda Matricial

n exemplul de mai sus avem calculat matricea de timp pentru o matrice de intrare de forma:n 3 n i n 3i n 1 i n ni n i n 1 n

Simulatorul va afia urmtoarele rezultate:

27

Fig 3.20 Exemplu de rezultate pentru metoda MatricialSe poate observa c pentru fiecare eveniment avem afiate 9 valori sub form de matrice. De exemplu,pentru ultimul eveniment al nodului P3, trebuie s scoatem elementele mTm[k][6][2], 8,0k . Sepoate verifica faptul c toate elementele din matricea de timp corespund cu valorile ceasurilor afiate peecran.Diagrama logic pentru calculul matricei de timp n cazul metodei Matriciale este afiat mai jos:Pentru c, luat n detaliu, diagrama logic pentru metoda Matricial este mai complicat, am preferats pun pe schema logic doar o descriere general a blocurilor urmnd ca mai trziu s detaliez rolulfiecrui bloc.

28

Da

Da

Da

Da

e[i-1][j]= i

mTm[k][i][j] = mTm[k][i-1][j]Linnk ,0 , nLinj ,0

incrementceas localmTi[i,i]

e[i-1][j]=m

increment ceas local alnodului surs

completez TS mesaj

actualizez matricea lanodul destinaie

incrementez ceas local noddestinaie

i=0

j=0

i>nCol

j>nLin

i + +STOP

Fig 3.21 Diagramalogic pentrumetoda Matricial

29

n blocul cel mai de sus, se copiaz toate valorile ceasurilor vectoriale de la momentul de timp i-1 lamomentul curent, i. Acest pas este necesar deoarece, mai trziu, n cazul unui mesaj, trebuie sacomparm valoarea ceasului local cu cea a tampilei de timp. Daca nu am fi fcut acest pas, la ceasullocal al nodului de recepie, pentru momentul de timp i, ar fi fost o valoare nedefinit sau valoarea 0.Urmtoarele blocuri logice vor s reprezinte dou bucle for folosite pentru a parcurge matricea deevenimente mEv[][]. Reamimtim faptul c i n cazul metodei Matriciale, ca i n cazul metodelorprecedente, lucrm cu matricea de timp i de evenimente transpus, deci, cu ajutorul buclelor for vomparcurge matricea de evenimente avnd pe linii momentele de timp i pe coloane nodurile.Dac evenimentul curent este un eveniment intern, atunci se incrementeaz ceasul scalar local pentrunodul la care se petrece evenimentul. Reamintim faptul c, pentru nodul i n cazul metodei matriciale,ceasul logic pentru nodul i este o matrice de dimensiunea n x n, unde n este numrul total de noduri.Pentru nodul i, al i-lea element din cadrul liniei i din ceasul matricial corespunztor acestui nodreprezint ceasul local. Al j-lea element din cadrul liniei i reprezint estimarea nodului i asupra a cteste ceasul logic scalar pentru nodul j. De asemenea, tot pentru ceasul matricial de pe nodul i, celelaltevalori scalare de ordinul k de pe alte linii ji reprezint ct tie nodul i c ar ti nodul j c este ceasullocal scalar pe nodul k.Pentru exemplul numeric din figura de mai sus, se observ c la final, nodul P3 are ceasul matricial

525020425

Fig 3.22 Exemplu de ceas matricial la nodul P3Putem spune c ceasul scalar local pentru nodul P3 este valorea m[3,3]=5. Restul valorilor de pe linia a3-a reprezint estimri. m[3,1] =5 reprezint pn la ce valoare tie nodul P3 c a progresat ceasulscalar logic local de pe nodul P1, iar m[3,2]=2 reprezint ct tie nodul P3 c a progresat ceasul logiclocal de pe nodul P2. Tot pentru nodul P3, valoarea m[1,1]=5 reprezint ct tie procesul P3 c tieprocesul P1 c ar fi ceasul local pe procesul P1. Pentru nodul P3, valoarea m[1,2]=2 reprezint ct tie procesulP3 c tie procesul P1 c ar fi ceasul logic local pe nodul P2.Dac evenimentul curent este eveniment intern, atunci blocul increment ceas local mTi[i,i] executurmtoarea secven de cod:

matrixTimeM[thrd * j + j][i][j]++;unde thrd reprezint numrul total de noduri.Dac evenimentul curent este un mesaj, nti se incrementeaz ceasul logic local al nodului surs cusecvena de cod

matrixTimeM[thrd * j + j][i][j]++;Dup ce s-a incrementat ceasul logic local, adic s-a executat regula R1 din algorimtul lui Lamport, amstocat ntr-o matrice separat numita TS (time-stamp tampil de timp) valorile ceasului matricial de penodul surs dup ce s-a executat R1. Practic aceast matrice va fi ataat la mesaj ca o tampil de timp.Cnd mesajul ajunge la nodul destinaie, se face actualizarea ceasului matricial de la nodul destinaie.tim din teorie c actualizarea ceasului matricial la destinaie se face in dou etape.Prima etap

1 k n : mti[i,k] = max( mti[i,k], mt[j,k] )iar a doua etap

1 k, l n : mti[k,l] = max( mti[k,l], mt[k,l] )nti nodul recepie Pi i actualizeaz linia i cu linia j a tampilei de timp, apoi i actualizeaz restulvalorilor din matrice.Prima etap este implementat cu ajutorul codului de mai jos

30

for (int inc = 0; inc < thrd; inc++)matrixTimeM[thrd * Rx + inc][i][Rx] = Math.max(matrixTimeM[thrd * Rx + inc][i][Rx],TS[Tx][inc]);

iar a doua etap este implementat de codul de mai josfor (k = 0; k < thrd * thrd; k++)matrixTimeM[k][i][Rx] = Math.max(matrixTimeM[k][i][Rx], TS[k / thrd][k% thrd]);

n final, dup ce procesul destinaie a actualizat ceasul logic cu valorile din tampila de timp amesajului, se execut regula R1 la nodul destinaie dup cum se specific n algoritmul Lamport.Incrementarea ceasului logic local la nodul destinaie se face su seciunea de cod

matrixTimeM[thrd * Rx + Rx][i][Rx]++;unde Rx reprezint identificatorul procesului destinaie al mesajului, iar thrd este numrul de noduridin sistemul distribuit.

3.3.5. Analiza ncrcrii reelein aceast seciune vom prezenta cum s-a implementat tabul pentru analiza performanei.

Generare mEv aleatorie cu 1000 de coloane inLin linii

i=0; j=0;

999,0,0][ jjsir

i > nLin

j > 1000

mEv[i][j]= mesaj

j++

i++ Nu

Nu

sir[j]++

Da

Da

Nu

spre blocul de calculurmtor

Fig 3.23 Diagramacodului din spatelebutonului deGenerareRezultate

31

n diagrama de mai sus este reprezentat secvena de pai care este executat atunci cnd se apasbutonul de Generare rezultate. nti se genereaz o matrice de evenimente cu un numr mare decoloane, adic de tacte de ceas simulate, 1000. irul sir va numra cte mesaje sunt pe fiecare tact deceas. Valoarea sir[i0] va reine cte mesaje sunt trimise pe parcursul tactului de ceas i0. Mai departe, setesteaz ce metod de sincronizare a ceasurilor logice este folosit. Dac este folosit metoda scalar,pentru fiecare mesaj se adaug cte un Octet la valoarea de ncrcare care va fi scris n fiierul textpentru tactul de ceas respectiv. Dac este folosit metoda Vectorial, pentru fiecare mesaj, se adaugcte nLin Octei la valoarea ncrcrii pentru un anumit tact de ceas. n sfrit, pentru metodaMatricial, pentru fiecare mesaj se vor aduga nLin * nLin Octei. Acest lucru este reprezentat diagramade mai

Fig 3.24 Analiza ncrcriidatorat metodei sincronizare

jos

32

Folosind sirurile de date rezultate din metoda de mai sus, ele se scriu n nite fiiere text. Pe prima linieeste scris ncrcarea n fiecare period de ceas cnd se folosete metoda Scalar, pe a doua linie estescris ncrcarea n fiecare perioad de ceas cnd se folosete metoda Vectorial, iar pe a treia linie estescris ncrcarea n fiecare perioad de ceas cnd metoda folosit este Metoda Matiricial.De asemenea, folosind datele de mai sus, se vor scrie i nite fiiere text cu numelePerfOverheadAve_< nLin>Threads.txt. n aceste fiiere se calculeaz la fiecare tact de ceas evoluiamediei eantioanelor trecute pentru ncrcare dup formula

nnovhmnm nn ][)1( 1

(3.8)unde mn reprezint media calculat la momentul de timp n, iar ovh[n] este valoarea ncrcrii lamomentul de timp n. Aces fiier este folosit pentru e afia pe acelai grafic i evoluia ncrcrii pentrufiecare moment de timp, dar i evoluia medie a ncrcrii.Avnd aceste date scrise n fiiere, utilizatorul poate s vizualizeze pe ecran grafice cu ncrcareapentru o anumit metod sau comparaie ntre ncrcarea meadie introdus de fiecare dintre cele treimetode de sincronizare a ceasurilor logice studiate n lucrare.

3.3.6. Comparaie ntre un caz n care se aplic metode de sincronizarea a ceasurilor logicei un caz n care nu se aplic nicio metod de sincronizare.n urmtoarea seciune vom ncerca s demonstm utilitatea metodelor de sincronizare Lamportfolosind un exemplu realizat cu ajutorul simulatorului descris anterior. Pentru aceasta, am realizat unscenariu n care exist o desincronizarea a ceasurilor pe nodurile din sistemul distribuit. Ceasurile dinexemplu pot fi considerate chiar ceasuri fizice.Dup cum am prezentat i n partea teoretic, n sistemele distribuite vor exista cazuri n care ceasurilefizice de pe nodurile sistemului vor fi desincronizate. n acest caz, dac un nod cu un ceas mai lent itrimite mesaj unui nod cu ceas mai rapid, mesajul va avea ataat o tampil de timp mai veche, ceea cenu va duna algoritmului care ruleaz pe sistemul distribuit. Dac ns un nod cu ceas mai rapid i vatrimie mesaj unui nod cu ceasul mai lent, atunci se poate ntmpla ca mesajul s aib ataat o tampilde timp mai nou dect ceasul pe nodul destinaie. Pentru nodul destinaie, acest mesaj este ca un mesajdin viitor, ceea ce poate duna algoritmului care ruleaz pe sistemul distribuit. Dac se folosesc nsistemul distribuit metode de sincronizare a ceasurilor logice, aceast situaie defavorabil poate firezolvat.Fereastra cu datele de intrare este similar cu situaia din tabul de simulare. Singura diferen este aceeac utilizatorul nu mai poate selecta metoda de sincronizare simulat, ci ea va fi setat implicit pemetoda scalar. O alt diferen este aceea c utilizatorul poate selecta perioada de ceas pe fiecare noddin sistemul distribuit.De aceea, pentru a ilustra comparativ rezultatele i pentru situaia in care se folosee metoda scalar desincronizare i pentru situaia n care nu se folosete nicio metod de sincronizare, au fost folosite doublocuri de calcul al rezultatelor, cte unul pentru fiecare caz.Mai jost este reprezentat schema logic de calcul a matricei de timp pentru cazul n care avemLamport. Exist nite mici diferene fa de schema de la simulatorul pentru metoda Scalar pe care levom discuta n paginile urmtoare.

33

Da

Nu

Nu

Da

Nu

Da

i = 1

i>nCol

mT[i][j] = mT[i-1][j] + step[j]nLinj ,1

j = 0

j>nLin

mEv[i-1][j] = msj

mT[i][msj] = max(mT [i][j], mT[i][msj])+ 1

j + +

i + +

START

STOP

Fig 3.25 Schma de calcul cuLamport in cazul comparatiei

34

Prima diferen ntre schema de mai sus i simulatorul pentru metoda Scalar a lui Lamport este aceeac n cazul de fa, ceasul se incrementeaz ca un ceas fizic, adic independent de ntmplarea sau nu aunor evenimente. Tot ca n cazul metodei scalare, se lucreaz cu matricea de timp i matricea deevenimente transpuse.Incrementarea variabliei i reprezint venirea unui noi tact de ceas fizic global. Primul bloc reprezintfaptul c la fiecare tact nou de ceas global, ceasul pe nodul respectiv se incrementeaz i el cu ovaloare. Valoarea cu care se incrementeaz ceasul de pe fiecare proces este reinut n vectorul sir[inc].O alt diferen ntre aceast schem i schema de la metoda Scalar este urmtoarea. Doar cazurile ncare se trimite mesaj de la un proces la altul sunt luate n calcul. n cazul n care avem eveniment intern,nu se mai increnteaz ceasul, deoarece acesta s-a incrementat deja la nceputul trecerii pe o linie noun matricea de evenimente. Deci evenimentele interne pot fi folosite doar ca mijloace pentru ca ceasulpe un anumit proces s fie afiat.n cazul n care nu se folosete vreo metod de sincronizare, lucrurile stau mult mai simplu caimplementare. for (i = 1; i

35

Fig 3.26 Exemplu de mesaje ntrziateAvnd n vedere cele spuse mai sus, coninutul lui mDist va fi:0 3 1 0 00 0 0 0 0n exemplul de mai sus avem mesaje doar ctre al doilea nod al sistemului distribuit. tiind nodul surs,tiind momentul de timp la care mesajele sunt trimise, i tiind ntrzierea fiecrui mesaj, se poatedetermina matricea mRec. Coninutul lui mRec pentru exemplul de mai sus este:0 0 0 0 01 0 0 3 2Dac analizm puin Fig3.26 i coninutul matricii mRec, putem vedea c indicele i al liniei careconine valoarea nenul va fi nodul de recepie de pe grafic, iar indicele coloanei j care conine valoareanenul este momentul de timp global la care ajunge mesajul la nodul destinaie. De exemplu, la i = 2, j= 4 avem 1 n matricea mRec, i vedem i pe diagram ca nodul P2 recepioneaz la tactul global 4,mesajul M3. Deci simulatorul, bazndu-se doar pe coninutul matricei mRec, tie unde s afiezerecepionarea mesajelor.Pentru algoritmul BSS trebuie s se compare valoarea cesurilor vectoriale de la nodul surs cu valoareatampilei de timp a mesajului. Pentru a reine tampilele de timp ale fiecrui mesaj care este transmis,se folosete un alt ir auxiliar, sirTs[].irTs[] conine valoarea tampilei de timp a mesajului, alturi de momentul de timp global la care afost trimis, i nodul surs al mesajului. Pentru exemplul de mai sus, sirTs[] va avea valorile:

1 0 1 0 2 0 2 0 3 0 3 0tampila M1 i j tampila M2 i j tampila M3 i j

36

n diagrama de mai sus este detaliat blocul de calcul al matricilor auxiliare. Matricile auxiliare sunt:mEv, mDist, mRec, mBr. O parte sunt calculate aici, cealalt parte sunt folosite la blocul de calcul altimpului i la blocul de afiare.Blocul Completeaz mEv citete valoarea din fiierul text i n funcie de i i j, o stocheaz lamEv[i][j]Blocul Completeaz mDist citete ntrzierile setate de utilizator asociate fierui mesaj i lestocheaz la mDist[i][j]. ntrzierea de la indicii i i j va fi asociat cu mesajul de la mEv[i][j].

Nu

Da

Nu

Da

Citete din MatrixEventInBSS.txt

Completeaz mEv

Completeaz mDist

i = 0

i > nLin

j = 0

j > nCol

j + +

i + +Spre blocul urmtor

Fig 3.27 Detaliereablocului de calcul almatricilor auxiliare

37

NuDa

Nu Da

DaDaDa

Nu Nu Nu

Nu

Da

Nu

Da

mEvTr =mesaj

mRecTr[i+dist][j]=indexRec

CompleteazsirTs[indexTs]

Regula 1 Lamport

mRecTr >0

Condiie BSS 1

Condiie BSS 2

C BSS1 i CBSS 2 true

Scrie n mBrTr Pune mesaj n coad

coad nevid

Condiie BSS 1

Condiie BSS 2

i = 0

i > nEv

j = 0

j > nNod j + +

Regula 2 Lamport

indexRec ++

indexTs ++

Fig 3.28 Detaliereablocului de calcul almatricei de timp

i + +

Spre blocul afiare date

C BSS1 iC BSS 2true

R1 Lamport

Scrie n mBrTr

38

n figura de mai sus este reprezentat schema detaliat a blocului de calcul al matricei de timp. Este denotat faptul c se lucreaz cu toate matricile transpuse. Deci numrul de linii va fi egal cu numrul deevenimente pentru un nod, iar numrul de coloane va fi egal cu numrul de noduri din sistemuldistribuit.Dup ce blocul anterior a completat matricea mEv cu evenimente i matricea auxiliar mDist, acum separcurge matricea mEvTr care este transpusa matricei mEv. Dac evenimentul la care a ajunsparcurgerea este un mesaj, atunci se completeaz matricea de recepie mRecTr. n funcie de ntrziereacare este stocat n matricea mDistTr, se stabilesc indicii i i j la care se completeaz matricea mRecTr.

indexRec ++ ;mRecTr[(i-1) + mDistTr[i-1][j]][auxInt1-1] = indexRec;

Apoi blocul Regula 1 Lamport aplic prima regula de sincronizare a ceasurilor vectoriale pentrunodul surs al mesajului

matrixTimeV[j][i][j] = matrixTimeV[j][i - 1][j] + 1; //R1Apoi, att ceasul vectorial ct i indicii i i j cureni se stocheaz n irul sirTs pentru a se ine mintetampila de timp pentru fiecare mesaj.for(int kk = 0; kk0. Am vzut mai sus, c dac mRec[i][j] are o valoare nenul, atunci nseamn c la nodul j, lamomentul de ceas global i, avem evenimentul de recpie al unui mesaj. Dac avem recepia unui mesaj,se verific cele dou condiii ale algoritmului BSS pentru a vedea dac mesajul primit poate fi difuzatctre celelalte noduri sau nu. Cele dou condiii ale algoritmului sunt enunate la partea teoretic.Implementarea primei condiii este n urmtoarele linii de cod:if(mTimeV[jBun][i-1][thdDest] == sirTs[(mRecTr[i-1][j]-1)*(Ciorna7.getNoThreads()+2)+jBun]-1 )

BUN1 =1;

Implementarea celei de-a doua condiii a algoritmului BSS este n liniile de mai josfor(int k=0; k=sirTs[(mRecTr[i-1][j]-1)*(Ciorna7.getNoThreads()+2)+k])

BUN2=1;elseBUN2=0;

}}

Dac ambele condiii sunt ndeplinite, atunci se execut i a doua regul Lamport i se difuzeazmesajul.Mai jos avei scris codul care execut a doua regul Lamport asupra ceasului vectorial al noduluidestinaie

39

if(BUN1==1 && BUN2==1){mBroadTr[i-1][j]=1;for(int kk=0; kk

40

3. Ghid de utilizare a aplicaiein acest capitol se va ilustra modul de utilizare al aplicaiei. Se va explica ce face fiecare buton

din interfaa grafic a programului i se va explica i cum s se analizeze informaia care este afiat peecran de ctre program.4.1. Seciunea de simulare a metodelor de sincronizaren figura de mai joa avei reprezentat fereastra cu meniul principal al simulatorului.

Fig 4.1 Fereastra principal a programului Cu ajutorul butoanelor de tip Radio Button utilizatorul poate s aleag metoda dorit, numrul decoloane i de linii pentru matricea Evenimentelor de intrare.

41

Dup ce a selectat numrul de coloane i de linii, utilizatorul poate s introduc manual matricea deintrare n program completnd campul de mai jos:

Fig 4.3 Unde se poate completa manual matricea de intrare

Am definit trei tipuri de evenimente care se pot petrece la un nod: Eveniment intern notat cu i n matricea datelor de intrare Eveniment neutru notat cu n n matricea datelor de intrare Mesaj ctre un alt nod al sistemului distribuit notat cu o cifr care reprezint nodul

destinaie pentru mesaj

Fig 4.4 Tipurile de evenimente i notaiile lor n simulatorn figura de mai jos este reprezentat un exemplu de matrice cu succesiunea de evenimente pentru 5noduri timp de 5 perioade de ceas.

Fig 4.5 Cum se completeaz matricea de intrareMai jos este reprezentat afiarea rezultatelor pentru matricea de intrare din figura de mai sus:Pentru a se afia rezultatele, utilizatorul, trebuie mai nti s completeze:1. Metoda folosit

42

2. Numrul de noduri i de tacte de ceas simulate3. Matricea cu succesiunea de evenimente4. Dup ce a completat toate elementele de mai sus se apas butonul finish

Fig 4.6 Exemplu de cum se reprezint evenimenteleSe observ pentru nodul P1, care e primul nod, c succesiunea evenimentelor afiate respect datele deintrare din matrice: Primul eveniment este un mesaj ctre nodul 3, apoi al doilea eveniment este unmesaj ctre nodul 5, al treilea mesaj este un eveniment intern, al patrulea i al cincilea mesaj suntambele evenimente neutre.

De asemenea, se poate observa i faptul c la afiarea grafic a evenimentelor si a valoriiceasului logic ataat, se folosesc culori diferite n funcie de tipul de eveniment. Pentru evenimenteleinterne se folosete culoarea albastr, iar pentru evenimentele de tip mesaj se folosete culoare roie.

Fig 4.7 Culori cu care sunt afiate evenimente interne i mesajeUn alt amnunt important este i acela c rezultatele simulrii cu ceasurile pentru fiecare proces

sunt afiate secvenial, adic se afieaz cte o perioad de ceas la fiecare click. Perioadele de ceas suntdelimitate de linii verzi dup cum se vede n figura de mai jos. Din cauz ca am folosit matrici pentrusimularea nodurilor din sistemul distribuit, de aceea evenimentele simulate vor avea un caractersincron. Practic, mesajele care pornesc de la noduri diferite, dar care sunt poziionate pe aceeai

43

coloan n matricea evenimentelor de intrare, acele mesaje vor pleca n acelai timp. De aceea, amdesenat cu verde nite linii care delimiteaz evenimentele care se petrec ntr-o anumit coloan dinmatricea evenimentelor. De asemenea, am afiat pe ecran tot cu verde un contor care arat a ctacoloan din matricea evenimentelor este desenat.

Fig 4.8 Delimitri ale tactelor logiceDin cauza faptului c programul afieaz rezultatele ntr-un mod sincron, exist unele limitri cu

privire la datele de intrare. Nu orice combinaie de evenimente pentru un anumit nod va da rezultateafiate corect de program. S lum urmtorul exemplu. Matricea cu secvena evenimentelor este cea demai jos, iar rezultatele afiate sunt sub matrice.

3 n in 3 ni n n

44

Fig 4.9 Limitri ale programuluiSe observ faptul c n acelai timp, adic la nceptului simulrii, n primul tact de ceas, nodul 1

i trimite mesaj nodului 3, iar nodul 3 are eveniment intern. Din cauza mecanismului de afiare, nprimul tact de ceas se afieaz doar o singur valoare de ceas. Aa c n primul tact de ceas, pentrunodul 3, se afieaz doar ceasul rezultat n urma evenimentului intern, nu i ceasul rezultat n urmamesajului recepionat de la nodul 1. Aceast limitare apare de fiecare dat cnd se ntmpl ca, pentruacelai nod, ntr-un singur interval de ceas, s se ntmple dou evenimente simultane.

Exist cazuri n care matricea cu secvena de evenimente poate avea dimensiuni foarte mari.Dac ar trebui ca utilizatorul s completeze manual matricea, ar fi o sarcin foarte grea. n plus, risculde a pica n limitarea pe care am prezentat-o mai sus crete n cazul n care avem multe noduri nsistemul distribuit. De aceea, s-a implementat un buton numit Random. Dup ce utilizatorulselecteaz metoda (scalar, vectorial, matricial) i dup ce se alege i numrul de noduri i de ceasurilogice, utilizatorul poate selecta butonul Random. n acel moment, se genereaz automat matricea cusecvena de evenimente. De asemnea, se pun nite validri astfel nct s nu existe cazuri n care pentruacelai nod s existe dou evenimente simultane n aceeai perioad de ceas.

4.2. Seciunea de ncrcare a reelei pentru cele trei metodeA doua parte a programului de simulare o constituie partea n care se face analiza performanei.

Dup cum se poate vedea, cele trei metode de sincronizare a ceasurilor logice difer ntre ele prindimensiunea tampilelor de timp. Pentru fiecare mesaj trimis, este necesar ca nodul care trimite mesajuls ataeze tampila de timp ca un header al pachetului trimis. Asta nseamn c metodele desincronizare a ceasurilor logice introduc o ncrcare suplimentar a reelei. Prin programul de simularese realizeaz un studiu al ncrcrii reelei introduse de algoritmii Lamport.

Se consider urmtoarele ipoteze: fiecare nod, cnd trebuie s trimit un mesaj, ataeaz lasfrit tampila de timp. Dac se folosete metoda scalar, se ataeaz un scalar, dac se folosetemetoda vectorial se ataeaz un vector de dimensiune n iar dac se folosete metoda matricial seataeaz o matrice.

Pentru a face analiza se folosete funcionalitatea de generare aleatare a matricei de intrare.Pentru analiza performanei se face urmtorul lucru: Se folosete butonul de Random pe care

l-am explicat mai sus. Se genereaz automat o matrice cu 1000 de evenimente. Pe aceast matrice senumr cte mesaje exist de la un nod la altul i n funcie de metoda de sincronizare folosit se ofero statistic privitoare la ncrcarea reelei.

Se consider urmtoarele ipoteze:

45

Nu se ia n considerare cantitatea de informaie din mesaj, ci doar ncrcarea produs de faptulc la mesaj se adaug tampila de timp cu valoarea ceasului.

Se consider c fiecare numr din structura de date care reprezint valoarea ceasului logicataat unui mesaj se reprezint pe 1 Octet. De exemplu, tampila de timp de ceas scalar 1 sereprezint pe 1 Octet. tampila de timp de ceas vectorial [1,2] se reprezint pe 2 Octei, etc.

Pentru a accesa partea cu analiza performanei, se apasa butonul din tabul de sus al ferestreimeniului principal:

Fig 4.10 Accesarea tabului de performan

Fig 4.11 Meniul seciunii de analiza performanelor pentru programul simulator dup ce utilizatorul a apsatbutonul de Generare Rezultate

Se observ c la nceput doar butonul de Generare Rezultate este activ, restul butoanelor fiindinactive. Dup ce utilizatorul apas pe butonul de Generare Rezultate, n directorul n care este instalatprogramul vor aprea mai multe fiiere text cu numele PerfOverhead_< nLin>Threads.txt, unde nLin= 8,3 .Coninutul unui astfel de fiier este afiat n figura de mai jos

Fig 4.12 Coninutul uni fiier PerfOverhead_< nLin>Threads.txt , nLin=5Pe prima linie este scris ncrcarea n fiecare period de ceas cnd se folosete metoda Scalar, pe adoua linie este scris ncrcarea n fiecare perioad de ceas cnd se folosete metoda Vectorial, iar pe atreia linie este scris ncrcarea n fiecare perioad de ceas cnd metoda folosit este MetodaMatricial.De asemenea, folosind datele de mai sus, se vor scrie i nite fiiere text cu numelePerfOverheadAve_< nLin>Threads.txt. n aceste fiiere se calculeaz la fiecare tact de ceas evoluiamediei eantioanelor trecute pentru ncrcare dup formula

46

nnovhmnm nn ][)1( 1

(4.1)unde mn reprezint media calculat la momentul de timp n, iar ovh[n] este valoarea ncrcrii lamomentul de timp n. Aces fiier este folosit pentru a afia pe acelai grafic i evoluia ncrcrii pentrufiecare moment de timp, dar i evoluia medie a ncrcrii.Dup ce utilizatorul apas pe butonul de Generare Rezultate i fiierele text se genereaz, celelaltebutoane de pe pagin se activeaz. Cu ajutorul butoanelor utilizatorul poate selecta ce statistic doretes vad.Dac utilizatorul apas pe butonul ncrcarea medie pentru toate cele trei metode, nr fix de noduri, seia numrul de noduri date de utilizator n interfaa grafic, i cu numrul de noduri se aleg doar fiierelePerfOverhead_< nLin>Threads.txt i PerfOverheadAve_< nLin>Threads.txt care au numrulselectat din interfaa grafic. Datele din aceste fiiere vor fi afiate pe acelai grafic dup cum se veden figura de mai jos:

Fig 4.13 Rezultatul apsrii butonului ncrcarea medie pentru toate cele trei metode, nr fix de noduri

Se vede n figura de mai sus c s-au luat datele din fiierul PerfOverheadAve_ 6Threads.txt de petoate liniile i s-au afiat pe ecran.Dac utilizatorul apas pe butonul Afiare ncrcare pentru o anumit metod, nr fix de noduri, nfuncie de metoda selectat se ia doar o linie din fiierul PerfOverhead_< nLin>Threads.txt i doar olinie din fiierul PerfOverheadAve_< nLin>Threads.txt.

47

Fig 4.14 Rezultatul apsrii butonului Afiare ncrcare pentru o anumit metod, nr fix de noduri pentru MetodaVectorial, 7 noduri

n exemplul de mai sus s-a selectat metoda Vectorial, 7 noduri n sistemul distribuit. n cazul acestaprogramul a luat datele de pe a doua linie din fiierul PerfOverhead_7Threads.txt i le-a reprezentatcu linia roie, i a luat datele de pe a doua linie din fiierul PerfOverheadAVE_7Threads.txtreprezentndu-le cu linia albastr.Din graficele afiate se pot trage nite concluzii. ncrcarea reelei este mai mare n cazul metodelormatriciale i vectoriale dect n cazul metodei scalare. Este un lucru normal deoarece n cazul metodeiscalare, le fiecare mesaj se ataeaz doar un scalar care ncape ntr-un octet. n cazul metodei Vectorialela fiecare mesaj se ataeaz un vector cu nLin elemente, unde nLin este numrul de noduri din sistemuldistribuit. Din aceast cauz, ncrcarea pe reea crete, fiecare element al vectorului ocupnd cte unOctet, deci nLin Octei pentru fiecare mesaj. n sfrit, metoda care cauzeaz cea mai mare ncrcare pereea este metoda matricial. n cazul acestei metode, la fiecare mesaj trimis se ataeaz o matrice cunLin x nLin elemente. Fiecare element al matricei este reprezentat pe 1 Octet, deci la fiecare mesajtrimis se produce o ncrcare de nLin2 Octei.Se poate concluziona c ncrcarea medie pentru cele trei metode se afl ntr-o progresie geometric curaia nLin. Cea mai mic este ncrcarea pentru metoda scalar, apoi urmeaz ncrcarea pentru metodavectorial de nLin ori mai mare, i cea mai mare fiind ncrcarea pentru metoda matricial care este denLin2 ori mai mare dect n cazul metodei scalare. Acest lucru se poate observa din graficul din Fig4.14.Acolo avem un caz particular n care avem 6 noduri n sistem. ncrcarea medie datorat metodeiscalare este de 2.5 Octeti / perioad de ceas, ncrcarea medie pentru metoda Vectorial este de 12.5Octei / perioad de ceas, deci de aproximativ 6 ori mai mult. n sfrit, ncrcarea n cazul metodeimatriciale este de 62 Octeti / perioad de ceas, adic de aproximativ 36 ori mai mult dect n cazulmetodei scalare.

48

4.3. Seciunea de Comparaie cu situaia n care avem doar ceasuri fizice desincronizaten urmtoarea seciune vom ncerca s demonstm utilitatea metodelor de sincronizare Lamportfolosind un exemplu realizat cu ajutorul simulatorului descris anterior. Pentru aceasta, am realizat unscenariu n care exist o desincronizarea a ceasurilor pe nodurile din sistemul distribuit. Ceasurile dinexemplu pot fi considerate chiar ceasuri fizice.

Fig 4.15 Exemplu n care cresc ceasurile fizice

Mai sus avem ilustrat o figur n care avem trei noduri. La fiecare tact de ceas global, fiecare nod iincrementeaz ceasul cu o valoare. Este de menionat faptul c ceasul reprezentat n figur poate ficonsiderat chiar ca un ceas fizic. Al doilea i al treilea proces, la fiecare tact de ceas global, iincrementeaz ceasul cu cte 100 de uniti. Aceste uniti pot fi considerate ca reprezentnd nano-secunde, milisecunde, sau orice alt unitate de msur pentru timp. Se observ faptul c primul nod areceasul desincronizat fa de celelalte noduri. Ceasul nodului 1 progreseaz mai ncet fa de celelalte. ntimp ce celalte noduri i incrementeaz ceasul cu cte 100 de uniti la fiecare tact global, nodul 1 areceasul mai ncet i i incrementeaz ceasul doar cu 50 de uniti.

Fig 4.16 Ceasuri desincronizate mesaj de la ceas ncet la ceas mai rapid

n cazul reprezentat n figura de mai sus, avem mesaje doar de la noduri cu ceas ncet ctre noduri cuceas mai rapid. Acest caz este unul fericit deoarece nu are un impact negativ asupra algoritmuluidistribuit care ruleaz pe fiecare nod. Singurul element negativ este acela c mesajul pare s fi avut ontrziere ma mare pe canalul de comunicaie dect n realitate.

49

Fig 4.17 Ceasuri desincronizate, mesaj de la ceas rapid la ceas ncetn figura de mai sus avei reprezentate i cazuri defavorabile. Unul dintre ele este acela n care setrimite un mesaj de la un nod cu ceas rapid ctre un nod cu ceas ntrziat. Atunci apare un evenimentne-dorit, n care mesajul are tampila de timp la plecare mai mare dect timpul la recepie, i apare ca icum mesajul ar fi venit din viitor n trecut. Aceste cazuri sunt mpotriva logicii i sunt foarte duntoarentr-un sistem distribuit. Un alt caz nefavorabil este urmtorul. n simulatorul implementat de mine,nrzierea mesajelor de la un nod la altul este neglijabil n comparaie cu durata unui tact global. ncazul n care avem mesaj ntre dou noduri care au ceasurile sincronizate, atunci poate aprea cazul ncare mesajul are aceeai tampil de timp i la emisie i la recepie. Acest caz este reprezentat tot nfigura de mai sus, la momentul de timp 4 cnd se trimite un mesaj de ctre nodul 3. Mesajul aretampila de timp 400, i ajunge la nodul 2, tot cu tamplia de timp 400.Aplicarea Algoritmului Lamport rezolv ambele probleme descrise n paragraful de mai sus. La fiecarerecepionare de mesaj, nodul de la recepie compar tampila de timp a mesajului cu valoarea ceasuluilocal. Dac valoarea ceasului local e mai mic dect tampila de timp, atunci nodul de la recepie iincrementeaz ceasul local la o valoare mai mare dect cea a tampilei de timp.

50

Fig 4.18 Comparaie cu / fara algoritmul Lamport aplicat nodurilor

Meniul pentru completarea aplicaiei este similar cu cel de la Simularea algoritmilor lui Lamport. El eafiat n figura de mai jos:

51

Fig 4.19 Meniul principal pentru Comparaie Cu / fara LamportDup cum se poate observa, meniul pentru Comparaie Cu / fara Lamport are multe componenteidentice cu cele de la tabul de simulare. n partea de sus a feresrei sunt 2 butoane de tip Drop Downcu care utilizatorul poate selecta numrul de coloane i de linii ale matricei de intrare. Apoi n parteadreapta centru exist o caset de text n care utilizatorul poate introduce matricea de intrare dupaceleai reguli dup care s-a fcut i matricea evenimentelor la simularea metodelor scalar, vectorial,matricial. De asemenea, exist buton de Finish i de Random. Butonul de Random completeazmatricea evenimentelor de intrare dup acelai algoritm ca cel prezentat la capitolul despre simulareametodei scalare, vectoriale, matriciale.Ce apare n plus n meniul pentru Comparaie cu / far Lamport este grupul de butoane Drop Downdin dreapta. Cu ajutorul acestor butoane, utilizatorul poate controla ct de rapid sau de ncet s fieceasul pe fiecare din nodurile din sistemul distribuit. n exemplul din figura de mai sus, nodul 1 areceasul mai ncet, deoarece la fiecare tact logic global ceasul su se incrementeaz cu 50 de uniti detimp, pe cnd nodurile doi i trei i incrementeaz ceasurile la ficare tact logic global cu cte 100 deuniti de timp.Ce este mai complicat la acest meniu, este faptul c numrul butoanelor Drop Down cu careutilizatorul schimba perioada ceasului pe fiecare nod depinde de numrul nodurilor din sistemuldistribuit. Dac utilizatorul schimb numrul de noduri, atunci i numrul butoanelor de tip Dropdown se schimb.

4.4. Simularea algoritmului Birman Schiper StephensonCa o aplicaie a metodei vectoriale de sincronizare a ceasurilor logice am gsit un algoritm care sefolosete de ceasurile vectoriale pentru a ordona mesajele de difuzare ntr-un sistem distribuit.

52

Mai jos este reprezentat fereastra cu meniul principal al programului.

Fig 4.20 Meniul simulatorului algoritmului BSS

Dup cum se vede, fereastra este similar celei de la simularea metodelor de sincronizare. Cea maimare deosebire este aceea c, pe lng faptul c utilizatorul poate defini mesaje de la un nod la altul, elpoate regla i ntrzierea cu care se simuleaz c va ajunge la nodul destinaie. De aceea, n matriceamEv din figura de mai sus, utilizatorul va completa n cazul unui eveniment de tip mesaj, dou cifre.Prima cifr este nodul destinaie, iar a doua cifr este ntrzierea cu care va ajunge mesajul la noduldestinaie.

20 23 21 n n n n nn n n n n n n nFig 4.21 Exemplu de date de intrare pentru algoritmul BSS

Din exemplul de matrice de evenimente de mai sus se nelege c la primul tact global nodul 1 i trimitemesaj nodului 2 cu ntrziere de 0 tacte. Apoi tot nodul 1 i trimite nodului 2 alt mesaj, de data aceastacu o ntrziere de 3 tacte globale. n final, nodul 1 i trimite nodului 2 un mesaj care ajunge la destinaiecu o ntrziere de 1 tact logic.Dup ce utilizatorul a completat datele de intrare, se apas butonul Finish i simulatorul va afiarezultatele simulrii.

53

Fig 4.22 Rezultatele simulrii algoritmului BSSn figura de mai sus se observ c nodul 1 respect secvena de evenimente dat n matricea de intrare.De asemenea, se respect i ntrzierile aplicate pentru fiecare mesaj. Pentru a fi mai uor de identifat,fiecare mesaj din sistmeul distribuit primete cte un nume diferit. n cazul acesta particular avemmesajele M1, M2, i M3.Se observ c la nodul destinaie, de fiecare dat cnd ajunge un mesaj, se verific cele dou condiiiale algoritmului BSS. Reamintim din teorie care sunt paii algoritmului BSS:

1. Fiecare proces Pi menine un ceas vectorial2. nainte de a difuza un mesaj m ctre toate celelalte noduri, un nod Pi i incrementeaz ceasul

vectorial local vti[i] i ataeaz noul ceas vti[i] ca o tampil de timp a mesajului. Vom notatampila de timp a mesajului m cu vtm.

3. Cnd nodul Pj recepioneaz mesajul m, nti verific urmtoarele condiii:a. vtj[i]=vtm[i]-1, ceea ce nseamn c toate mesaje anterioare trimise de ctre nodul Pi au

fost recepionate de ctre Pjb. vtj[k] vtm[k], },...2,1{ nk k i, ceea ce nseamn c nodul Pj a recepionat toate

celelalte mesaje care au trecut pe la Pi (dar nu au fost emise de ctre Pi).4. Dac una dintre cele dou condiii nu e ndeplinit, nodul Pj pune mesajul m ntr-o coad i va

testa tot aceste dou condiii mai trziu5. Dac ambele condiii sunt ndeplinite, atunci procesul Pj difuzeaz mesajul m ctre toate

celelalte noduri din sistemul distribuit, mai puin Pi.Cele dou condiii care sunt verificare la fiecare recepionare a unui mesaj sunt notate cu a i b n paiide mai sus.Se observ c n cazul mesajului M1, cele dou condiii sunt respectate, deci mesajul M1 este difuzat dectre nodul 2 imediat dup recepionarea mesajului.n cazul mesajului M3, se observ c el este transmis de nodul 1 dup transmiterea mesajului M2, dardin cauza canalului de comunicaie, mesajul M2 ajunge mai trziu la destinaie dect mesajul M3. Cndnodul 2 recepioneaz mesajul M3, el verific dac se ndeplinesc condiiile algoritmului BSS. Se poateobserva dac se fac nlocuirile n formul c nu se ndeplinete prima condiie a algoritmului BSS i deaceea mesajul M3 este trecut n coada nodului 2.Se observ c la urmtorul tact global (tactul 5) c ajunge la destinaie i mesajul M2. Nodul 2 verifici n cazul acesta cele dou condiii ale algoritmului BSS. n cazul mesajului M2, cele dou condiiisunt respectate i de aceea mesajul M2 este difuzat.n urmtorul tact global (tactul 6), nodul 2 nu mai recepioneaz niciun mesaj i de aceea ncearc dacpoate treimite vreun mesaj din coada local de ateptare. De aceea iar testeaz cele dou condiii ncazul mesajului M2. Dac se fac nlocuirile se vede c de data aceasta sunt ndeplinite condiiilealgoritmului BSS i mesajul M2 este scos din coad i difuzat.

54

4.5. Limitri ale simulatorului algoritmului Birman Schiper StephensonDin pcate implementarea algoritmului BSS a fost mai delicat din cauza numrului mare de matriciauxiliare i de aceea a fost nevoie de aplicarea unor limitri. Nu se poate simula chiar orice combinaiede mesaje i de ntrzieri a mesajelor.Cea mai important limitare este aceea c se pot simula doar dou noduri. Nodul 1 va fi ntotdeaunanodul care trimite mesaje, iar nodul 2 va fi permanent nodul care recepioneaz mesaje. Utilizatorul nupoate trimite mesaje de la nodul 2 la nodul 1, ci doar de la nodul 1 la nodul 2.O alt limitare important a simulatorului e similar cu cea de la simularea metodelor scalar,vectorial, matricial. Datele nu sunt valide dac se ntmpl mai mult de dou evenimente n aceeaiperioad de ceas global la acelai nod. S considerm exemplul de mai jos care are matricea de intrare

23 n 21 nn n n n

Fig 4.23 Limitare a simulatorului pentru algoritmul BSSSe observ c la tactul 4, se ntmpl dou evenimente diferite la acelai nod, nodul P2. Simulatoruldetecteaz acest lucru i afieaz mesajul de eroare de mai jos. Totui el reprezint grafic evenimentelepentru ca utilizatorul s vad mai uor unde este limitarea.

4.6. Analiza perfomanei ca timp de calcul. Comparaie ntre cele trei metode desincronizare a ceasurilor logicePe lng analiza ncrcrii suplimentare introdus de cele trei metode de sincronizare, este util sstudiem i timpul de calcul pe care l consum fiecare metod de sincronizare n parte. Timpul de calculeste o mrime demn de luat n seam atunci cnd se proiecteaz un sistem distribuit. Un timp de calculmare face ca mainile s raspund greu la cereri, face ca transferul de mesaje pe canalul de comunicaies se realizeze greu.Pentru a msura timpul de procesare, am folosit metoda System.currentTimeMillis(). Aceastmetod returneaz timpul raportat de sistemul de operare, in milisecunde. Pentru a msura timpul decalcul, am introdus liniile de cod

startTime = System.currentTimeMillis();endTime = System.currentTimeMillis();

time = endTime-startTime;

55

Linia cu startTime am introdus-o la inceputul seciunii de cod care calculeaz matricea de timp, liniacu endTime, am introdus-o la finalul seciunii de cod. Facnd diferena dintre cele dou, am obinutintervalul de timp ct a durat calculul matricei de timp.Pentru a obine nite rezultate concludente, am facut urmtorii pai. Cu ajutorul metodei descrise lanceputul capitolului 5 am generat o matrice de evenimente cu valori aleatoare. Am observat c pentruvalori normale ale dimensiunilor matricei, timpul de calcul era sub 1 ms. De aceea, am generat omatrice de evenimente cu dimensiuni foarte mari, pentru ca s se vad mai bine diferena ntre cele treimetode de sincronizare. Pentru determinarea timpului de procesare am folosit o matrice de evenimentecu 8 linii si 5000 de coloane. Am folosit metoda descris la nceputul capitolului 5 pentru a completaautomat matricea.Apoi am deschis programul, am introdus prima realizare particular a matricei, am calculat matricea detimp cu metoda scalar i am obinut prima valoare a timpului de procesare. Apoi iar am inchisprogramul, l-am deschis din nou, i am mai generat inca o data o matrice cu 8 linii si 5000 de coloane.Bineneles c aceasta a fost o alt realizare particular a matricei generat aleator. Am rulat simulareai pentru aceast matrice i am obinut o alt valoare pentru timpul de calcul. n total, am repetat paiidescrii anterior de 10 ori pentru fiecare metod de sincronizare. n final, am obinut urmtoarelerezultate:

1 2 3 4 5 6 7 8 9 100

100

200

300

400

500

600

700

800

900

1000Timpul de calcul

Matrice de intrare particulara

Durat

a [ms

]

Metoda ScalaraMetoda VectorialaMetoda Matriciala

Fig 4.24 Timpii de calculPe axa oX sunt reprezentate cele 10 realizri particulare a matricei de intrare generat aleator. Pe axaoY este reprezentat timpul, msurat in milisecunde. Se observ c pentru metoda Scalar, durata mediede execuie a fost de aproximativ 30 ms, pentru metoda Vectorial, de aproximativ 300 ms, iar pentrumetoda Matricial timpul de procesare a fost cel mai mare, ajungnd la valoarea de 900 ms. Acestemsurtori confirm estimarea c, la fel ca n cazul ncrcrii pe reea, timpul de procesare este maimare n cazul metodelor matricial i vectorial dect n cazul metodei scalare.