Pentru a recunoaște o stare de blocaj, este necesar ca fiecare proces să determine dacă va fi vreodată capabil să se dezvolte din nou, adică să-și schimbe stările. Din moment ce suntem interesați de posibilitatea dezvoltării procesului și nu de procesul de schimbare a statului în sine, este suficient să se ia în considerare numai cele mai favorabile schimbări ale statului.
Evident, un proces deblocat (care tocmai a primit o resursă și, prin urmare, nu este blocat) după un timp eliberează toate resursele sale și apoi se termină în siguranță. Scutirea resurselor ocupate anterior poate "trezi" unele procese blocate anterior, care, la rândul lor, în curs de dezvoltare, vor putea elibera alte resurse ocupate anterior. Acest lucru poate continua până când nu există procese deblocate sau un anumit număr de procese rămâne în continuare blocat. În cel de-al doilea caz (dacă există procese blocate la sfârșitul secvenței de acțiuni specificate), starea inițială S este starea de blocare, iar procesele rămase sunt într-un blocaj în starea S. Altfel S nu este o stare de blocaj.
Detectarea unui blocaj prin reducerea graficului resurselor reutilizabile
Condițiile cele mai favorabile pentru un proces deblocat Pi pot fi reprezentate prin reducerea (reducerea) graficului resurselor reutilizabile (vezi prima secțiune a acestui capitol, o descriere a modelului Holt). Reducerea graficului poate fi descrisă după cum urmează:
Graficul grafic al resurselor reutilizabile este scurtat de procesul Pp, care nu este nici blocat, nici vertex izolat, eliminând toate marginile care intră în vertexul Pi și lăsând Pi. Această procedură este echivalentă cu achiziționarea, de către procesul Pi, a anumitor resurse la care a solicitat anterior și apoi eliberarea tuturor resurselor sale. Apoi Pi devine un vertex izolat.
Graficul resurselor reutilizabile nu este redus (nu este redus), dacă nu poate fi redus prin nici un proces.
Graficul grafic al resurselor de tipul RS este abreviat complet dacă există o serie de abrevieri care șterg toate arcile din grafic.
Dăm o lemă care ne permite să propunem algoritmi pentru detectarea unui punct mort.
Lema. Pentru resursele de tip SR, ordinea contracțiilor este imaterială; toate secvențele duc la același grafic incontractibil.
Dovada. Să presupunem că lema este falsă. Apoi, trebuie să existe un non-stat este S, care este redusă la o anumită co-picioare S1 ireductibilă prin secvențe seq1 și la o sostoyaniyaS2 ireductibilă - folosind posledovatelnostiseq2 deci chtoS1 S2 (adică, toate procesele din sostoyaniyahS1 IS2 sau blocate sau izolate).
Dacă vom face această presupunere, atunci vom ajunge la o contradicție, care este eliminat numai în măsura în care S1 = S2. Într-adevăr, să presupunem că secvența seq1 constă într-o listă ordonată de procese (P1, P2, Pk). Apoi secvența seq1 trebuie să conțină procesul P, care nu este conținut în secvența seq2. În caz contrar, S1 = S2. deoarece reducerea graficului elimină numai arcul, existent într-o stare de S, iar în cazul în care secvențele de seq1 iseq2 conțin același set de proces-bufnițele (deși într-o ordine diferită), acesta trebuie să fie eliminate în același set de arce. Și dovada va arăta prin inducție că PPi (i = 1,2, k) duce la contradicția indicată de noi.
P P1. deoarece vârful S poate fi redus prin procesul P1. prin urmare, starea S2 trebuie să conțină și procesul P1.
Fie P Pi. (i = 1, 2. j). Cu toate acestea, deoarece după reducerea prin procesele Pi (i = 1, 2. j), este posibil să se reducă graficul prin procesul Pj + 1. același lucru ar trebui să fie valabil și pentru secvența secvenței seq2, indiferent de secvența proceselor. Același set de margini ale graficului este șters de procesul Pi. Astfel, PPj + 1
Prin urmare, P Pi pentru i = 1, 2. k și P nu pot exista și acest lucru contrazice presupunerea noastră că S1 S2. Prin urmare, S1 = S2.
Teorema impasului. Stare Există o stare de blocaj dacă și numai dacă graficul de resurse reutilizabile în starea S nu este complet reductibil.
a) Să presupunem că starea S este o stare finală și procesul Pi este la un punct mort în S. Apoi pentru toate Sj. astfel încât S
b) Să presupunem că S nu este complet reductibil. Apoi, există un proces Pi. care rămâne blocat pentru toate secvențele posibile de operații de reducere în conformitate cu lema. Deoarece orice secvență de operații de reducere conta de resurse reutilizabile, se încheie o condiție ireductibilă se asigură că toate resursele tipaSR care pot fi vreodată puse la dispoziție, în fapt, viespi vobozhdeny apoi protsessPi blocat permanent și, prin urmare, este într-un impas.
Corolar 1. Procesul Pi nu se află la capăt, dacă și numai dacă seria contracțiilor conduce la o stare în care Pi. nu este blocat.
Corolarul 2. Dacă S este o stare de sfârșit de sfârșit (pentru resurse de tip SR), atunci cel puțin două procese sunt la un sfârșit de capăt în S.
Din teorema blocajului, algoritmul de detecție a blocării este urmat direct. Trebuie doar să încercați să reduceți graficul cât mai eficient posibil; dacă graficul nu este complet contractat, atunci starea inițială a fost o stare de blocaj pentru acele procese ale căror noduri au rămas în graficul necorectat. Lemma luată în considerare ne permite să organizăm convenabil contracțiile.
Graficul grafic al resurselor reutilizabile poate fi reprezentat fie de matrice, fie de liste. În ambele cazuri, economiile de memorie poate fi realizată cu ajutorul unei multigraphs orientate ponderate (comasarea unor arce obțin sau arce de interogare între o anumită resursă și date de proces într-un singur arc cu o greutate corespunzătoare care determină numărul de unități de resurse).
Luați în considerare varianta cu reprezentarea matricei. Deoarece graficul este bipartit, acesta este reprezentat de două matrici de dimensiune nm. O matrice matrice de distribuție D = || || dij, unde elementul dij reflectă suma edinitsRj resursă alocată procesului estdij Pi = | (Rj, R;) |, unde (Rj, Pi) - este un arc între nodurile Rj IPI . conducând de la Rj la Pi. A doua matrice este o matrice-Lock cos N = || || NIJ, gdenij = | (P i, Rj) |.
Dacă utilizați liste legate pentru a afișa aceeași structură, puteți construi două grupuri de liste. Resursele alocate unui anumit proces Pi. sunt asociate cu Pointer:
În mod similar, resursele solicitate de procesul Pi. sunt conectate împreună.
Liste similare sunt create pentru resurse (liste de resurse distribuite și solicitate).
Pentru ambele concepte este, de asemenea, convenabil de a avea un tablou unidimensional de unități de resurse disponibile (. R1, r2 rm), Gderi indică numărul de unități disponibile (nealocat-guvernamentale resursaRi estri = |. Ri | - | (Ri, Pk) |.
Fiecare test necesită testarea resurselor m. Astfel, timpul de execuție al unui astfel de algoritm în cel mai rău caz este proporțional cu mn2.
Un algoritm mai eficient poate fi obținut prin stocarea unor informații suplimentare despre interogări. Pentru fiecare vârf al procesului Pi, se determină așa-numita așteptare a contorului wi. care afișează numărul de resurse (nu numărul de unități al resurselor), care la un moment dat determină blocarea procesului. În plus, puteți salva pentru fiecare cerere de resurse, ordonată după dimensiune (numărul de unități din resursă). Apoi următorul algoritm de abreviere scris pe pseudocod are un timp de execuție maxim proporțional cu mn.
Pentru toate P L face
Începeți pentru toate Rj | (Rj. P) |> 0 face
Aici, L este lista curentă de procese care pot efectua reducerea graficului. Putem spune că L: = i wi = 0>. Programul selectează procesul P din lista L, procesul P scurtează graficul, mărind numărul de unități disponibile jj ale tuturor resurselor Rj. distribuit procesului P, actualizează contorul de așteptare wi al fiecărui proces Pi care poate satisface cererea sa către resursa privată Rj. și adaugă Pi la L dacă numărul de așteptare devine zero.