Questa voce è orfana, ovvero priva di collegamenti in entrata da altre voci.

Inseriscine almeno uno pertinente e utile e rimuovi l'avviso. Segui i suggerimenti del progetto di riferimento.

Questa voce o sezione sull'argomento sistema operativo non cita le fonti necessarie o quelle presenti sono insufficienti.

---

Puoi migliorare questa voce aggiungendo citazioni da fonti attendibili secondo le linee guida sull'uso delle fonti.

Questa voce o sezione sull'argomento informatica non è ancora formattata secondo gli standard.

---

Contribuisci a migliorarla secondo le convenzioni di Teknopedia. Segui i suggerimenti del progetto di riferimento.

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 ${\displaystyle G(V,E)}$ dove:

• ${\displaystyle 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.
• ${\displaystyle 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:

1. La risorsa ha una sola istanza, pertanto si avrà una situazione di deadlock.
2. 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à ${\displaystyle O(n^{2})}$, dove ${\displaystyle n}$ indica il numero di processi.

• Abraham Silberschatz, Peter Baer Galvin, Greg Gagne, "Sistemi operativi. Concetti ed esempi", Pearson, 2014.

Portale Informatica: accedi alle voci di Teknopedia che trattano di informatica