Algoritmi Paraleli

Un algoritm rapid necesita folosirea variabilelor partajate cu scriere multipla; daca fiecare variabila ar fi scrisa numai de un singur procesor, atunci un procesor care ar dori sa intre în sectiunea critica trebuie sa verifice cel putin n variabile pentru posibila competitie.

Algoritmul combina doua mecanisme: unul pentru a obtine intrare rapida în sectiunea critica când numai un singur procesor doreste sa acceada sectiunea critica si altul pentru a asigura inexistenta deadlockului când exista competitie.

Un procesor poate intra în sectiunea critica sau gasind Fast-lock = i (linia 8) sau gasind Slow-lock = i (linia 11).

• Daca nici un procesor nu este în sectiunea critica sau în sectiunea entry, slow-lock = 0 si Want este false pentru toate componentele. Atunci când doar un singur procesor pi trece în sectiunea entry, pune Want [i] pe true si Fast-lock pe i. Apoi verif Slow-lck care este 0. Apoi verif Fast-lock si cum nici un procesor nu-i în sectiunea critica, îl gaseste i si deci pi intra în sectiunea critica pe calea rapida executând 3 write si 2 read.

• Nici un alt procesor nu poate intra în sectiunea critica pe calea rapida pâna pi nu iese din sectiunea critica si reseteaza Slow-lock (linia 14).

• Daca Fast-lock ¹ i atunci pi asteapta pâna ce toate steagurile Want sunt coborâte. Dupa ce un procesor executa bucla for din linia 10, valoarea lui Slow-lock ramâne neschimbata pâna ce un anumit procesor paraseste sectiunea critica si-l reseteaza. Deci cel mult un singur procesor pj poate gasi Slow-lock = j si acest procesor intra în sectiunea critica pe drumul lent.

• Se poate verifica usor ca daca un procesor pi intra în sectiunea critica pe calea rapida, nici un alt proceosr py nu poate intra în sectiunea critica pe o cale lenta.

Observatii 1. Algoritmul nu garanteaza lipsa lockout-ului.

2. Se poate arata ca orice algoritm pentru excluderea mutuala care asigura lipsa deadlockului folosind variabilele R/W trebuie sa foloseasca cel putin n variable partajate indiferent de marimea lor. Evident, se permite ca variabilele partajate sa fie cu multi-write (altfel, marginea inferioara anuntata e evidenta).

....

Într un sistem distribuit nu exista un observator care sa înregistreze un instantaneu al starii sistemului. Aceasta ar fi necesar pentru rezolvarea unor probleme ca: restaurarea sistemului dupa o cadere, determinarea existentei unui deadlock sau detectarea terminarii.

Se poate obtine un instantaneu aproximativ prin cooperarea procesoarelor. Pentru simplificarea expunerii vom presupune ca fiecare eveniment de calcul primeste cel mult un mesaj (se poate implementa o coada locala a mesajelor sosite si procesând un singur mesaj la fiecare pas).

Fie a o executie fixata. Pentru fiecare procesor se pot numara evenimentele de calcul.

O taietura a executiei este un vector k=(k0, …, kn-1) de întregi pozitivi. Pentru fiecare taietura se poate construi o multime de stari ale procesoarelor: starea procesorului pi este starea sa din a imediat dupa evenimentul de calcul numarul ki din pi.

Taietura k a lui a este consistenta daca pentru "i,j

evenimentul de calcul numarul ki+1 al lui pi în a nu se întâmpla înaintea evenimentului kj al procesorului pj din a (evenimentul numarul kj din a al procesorului pj nu depinde de nici o actiune luata de alt procesor dupa taietura).

Vom presupune ca fiecare canal livreaza mesajele într o ordine FIFO.