Algoritmi Paraleli și Distribuiți Ceasuri Logice PDF

Algoritmi Paraleli și Distribuiți Ceasuri Logice Ordonarea evenimentelor Prof. Ciprian Dobre [email protected] De la ceasuri fizice la... ceasuri logice  Ceasuri fizice Timpul este ne-ambiguu în sisteme ne-distribuite...

Algoritmi Paraleli și Distribuiți Ceasuri Logice Ordonarea evenimentelor Prof. Ciprian Dobre [email protected] De la ceasuri fizice la... ceasuri logice  Ceasuri fizice Timpul este ne-ambiguu în sisteme ne-distribuite  există un singur ceas și (de obicei) kernelul face apeluri pentru a-i accesa valoarea Folosit implicit în multe aplicații  Ex: make (pentru a determina fișierele care trebuie recompilate) Sistemele distribuite introduc ambiguitatea în legătură cu timpul  Ceasuri fizice (2) Computerele folosesc un cristal de quartz care oscilează la o valoare bine definită și generează întreruperi (clock ticks) la intervale regulate Fiecare clock tick incrementează o valoare din memorie – kernelul convertește această valoare într-un format standardizat  Ex: nr. de milisecunde pornind de la Thu Jan 1 12:00:00 GMT 1970. Diferența în timp dintre calculatoare se numește clock skew.  Ceasuri fizice (3) Clock skew dintre cele 2 computere confuzează make-ul: 2144 2145 2146 2147 Conform timpului Calculatorul local pe care rulează compilatorul crearea output.o 2142 2143 2144 2145 Conform timpului Calculatorul local pe care rulează Vim crearea output.o  Sincronizarea ceasurilor fizice 2 tipuri:  doar între 2 calculatoare  sincronizare cu un standard (ex: UTC) Este imposibil de eliminat complet clock skew și imposibil de a asigura acuratețea perfectă a unui ceas. 𝑑𝐶 >1 𝑑𝑡 𝑑𝐶 =1 Timp ceas, C 𝑑𝑡 𝑑𝐶 0, s decrementat și mesajul șters mesajele P sunt procesate în ordinea în care apar în prefixul stabil deci fiecare proces ia aceeași decizie despre ordinea terminării operațiilor P  Aplicație: semafoare distribuite (2) Implementarea semafoarelor:  procesele Utiliz(i) iniţiază operaţiile P sau V  procesele Ajutor(i) implementează operaţiile P și V Utiliz[i] Utiliz[j] Ajutor[j] start[i] opsem[i] Ajutor[i]  Aplicație: semafoare distribuite (3) enum fel(V, P, ack); chan opsem[1:n](int transm, fel op, int timp); chan start[1:n](int timp); process Utiliz[i= 1 to n] { int cl = 0; int ts;... cl = cl + 1; broadcast opsem(i, V, cl);... cl = cl + 1; broadcast opsem(i, P, cl); receive start[i](ts); cl = max(cl, ts)+1;... }  Aplicație: semafoare distribuite (4) process Ajutor[i = 1 to n]{ typedef struct{int transm, fel k, int ts) qelem; qelem qm[lmax]; int cl = 0; int sem = valoare_initială; int transm; fel k; int ts; while (true) { receive opsem[i](transm, k, ts); cl = max(cl, ts) + 1; if (k == P or k == V) { inserează (transm, k, ts) în locul corespunzător în qm; cl = cl + 1; broadcast opsem(i, ack, cl); } else if (k == ack) { înregistrează transmiterea unui ack; for [mesajele V complet confirmate] { scoate mesaj din qm; sem = sem + 1; } for [mesajele P complet confirmate st sem > 0] { scoate mesaj (transm, k, ts) din qm; // atentie la coliziuni sem = sem - 1; if (tansm == i) {cl = cl + 1; send start[i](cl);} } } } } Ceasuri logice vectoriale  Ceasuri logice vectoriale Cu soluţia Lamport: e precede f ⇒ amprenta_logică (e) < amprenta_logică (f) Dar amprenta_logică (e) < amprenta_logică (f) ⇏ e precede f Ex: se poate spune ca e precede c ? Soluția: ceasuri logice vectoriale. 1 2 𝑷𝟏 a b 𝒎𝟏 3 4 Timp 𝑷𝟐 c d 𝒎𝟐 fizic 1 5 𝑷𝟑 e f  Ceasuri logice vectoriale (2) Fiecare 𝑃𝑖 are asociat un tablou 𝑉𝑖 [1.. 𝑛] în care:  𝑉𝑖 [𝑖] este numărul de evenimente produse în procesul 𝑃𝑖  𝑉𝑖 [𝑗] este numărul de evenimente despre care 𝑃𝑖 ştie (a aflat) că au avut loc la 𝑃𝑗. Procesul 𝑃𝑖 actualizează 𝑉𝑖 la fiecare eveniment din 𝑃𝑖  e.g. pentru procesorul 3, (1,2,1,3) → (1,2,2,3) Când 𝑃𝑖 transmite mesajul m (eveniment send m):  𝑃𝑖 incrementează 𝑉𝑖 [𝑖]  𝑃𝑖 adaugă 𝑉𝑖 la m ca vector de amprente de timp curent 𝒗𝒕𝒎 Când 𝑃𝑗 primeşte m și 𝒗𝒕𝒎 (eveniment receive m):  𝑃𝑗 ajustează: 𝑉𝑗 𝑘 = 𝑚𝑎𝑥 𝑉𝑗 𝑘 , 𝑣𝑡𝑚 [𝑘] pentru fiecare 𝑘 e.g., 𝑃2 primește un mesaj cu timpul (3,2,4) iar timpul curent al lui 𝑃2 este (3,4,3), atunci 𝑃2 ajusteaza timpul la (3,4,4)  𝑃𝑗 incrementează 𝑉𝑗 𝑗 cu 1  Ceasuri logice vectoriale (3) (1, 0, 0) (2, 0, 0) 𝑷𝟏 a b 𝒎𝟏 (2, 1, 0) (2, 2, 0) Timp 𝑷𝟐 c d 𝒎𝟐 fizic (0, 0, 1) (2, 2, 2) 𝑷𝟑 e f Aplicarea regulilor ceasurilor logice vectoriale Reguli: 𝑉𝑇1 = 𝑉𝑇2  𝑉𝑇1 𝑖 = 𝑉𝑇2[𝑖], pentru 𝑖 = 1, … , 𝑁 𝑉𝑇1 ≤ 𝑉𝑇2  𝑉𝑇1 𝑖 ≤ 𝑉𝑇2 [𝑖], pentru 𝑖 = 1, … , 𝑁 𝑉𝑇1 < 𝑉𝑇2  𝑉𝑇1 𝑖 ≤ 𝑉𝑇2 [𝑖], și 𝑉𝑇1 𝑉𝑇2 (de exemplu (1,2,2) < (1,3,2)) Fie vt(a) şi vt(b) vectorii de amprente de timp asociaţi ev. a şi b. Atunci: vt(a) < vt(b) ⇒ evenimentul a precede cauzal b vt(a) ≮ vt(b) and vt(a) ≯ vt(b) and vt(a) ≠ vt(b)  evenimentele a şi b sunt concurente Aplicație: Ordonare Cauzală Multicast  Ordonare Cauzală Multicast Procesele unei colecţii P comunică între ele doar prin mesaje cu difuzare Se cere ca mesajele să respecte dependenţa cauzală m → m' ⇒ livrarep (m) → livrarep (m') Protocolul (vectori de timp):  fiecare proces 𝑃𝑖 = (𝑖 = 1.. 𝑛) are asociat un vector 𝑉𝑖 [1.. 𝑛], cu toate elementele iniţial 0  se numara doar operatiile de transmitere de mesaje  𝑉𝑖 [𝑖], este nr ev. transmitere de mesaje produse de 𝑃𝑖 ;  𝑉𝑖 𝑗 este nr ev. transmitere de mesaje despre care 𝑷𝒊 ştie (a aflat) că au avut loc la 𝑃𝑗.  Procesul 𝑃𝑖 actualizează 𝑉𝑖 la fiecare eveniment de trimitere sau recepţie de mesaj din 𝑃𝑖.  Ordonare Cauzală Multicast (2) Când 𝑃𝑆 transmite mesajul m:  𝑷𝑺 incrementează 𝑽𝑺 [𝒔]  𝑷𝑺 adaugă 𝑽𝒔 la m ca vector de amprente de timp curent 𝒗𝒕𝒎 ▪ Obs: Pentru ordonare cauzală, incrementarea lui 𝑽𝒔 [𝒔] se face doar la transmiterea de mesaje de către s ▪ 𝑣𝑡𝑚 spune receptorului câte evenimente (din alte procese) au precedat m şi ar putea influenţa cauzal pe m. Când 𝑃𝑑 primeşte mesajul m împreună cu 𝑣𝑡𝑚 , mesajul este păstrat într-o coadă de întârziere şi este livrat doar dacă:  𝒗𝒕𝒔 𝒔 = 𝑽𝒅 𝒔 + 𝟏 (acesta este următorul timestamp pe care d îl așteaptă de la s)  𝒗𝒕𝒎 𝒌 ≤ 𝑽𝒅 𝒌 𝒑𝒆𝒏𝒕𝒓𝒖 𝒌 𝒔 (d a văzut toate mesajele ce au fost văzute de s la momentul când a trimis mesajul m) Când mesajul este livrat, 𝑉𝑑 este actualizat conform regulilor vectorilor de timp: 𝑽𝒅 𝒌 = 𝒎𝒂𝒙 𝑽𝒅 𝒌 , 𝒗𝒕𝒎[𝒌] pentru fiecare 𝒌 = 𝟏, 𝒏.  Ordonare Cauzală Multicast (3) 𝑷𝟏 (1, 0, 0) 𝑷𝟐 (1, 1, 0) (1, 0, 0) 𝑷𝟑 Timp Alte acţiuni ale protocolului la livrarea mesajelor: dacă 𝑣𝑡𝑚 𝑘 > 𝑉𝑑 [𝑘] pentru un oarecare k atunci se întârzie m 𝑃𝑆 a primit mesaje de care mesajul curent poate fi cauzal dependent, dar pe care 𝑃𝑑 încă nu le-a primit; dacă 𝑣𝑡𝑚 𝑠 > 𝑉𝑑 𝑠 + 1 atunci se întârzie m mai sunt mesaje de la 𝑃𝑆 pe care 𝑃𝑠 nu le-a primit (asigură ordinea FIFO pentru canale nonFIFO) dacă 𝑣𝑡𝑚 𝑠 < 𝑉𝑑 [𝑠] atunci rejectează m m este un duplicat al unui mesaj primit anterior  Sumar Ceasuri fizice Ceasuri logice și ordonarea evenimentelor Semafoare distribuite Ceasuri logice vectoriale Ordonare cauzală multicast