Resource Allocation Graphs
Un Resource Allocation Graph (in breve RAG) è un modello astratto per la determinazione e l'eliminazioni di situazioni di deadlock. Il RAG è un grafo dove:
- 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 corrisondenti a tale risorsa.
- 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.
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.