Grafo delle attese
Da Wikipedia, l'enciclopedia libera.
In informatica, un grafo delle attese (o grafo di Holt) è costituito da una coppia (V, E), dove V è l'insieme dei vertici ed E l'insieme degli archi tra i vertici appartenenti a V.
Si tratta di un grafo bipartito diretto in cui l'insieme V è suddiviso in due sottoinsiemi: Vp e Vr.
- Vp rappresenta i processi del sistema.
- Vr rappresenta le risorse del sistema.
Il grafo si connette nel modo seguente:
- Si aggiunge un arco tra un processo p ed una risorsa r , se p è in attesa di r
- Si aggiunge un arco tra una risorsa r ed un processo p, se r è assegnata p
Nel caso in cui un processo richiedesse più istanze di una stessa risorsa (o analogamente a un processo fossero assegnate più istanze di una stessa risorsa), gli archi sono pesati.
L'utilità del grafo delle attese si manifesta nel deadlock detection, ovvero nella rilevazione del deadlock: dato un grafo delle attese G rappresentante lo stato attuale del sistema in esame, se le risorse sono ad accesso mutualmente esclusivo, seriale e non prerilasciabili, si può affermare che nel sistema vi è una situazione di stallo (deadlock) se e solo se nel grafo è presente un ciclo (si può dimostrare questo teorema utilizzando una variante del grafo di Holt detto grafo Wait-For che si costruisce eliminando i nodi di tipo risorsa e collassando gli archi appropriati, per cui il grafo di Holt contiene un ciclo se e solo se il grafo Wait-For contiene un ciclo e pertanto si ha l'attesa circolare).
Un grafo di Holt si dice riducibile se esiste almeno un nodo processo con soli archi entranti e la riduzione consiste nell'eliminare tutti gli archi di tale nodo e riassegnare le risorse ad altri processi e pertanto lo stato non è di deadlock se e solo se il grafo di Holt è completamente riducibile, ossia esiste una sequenza di passi che elimina tutti gli archi del grafo.
