*BlocajeCurs 6

Conceptul de blocajIgnorarea blocajelor sau algoritmul struuluiDetectarea i rezolvarea blocajelor Evitarea blocajelorPrevenirea blocajelor

*Resurse(1)Exemple de resurseimprimanteplottereCd-recorderProcesele necesit acces la resurse ntr-o ordine rezonabilPresupunnd c un proces deine resursa A i cere resursa Bn acelai timp un alt proces deine resursa B i cere resursa AAmbele procese sunt blocate

*Resurse(2)Blocajele apar cndProcesele dein acces exclusiv asupra unui dispozitivNe referim la dispozitive cu termenul general de resursResursele pot fiPreemptibileNonpreemptibile

*Resurse (3)Secvena de evenimente necesar utilizrii unei resurse este urmtoarea:Solicit resursaUtilizez resursaEliberez resursa Dac resursa solicitat nu este disponibilProcesul poate fi blocat sauPoate returna un cod de eroare

*Conceptul de blocajDefiniia formal : Un set de procese este blocat dac fiecare proces din setul respectiv ateapt un eveniment care poate fi cauzat doar de un alt proces din acest set.De obicei evenimentul face referire la eliberarea unei resurse.Nici unul din procese nu poate:RulaElibera resursePoate trece n starea awake

*Condiiile de apariie a unui blocajDe excluziune mutualFiecare resurs este fie ocupat de un proces fie liber.De deinere-ateptare a unei resurseUn proces ce deine resurse poate solicita resurse noi.NonpreemptivitiiResursele ocupate nu pot fi retrase forat unui proces.De ateptare circularLanul circular de ateptare este format din cel puin dou procese.Fiecare resurs solicitat este deinut de urmtorul proces din lanul circular.

*Modelarea blocajelor(1)Modelarea blocajelor utiliznd grafuri orientate

Resursa R este alocat procesului A (vezi orientarea sgeii)Procesul B solicit/ateapt resursa S (vezi orientarea sgeii)Procesele D i C sunt blocate la solicitarea resurselor T i U

*Modelarea blocajelor(2)Strategii pentru rezolvarea blocajelor:Ignorarea problemei blocajelorDetectarea i rezolvarea blocajelorEvitarea dinamic blocajelorAlocarea atent a resurselorPrevenirea blocajelorNegarea uneia din cele patru condiii de apariie a blocajelor

*Cum apare un blocajA B CModelarea blocajelor(3)

*Modelarea blocajelor(4)Cum poate fi evitat un blocaj(o) (p) (q)

*Ignorarea blocajelor- algoritmul struuluiSe bazeaz pe prezumpia c nu exist blocajePrezumpia este rezonabil dacBlocajele apar foarte rarCostul prevenirii blocajelor este mareUNIX i Windows utilizeaz aceast abordareEste un compromis ntrecomoditatecorectitudine

*Detecia i rezolvarea blocajelorMonitorizeaz solicitrile i eliberrile de resurse.Poate fi identificat un ciclu care denot apariia unui blocaj

*Rezolvarea blocajelor(1)Rezolvare prin preempiuneEliberarea unei resurse alocate unui alt procesMetod dependent de natura resurseiRezolvare prin derulare napoi(rollback)Marcarea punctelor de execuie a unui procesSalvarea strii unui proces i utilizarea eiRestartarea procesului din punctul de execuie marcat dac se identific blocaj

*Rezolvarea blocajelor(2)Rezolvarea blocajelor prin oprirea proceselorCea mai simpl i eficient metodOprirea unui proces din ciclul identificat dar i a unui proces dinafara cicluluiEste indicat oprirea unor procese a cror execuie poate fi reluat de la nceput ( de exemplu NU se oprete un proces de actualizare a unei baze de date)

*Evitarea blocajelorTraiectoria resurselorTraiectoriile resurselor a dou procese

*Stri sigure i nesigure(1)Demonstraie: starea (a) este sigur/nesigur?(a) (b) (c) (d) (e)

*Stri sigure i nesigure(2)Demonstraie: starea (b) este sigur/nesigur?(a) (b) (c) (d)

*Algoritmul bancherului pentru o singur resursPrecizai care din cele trei stri este nesigur, tiind c sunt disponibile 10 uniti.(a) (b) (c)

*Algoritmul bancherului pentru resurse multiple

*Prevenirea blocajelor Eliminm condiia de excluziune mutualUnele dispozitive cum ar fi imprimanta pot utiliza tehnica spoolingBlocajul la imprimant este eliminat.Nu toate resursele utilizeaz tehnica spooling.Poate funciona dac:Evitarea alocrii resurselor dect n cazuri absolut necesare.Ct mai puine procese realizeaz solicitarea unei anumite resurse.

*Prevenirea blocajelor Eliminm condiia de deinere-ateptareProcesele trebuie s solicite resurse nainte de fi lansate n execuieUn proces nu ateapt niciodat resursele de care are nevoie.ProblemeProcesul nu tie ntotdeauna de care resurse are nevoie nainte de a-i ncepe execuia.Procesul poate ocupa inutil resurse care pot fi alocate altor procese.Variaie: Procesele s poat elibera toate resurselei s le primeasc imediat napoi dac le solicit.

*Prevenirea blocajelor Eliminm condiia de nonpreempiuneNu este o opiune viabil deoarece nu se poate retrage forat o resurs unui proces.Exemplu: un proces ce tiprete un document pierde accesul la imprimant n mijlocul operaiei de tiprire

*Prevenirea blocajelor Eliminm condiia de ateptare circular Resurse accesate n ordine cresctoareGraful resurselor nu va prezenta cicluri(a) (b)

*Recapitulare prevenirea blocajelor

CondiieAbordareExcluziune mutualSpoolingDeinere-AteptareSolicit toate resursele iniialNonpreempiuneRetrage resursaAteptare circularNumeroteaz i acceseaz resursele n ordine cresctoare

*Alte tipuri de blocajeTwo-phase lockingFaza 1Procesul rezerv nregistrrile de care are nevoie una cte unaDac cel puin una din nregistrri este deja rezervat i reia execuiaDac faza 1 s-a ncheiat cu succes procesul va: Realiza actualizriElibera nregistrrileEste similar metodei n care toate resursele sunt alocate nainte de execuia propriu-zis a procesuluiAlgoritmul funcioneaz dac programatorul este foarte atent ca un proces care a fost oprit din execuia primei faze s poat fi restartat.

*Comunication deadlocksDou procese se pot bloca chiar dac nu doresc partajarea aceleiai resurse:Procesul A trimite o cerere ctre procesul B.Procesul A intr n starea blocked pn la recepionarea unui mesaj de la procesul B.Procesul B trimite mesaj ctre procesul A i intr la rndul su n starea blocked.Mesajul se pierde i ambele procese sunt blocate.

*Livelock2 procese A i B acceseaz 2 resurse R1 i R2 n ordinea de mai jos:

Nici unul din procese nu va realiza un progres n execuia sa dar nici nu va intra n starea blocked. Acest tip de blocaj se numete livelock.

void A(void){enter_region(&R1);enter_region(&R2);use_both_resources();leave_region(&R2);leave_region(&R1);}void B(void){enter_region(&R2);enter_region(&R1); use_both_resources();leave_region(&R1);leave_region(&R2);}

*StarvationAlgoritm pentru alocarea imprimantei:fiierele de dimensiune mai mic au prioritate la tiprire.Algoritmul funcioneaz dac imprimanta primete numeroase cereri de tiprire a unor fiiere de dimensiune mic.Totui dac apare o cerere de tiprire a unui fiier de dimensiune mare, aceast cerere va fi amnat la infinit fr a comuta procesul aferent n starea blocked (The process is starving to death.)Soluia este: aplicarea strategiei de alocare primul sosit primul servit.

*De tiut...Definii blocajul.Ce este o resurs preemptibil?Ce este o resurs nonpreemptibil?Care sunt condiiile de apariie a unui blocaj?Cum se pot modela blocajele?Caracterizai algoritmul struului.Cum se realizeaz detecia i rezolvarea blocajelor?Cum se evit blocajele?Caracterizai starea sigur i nesigur.Caracterizai algoritmul bancherului pentru o singur resurs.Caracterizai algoritmul bancherului pentru resurse multiple.Cum se previn blocajele?Explicai i dai exemplu de two-phase blocking.Explicai i dai exemplu de comunication deadlock.Ce reprezint un livelock? Exemplificai.Exemplificai noiunea de starvation.Explicai diferenele dintre blocaj, livelock i starvation.

*De tiut...Un sistem lanseaz dou procese care pot solicita 3 resurse. Fiecare proces are nevoie de maximum 2 resurse. Sistemul se poate bloca? Explicai.Un sistem lanseaz patru procese care pot solicita cinci resurse. Alocarea curent a resurselor i maximul necesar sunt:

Care este cea mai mic valoare a lui x pentru ca aceasta s fie o stare sigur?

Sheet1

AlocateMaximumDisponibil

Procesul A102111121300x11

Procesul B2011022210

Procesul C1101021310

Procesul D1111011221

*De tiut...Dou procese A i B au nevoie de 3 nregistrri 1, 2, 3 dintr-o baz de date. Dac A solicit nregistrrile n ordinea 1,2,3 i B n ordinea 1,2,3 nu va exista blocaj. Dac n schimb A solicit nregistrrile n ordinea 1,2,3 i B n ordinea 3,2,1 va exista blocaj. Avnd la dispoziie trei resurse exist posibilitatea apariiei a 3!=6 solicitri din partea proceselor. Ce procent din aceste solicitri nu vor genera blocaje?

*BibliografieA. Silberschatz, P. Galvin, Operating System Concepts, John Wiley and Sons Inc., 2005, pag 90-108, 245-275.A. Tanembaum, Modern Operating Systems, Prentice Hall, 2007, pag 433-466.Gh. Dodescu, Sisteme de operare, Ed. Economic, 2003, pag 208-215.

*******************