Algoritmi Paralel și Distribuiți: Ceasuri Logice

Un semafor distribuit gestionează accesul la o resursă partajată într-un sistem distribuit.

Procesele Utiliz[i] sunt responsabile pentru inițierea operațiilor P sau V pe semaforul distribuit.

Procesele Ajutor[i] sunt responsabile pentru implementarea operațiilor P și V pe semaforul distribuit.

Chan opsem[1:n] este un canal de comunicare care permite proceselor Utiliz să trimită operații P și V către procesele Ajutor.

Chan start[1:n] este un canal de comunicare care permite proceselor Ajutor să trimită semnale de start către procesele Utiliz.

Timpul este un concept clar în sistemele ne-distribuite, deoarece există un singur ceas gestionat de sistemul de operare. Sistemul de operare gestionează un ceas fizic intern care incrementează o valoare din memorie, valoarea fiind apoi convertită într-un format standardizat, cum ar fi numărul de milisecunde de la începutul epocii Unix (Jan 1, 1970).

Un ceas fizic este o componentă hardware care se bazează pe un cristal de quartz pentru a genera periodic un semnal care indică o unitate de timp. Aceste semnale sunt numite "clock ticks" și sunt utilizate pentru a incrementa o valoare din memorie, reprezentând timpul. Kernelul sistemului de operare transformă această valoare într-un format standardizat, cum ar fi numărul de milisecunde de la începutul epocii Unix.

Diferența de timp dintre două ceasuri fizice din sisteme distribuite, datorată variațiilor de timp ale cristalelor de cuarț, este cunoscută sub numele de "clock skew".

Sincronizarea ceasurilor fizice se poate realiza între două calculatoare sau cu un standard extern, cum ar fi UTC (Coordinated Universal Time). Scopul este de a reduce "clock skew", dar nu poate fi eliminat complet.

Sistemele distribuite prezintă o ambiguitate în legătură cu timpul deoarece fiecare nod are propriul său ceas fizic. Această discrepanță în timp poate crea confuzii atunci când se utilizează instrumente care se bazează pe timpul real, cum ar fi sistemul de control al versiunilor "make".

Un ceas logic vectorial este o tehnică folosită pentru a ordona evenimentele în sistemele distribuite, asigurându-se o relație totală de ordine între evenimentele din procese diferite.

Un ceas logic vectorial este un vector de valori întregi, cu o dimensiune egală cu numărul de procese din sistemul distribuit.

Fiecare element din vectorul ceasului logic corespunde unui proces din sistem. Valoarea din elementul corespunzător procesului local este numărul de evenimente produse de acel proces, iar celelalte valori reprezintă numărul de evenimente din procesele respective despre care procesul local este informat.

Când un proces 𝑃𝑖 trimite un mesaj către 𝑃𝑗, este atașat ceasul logic 𝑉𝑖. La primirea mesajului, 𝑃𝑗 își actualizează ceasul logic: 𝑉𝑗[𝑗] = 𝑉𝑗[𝑗] + 1 și 𝑉𝑗[𝑖] = max(𝑉𝑗[𝑖], 𝑉𝑖[𝑖])

Utilizând ceasuri logice vectoriale, se poate demonstra că e precede f dacă și numai dacă 𝑉𝑖[𝑖] < 𝑉𝑗[𝑗] pentru orice 𝑖 (inclusiv 𝑖 = 𝑗), fiind 𝑖 procesul în care are loc evenimentul e și 𝑗 procesul în care are loc evenimentul f.

Ceasurile logice vectoriale asigură o relație totală de ordine între evenimentele din sistemele distribuite, comparativ cu ceasurile logice scalare din soluția Lamport, care oferă o relație parțială de ordine.

Ceasurile logice vectoriale sunt utilizate în diverse sisteme distribuite, cum ar fi sistemele de gestionare a tranzacțiilor, sistemele de sincronizare a datelor, și sistemele de mesagerie.

Vectorul de amprente de timp este un vector cu N componente, unde N este numărul de procese din sistem. Fiecare componentă a vectorului reprezintă numărul de mesaje trimise de procesul respectiv, despre care un proces particular știe că au fost trimise. De exemplu, vt(P1) = (1,2,1,3) înseamnă că procesul P1 a trimis 1 mesaj către el însuși, 2 mesaje către P2, 1 mesaj către P3 și 3 mesaje către P4.

Când un proces P trimite un mesaj, el incrementă componenta sa proprie din vectorul de timp, indicând că a trimis un mesaj nou. De asemenea, el adaugă vectorul său de timp actual la mesajul trimis. Aceasta permite proceselor care primesc mesajul să își actualizeze vectorii de timp și să aibă o imagine mai precisă despre numărul de mesaje trimise de fiecare proces.

Când un proces P primește un mesaj, el compară vectorul de timp din mesaj cu vectorul său de timp actual. Pentru fiecare proces din sistem, el ia valoarea maximă dintre componenta corespunzătoare din vectorul mesajului și componenta corespunzătoare din propriul vector de timp. Această operație asigură actualitatea vectorului de timp al procesului care primește mesajul, reflectând numărul total de mesaje trimise de fiecare proces.

Două evenimente sunt concurente dacă cele două vectori de timp nu pot fi comparate folosind operațiile < și >. Acest lucru înseamnă că evenimentele nu au o ordine cauzală clară, adică nu se poate determina sigur care eveniment a avut loc înaintea celuilalt.

Două vectori de timp sunt egali dacă toate componentele lor au aceeași valoare. De exemplu, (1,2,3) = (1,2,3).

Un vector de timp VT1 este mai mic decât un vector de timp VT2 dacă VT1[i] <= VT2[i] pentru toate componentele i, și VT1 != VT2. De exemplu, (1,2,2) < (1,3,2).

Protocolul vectorilor de timp este o tehnică utilizată pentru a ordona mesajele într-un sistem multicast, asigurând respectarea dependenței cauzale. Fiecare proces menține un vector de timp local care este actualizat la fiecare trimitere sau primire de mesaje. Mesajele sunt trimise împreună cu vectorul de timp al procesului emitent, iar procesele receptoare își actualizează vectorii de timp pentru a asigura o ordonare corecta a mesajelor.

Atunci când un proces Ps transmite un mesaj m, Ps incrementează Vs[s] și adaugă Vs la mesaj ca un vector de ștampile de timp curent, vtm. Vs este incrementat doar la transmiterea mesajelor, iar vtm spune receptorului câte evenimente din alte procese au precedat m și ar putea influența cauzal m.

Când un proces Pd primește un mesaj m cu vectorul de timp vtm, mesajul este păstrat într-o coadă de întârziere și este livrat doar dacă: Vts s = Vd s + 1 și vtm k ≤ Vd k pentru k s.

După livrarea mesajului, Vd este actualizat conform regulilor vectorilor de timp: Vd k = max Vd k, vtm[k] pentru fiecare k = 1, n.

Dacă vtm k > Vd[k] pentru un oarecare k, atunci mesajul m este întârziat. Ps a primit mesaje de care mesajul curent m poate fi cauzal dependent, dar pe care Pd încă nu le-a primit.

Dacă vtm s > Vd s + 1, atunci mesajul m este întârziat. Există mesaje de la Ps pe care Pd nu le-a primit încă.

Dacă vtm s < Vd[s], atunci mesajul m este respins. Mesajul m este un duplicat al unui mesaj primit anterior.

Ordonarea cauzală multicastr este o tehnică de ordonare a mesajelor în sistemele distribuite care asigură că mesajele sunt livrate într-o ordine care respectă relația de cauzalitate dintre ele.

Vectorii de timp sunt utilizați pentru a urmări relația cauzală dintre evenimentele din diferite procese. Vectorul de timp Vs al unui proces Ps reprezintă un vector de n componente, unde n este numărul de procese din sistem. Fiecare componentă Vs[i] reprezintă ultimul eveniment care a fost observat de procesul Ps din procesul Pi.