Sistemi Operativi - Appunti caotici

Torna alla pagina di Sistemi Operativi

---

 :: Appunti caotici ::

Lezione 3 Tecniche per evitare il deadlock

Pag 1

Sommario

...

Pag 2

Obiettivi

...

Principio di evitare il deadlock

...

Pag 3

Informazioni per evitare il deadlock

Necessità di informazioni a priori sul comportamento dei processi:

• numero massimo di risorse per ogni accesso
• risorse assegnate
• risorse disponibili
• richieste e rilasci futuri di risorse

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.

Stato sicuro (1)

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.

Pag 4

Stato sicuro (2)

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

Come evitare il deadlock?

Bisogna garantire che il sistema passi da uno stato sicuro ad un altro stato sicuro quando un processo chiede una nuova risorsa.

• si parte da uno stato iniziale sicuro (per forza, nessuno ha ancora richiesto risorse!)
• una richiesta di risorsa viene soddisfatta se la risorsa è disponibile e se il sistema va in uno stato sicuro
• se la risorsa non è disponibile, il processo deve attendere perché non riuscirei a garantire che rimanga in uno stato sicuro.

Pag 5

Algoritmo del grafo di allocazione delle risorse (1)

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.

Algoritmo del grafo di allocazione delle risorse (2)

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.

Pag 6

Algoritmo del grafo di allocazione delle risorse (3)

...

Algoritmo del banchiere (1)

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:

• gestisce istanze multiple delle risorse (quindi potrei anche avere cicli senza che si presentino deadlock)
• è meno efficiente dell'algoritmo del grafo di allocazione delle risorse, essendo più pesante computazionalmente
• il numero massimo di istanze delle risorse deve essere dichiarato a priori. Ai processi che non sanno dire di quante istanze hanno bisogno, l'algoritmo rigetta le richieste. Ragiona in questo proprio come un banchiere: deve sapere quanti soldi dare
• un processo deve restituire in un tempo finito le risorse utilizzate. Teoricamente il processo potrebbe non finire mai, e non me ne fregherebbe comunque niente, l'importante è che prima o poi rilasci le risorse. Non mi preoccupo minimamente dei tempi d'attesa dei processi: l'unica cosa che voglio è evitare il deadlock, se questo è il prezzo, tebbona.

Pag 7

Algoritmo del banchiere (2)

...

Algoritmo del banchiere (3)

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

Pag 8

Algoritmo del banchiere (4)

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.

---

Torna alla pagina di Sistemi Operativi