Algoritmi Paraleli

Extras din referat Cum descarc?

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 in sectiunea critica trebuie sa verifice cel putin n variabile pentru posibila competitie.
Algoritmul combina doua mecanisme: unul pentru a obtine intrare rapida in sectiunea critica cand numai un singur procesor doreste sa acceada sectiunea critica si altul pentru a asigura inexistenta deadlockului cand exista competitie.
Un procesor poate intra in sectiunea critica sau gasind Fast-lock = i (linia 8) sau gasind Slow-lock = i (linia 11).
o Daca nici un procesor nu este in sectiunea critica sau in sectiunea entry, slow-lock = 0 si Want este false pentru toate componentele. Atunci cand doar un singur procesor pi trece in 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 in sectiunea critica, il gaseste i si deci pi intra in sectiunea critica pe calea rapida executand 3 write si 2 read.
o Nici un alt procesor nu poate intra in sectiunea critica pe calea rapida pana pi nu iese din sectiunea critica si reseteaza Slow-lock (linia 14).
o Daca Fast-lock 1 i atunci pi asteapta pana ce toate steagurile Want sunt coborate. Dupa ce un procesor executa bucla for din linia 10, valoarea lui Slow-lock ramane neschimbata pana 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 in sectiunea critica pe drumul lent.
o Se poate verifica usor ca daca un procesor pi intra in sectiunea critica pe calea rapida, nici un alt proceosr py nu poate intra in 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).
....
Intr un sistem distribuit nu exista un observator care sa inregistreze 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 procesand 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 intregi 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 in a nu se intampla inaintea 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 intr o ordine FIFO.


Fisiere in arhiva (3):

  • 01.Procesare distribuita.doc
  • 02.Cauzalitate si timp.doc
  • 03.SIMULARE DE SISTEME.doc

Imagini din acest proiect Cum descarc?

Descarca gratuit aceast referat (0 €)

Completezi numele, prenumele și adresa de email. După aceea primesti prin email link-ul pentru descărcare. Completeaza o adresă de email validă.

1. Numele, Prenumele si adresa de email:

Daca nu gasesti email-ul, verifica si directoarele spam, junk sau toate mesajele.



Hopa sus!