Tehnici de tratare a deadlock-ului

A. Se permite apariţia deadlock-ului, se detectează şi se iau măsuri

B. Se evită dinamic deadlock-ul prin alocarea cu atenţie a

resurselor C. Se previne apariţia deadlock-ului prin negarea la nivel

structural a uneia din cele 4 condiţii de deadlock

A. Se permite apariţia deadlock-ului, se detectează şi se iau măsuri:

A.1 Algoritm pt. detectarea deadlock-ului când există câte o singură resursă de fiecare tip A.2 Algoritm pt. detectarea deadlock-ului când există mai multe resurse de fiecare tip

Detectarea unui deadlock se poate face: a) de fiecare dată când se solicită o resursă consum mare de timp CPU. b) la un anumit interval de timp sau atunci când gradul de utilizare CPU scade sub o valoare de prag.

A.3 Refacerea din deadlock

A1. Algoritm pt. detectarea deadlock-ului când există câte o singură resursă de fiecare tip Următorul algoritm inspectează un graf şi se termină când găseşte un ciclu sau când demonstrează că nu există nici unul. Algoritmul utilizează o listă a nodurilor (L) şi marchează arcele ce au fost inspectate. Pentru fiecare nod N al grafului: Consideră N nod de start, iniţializează L cu lista vidă şi setează toate arcele ca fiind nemarcate:

Pas 1. Adaugă nodul curent la L şi verifică dacă el apare de două ori în listă. Dacă da, graful conţine un ciclu şi algoritmul se termină. Pas 2. Verifică dacă, pentru nodul curent, există arce nemarcate de ieşire. Dacă da, se trece la pasul 3. Dacă nu, se trece la pasul 4. Pas 3. Alege un arc nemarcat de ieşire la întâmplare şi marchează arcul. Nodul în care intră arcul selectat devine nodul curent şi se revine la pasul 1. Pas 4. Elimină nodul curent din L. Nodul depus anterior în L devine nodul curent şi se revine la pasul 1. Dacă noul nod curent este nodul de start, atunci graful nu are cicluri conţinându-l pe N, şi se trece la următorul nod al grafului.

Exemplu Fie 7 procese (A G) şi 6 resurse (R W). Modul în care resursele sunt deţinute / solicitate este următorul:

Exemplu de aplicare a algoritmului anterior (nodurilor sunt alese de la stânga la dreapta şi de sus în jos, adică în ordinea R, A, B, C, S, D, T, E, F,…): Start = R: L = {R} L = {R,A} L = {R,A,S} L = {R,A} L = {R} - STOP Start = A L = {A} L = {A,S} L = { A } –STOP Start = B L = {B} L = {B,T} L = {B,T,E} …L = {B,T,E,V,G,U,D} L = {B,T,E,V,G,U,D,S} L = {B,T,E,V,G,U,D,T} – ciclu deadlock

A2. Algoritm pt. detectarea deadlock-ului când există mai multe resurse de fiecare tip Fie n procese, notate P1,…Pn şi m tipuri de resurse. Există resurse de tip 1, resurse de tip 2, ş.a.m.d. 1E 2ENotaţii:

1 2 mE E EE ; – vectorul resurselor existente, E

1 2 mA A AA A – vectorul resurselor disponibile, , unde jA

reprezintă numărul resurselor de tipul j disponibile, ; 1 j m

ijC C – matricea de alocare a resurselor, , reprezintă numărul resurselor de tip j deţinute de , ijC iP 1 i n , 1 j m ;

ijR R – matricea solicitărilor, ijR reprezintă numărul resurselor de tip j solicitate de , iP 1 i n , 1 j m .

Este satisfăcută relaţia: m1

, 1n

ij j ji

C A E j

Între doi vectori X şi Y de aceeaşi dimensiune m, se defineşte relaţia de ordine astfel: i iX Y X Y , 1 i m . Dacă X este o matrice, : denotă linia i a matricei. ,iX

Algoritm: Iniţial, toate procesele sunt nemarcate. Pe măsură ce algoritmul avansează, se marchează procese, indicând faptul că se pot termina şi deci, nu sunt în deadlock. La terminarea algoritmului, procesele nemarcate sunt în deadlock. Pas 1: Caută un proces nemarcat Pi astfel încât linia i din R, notată , satisface ,:iR ,:i R A . Pas 2: Dacă există un astfel de i, se adună linia i a matricei C la A, ,:i A A C , se marchează procesul Pi şi se reia pasul 1. Pas 3: Dacă nu există i de la pasul 1, se termină algoritmul.

Exemplu:

[4 2 3 1]; [2 1 0 0];0 0 1 0 2 0 0 1

.2 0 0 1 ; 1 0 1 00 1 2 0 2 1 0 0

E A

C R

Singurul proces care satisface cerinţa de la pasul 1 este P3, 3,: R A . După ce P3 se execută se ajunge la:

, şi P3 este marcat. 0 0 0

0

0

0 1 02 0 0 1 , [2 2 2 0]C A

Următorul proces ce se poate executa este P2, deoarece 2,: R A . După execuţia lui P2, se obţine:

1 , şi P2 este marcat. 0 0 0 00 0

0 0 1 0, [4

02

02 ]C A

În acest moment se poate executa şi P1, deoarece 1,: R A . După execuţia lui P1, se obţine:

0 0 0 0 şi P1 este marcat. 0 0 0 0

0 0, [4 3 2 1],

0 0C A

În sistem nu există deadlock.

A3. Refacerea sistemului din deadlock

Refacerea prin preempţie - preemptarea unei resurse de la procesul proprietar, şi suspendarea acestui proces - atribuirea acelei resurse unui alt proces - când al doilea proces îşi încheie execuţia, resursa este redată vechiului proprietar

Dezavantaj: preemptarea unei resurse este puternic dependentă de tipul acesteia

Refacerea prin rollback

- Se creează periodic puncte de verificare pentru toate procesele din sistem (checkpoints), prin salvarea stării proceselor într-un fişier. Fişierele nu sunt suprascrise.

- La dedectarea unui deadlock, se verifică resursele necesare refacerii. Un proces deţinând o astfel de resursă este readus la o stare anterioară solicitării resursei respective (resetat la un moment anterior de timp)

- Resursa este atribuită unui proces aflat în deadlock

Refacerea prin distrugere de procese Se distruge un procesul şi se eliberează resursele deţinute, în vederea ieşirii din deadlock. Alegerea procesului distrus...

B. Evitarea deadlock-ului

Stare sigură: O stare a unui sistem este sigură dacă nu corespunde unui deadlock şi există o ordine de planificare în care fiecare proces îşi poate termina execuţia chiar dacă toate procesele solicită simultan toate resursele necesare. Traiectoriile resurselor:

B1. Algoritmul bancherilor pt. un singur tip de resurse Procesele anunţă de la început nr. maxim de resurse necesare pt. a-şi termina execuţia. La fiecare cerere de resursă, se verifică dacă alocarea resursei conduce într-o stare sigură.

- dacă da, resursa se alocă - dacă nu, cererea este amânată

Exemple de stări sigure şi nesigure:

stare sigură stare sigură stare nesigură

Algoritm pt. a verifica dacă o stare este sigură (un singur tip de resurse): n procese (P1,…Pn), care utilizează un singur tip de resurse, numărul total de resurse fiind N Date cunoscute:

TnMMMM ... 21 , iM reprezintă numărul maxim de resurse necesare pentru terminarea procesului , iP iM N , 1 i n TnCCCC ... 21 vectorul de alocare a resurselor, , reprezintă numărul resurselor deţinute de , niC iP 1 i , C ≤ M

Se calculează: R = M – C , vectorul solicitărilor, iR reprezintă numărul resurselor solicitate de , iP 1 i n

n

iiCNA

1– numărul de resurse disponibile

Fie: , unde 1

1 2 0,1T nnF F F F 1iF dacă procesul s-a terminat şi în caz contrar, iP 0iF 1 i n

Algoritm: Se iniţializează 0iF , 1 i n . Pas 1: Cât timp în vectorul F mai există elemente nule, caută i astfel încât 0iF şi iR A . Dacă nu există i, STOP starea NU este sigură. Dacă există i, se trece la pasul 2. Pas 2: (i) se evaluează: i iC M , iA A R , 0iR . (ii) se calculează: iA A C , 0iC , 0iM . (iii) 1.iF Se reia pasul 1. Pas 3: Dacă , n1iF 1 i , atunci starea este sigură.

Problemă: Fie 3 procese P1, P2 şi P3 şi 10N resurse de acelaşi tip. Nr. maxim de resurse ce pot fi cerute de procese: T M 7 ,4 ,9 Care din următoarele două stări este sigură? Dacă starea este sigură, ce secvenţă de alocare rezultă în urma aplicării algoritmului anterior? Starea 1: TC 2 2, ,3 Starea 2: TC 2 2, ,4 Idee rezolvare: Pt. Starea 1, la începutul rulării algoritmului:

C M R F P1 3 9 6 0 P2 2 4 2 0 P3 2 7 5 0

A = 3 Ce proces este selectat întâi, şi cum se modifică tabelul de mai sus? Continuaţi până algoritmul se termină.

B2. Algoritmul bancherilor pt. mai multe tipuri de resurse Algoritmul este foarte asemănător cu cel pt. detectarea deadlock-ului pt. mai multe resurse de fiecare tip (secţiunea A2). Fie n procese, notate P1,…Pn şi m tipuri de resurse. Există resurse de tip 1, resurse de tip 2, ş.a.m.d. 1E 2ESe dau:

– vectorul resurselor existente, E 1 2 mE E EE

;

ijMM – matricea maximelor, reprezintă numărul maxim de resurse de tip j solicitate de , 1 i n , 1 j m . ijM iP

ijC C – matricea de alocare a resurselor, , reprezintă numărul resurselor de tip j deţinute de , ijC iP 1 i n , 1 j m Se calculează: A – vectorul resurselor disponibile, 1 2 mA A AA , unde jA reprezintă numărul resurselor de tipul j disponibile,

1 j m : ;

n

iijjj CEA

1

ijR R – matricea solicitărilor, ijR reprezintă numărul resurselor de tip j solicitate de , iP 1 i n , 1 j m . Se presupune că fiecare proces solicită toate resursele necesare execuţiei sale, adică: CMR .

Fie: – 1

1 2 0,1T nnF F F F 1iF dacă procesul s-a terminat şi iP 0iF în caz contrar, 1 i n .

Notaţii:

Dacă X este o matrice, : denotă linia i a matricei ,iX

Între doi vectori X şi Y de aceeaşi dimensiune m, se defineşte relaţia de ordine astfel: i iX Y X Y , 1 i m .

Algoritm:

Se iniţializează 0iF , n1 i . Pas 1: Cât timp în vectorul F mai există elemente nule,

0 - caută i astfel încât iF şi ,:i R A . Dacă nu există i, STOP starea NU este sigură. Dacă există i, se trece la pasul 2. Pas 2. Marchează procesul i ca terminat, 1iF , şi ,:i A A C , ,:i R 0 , 0i,:C . Treci la pasul 1. Pas 3. Dacă toate procesele sunt marcate ca terminate, , 1iF 1,i n stare sigură

Exemplu:

Starea curentă (iniţială): , , 2436E

0201A

01121111012421201114

M

00001011011100101103

C

se calculează: ,

01120100001321100011

R

Rularea algoritmului:

0 0 0 0 0F , poate fi ales doar procesul 4:

3 0 1 1 1 1 0 00 1 0 0 0 1 1 2

4 : , , 2 1 2 11 1 1 0 3 1 0 0

0 0 0 0 2 1 10 0 0 0 0 0 0 0

00 0 0 1 0

i

C R A

F

-> următorul proces ce poate fi ales este 1 sau 5; alegem procesul 5

3 0 1 1 1 1 0 00 1 0 0 0 1 1 2

5 : , , 2 1 2 11 1 1 0 3 1 00 0 0 0 0 0 0 00 0 0 0 0 0 0

0

0 0 00

1 1

i

C R A

F

0 0 0 0 0 0 00 1 0 0 0 1 1 2

1: , , 5 1 3 21 1 1 0 3 1

0

0 0 0 0 0 0 0 00 0 0 0 0 0

0 0

1 0 0 1 10 0

i

C R A

F

0 1 0 0 0 1 10 0 0 0 0 0 0 00 0 0 0 0 0 0 00 0 0 0 0 0

23: , , 6 2 4 2

1 0 1 10 0

1

i

C R A

F

0 0 0 0 0 0 0 0

2 : 6 3 4 2 , 1 1 1 1 1i A F

Starea este sigură. Dacă se alocă resursele în ordinea P4, P5, P1, P3, P2 toate procesele îşi încheie execuţia.

C. Prevenirea deadlock-ului Există 4 condiţii prezentate care duc la producerea fenomenului de deadlock. Dacă se invalidează cel puţin una dintre cele 4 condiţii, se previne apariţia deadlock-ului.

1. Invalidarea condiţiei de excludere mutuală Nici o resursă nu este atribuită exclusiv unui proces. În general soluţie neviabilă (excluderea mutuală era necesară pt. folosirea corectă a resurselor partajate – vezi cursurile anterioare).

2. Invalidarea condiţiei de “hold & wait” Un proces care deţine resurse nu trebuie să solicite alte resurse. Se poate realiza prin 2 modalităţi: a) Se cere fiecărui proces să solicite toate resursele de care are nevoie la lansarea în execuţie. Dacă toate resursele

necesare sunt disponibile, ele vor fi alocate procesului şi procesul se poate executa. Dacă cel puţin o resursă nu este disponibilă, nici o resursă nu va fi alocată procesului şi procesul va trebui să aştepte. Dezavantaje:

- pentru multe procese, resursele necesare sunt cunoscute abia în momentul în care se execută; - resursele nu sunt utilizate optimal.

b) Se cere unui proces să elibereze toate resursele deţinute înainte de a solicita alte resurse.

3. Invalidarea condiţiei de nepreempţiune

Dacă un proces P solicită resurse, se verifică dacă resursele sunt disponibile. În caz afirmativ, procesul primeşte resursele. Dacă resursele nu sunt disponibile, ci sunt alocate unui alt proces Q care aşteaptă să primească alte resurse, atunci resursele solicitate de P vor fi luate de la procesul Q şi acordate lui P. Strategia poate fi aplicată pe resurse ce pot fi salvate şi restaurate cu uşurinţă (exemplu procesor, memorie), dar nu poate fi aplicată pe resurse nepreemptibile (exemplu imprimantă, unităţi de bandă magnetică).

4. Invalidarea condiţiei de aşteptare circulară Condiţia de aşteptare circulară poate fi invalidată dacă se ordonează tipurile de resurse şi fiecare proces solicită resurse în ordinea crescătoare enumerării. Fie 1 2, , , mR R R R mulţimea tipurilor de resurse. Se asignează fiecărui tip de resursă un număr întreg unic ce va fi utilizat pentru a decide dacă o resursă precede o altă resursă. Formal, se defineşte funcţia bijectivă NRF : , care asociază fiecărui tip de resursă un număr natural. Un proces care deţine una sau mai multe instanţe ale resursei de tip Ri poate solicita instanţe ale resursei Rj doar dacă F(Rj) > F(Ri). Dacă un proces are nevoie de mai multe resurse de acest tip, el trebuie să le solicite cu un singur apel sistem. Se mai poate impune restricţia ca un proces care solicită resurse de tip Rj să fi eliberat înainte resursele de tip Ri cu F(Ri) > F(Rj). Dacă sunt respectate aceste restricţii, graful resurselor nu poate avea cicluri.

Dacă F(R1) < F(R2), procesul B nu poate solicita resursa de tip R1. Dacă F(R1) > F(R2), procesul A nu poate solicita resursa de tip R2.

În concluzie, nu se poate ajunge la deadlock.

Exemplu de invalidare a condiţiei 4:

A

R2

B

R1