Ogni processo e' bloccato in attesa che un altro processo rilasci una risorsa, ma questo non avviene perche' anch'esso e' fermo nell'attesa dello stesso evento.
Il blocco e' permanente poiche' il rilascio da parte di un processo di una risorsa non avviene, visto che aspetta altre risorse per concludere il lavoro.
Esempi nella vita comune sono gli incroci, in cui se arrivano 4 macchine e si fermano in attesa che passi prima la vettura alla loro destra, non procedono, e se non rispettano la regola e avanzano insieme all'istante si bloccano contemporaneamente allo stesso modo.
Un altro esempio e' la legge del Kansas del XX secolo: "Quando due treni convergono ad un incrocio, entrambi devono arrestarsi, e non possono procedere fin quando uno dei due non si allontana."
Cosa succede nel sistema?
La vita di un processo prevede l'utilizzo di diverse risorse, ed il metodo per sfruttarle richiede che sia rispettata la seguente sequenza: richiesta, uso, rilascio.
Le situazioni di stallo sono caratterizzate da 4 condizioni che avvengono contemporaneamente:
1. Mutua esclusione,
2. Possesso e attesa,
3. Impossibilita' di prelazione
4. Attesa circolare.
Mentre un metodo di visualizzazione dello stato del sistema e' il grafo di assegnamento risorse, che contiene due tipi di nodi, rappresentati da un processo o da una risorsa, e due tipi di archi, quello che va dalla risorsa al processo (arco di assegnazione) e quello che va dal processo alla risorsa (arco di richiesta).
Se il grafo contiene cicli allora il sistema e' in deadlock.
...Comunque come gestire il problema del deadlock?
Ci sono tre possibilita', anche se non sono tutte implementabili.
E' possibile evitarlo, risolverlo, o ignorarlo.
Prevenire il deadlock:
Se non avviene una delle 4 condizioni il sistema non entra in stallo. Un sistema che possiede risorse condivisibili non ha bisogno di mutua esclusione (es: file aperti), per quanto riguarda il possessso e attesa vi sono diversi algoritmi, in pratica un processo che richiede non deve possedere risorse, quindi o puo' richiederle solo se non ha risorse, o deve rilasciarle tutte prima di effettuare richieste.Oppure deve richiedere tutte le risorse prima dell'esecuzione e gli devono essere assegnate.
Questo non solo porta ad un utilizzo poco efficiente delle risorse, ma porta al verificarsi del problema dell'attesa indefinita.
Per quanto riguarda l'impossibilita' di prelazione, e' possibile che non accada in diverse maniere, ad esempio si puo' far si' che un processo rilasci tutte le risorse se una non gli puo' essere assegnata.E quindi essere sottratto dall'utilizzo in cpu.
Attesa circolare: per non permettere il verificarsi di attesa circolare, c'e' bisogno di un algoritmo che assegni risorse in modo tale che le richieste siano ordinate rispetto alle risorse, quindi da evitare che un processo richiede risorse in possesso da una altro processo in attesa.E possibile ad esempio richiedendo risorse in sequenza crescente in numeri di istanza.
Evitare il deadlock:
Evitare il deadlock e' sicuramente piu' probabile anche se meno semplice, poiche' prevenire il deadlock vuol dire privare il sistema di funzioni necessarie per il corretto funzionamento. Come ad esempio la mutua esclusione: non si puo' lasciare in vita un sistema senza mutua esclusione, si annienterebbe il concetto di multiprogrammazione che e' alla base dell'efficienza di un sistema operativo.
Evitare vuol dire prevedere, ed in tal caso simulare l'assegnamento. Per far cio' bisogna definire uno stato in cui il sistema puo' assegnare risorse a ciascun processo.
Lo stato sicuro e' la condizione in cui il sistema operativo assegna le risorse in un certo ordine e impedisce una situazione di stallo. Questo avviene se c'e' una sequenza sicura.
Una sequenza si dice sicura se per ogni Pi si puo' assegnare il numero di risorse che richiede impiegando le risorse disponibili piu' quelle possedute da tutti i Pj con j
R(Pi) = Disponibili+Allocate(Pj)
Algoritmo del banchiere: viene utilizzato per prevedere l'assegnamento e verificare se e' possibile dimostrando che la sequenza delle richieste lascia il sistema in uno stato sicuro. Questo e' possibile attraverso due algoritmi: di verifica della sicurezza e di richiesta.
L'algoritmo del banchiere si avvale di 4 vettori: Disponibili, Massimo, Allocated, Need.
Si applica prima l'algoritmo della verifica di sicurezza, per verificare appunto se il sistema e' in uno stato sicuro.
if(Need <= Disponibili)
Disponibili += Allocate
Ora che e' verificato che il sistema vive in uno stato sicuro, e' possibile applicare l'algoritmo di richiesta delle risorse. Quest'ultimo necessita di una variabile in piu' che e' il vettore Richieste.
if(Richieste <= Need)
if(Richieste <= Disponibili)
Disponibili -= Richieste
Allocate += Richieste
Need -= Richieste
Se non c'e' modo di prevenire o evitare lo stallo c'e' bisogno di un metodo per verificare, o meglio rilevare le situazioni di stallo, ed in tal caso ripristinare.
Vuol dire permettere he un sistema entri in stallo per poi risolvere la situazione.
Per questa necessita' e' possibile modificare il grafo di assegnamento risorse che prevede l'utilizzo di due archi, di richiesta e di assegnamento, e due tipologie di vertici: risorsa (con il numero di istanze disponibili) e processo; trasformandolo in un grafo di attesa, introducendo un nuovo tipo di arco che va da processo a processo, eliminando il vertice risorsa, in modo tale che l'arco appena introdotto indichi che un processo "e' in attesa di una risorsa posseduta da".
Anche in questo caso i cicli indicano l'avvenimento del deadlock, un algoritmo che individua un ciclo e' capace di verificare una situazione di deadlock, quindi pericolosa per il sistema.
Nessun commento:
Posta un commento