Grafice de alocare a resurselor

Exemplu de RAG. V = {(P1, P2, P3), (R1, R2, R3)} E = {R1 -> P1, R2 -> P2, R3 -> P2, P3 -> R3}

Un grafic de alocare a resurselor ( RAG pe scurt) este un model abstract pentru determinarea și reprezentarea posibilelor situații de impas . RAG este un grafic $G(V,E)$ ${\ displaystyle G (V, E)}$ ${\ displaystyle G (V, E)}$ unde este:

$V.$ ${\ displaystyle V}$ $V.$ indică numărul de noduri: cercuri pentru a indica procese și dreptunghiuri pentru a indica resurse; în interiorul dreptunghiurilor, numărul instanțelor corespunzătoare acestei resurse va fi indicat cu puncte.
$ȘI$ ${\ displaystyle E}$ $ȘI$ indică numărul de arce: de la proces (cerc) la resursă (dreptunghi) înseamnă că procesul necesită această resursă; de la resursă la proces indică faptul că resursa respectivă este deținută de acel proces. Arcurile pot fi orientate și sunt indicate cu o săgeată.

Dacă RAG nu conține bucle, nu există blocaje . Dacă are cicluri, putem distinge două cazuri:

Resursa are o singură instanță , deci va exista o situație de impas.
Există mai multe instanțe , deci determinarea blocajului depinde de schema de alocare.

O tehnică de prevenire a blocajului este prevenirea dinamică ; această tehnică constă din două alternative: algoritmul bancherului sau algoritmul cu RAG (care poate fi utilizat numai dacă resursele au o singură instanță).

Pentru a doua alternativă, adică algoritmul cu RAG, se adaugă un nou tip de arc în RAG: un arc punctat de la proces la resursă, ceea ce înseamnă că acest proces ar putea necesita această resursă. Prin urmare, algoritmul cu RAG poate distinge situațiile numite sigure , dacă nu există cicluri, și situațiile numite nesigure , dacă există cicluri în RAG. O stare nesigură nu înseamnă întotdeauna că există un impas, dar impasul poate apărea doar într-o stare nesigură .
Acest algoritm prezintă o complexitate $O(n^{2})$ ${\ displaystyle O (n ^ {2})}$ $O (n ^ {2})$ , unde este $n$ ${\ displaystyle n}$ $n$ indică numărul de procese.

Bibliografie

Abraham Silberschatz, Peter Baer Galvin, Greg Gagne, "Sisteme de operare. Concepte și exemple", Pearson, 2014.