Algoritmul bancherului

Algoritmul bancherului este un algoritm utilizat pentru a evita blocajele în alocarea resurselor . În special, acest algoritm poate indica dacă un sistem - în special un sistem de operare - s-ar găsi într-o stare sigură sau nu dacă ar atribui o resursă unuia dintre procesele solicitante.

Complexitatea de calcul a acestui algoritm este $O(n^{2}m)$ ${\ displaystyle O (n ^ {2} m)}$ $O (n ^ {2} m)$ , unde este $n$ ${\ displaystyle n}$ $n$ este numărul de procese și $m$ ${\ displaystyle m}$ $m$ numărul de tipuri de resurse (mai multe resurse pot fi disponibile pentru fiecare tip - de exemplu, două imprimante echivalente, porturi de comunicații etc.).

Concept de bază

Un sistem, în alocarea resurselor solicitate, trebuie să procedeze așa cum ar face o bancă : procesele sunt văzute ca clienți care pot solicita credit de la bancă (până la o anumită limită individuală), iar resursele alocabile sunt văzute ca bani.

Este clar că sistemul, la fel ca banca, nu poate permite tuturor clienților să își atingă limita de credit în același timp, deoarece banca ar eșua (iar sistemul nu ar putea aloca suficiente resurse, provocând un impas).

Operațiune

Patru tablouri sunt utilizate pentru a stoca următoarele informații apelând $m$ ${\ displaystyle m}$ $m$ numărul de resurse disponibile, $k_{i}$ ${\ displaystyle k_ {i}}$ $k_ {i}$ numărul de instanțe ale primei resurse, e $n$ ${\ displaystyle n}$ $n$ numărul de procese active:

matrice de resurse disponibile $D[m]$ ${\ displaystyle D [m]}$ $D [m]$ : cu $De_{i}=k_{i}$ ${\ displaystyle De_ {i} = k_ {i}}$ $De_ {i} = k_ {i}$ stochează cantitatea fiecărui tip de resursă disponibilă pe sistem
matrice de resurse alocate $A[m\times n]$ ${\ displaystyle A [m \ times n]}$ $A [m \ times n]$ : cu $e_{j}^{'}A=A_{j}$ ${\ displaystyle e_ {j} ^ {'} A = A_ {j}}$ $e_ {j} ^ {{'}} A = A_ {j}$ vector care indică câte instanțe din fiecare resursă au fost atribuite procesului $P_{j}$ ${\ displaystyle P_ {j}}$ $Pijamale}$
matrice de resurse maxime $M[m\times n]$ ${\ displaystyle M [m \ times n]}$ $M [m \ ori n]$ : cu $e_{j}^{'}M=M_{j}$ ${\ displaystyle e_ {j} ^ {'} M = M_ {j}}$ $e_ {j} ^ {{'}} M = M_ {j}$ vector care indică câte instanțe din fiecare resursă vor fi solicitate cel mult de către proces $P_{j}$ ${\ displaystyle P_ {j}}$ $Pijamale}$ pentru a finaliza calculul
matrice de resurse reziduale $N[m\times n]$ ${\ displaystyle N [m \ times n]}$ $N [m \ ori n]$ : cu $e_{j}^{'}N=N_{j}$ ${\ displaystyle e_ {j} ^ {'} N = N_ {j}}$ $e_ {j} ^ {{'}} N = N_ {j}$ vector care indică câte instanțe din fiecare resursă sunt necesare procesului $P_{j}$ ${\ displaystyle P_ {j}}$ $Pijamale}$ pentru a-și finaliza calculul (calculat prin scăderea matricei atribuite din matricea maximă).

Metodă

Algoritmul continuă iterativ, garantând resursele necesare proceselor care, comparând matricea lor de Necesități cu cea a resurselor disponibile în prezent în sistem, își pot finaliza execuția. După executare, procesul eliberează resursele pe care le-a alocat anterior (adică matricea de resurse alocate procesului se adaugă resurselor disponibile). În acest fel, algoritmul poate selecta un proces suplimentar care, cu resursele disponibile în prezent pentru sistem, poate termina și, la rândul său, elibera resursele alocate. Putem împărți algoritmul în două părți principale: partea de verificare a stării curente și partea de simulare a atribuirii. Verificarea stării curente va asigura că alocarea resurselor curente către procese este o alocare care menține sistemul într-o stare sigură. O stare este definită ca sigură dacă există o secvență de planificare a proceselor $<P_{i},P_{j},P_{n},....P_{k}>$ ${\ displaystyle <P_ {i}, P_ {j}, P_ {n}, .... P_ {k}>}$ $<P_ {i}, P_ {j}, P_ {n}, .... P_ {k}>$ care asigură încetarea întregului set de procese care rulează în prezent. Partea de simulare a sarcinii va rula atunci când un proces $P_{j}$ ${\ displaystyle P_ {j}}$ $Pijamale}$ va necesita resurse. Algoritmul va simula această atribuire și apoi va rula o verificare a stării pentru a vă asigura că atribuirea vă permite să vă aflați într-o stare sigură.

Verificați starea

Este $F[n]$ ${\ displaystyle F [n]}$ $F [n]$ o serie de valori booleene $(false,true)$ ${\ displaystyle (false, true)}$ $(fals adevarat)$ unde fiecare variabilă este inițial falsă și definim L ca. $L[m]=D[m]$ ${\ displaystyle L [m] = D [m]}$ $L [m] = D [m]$
găsiți un index $j$ ${\ displaystyle j}$ $j$ astfel încât $F_{j}=false$ ${\ displaystyle F_ {j} = false}$ $F_ {j} = fals$ Și $L\geq N_{j}$ ${\ displaystyle L \ geq N_ {j}}$ $L \ geq N_ {j}$ dacă acest lucru nu există, treceți la pasul 4
cere $L=L+A_{j}$ ${\ displaystyle L = L + A_ {j}}$ $L = L + A_ {j}$ , $F_{j}=true$ ${\ displaystyle F_ {j} = adevărat}$ $F_ {j} = adevărat$ și treceți la pasul 2
de sine $F_{j}==true$ ${\ displaystyle F_ {j} == adevărat}$ $F_ {j} == adevărat$ pentru fiecare i, atunci sistemul este într-o stare sigură

Simularea atribuirii

Să presupunem procesul $P_{j}$ ${\ displaystyle P_ {j}}$ $Pijamale}$ necesită resurse noi. Este $R_{j}[m]$ ${\ displaystyle R_ {j} [m]}$ $R_ {j} [m]$ vectorul de solicitare a procesului astfel încât $R_{j}e_{i}=k_{i}$ ${\ displaystyle R_ {j} e_ {i} = k_ {i}}$ $R_ {j} e_ {i} = k_ {i}$ numărul de instanțe ale primei resurse solicitate de $P_{j}$ ${\ displaystyle P_ {j}}$ $Pijamale}$

Verific asta $R_{j}\leq N_{j}$ ${\ displaystyle R_ {j} \ leq N_ {j}}$ ${\ displaystyle R_ {j} \ leq N_ {j}}$ dacă acest lucru este fals, generez o eroare, deoarece procesul a necesitat mai multe resurse decât poate solicita
Verific asta $D\geq R_{j}$ ${\ displaystyle D \ geq R_ {j}}$ $D \ geq R_ {j}$ în cazul în care acest lucru este fals, nu accept cererea procesului $P_{j}$ ${\ displaystyle P_ {j}}$ $Pijamale}$ din lipsa resurselor
Simulez misiunea prin plasare $A_{j}=A_{j}+R_{j}\;\;\;\;D=D-R_{j}\;\;\;\;N_{j}=N_{j}-R_{j}$ ${\ displaystyle A_ {j} = A_ {j} + R_ {j} \; \; \; \; D = D-R_ {j} \; \; \; \; N_ {j} = N_ {j} -R_ {j}}$ $A_ {j} = A_ {j} + R_ {j} \; \; \; \; D = D-R_ {j} \; \; \; \; N_ {j} = N_ {j} -R_ { j}$ și execut prima parte a algoritmului pentru a verifica dacă este o sarcină sigură, dacă nu este, resping cererea pentru $P_{j}$ ${\ displaystyle P_ {j}}$ $Pijamale}$

Rezultat

Algoritmul poate decide că sistemul este într-o stare sigură dacă, prin încercările sale repetate de a găsi o ordine de execuție a proceselor, descoperă o secvență prin care toate $n$ ${\ displaystyle n}$ $n$ procesele sunt alocate resurse prin încheierea executării lor.

Stare sigură

Conceptul de stare sigură a fost introdus de Edsger W. Dijkstra probabil în 1965 (sau 1966) când și-a dezvoltat sistemul de operare multiprogramabil THE (Technische Hogeschool Eindhoven). O descriere formală poate fi dată de următoarea afirmație (în pseudocod C ++):

 dacă (
    Initial_State == SECURE &&
    All_Commands == SECURE &&
    All_Transactions == SECURE &&
    Toate_Axiomele == adevărat
) System_State = SECURE

Prin urmare, starea sigură este o stare în care este posibil să se aloce toate resursele necesare unui proces, fără ca acesta din urmă să conducă la un blocaj cu un alt proces. Faptul că sistemul se află într-o stare sigură nu implică faptul că toate alocările de resurse vor avea succes, ci doar că există cel puțin o modalitate sigură de a aloca toate resursele. Dacă sistemul se află într-o stare sigură, impasul poate fi evitat, dar evident o stare nesigură nu implică neapărat un impas. De fapt, sistemul poate evita complet standurile dacă la fiecare cerere de resursă printr-un proces, verifică starea în care ar fi, alocând resursa. Dacă starea viitoare este sigură, atunci resursa poate fi alocată în siguranță. Pentru aceasta poate fi utilizat algoritmul bancherului.

Acest concept este dificil de implementat pe sistemele moderne, atât pentru că nu este posibil să se prevadă într-un mod determinist alocarea resurselor, așa cum este cerut de algoritmul bancherului, cât și pentru că ar fi prea costisitor din punct de vedere economic. Majoritatea sistemelor de operare, începând de la Unix , nu iau în considerare problema unui blocaj, deoarece este de fapt un eveniment foarte rar, având în vedere abundența resurselor disponibile. Mai mult, ar trebui adăugat că, în zilele noastre, managementul blocajului este cu siguranță mai critic în bazele de date decât în sistemele de operare .

Elemente conexe

Bibliografie

Een algorithme ter voorkoming van de dodelijke omarming.

Portal IT

Portalul de matematică