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.[1]
Descrizione[modifica | modifica wikitesto]
Il grafo delle attese è costituito da una coppia , dove è l'insieme dei nodi ed l'insieme degli archi. L’insieme è partizionato in due parti:
- , che rappresenta tutti i processi appartenenti al sistema;
- , 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 ;
- 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 .
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.[2]
Tipologie di risorse[modifica | modifica wikitesto]
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. [3]
Rappresentazione grafica[modifica | modifica wikitesto]
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.[3] Immaginiamo quindi di dover rappresentare la seguente situazione:
P:{ P1, P2 } // insieme dei processi
R:{ R1, R2 } // insieme delle risorse
R1 molteplicità 1
R2 molteplicità 2
E:{ P1→ R1, P1→ R2, P2→ R2, P2→ R1} //insieme rappresentante gli archi del grafo
P1 richiede R1 //arco di richiesta
P1 richiede R2 //arco di richiesta
P2 richiede R2 //arco di richiesta
P2 richiede R1 // arco di assegnazione
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.[1]
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)[modifica | modifica wikitesto]
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.[4] 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:
P:{ P1, P2, P3}
R:{ R1, R2, R3}
R1 molteplicità 1
R2 molteplicità 1
R3 molteplicità 2
E:{ P1→R3, P2→R1, P3→R2, P2→R3, P1→R1, P2→R2, P3→R3}
P1 richiede R3
P2 richiede R1
P3 richiede R2
P2 richiede R3
P1 richiede R1 //arco di assegnazione
P2 richiede R2 // arco di assegnazione
P3 richiede R3 // arco di assegnazione
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.[2]
Grafo riducibile[modifica | modifica wikitesto]
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. [1]
Note[modifica | modifica wikitesto]
- ^ a b c Paolo Camagni, Riccardo Nikolassy, Tecnologie e progettazione di sistemi informatici e telecomunicazioni, 2016, p. 18.
- ^ a b Abraham Silberschatz, Peter Baer Galvin, Sistemi operativi, 1998, p. 199.
- ^ a b Richard C. Holt, Some deadlock properties of computer system, in ACM Computing Surveys, vol. 4, n. 3, settembre 1972, DOI:10.1145/356603.356607.
- ^ Andrew S. Tanenbaum, I moderni sistemi operativi, 2002, p. 149.
Bibliografia[modifica | modifica wikitesto]
- Andrew S. Tanenbaum, I moderni sistemi operativi, Jackson Università, ISBN 8825618980.
- Abraham Silberschatz, Peter Baer Galvin, Sistemi operativi, Addison Wesley, 2002, ISBN 8871920643.
- Paolo Camagni, Riccardo Nikolassy, Tecnologie e progettazione di sistemi informatici e telecomunicazioni, Hoepli, ISBN 9788820378424.
Voci correlate[modifica | modifica wikitesto]
Altri progetti[modifica | modifica wikitesto]
Wikimedia Commons contiene immagini o altri file sul Grafo delle attese
