Torna alla pagina di Sistemi Operativi
:: Appunti caotici ::
Lezione 3 Tecniche per evitare il deadlock
...
...
...
Necessità di informazioni a priori sul comportamento dei processi:
Tutto questo serve a vedere se esiste almeno un ordine di richieste e concessioni di risorse che evita di far entrare il sistema in uno stato di deadlock.
Uno stato si dice sicuro se il sistema operativo può allocare le risorse richieste da ogni processo in un certo ordine garantendo che non si verifichi deadlock.
Se sono in uno stato sicuro sono certo di non essere in stallo e di avere una configurazione delle allocazioni delle risorse ai processi che non mi conduce in una situazione di stallo. Se invece sono in uno stato non sicuro non vuol dire che ho la certezza di avere un deadlock in futuro, ma che non ho la certezza di non averlo. Non potendo garantire tale condizione, tanto basta perché non sia considerato sicuro.
Una sequenza di processi P1, P2, ... , Pn è una sequenza sicura per l'allocazione corrente se le richieste che ogni processo Pi può fare possono essere soddisfatte dalle risorse attualmente disponibili più tutte le risorse detenute dai processi Pj con j < i. Si tratta quindi di un ordine con cui andare a considerare le richieste dei processi, garantendo così di non avere attese circolari.
Uno stato è sicuro se esiste una sequenza sicura
Bisogna garantire che il sistema passi da uno stato sicuro ad un altro stato sicuro quando un processo chiede una nuova risorsa.
L'arco di prenotazione, rappresentato come una freccia tratteggiata, indica quali risorse saranno prima o poi necessarie ad un processo perché possa portare avanti la propria computazione.
Nel grafo in slide ad esempio so già che P1 e P2 richiederanno prima o poi l'accesso alla risorsa R2.
Con l'utilizzo degli archi di prenotazione in aggiunta a quelli classici di richiesta. posso prevedere l'eventuale comparsa di condizioni di deadlock.
Nel grafo in slide ho rappresentato uno stato non sicuro. P1 potrebbe infatti effettuare la richiesta della risorsa R2 prima che questa abbia evaso la richiesta di P2, generando quindi una situazione di stallo. Proprio perché non so se questo può accadere o no, considero lo stato non sicuro.
...
L'algoritmo del banchiere opera concedendo le risorse solo se sono certo di non rischiare troppo di andare in stallo. Dovrò quindi verificare se ho risorse a sufficienza per soddisfare le varie richieste, rimanendo sempre in stati sicuri.
In particolare:
...
La prima parte dell'algoritmo consiste nella verifica dello stato sicuro, ovvero trovare se esiste un ordine con cui assegnare le risorse richieste senza entrare in stallo.
Di seguito sarà rappresento in grassetto l'algoritmo e subito sotto, in corsivo, i commenti:
Work[1..m]
\\ un vettore che rappresenta quali sono le richieste di risorse
Finish[1..n]
\\ un vettore che rappresenta quali processi hanno completato la computazione, e quindi hanno rilasciato a un certo punto le risorse
1. Work = Available; Finish[i] = false per i = 0, 1, ... , n-1
\\ fase di inizializzazione: segno come disponibili gli elementi del vettore delle risorse, e assegno valore negativo per ogni processo del vettore Finish (dato che non hanno ancora terminato la computazione)
2. Si cerca i tale che
Se non esiste tale i, vai al passo 4
\\scandisco Finish finché trovo un processo non ancora terminato e che richiede un numero di risorse inferiore a quelle indicate nel vettore Work
3. Work = Work + Allocation[i]; Finish[i] = true
Vai al passo 2
\\ rappresenta il caso in cui posso soddisfare la richiesta. Una volta che il processo ha terminato la computazione e rilasciato le risorse, andrò ad aggiornare il vettore delle allocazioni disponibili, sommandogli le risorse che erano state assegnate al processo i-simo (ormai rilasciate)
4. Se, per ogni i, Finish[i]==true, allora lo stato è sicuro
Ora che so di essere in uno stato sicuro, posso procedere con l'algoritmo di richiesta delle risorse.
Come prima, rappresento in grassetto l'algoritmo e subito sotto, in corsivo, i commenti:
Request[i]
\\ rappresenta la richiesta del processo Pi in un certo momento
1. Se Request[i]<=Need[i], vai al passo 2
Altrimenti solleva errore: il processo ha ecceduto il numero massimo di richieste
\\ se il numero di richieste è minore (o al più uguale) al numero massimo di richieste che saranno effettuate da i, allora vai al passo 2. Se lo supera, allora il processo aveva cannato a fornire al sistema il numero massimo di richieste che avrebbe chiesto
2. Se Request[i]<=Available, vai al passo 3
Altrimenti Pi deve attendere: risorse non disponibili
\\ se il numero di richieste è minore o uguale a quelle disponibili in quel momento, allora posso passare al passo 3, in cui tali richieste saranno soddisfatte.
3. Si ipotizzi di stanziare le risorse richieste
Se lo stato risultante è sicuro, al processo Pi vengono confermate le risorse assegnate. Altrimenti Pi deve aspettare per le richieste Request[i] e viene ristabilito il vecchio stato di allocazione delle risorse.
\\ la sicurezza dell'assegnamento viene valutata in tre punti: in 3.1 viene diminuito il numero di risorse disponibili in base alle richieste del processo; in 3.2 viene incrementanto il numero di risorse assegnate al processo; in 3.3 viene decrementato il numero di risorse del processo che ancora devono essere soddisfatte. Se queste allocazioni mi lasciano in uno stato sicuro (e lo verifico con l'algoritmo di verifica visto prima) confermo tutto, altrimenti non posso dare le risorse al processo perché entrerei in uno stato non sicuro. In questo secondo caso riporto tutto alla situazione precedente all'allocazione e lascio che il processo attenda.