# Grafo delle attese

In informatica, il grafo delle attese (anche detto grafo di Holt), è un grafo orientato diretto. Introdotto a partire dal 1972, è usato per rappresentare gli stati di allocazione tra risorse e processi al fine di evitare uno stallo.

## Descrizione

Il grafo delle attese è costituito da una coppia $(V,E)$, dove $V$ è l'insieme dei nodi ed $E$ l'insieme degli archi. L’insieme $V$ è partizionato in due parti:
* $P=\{P_{1},P_{2},...,P_{n}\}$, che rappresenta tutti i processi appartenenti al sistema;
* $R=\{R_{1},R_{2},...,R_{n}\}$, che rappresenta le risorse.
Gli archi all’interno del grafo possono essere di due tipologie:
* Un arco che va da un nodo di tipo processo ad uno di tipo risorsa, chiamato arco di richiesta, rappresenta la richiesta e successivamente l’assegnazione della risorsa $(P_{i}\to R_{j})$;
* Un arco che va da una risorsa ad un processo, chiamato arco di assegnazione, indica che quest’ultima è momentaneamente già assegnata ad un altro processo. Questa tipologia di stato può essere evitata nel caso in cui i singoli processi vengano eseguiti in maniera sequenziale, ovvero permettendo l’esecuzione in ordine di arrivo della richiesta $(R_{j}\to P_{i})$.
All’interno del grafo, le risorse e i processi sono rappresentati mediante due tipologie di nodi:
* Le risorse vengono rappresentate tramite una forma rettangolare;
* I processi vengono rappresentati tramite una forma circolare.
Ciascuna risorsa all'interno del grafo può possedere più di un'unità utilizzabile, definita istanza. Si effettua così una partizione della risorsa stessa indicando la molteplicità con punti all'interno della rappresentazione grafica del nodo della risorsa. Ciascuna istanza può essere associata soltanto ad un processo per volta.

## Tipologie di risorse

All'interno del grafo si possono riscontrare principalmente due tipologie differenti di risorse:
Le risorse riutilizzabili, che si contraddistinguono tramite le seguenti caratteristiche:
* Una determinata unità di una risorsa può essere assegnata, al massimo, ad un processo per volta;
* Le unità non possono essere prevenute; una volta che un processo ha acquisito un'unità, l'unità non sarà disponibile fino a quando non verrà rilasciata dal processo stesso.
Esempi di risorse riutilizzabili possono essere dispositivi fisici come i dischi e i nastri di memoria.
La seconda tipologia è quella delle risorse consumabili:
* All’interno di esse non esiste un numero definito di istanze disponibili;
* Ogni volta che viene acquisita un'unità di una risorsa, essa cessa di esistere e verrà resa di nuovo disponibile soltanto dopo il rilascio da parte del processo.
La differenza principale tra le risorse riutilizzabili e quelle consumabili è che le unità di una risorsa riutilizzabile non vengono mai create o distrutte, ma ne viene modificato lo stato, il quale può identificarsi come "richiesto", "acquisito" o " rilasciato". Invece, le unità di ciascuna risorsa consumabile vengono create e distrutte ogni volta che vengono richieste e rilasciate.

## Rappresentazione grafica

Il grafo delle attese permette di analizzare anche i casi di deadlock, ovvero quando uno o più processi si trovano in una situazione di blocco aspettando l’esecuzione di una particolare azione, come il rilascio di una risorsa. Un caso di deadlock viene rappresentato tramite la presenza di un ciclo il quale permetterà l’invio di un messaggio così da avvisare il processo interessato. Immaginiamo quindi di dover rappresentare la seguente situazione:
I processi interessati avranno il seguente stato:
* Il processo P1 acquisisce l’unica istanza della risorsa R1 e un’istanza della risorsa R2
* Il processo P2 acquisisce un’istanza della risorsa R2; richiede inoltre la risorsa R1, che non gli viene assegnata, e viene posto in attesa.
In questo caso la seconda richiesta effettuata dal processo P2 non potrà essere soddisfatta, in quanto la risorsa non possiede unità disponibili, quindi l’arco sarà definito a partire dal processo verso la risorsa.
All'interno del grafo verrà quindi rappresentato un arco entrante al nodo risorsa, graficamente indicato in colore rosso, per poter evidenziare la presenza di un arco di assegnazione, e l'attesa da parte del processo P2 della risorsa R1.

## Stato di blocco (deadlock)

All’interno di un sistema in uno stato di deadlock i processi non terminano mai la loro esecuzione e di conseguenza le risorse vengono bloccate. Il caso di deadlock si dimostra evidente di fronte alla presenza di un ciclo all’interno del grafo.
Esistono varie condizioni necessarie per determinare la presenza di uno stato di blocco:
* Ogni processo appartenente al ciclo si trova in deadlock.
* All’interno del ciclo sono presenti risorse di un particolare insieme, ognuna composta da una sola istanza.
Al contrario, esistono condizioni necessarie ma non sufficienti come la presenza di risorse con più di una singola istanza.
Rappresentiamo quindi un caso di deadlock:
In questo caso i processi P1, P2, P3 sono in deadlock. Il processo P2 è in attesa della risorsa R2, posseduta dal processo P3. Il processo P3, invece, attende che il processo P1 o P2 rilasci la risorsa da lui richiesta; inoltre il processo P1 attende che P2 rilasci la risorsa R1.

## Grafo riducibile

Un grafo può essere definito riducibile nel caso in cui sia presente un nodo di tipo processo che ha soltanto archi entranti, ovvero archi di assegnazione. Il concetto che si trova alla base di questo meccanismo è quello che il processo interessato, che non ha bisogno di altre risorse, sicuramente terminerà la sua elaborazione, rilasciando le risorse che sta utilizzando.