Resource Allocation Graphs

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

Un Resource Allocation Graph (in breve RAG) è un modello astratto per la determinazione e la rappresentazione di eventuali situazioni di deadlock. Il RAG è un grafo $G(V,E)$ dove:

$V$ indica il numero di nodi: cerchi per indicare i processi e rettangoli per indicare le risorse; all'interno dei rettangoli verranno indicate con dei pallini il numero di istanze corrispondenti a tale risorsa.
$E$ indica il numero di archi: dal processo (cerchio) alla risorsa (rettangolo) significa che il processo richiede tale risorsa; dalla risorsa al processo indica che tale risorsa è detenuta da quel processo. Gli archi possono essere orientati e vengono indicati con una freccia.

Se il RAG non contiene cicli, non sono presenti deadlock. Se presenta cicli, possiamo distinguere due casi:

La risorsa ha una sola istanza, pertanto si avrà una situazione di deadlock.
Ci sono più istanze, allora la determinazione del deadlock dipende dallo schema di allocazione.

Una tecnica di prevenzione del deadlock è la prevenzione dinamica; tale tecnica consta di due alternative: algoritmo del banchiere o algoritmo con RAG (utilizzabile solo nel caso in cui le risorse presentano una sola istanza).

Per la seconda alternativa, ovvero l'algoritmo con RAG, si aggiunge una nuova tipologia di arco nel RAG: un arco tratteggiato dal processo alla risorsa, che significa che tale processo potrebbe richiedere tale risorsa. L'algoritmo con RAG quindi può distinguere situazioni dette safe, se non sono presenti cicli, e situazioni dette unsafe, se sono presenti cicli nel RAG. Non sempre uno stato unsafe significa presenza di deadlock, ma il deadlock si può verificare solo in uno stato di unsafe.
Tale algoritmo presenta una complessità $O(n^{2})$ , dove $n$ indica il numero di processi.