|
|
|
INTERBLOCAREA (DEADLOCK)
Alaturi de problema sectiunii critice, interblocarea reprezinta una din principalele probleme ce trebuiesc solutionate in functionarea unui SO. Mecanismul principal al interbocarii consta in faptul ca o resursa ceruta de un proces este detinuta de alt proces. Pana cand procesul care detine resursa o va elibera, apare o situatie tipica de interblocare.
Deoarece interblocarea este strans legata de resursele sistemului de operare, vom prezenta, mai intai, cateva notiuni referitoare la aceste resurse.
1. Resurse
1.1. Clasificarea resurselor din punct de vedere al interblocarii
Cea mai importanta clasificare din punct de vedere al interblocarii este:
a) resurse partajabile ;
b) resurse nepartajabile.
O resursa partajabila poate fi utilizata in comun de mai multi utilizatori. Un exemplu clasic in acest sens este citirea unui fisier de catre mai multi utilizatori.
O resursa nepartajabila nu poate fi folosita in acelasi timp de catre mai multi utilizatori. Un exemplu este imprimanta. Evident, mai multi utilizatori nu pot tipari in acelasi timp pe aceeasi imprimanta. Numai resursele nepartajabile conduc la situatii de interblocare; cele partajabile nu pun probleme din acest punct de vedere. Sistemul de operare, in procesul de control al interblocarii, trebuie sa aiba o gestiune doar a resurselor nepartajabile.
O alta clasificare a resurselor, importanta pentru interblocare, este:
a) resurse cu un singur element;
b) resurse cu mai multe elemente.
Pentru situatii diferite de interblocare, aceasta clasificare este foarte importanta, ea ducand la decizii diferite. Un exemplu tipic unde intervine aceasta clasificare este graful de alocare a resurselor.
1.2. Etapele parcurse de un proces pentru utilizarea unei resurse
In vederea utilizarii unei resurse, un proces trebuie sa execute urmatoarele etape:
a)Cererea de acces la resursa. Procesul formuleaza o cerere de acces la resursa respectiva. Daca nu ii este repartizata imediat, intra intr-o coada de asteptare si va astepta pana cand poate dobandi resursa.
b)Utilizarea resursei. Este etapa in care procesul a primit permisiunea de utilizare a resursei, iese din coada de asteptare si utilizeaza efectiv resursa.
c)Eliberarea resursei. Se elibereaza resursa si se incheie utilizarea resursei de catre proces.
Pentru implementarea de catre SO a acestei operatii, exista tabele ale SO in care fiecarei resurse ii este asociat procesul ce o utilizeaza si, de asemenea, fiecare resursa are asociata o coada de asteptare cu toate procesele care au facut cerere de utilizare a resursei. De obicei, sistemele de operare implementeaza, pentru fiecare din etapele de mai sus, apeluri sistem sau semafoare.
2. Conditii necesare pentru aparitia interblocarii
In anul 1971, Cofman a identificat patru conditii necesare care, daca sunt indeplinite simultan, pot conduce la aparitia interblocarii. Aceste conditii sunt:
a)Excluderea mutuala. Existenta excluderii mutuale presupune ca un proces a obtinut resursa si exista o coada de asteptare a altor procese la aceeasi resursa.
b)Ocupare si asteptare. Exista cel putin un proces care a obtinut resursa dar care asteapta si alte resurse suplimentare care, la randul lor, sunt ocupate de alte resurse.
c)Imposibilitatea achizitionarii fortate. Un proces nu poate achizitiona fortat o resursa aferenta altui proces decat dupa eliberarea resursei de catre acel proces.
d)Asteptare circulara. Exista un sir de procese P1, P2, .Pn, toate in asteptare, in asa fel incat P1 asteapta eliberarea resurse de catre P2, P2 asteapta eliberarea resursei de catre P3...Pn asteapta eliberarea resursei de catre P1.
P1→P2→P3→.......Pn-1→Pn
3. Graful de alocare a resurselor
Pentru descrierea starii de interblocare este folosit un graf orientat, numit graful de alocare a resurselor. Nodurile grafului sunt alcatuite din procese si resurse. Vom nota procesele cu P si resursele cu R.
Resursa cu indice i :
Ri
Procesul cu indice j :
Arcele grafului sunt orientate si sunt de doua feluri:
a) arce cerere, care reprezinta faptul ca procesul Pj facut o cerere de alocare a resursei Ri si asteapta dobandirea ei;
c) arce alocare, care reprezinta faptul ca procesului Pj i-a fost alocata resursa Ri .
Cea mai importanta aplicatie a acestui graf este legata de detectia starii de interblocare. Pentru un graf alcatuit numai din resurse simple, existenta unei bucle in graf inseamna ca in sistem a aparut o interblocare. De exemplu, in graful urmator.
Fig. Graf de resurse.
In graful de mai sus, procesului P1 ii este alocata resursa R1 si procesului P2 resursa R2 . Procesul P1 a facut o cerere de alocare a resursei R2 detinuta de P2 iar P2 a facut o cerere de alocare a resursei R1 detinuta de P1 . Este o situatie clara de interblocare. In graful din figura aceasta interblocare este vizibila prin existenta buclei.
De mentionat ca pentru grafurile cu resurse multiple existenta buclei nu inseamna o situatie de interblocare.
De exemplu, in cazul din figura 4.3., existenta buclei nu inseamna interblocare.
Fig. 4.3. Graf fara situatie de interblocare.
4. Rezolvarea problemei interblocarii
Exista doua tipuri de metode pentru rezolvarea interblocarii:
a) metoda in care nu i se permite niciodata sistemului de operare sa intre in interblocare;
b) metoda in care se permite sistemului de operare sa intre in interblocare si apoi se incearca scoaterea sa din aceasta stare
In cadrul primei metode se face prevenirea sau evitarea interblocarii.
In cadrul celei de-a doua metode se utilizeaza un mecanism de detectie a interblocarii si revenire din aceasta stare.
4.1. Prevenirea interblocarii
Pentru a putea preveni interblocarea este suficient ca una din conditiile de aparitie a acesteia sa nu fie indeplinita. Sa vedem cum poate fi impiedecata indeplinirea fiecarei din cele patru conditii.
a) Excluderea mutuala
Pentru o resursa nepartajabila nu este posibila prevenirea interblocarii prin neindeplinirea conditiei de excludere mutuala.
b) Ocupare si asteptare
Pentru neindeplinirea conditiei de ocupare si asteptare sunt posibile doua protocoale:
-un protocol in care fiecare proces isi poate incepe executia numai dupa ce si-a achizitionat toate resursele necesare;
-un protocol in care unui proces nu i se permite sa achizitioneze decat o resursa, achizitionarea resurselor suplimentare facandu-se cu eliberarea resurselor deja angajate.
Desi prin ambele protocoale se asigura neindeplinirea conditiei de asteptare si asteptare, totusi ele prezinta doua mari dezavantaje:
-utilizarea resurselor este destul de redusa, in sensul ca timpul cat o resursa este alocata unui proces si neutilizata este foarte mare;
-apare un proces de infometare, deoarece un proces nu poate sa astepte la infinit alocarea unei resurse.
c) Imposibilitatea achizitionarii fortate
Neindeplinirea acestei conditii inseamna de fapt ca un proces sa poata lua o resursa alocata altui proces in orice moment. Desigur, aceasta achizitionare fortata a resurselor unui alt proces nu trebuie facuta haotic, ci in cadrul unui protocol de achizitionare fortata. Un exemplu de astfel de protocol este urmatorul : un proces care isi achizitioneaza resurse in vederea executiei va putea lua fortat resurse de la alt proces numai daca procesul respectiv este in asteptare. Acest protocol se aplica frecvent in cazul resurselor a caror stare poate fi usor salvata si refacuta (ex. registrele procesorului, spatiul de memorie).
d) Asteptare circulara
Un algoritm simplu pentru eliminarea asteptarii circulare este dat in continuare.
Se creeaza o corespondenta biunivoca intre toate resursele nepartajabile ale sistemului si mutimea numerelor naturale, astfel incat fiecare resursa este identificata orintr-un numar natural. De exemplu:
hard disc ....1
CD ROM....2
imprimanta....3
MODEM....4
scaner......5
Apoi, un proces poate cere resursa cu numar de ordine k , cu conditia ca sa elibereze toate resursele cu indice mai mare decat k, adica k+1, k+2,...n. In felul acesta se elimina posibilitatea de asteptare circulara.
In concluzie, pentru prevenirea interblocarii se utilizeaza algoritmi care impun ca cel putin una din conditiile necesare sa nu fie indeplinite. Acesti algoritmi actioneaza prin stabilirea unor restrictii asupra modului in care se pot formula cererile de acces. Principalele dezavantaje ale acestei metode sunt gradul redus de utilizare a resurselor si timpul mare de asteptare a unui proces pentru o resursa.
Evitarea interblocarii
Daca pentru prevenirea interblocarii se folosesc restrictii asupra modurilor de formulare a cererilor pentru resurse, in evitarea interblocarii se utilizeaza informatii suplimentare referitoare la modul in care se face cererea de acces. Algoritmii de evitare difera prin tipul si cantitatea acestor informatii.
Se definesc doua notiuni: stare sigura si secventa sigura.
In cazul acestor algoritmi, fiecare proces trebuie sa declare numarul maxim de resurse de fiecare tip de care ar putea avea nevoie. Algoritmul examineaza mereu starea alocarii resurselor pentru a avea certitudinea ca nu va exista asteptare circulara.
Secventa sigura
Fie un sir de
procese P1 , P2 , ....Pn exact in aceasta ordine. Spunem ca
aceasta secventa este sigura daca pentru orice proces
Pi cu (1 ≤ i ≤ n) s-ar cere numarul maxim de
resurse, declarat initial, atunci diferenta intre numarul maxim
de resurse si numarul de resurse al procesului in acel moment nu
depaseste numarul resurselor obtinute din insumarea resurselor disponibile cu resursele eliberate de procesele Pj
cu j
i. Daca nu se indeplineste aceasta
conditie, atunci secventa este nesigura.
Stare sigura
Sistemul este intr-o stare sigura daca contine cel putin o secventa sigura. De exemplu, fie secventa de procese:
P1 P2 P3 P4 P5
P1
P2
P3
P4
P5
Maxim resurse cerute
10
15
20
25
30
Cerere initiala
5
5
10
10
20
Total resurse = 60
Resurse disponibile = 60-5-5-10-10-20 = 10
Sa analizam secventa P1 P2 P3 P4 P5 .
P1 la cerere maxima de resurse ar avea nevoie de
10-5 = 5 resurse < 10 resurse disponibile
P215-5 = 10 resurse < 5(eliberate de P1 ) + 10(disponibile)
P320-10=10 resurse < 5(P1 ) + 5(P2) +10(disponibile)
P425-10=15 resurse < 5(P1) + 5(P2) + 10(P3) + 10 (disponibile)
P530-20=10 resurse < 5(P1)+5(P2)+10(P3)+10(P4)+10(dispon.)
Deci aceasta secventa este sigura.
Sa analizam secventa P4 P5 P1 P2 P3.
P425-10 = 15 > 10 (resurse
disponibile) 
secventa
nesigura.
a) Algoritmul bancherului
Un algoritm clasic de evitare a interblocarii, bazat pe notiunea de secventa sigura, este algoritmul bancherului. Se numeste asa deoarece poate fi folosit in sistemul bancar la plata unor sume catre diferiti clienti ai bancii, plata care trebuie sa lase mereu banii intr-o stare sigura.
Pentru a putea aplica acest algoritm trebuie sa se cunoasca de la inceput numarul maxim de resurse cerute de fiecare proces. Apoi, la fiecare cerere a unor resurse noi, se aplica algoritmul pentru a vedea daca aceasta cerere duce la o stare sigura sau nesigura. Daca e sigura, cererea este acceptata, daca nu e sigura, cererea nu este acceptata si procesul ramane in asteptare.
Structurile de date folosite de algoritm sunt:
n - numarul de procese din sistem
m - numarul de tipuri resursa
-disponibil[m] - un vector care indica numarul de resurse disponibile pentru fiecare tip in parte;
-maxim [n][m] - o matrice care arata numarul maxim de cereri ce pot fi formulate de catre fiecare proces;
-alocare[n][m]- o matrice care arata numarul de resurse din fiecare tip de resurse care este alocat fiecarui proces;
-necesar[n][m] - o matrice care arata numarul de resurse care ar mai putea fi necesare fiecarui proces.
Daca necesar[i][j] = t , atunci procesul Pi ar mai avea nevoie de t elemente din resursa rj .
Avem relatia:
necesar[i][j] = maxim[i][j] - alocare[i][j]
-cerere[n][m]-matricea cererilor formulate de un proces
Daca cerere[i][j]= t, atunci procesul Pi doreste t elemente din resursa rj .
Algoritmul banchetului are urmatorii pasi:
Pas 1
Procesul Pi formuleaza o cerere de resurse. Daca linia i din matricea cerere este mai mare decat linia i din matricea necesar, atunci este eroare, deci nu se trece la pasul 2.
Precizam ca V1[n] < V2[n] , daca V1[i] < V2[i] pentru oricare i=1..n
if
cerere[i][x]<=necesar[i][x] 
x=
, → Pas2
else eroare
Pas 2
if cerere[i][x]<=disponibil[x] se trece la pas 3
else wait (resursele nu sunt disponibile)
Pas 3
Se simuleaza alocarea resurselor cerute de procesul Pi , starile modificandu-se astfel:
disponibil[x]=disponibil[x]-cerere]i][x];
alocare[i][x]=alocare[i][x]+cerere[i][x];
x=1..m
necesar[i][x]=necesar[i][x]-cerere[i][x];
Pas 4
In acest moment se testeaza daca noua stare este sigura sau nu. In acest scop se mai utilizeaza doi vectori:
lucru[m]
terminat[n]
Subpasul 1
Se initializeaza acesti vectori astfel:
lucru[i]=disponibil[i];
terminat[i]=fals
pentru i=1,2,3....n
Subpasul 2
Se cauta o valoare i astfel incat:
terminat[i]=fals;
necesar[i][x]<=lucru[x];
Daca nu exista, se trece la subpasul 4.
Subpasul 3
Se simuleaza incheierea executiei procesului, deci se executa:
lucru[x]=lucru[x]+alocare[i][x]
terminat = true;
Se trece la subpasul 2.
Subpasul 4
Daca:
terminat[i]=true pentru i=1..n ,
Atunci sistemul este intr-o stare sigura.
Algoritmul bancherului poate fi utilizat in orice sistem de alocare a resurselor, pentru determinarea starilor sigure, avand un mare grad de generalitate. Principalul sau dezavantaj este numarul mare de operatii pe care il cere.
b) Folosirea grafului de alocare a resurselor
O
alta metoda pentru determinarea unei stari sigure este folosirea
grafului de alocare a resurselor. Fata de graful prezentat anterior,
elementul nou este arcul revendicare. Acest arc arata ca este
posibil ca procesul Pi sa revendice in viitor resursa Rj
. Ca mod grafic de reprezentare , el este trasat cu linie intrerupta. Cand
procesul Pi cere resursa Rj , arcul revendicare (PiRj)
se transforma in arc cerere (PiRj). Cand resursa Rj
este eliberata de procesul Pj ,arcul alocare (PiRj)
este transformat in arc revendicare (PiRj). Pentru a
determina starile nesigure, se cauta in graf bucle in care intra
arcuri revendicare. O astfel de bucla reprezinta o stare
nesigura. Exemplu:
Fig. 4.4. Graf de alocare cu arcuri revendicative.
In graful de mai sus, procesului P1 ii este alocata resursa R1, iar procesului P2 ii este alocata resursa R2 . In acelasi timp procesul P1 poate sa ceara in viitor resursa R2 ceea ce in graf se concretizeaza prin arcul revendicare (P1R2). La fel, Procesul P2 poate revendica resursa R1 prin arcul (P2R1). Se observa ca exista o bucla (P1R2P2R1), ceea ce face ca aceste revendicari sa conduca la o stare nesigura.
4.3.Detectarea interblocarii si revenirea din ea
Atunci cand, din diverse motive, nu se pot aplica algoritmii de prevenire si evitare a interblocarii, se intra in aceasta stare. In acest caz trebuie sa se execute alte doua tipuri de algoritmi:
-algoritmi de detectie care sa informeze sistemul asupra momentului in care s-a ajuns la aceasta stare;
-algoritmi de revenire din starea de interblocare.
c)Detectia interblocarii
In acest scop se folosesc doi algoritmi:
-un algoritm foarte asemanator cu algoritmul bancherului;
-un graf de alocare a resurselor de tip WAIT FOR.
Deoarece algoritmul bancherului a fost discutat in amanunt, ne vom ocupa doar de graful WAIT FOR. Acest graf se obtine din graful de alocare a resurselor prin eliminarea nodurilor de tip resursa (Rj) si contopirea arcelor corespunzatoare. In acest caz, un arc (PiPj) arata ca Pi asteapta ca Pj sa elibereze resursa care ii este necesara.
Fig. 4.5.Graf de alocare a resurselor.
In acest caz, existenta buclei nu inseamna interblocare.
Fig.4.6.Graf WAIT FOR.
Algoritmul WAIT FOR se poate aplica numai pentru resurse simple.
Se observa ca bucla existenta in graful de alocare a resurselor este mai bine pusa in evidenta in graful WAIT FOR. Dar avantajul principal al utilizarii grafului WAIT FOR consta in costurile mai mici pentru detectia unei bucle, deci a interblocarii.
Indiferent de tipul algoritmului de detectie a interblocarii, se pune problema cat de des trebuie sa fie acesta apelat. Exista, in general, doua modalitati de apelare:
a)apelarea algoritmului ori de cate ori se formuleaza o cerere de resurse;
b)apelarea algoritmului la intervale regulate de timp.
Prima modalitate detecteaza rapid interblocarea dar presupune un substantial consum suplimentar de timp de calcul.
In a doua modalitate , se alege un interval de timp la care se apeleaza algoritmul de detectare. Desigur, un interval scurt va introduce costuri suplimentare iar la un interval lung este posibil ca starea de interblocare sa fie detectata foarte tarziu, cu consecinte nedorite in functionarea sistemului.
d) Revenirea din interblocare
Revenirea din interblocare se poate face in doua moduri:
-manual, facuta de catre operatorul sistemului;
-automat, executata de anumite programe ale sistemului de operare.
In general, exista doua metode de revenire din starea de interblocare:
1)-Prin disparitia asteptarii circulare; in acest caz se forteaza terminarea unor procese.
2)-Prin negarea achizitiei fortate; in acest caz procesele pot sa achizitioneze resurse de la alte procese.
1)Folosirea metodei de disparitie a asteptarii circulare are doua forme:
-Incheierea fortata a tuturor proceselor interblocate; in acest fel se revine sigur din starea de interblocare dar se pierd toate rezultatele fiecarui proces implicat in interblocare.
-Incheierea fortata a cate unui singur proces implicat in interblocare; in acest caz se incheie fortat un proces si apoi se apeleaza algoritmul de detectie a interblocarii pentru a vedea daca mai persista starea de interblocare; daca da, se incheie fortat alt proces si se apeleaza di nou algoritmul de detectie, operatia continuand pana la disparitia starii de interblocare. Avantajul fata de prima metoda este ca nu se pierd rezultatele de la toate procesele. Dezavantajul consta in timpul suplimentar, pentru ca, dupa terminarea fortata a unui proces, trebuie apelat algoritmul de detectie.
O alta problema a acestei metode este determinarea procesului sau proceselor care trebuiesc terminate fortat. Pot intra in discutie mai multi factori:
-prioritatea procesului;
-numarul resurselor care ar mai fi necesare procesului
pentru a-si incheia normal executia;
-numarul resurselor care au fost deja folosite de un proces;
-timpul necesar pana la terminarea normala a procesului.
Din enumerarea acestor factori, se observa ca este necesar un algoritm pentru alegerea procesului sau proceselor care vor fi terminate fortat. De obicei se alege factorul ce necesita un timp minim. Cel mai frecvent se utilizeaza alegerea dupa prioritate, cu atat mai mult cu cat prioritatea proceselor este deja calculata din algoritmii de planificare a procesorului.
2)Permiterea achizitionarii fortate a resurselor de la procese este a doua metoda de revenire din interblocare. Problemele care apar in acest caz sunt:
-alegerea "victimelor", ceea ce inseamna si selectarea resurselor care vor fi achizitionate fortat;
-continuarea procesului caruia i s-au preluat fortat resursele;
-prevenirea "infometarii", adica evitarea faptului ca un acelasi proces sa fie ales mereu victima.
4.4. Rezolvarea interblocarii in practica
De obicei, in mod practic, interblocarea poate fi tratata in doua moduri:
a)-prin ignorarea ei;
b)-printr-o metoda mixta de tratare.
Ignorarea se aplica, de exemplu, sistemelor de operare instalate pe PC-uri. Atat WINDOWS-ul cat si UNIX-ul ignora interblocarea, neavand programe pentru rezolvarea ei.
Exista sisteme de operare in care interblocarea ar duce la perturbatii grave in functionare, de exemplu, in unele sisteme de operare functionand in timp real. Acestor sisteme li se aplica metode mixte de tratare a interblocarii.
O metoda mixta clasica are la baza impartirea resurselor in clase de resurse ordonate ierarhic, asa cum am prezentat la prevenirea interblocarii pentru a impiedica asteptarea circulara. In acest mod, o eventuala interblocare ar putea aparea doar in interiorul unei clase.
In interiorul clasei se pot aplica metodele prezentate de prevenire, evitare, detectie si revenire din interblocare.
