|
|
Una situazione di Deadlock può essere riconosciuta analizzando il Grafo delle attese o grafo di assegnazione delle risorse. Questo grafo orientato consiste di un insieme di vertici V, suddiviso in due sottoinsiemi disgiunti (P, costituito dai processi attivi nel sistema; R, costituito da tutti i tipi di risorse presenti nel sistema), e di un insieme E di archi che congiungono un vertice di P ed un vertice di R. Graficamente i processi sono rappresentati da cerchi e le risorse da rettangoli all’interno dei quali compaiono tanti cerchietti quante sono le copie disponibili della risorsa.
Un arco orientato dal cerchio P al rettangolo R indica che il processo P ha richiesto una risorsa del tipo R ed e’ in attesa di tale risorsa (arco di richiesta). Un arco orientato da uno dei cerchietti di una risorsa R ad un cerchio P indica che una risorsa di tipo R e’ stata assegnata al processo P (arco di assegnazione).
Allorché un processo richiede una risorsa, si inserisce un arco di richiesta nel grafo: se la richiesta può essere soddisfatta, l’arco e’ trasformato in un arco di assegnazione. Naturalmente quando un processo non usa più una risorsa, l’arco di assegnazione e’ rimosso. Di seguito un esempio riporta un grafo di allocazione delle risorse:
Se un grafo di allocazione delle risorse non contiene cicli si può dimostrare che non vi sono processi in condizione di stallo. Se un grafo contiene un ciclo, si ha stallo se il ciclo coinvolge solo risorse delle quali esiste una sola copia nel sistema (in effetti sono in condizione di stallo tutti i processi che sono coinvolti nel ciclo) mentre se il ciclo coinvolge risorse delle quali esistono più copie non è detto che si sia verificato uno stallo. Se, per esempio, a partire dalla situazione indicata sopra si aggiunge la richiesta da parte di P3 di una copia della risorsa R2, nel grafo di allocazione risultante vi sono due cicli e tutti e tre i processi sono in situazione di stallo. Infatti P2 è in attesa di R3 che è stata assegnata a P3 , P3 è in attesa che P1 o P2 rilascino R2 ed infine P1 e’ in attesa di R1 assegnata a P2 .
Nel grafo di allocazione seguente è pure presente un ciclo ma non vi è stallo: è sufficiente infatti che, per esempio, il processo P4 rilasci la sua copia di R2 perchè questa risorsa venga assegnata a P3 spezzando il ciclo.
Tutto quanto riportato in questa pagina è a puro scopo informativo personale. Se non ti trovi in accordo con quanto riportato nella pagina, vuoi fare delle precisazioni, vuoi fare delle aggiunte o hai delle proposte e dei consigli da dare, puoi farlo mandando un email. Ogni indicazione è fondamentale per la continua crescita del sito.