Algoritmi Paraleli si Distribuiti - Lucru cu semafoare PDF

Algoritmi Paraleli și Distribuiți Lucru cu semafoare Prof. Ciprian Dobre [email protected] Sincronizare: Notiuni introductive  Dezvoltarea algoritmilor folosind variabile partajate (MIMD) ▪ Sincronizarea: excluderea mutuală ş...

Algoritmi Paraleli și Distribuiți Lucru cu semafoare Prof. Ciprian Dobre [email protected] Sincronizare: Notiuni introductive  Dezvoltarea algoritmilor folosind variabile partajate (MIMD) ▪ Sincronizarea: excluderea mutuală şi sincronizarea condiţionată. ▪ Câteva rezultate notabile: ‒ mutex ‒ semafoare o regiuni critice ‒ bariere ▪ Câteva dintre problemele clasice: ‒ producători-consumatori ‒ problema filozofilor ‒ cititori-scriitori ‒ problema bărbierului  Sectiuni critice ▪Problema: fiecare proces P(i) al unei colectii de procese P(i:1..n) executa ciclic o sectiune critica, in care are acces exclusiv la anumite resurse partajate, urmata de o sectiune necritica in care foloseste doar resurse locale. ▪Semafor = tip special de variabile partajate manipulate prin 2 operații atomice: P și V (Dijkstra, 1965) ‒ Asigura excluderea mutuala intre procesele care acceseaza sectiunea critica.  Secțiuni critice sem mutex= 1; process P[i=1 to n] { while (true) { P(mutex); Secțiune critică; V(mutex); Secțiune necritică } } Exemplu executie… Sectiune critica time  Zonă Critică P() sau Proberen 1 V() sau Verhogen - Dijsktra Doar un thread poate fi în zona critică la un moment dat  Zonă Critică P() sau Proberen 1 V() sau Verhogen - Dijsktra Doar un thread poate fi în zona critică la un moment dat  Zonă Critică P() sau Proberen 1 V() sau Verhogen - Dijsktra Doar un thread poate fi în zona critică la un moment dat  Zonă Critică P() sau Proberen 0 V() sau Verhogen - Dijsktra Doar un thread poate fi în zona critică la un moment dat  Zonă Critică P() sau Proberen 0 V() sau Verhogen - Dijsktra Doar un thread poate fi în zona critică la un moment dat  Zonă Critică P() sau Proberen 1 V() sau Verhogen - Dijsktra Doar un thread poate fi în zona critică la un moment dat  Zonă Critică P() sau Proberen 0 V() sau Verhogen - Dijsktra Doar un thread poate fi în zona critică la un moment dat  Zonă Critică P() sau Proberen 0 V() sau Verhogen - Dijsktra Doar un thread poate fi în zona critică la un moment dat  Zonă Critică P() sau Proberen 0 V() sau Verhogen - Dijsktra Doar un thread poate fi în zona critică la un moment dat  Zonă Critică P() sau Proberen 0 V() sau Verhogen - Dijsktra Doar un thread poate fi în zona critică la un moment dat  Zonă Critică P() sau Proberen 0 V() sau Verhogen - Dijsktra Doar un thread poate fi în zona critică la un moment dat  Zonă Critică P() sau Proberen 0 V() sau Verhogen - Dijsktra Doar un thread poate fi în zona critică la un moment dat  Zonă Critică P() sau Proberen 0 V() sau Verhogen - Dijsktra Doar un thread poate fi în zona critică la un moment dat  Zonă Critică P() sau Proberen 0 V() sau Verhogen - Dijsktra Doar un thread poate fi în zona critică la un moment dat  Zonă Critică P() sau Proberen 1 V() sau Verhogen - Dijsktra Doar un thread poate fi în zona critică la un moment dat  Zonă Critică P() sau Proberen 1 V() sau Verhogen - Dijsktra Doar un thread poate fi în zona critică la un moment dat  Zonă Critică P() sau Proberen 0 V() sau Verhogen - Dijsktra Doar un thread poate fi în zona critică la un moment dat Producator-consumator Producer - Consumer  Producători și consumatori ▪ Problema ‒ Se consideră M producători și N consumatori care comunică printr-un singur buffer partajat. T Am loc? Am ce prelua? T T  Producători și consumatori typeT buf; sem gol= 1, plin= 0; process Producător[i=1 to M]{ process Consumator[i=1 to N]{ typeT v; typeT w; while(true) { while(true) { v = produce(); P(plin); P(gol); w = buf; buf = v; V(gol); semnalizare V(plin); consumă(w); } } } }  Comunicarea producător și consumator prin tampon limitat typeT buf[1:k]; sem gol = k, plin = 0; process Producător { typeT v; int ultim= 1; while (true) { v = produce(); P(gol); buf[ultim] = v; ultim = ultim mod k + 1; V(plin); } } process Consumator { typeT w; int prim= 1; while (true) { P(plin); w = buf[prim]; prim = prim mod k + 1; V(gol); consumă(w); } } Comunicarea producător și consumator prin tampon limitat kxT Am loc? Am ce prelua? T T  Mai mulți producători și mai mulți consumatori typeT buf[1:k]; int prim = 1, ultim = 1; sem gol = k, plin = 0; sem mutexP = 1, mutexC = 1; process Producător[i=1 to M]{ process Consumator[i=1 to N]{ typeT v; typeT w; while (true) { while (true) { v = produce(); P(plin); sectiune critica P(gol); P(mutexC); P(mutexP); w = buf[prim]; buf[ultim] = v; prim = prim mod k + 1; ultim = ultim mod k + 1; V(mutexC); V(mutexP); V(gol); V(plin); consumă(w); } } } } Problema filozofilor  Problema filozofilor Socrate process Filozof[i=1 to 5]{ while (true) { ia bețișoare; Descartes 4 Confucius mănâncă; 4 eliberează bețișoare; 5 gândește; 5 3 } 1 3 } Platon Eliade 2 1 DEADLOCK 2 Fiecare mai are nevoie de un bețișor  Problema filozofilor (2) sem f[1:5] = (1); Socrate process Filozof[i=1 to 4]{ while (true) { P(f[i]); P(f[i+1]); mănâncă; 4 Descartes Confucius V(f[i]); V(f[i+1]); gândește; 4 5 } } process Filozof[i=5]{ 5 3 while (true) { 1 3 P(f); P(f); Platon Eliade mănâncă; V(f); V(f); 2 gândește; } } 1 2 Problema cititori-scriitori Problema cititorilor și scriitorilor Excludere mutuală zona de memorie (resursa critica) 1) Un singur scriitor are dreptul sa scrie la un moment dat, 1) Un cititor poate citi din 2) Doar daca nu exista un memorie, indiferent daca cititor curent care citeste deja exista alti cititori ce deja citesc 2) Doar daca nu exista un scriitor care scrie  Problema cititorilor și scriitorilor Excludere mutuală sem rw = 1; process Cititor[i=1 to m]{ while (true){ P(rw); citește din resursa comună; V(rw); } } Excludere mutuala strica ! process Scriitor[j=1 to n]{ Un singur proces are voie sa execute while (true){ opeartii pe resursa critica… P(rw); scrie în resursa comună; V(rw); } } zona de memorie (resursa critica)  Problema cititorilor si scriitorilor Excludere mutuală (2) int nr = 0; sem mutexR = 1, rw = 1; process Cititor[i=1 to m]{ while (true){ P(mutexR); nr = nr + 1; sectiune critica if (nr == 1) P(rw); V(mutexR); citește din resursa comună; P(mutexR); nr = nr - 1; if (nr == 0) V(rw); V(mutexR); } } process Scriitor[j=1 to n]{ while (true){ P(rw); scrie în resursa comună; V(rw); } } zona de memorie (resursa critica) nr = 0 nr = 1 nr = 2  Problema cititorilor și scriitorilor Sincronizare condiționată ▪Invariant global: RW: ( nr == 0 || nw == 0 ) && nw 0 sau dw>0 */ sem w = 0; int dr = 0; int dw = 0;  Problema cititorilor și scriitorilor Sincronizare condiționată (4) Split binary semaphore ▪ Folosit pentru a implementa atât excluderea mutuală cât și sincronizarea condiționată. ▪ Semafoarele e, r și w formează împreună un semafor splitat (split binary semaphore): ‒ cel mult un semafor este 1 la un moment dat 0 ≤ e + r + w ≤ 1 ‒ fiecare cale de execuție începe cu un P și se termină cu un singur V ‒ instrucțiunile între P și V se execută în excludere mutuală. ▪ Tehnica se numește pasarea ștafetei: ‒ Inițial un semafor este 1 și un proces poate prelua ștafeta printr-o operație P asupra semaforului ‒ când un proces deține ștafeta (se execută într-o secțiune critică și toate semafoarele sunt 0), el poate pasa ștafeta altui proces printr-o operație V asupra unuia din cele trei semafoare.  Problema cititorilor și scriitorilor Sincronizare condiționată (5) process Cititor[i=1 to m]{ while (true){ P(e); if (nw > 0 or dw > 0){ dr = dr + 1; V(e); P(r); } nr = nr + 1; if (dr > 0) { dr = dr - 1; V(r); } else if (dr == 0) V(e); citește din resursa comună; P(e); nr = nr - 1; if (nr == 0 and dw > 0) { dw = dw - 1; V(w); } else if (nr > 0 or dw == 0) V(e); } }  Problema cititorilor și scriitorilor Sincronizare condiționată (6) process Scriitor[j=1 to n]{ while (true){ P(e); if (nr > 0 or nw > 0) { dw = dw + 1; V(e); P(w) } nw = nw + 1; V(e); scrie în resursa comună; P(e); nw = nw - 1; if (dr > 0 and dw == 0) { dr = dr - 1; V(r); } else if (dw > 0) { dw = dw-1; V(w); } else if (dr == 0 and dw == 0) V(e); } } Problema barbierului  Problema bărbierului ▪Problema: ‒O frizerie cu un bărbier, un scaun de bărbier, n scaune de așteptare. ‒Când nu sunt clienți, bărbierul doarme. ‒Când sosește un client fie trezește bărbierul, fie așteaptă dacă acesta e ocupat. ‒Dacă toate scaunele sunt ocupate, clientul pleacă. Pas 1 clienti BarbierGata Pas 2 clienti BarbierGata Pas 3 clienti BarbierGata Pas 4 clienti BarbierGata  Problema bărbierului (1) int NumărScauneLibere = n; sem Clienți = 0; sem BărbierGata = 0; sem Scaune = 1; sincronizare cu Client process Bărbier{ while (true){ P(Clienți); P(Scaune); NumărScauneLibere++; V(BărbierGata); V(Scaune); } }  Problema bărbierului (2) process Client[i=1 to m]{ while (true) { sincronizare cu Barbier P(Scaune); if (NumărScauneLibere > 0){ NumărScauneLibere--; V(Clienți); atomicitate V(Scaune); P(BărbierGata); } else { V(Scaune); } } }  Problema bărbierului (var. mutex) emptyChairs = N Bărbier Clients = 0 Client BarberReady = 0 Chairs = 1 Chairs.lock(); while(true) { if(emptyChairs>0) { Clients.lock(); emptyChairs--; Chairs.lock(); Clients.unlock(); emptyChairs++; Chairs.unlock(); BarberReady.unlock(); BarberReady.lock(); Chairs.unlock(); getHairCut(); } else { cutHair(); Chairs.unlock(); } }  Sumar ▪Dezvoltarea algoritmilor folosind variabile partajate (MIMD) ▪Semafoare ▪Secțiuni critice ▪Probleme: ‒ Producători și consumatori ‒ Problema filozofilor ‒ Problema cititorilor și scriitorilor ‒ Problema bărbierului