Deadlock
•
•
•
•
•
•
•
•
Modello del sistema
Caratterizzazione dei deadlock
Metodi per la gestione dei deadlock
Prevenire i deadlock
Evitare i deadlock
Rilevamento dei deadlock
Ripristino da situazioni di deadlock
Approccio combinato alla gestione dei deadlock
Sistemi Operativi
7.1
Il problema del deadlock
•
•
•
Un insieme di processi bloccati: ciascun processo “possiede” una
risorsa, ed attende di acquisire una risorsa posseduta da un altro
processo dell’insieme.
Esempio
– Il sistema ha 2 lettori di nastri.
– P1 e P2 posseggono ciascuno un lettore, e ciascuno ha
bisogno di quello posseduto dall’altro processo.
Esempio
– semafori A e B, inizializzati a 1
P0
P1
wait (A);
wait (B);
Sistemi Operativi
wait(B)
wait(A)
7.2
Esempio: attraversamento di un ponte
•
•
•
•
•
Sul ponte possono transitare autoveicoli solo in una direzione
alla volta.
Ciascuna sezione del ponte può essere vista come una risorsa.
Se si verifica un deadlock, può essere risolto se un’auto torna
indietro (rilascia la risorsa).
Può essere necessario che più auto debbano tornare indietro in
caso di deadlock.
E’ possibile la starvation (attesa indefinita).
Sistemi Operativi
7.3
Modello di sistema
•
•
•
Tipi di risorse R1, R2, . . ., Rm
Cicli di CPU, spazio di memoria, dispositivi di I/O
Ciascun tipo di risorsa Ri ha Wi istanze.
Ciascun processo impiega una risorsa in uno dei seguenti modi:
– richiesta
– uso
– rilascio
Sistemi Operativi
7.4
Caratterizzazione dei deadlock
Un deadlock può avvenire se e solo se sono verificate le seguenti
quattro condizioni contemporaneamente.
•
•
•
•
Mutua esclusione: un solo processo alla volta può usare una
risorsa.
Possesso ed attesa: un processo che possiede almeno una
risorsa, attende di acquisire ulteriori risorse possedute da altri
processi.
Impossibilità di prelazione: una risorsa può essere rilasciata
dal processo che la possiede solo volontariamente, al termine del
suo compito.
Attesa circolare: esiste un insieme {P0, P1, …, Pn} di processi in
attesa, tali che P0 è in attesa per una risorsa che è posseduta da
P1, P1 è in attesa per una risorsa che è posseduta da P2, …, Pn–1
è in attesa per una risorsa che è posseduta da Pn, e Pn è in
attesa per una risorsa che è posseduta da P0.
Sistemi Operativi
7.5
Grafo di allocazione delle risorse
Un grafo è un insieme di vertici (o nodi) V e un insieme di archi E.
•
•
•
V è partizionato in due tipi :
– P = {P1, P2, …, Pn}, è l’insieme costituito da tutti i processi
nel sistema.
– R = {R1, R2, …, Rm}, è l’insieme costituito da tutti i tipi di
risorse nel sistema.
Arco di richiesta (arco orientato) P1  Rj
Arco di assegnamento (arco orientato) Rj  Pi
Sistemi Operativi
7.6
Grafo di allocazione delle risorse
•
Processo
•
Tipo di risorsa con 4 istanze
•
Pi richiede un’istanza di Rj
Pi
•
Rj
Pi possiede una risorsa di Rj
Pi
Rj
Sistemi Operativi
7.7
Grafi di allocazione con e senza deadlock
Sistemi Operativi
7.8
Grafo di allocazione delle risorse
•
•
Se il grafo non contiene cicli  no ci sono deadlock.
Se il grafo contiene un ciclo 
– se si ha una sola istanza per ogni tipo di risorsa, allora si ha
un deadlock.
– se si hanno più istanze per tipo di risorsa, allora il deadlock
è possibile.
Sistemi Operativi
7.9
Metodi per la gestione dei deadlock
•
•
•
Assicurare che il sistema non entri mai in uno stato di deadlock.
– 1) Prevenzione dei deadlock: rimuovere dal sistema ogni
possibilità che ci sia un deadlock => basso utilizzo risorse.
– 2) Evitare i deadlock: ci sono le condizioni perché intervenga un
deadlock, ma si evita di entrarci effettivamente.
Permettere al sistema di entrare in uno stato di deadlock, ma poi
risolvere questo problema (ripristinare il sistema).
– 3) Determinare la presenza di un deadlock.
– 4) Ripristinare il sistema da un deadlock.
Ignorare il problema e fingere che i deadlock non avvengano mai nel
sistema; impiegato dalla maggioranza dei sistemi operativi, incluso
UNIX.
Sistemi Operativi
7.10
Prevenzione dei deadlock
Limitare i modi in cui possono essere fatte delle richieste.
•
Mutua Esclusione – non è richiesta per risorse che possono
essere condivise; deve valere per risorse che non possono
essere condivise.
•
Possesso e attesa – si deve garantire che quando un processo
richiede una risorsa, questo non possieda altre risorse.
– Richiedere ad un processo di stabilire ed allocare tutte le
sue risorse prima che inizi l’esecuzione, o consentire ad un
processo di richiedere risorse solo quando il processo non
ne possiede alcuna.
– Si ha un basso impiego delle risorse. E’ possibile che si
verifichi l’attesa indefinita.
Sistemi Operativi
7.11
Prevenzione dei deadlock
•
•
Impossibilità di prelazione
– Se un processo che possiede alcune risorse richiede
un’altra risorsa che non gli può essere allocata
immmediatamente, allora rilascia tutte le risorse possedute.
– Le risorse rilasciate (prelazionate dal processo stesso) sono
aggiunte alla lista delle risorse che il processo sta
attendendo.
– Il processo viene avviato nuovamente solo quando può
ottenere le sue vecchie e nuove risorse.
Attesa circolare – si impone un ordinamento totale di tutti i tipi di
risorsa e si pretende che ciascun processo richieda le risorse con
un ordine di numerazione crescente.
Sistemi Operativi
7.12
Evitare i deadlock
Richiede che il sistema possegga alcune informazioni addizionali a priori.
•
•
•
Il modello più semplice e utile richiede che ciascun processo
dichiari il numero massimo di risorse di ciascun tipo di cui può
avere bisogno.
L’algoritmo per evitare i deadlock esamina dinamicamente lo
stato di allocazione delle risorse per assicurare che non ci possa
mai essere una condizione di attesa circolare.
Lo stato di allocazione delle risorse è definito dal numero di
risorse disponibili ed allocate, e dal massimo numero di richieste
dei processi.
Sistemi Operativi
7.13
Stato sicuro
•
•
•
Quando un processo richiede una risorsa disponibile, il sistema
deve decidere se l’allocazione immediata porti il sistema in uno
stato sicuro.
Il sistema è in uno stato sicuro se esiste una sequenza sicura di
esecuzione di tutti i processi.
La sequenza <P1, P2, …, Pn> è sicura se per ogni Pi, le risorse che
Pi può ancora richiedere possono essere soddisfatte dalle risorse
correntemente disponibili + risorse possedute da tutti i Pj, con j<i.
– Se le richieste della risorsa Pi non sono immediatamente
disponibili, allora Pi può attendere finché Pj ha terminato.
– Quando Pj ha terminato, Pi può ottenere le risorse richieste,
eseguire i suoi compiti, restituire le risorse allocate e terminare.
– Quando Pi termina, Pi+1 può ottenere le risorse richieste, e così
via.
Sistemi Operativi
7.14
Stato sicuro
•
Se un sistema è in uno stato sicuro  non si evolve verso il
deadlock.
•
Se un sistema è in uno stato non sicuro  possibilità di un
deadlock.
•
Avoidance  assicura che un sistema non entri mai in uno stato
non sicuro.
Sistemi Operativi
7.15
Algoritmo con grafo di allocazione delle risorse
•
•
•
•
Un arco di reclamo Pi  Rj indica che il processo Pj può
richiedere la risorsa Rj; rappresentata da una linea tratteggiata.
Un arco di reclamo viene convertito in un arco di richiesta
quando un processo richiede una risorsa.
Quando una risorsa viene rilasciata da un processo l’arco di
assegnamento viene riconvertito in un arco di reclamo.
Le risorse devono venir reclamate a priori nel sistema. Prima che
il processo Pi inizi l’esecuzione, tutti i suoi archi di reclamo
devono essere già inseriti nel grafo di allocazione risorse.
Sistemi Operativi
7.16
Grafo di allocazione risorse per evitare deadlock
e stato non sicuro in un grafo di allocazione risorse
Sistemi Operativi
7.17
Algoritmo del banchiere
•
•
•
•
Permette di gestire istanze multiple di una risorsa (a differenza
del grafo di allocazione delle risorse).
Ciascun processo deve dichiarare a priori il massimo impiego di
risorse.
Quando un processo richiede una risorsa può aver bisogno di
attendere.
Quando un processo prende tutte le sue risorse deve restituirle in
un tempo finito.
Sistemi Operativi
7.18
Strutture dati per l’algoritmo del banchiere
Sia n = numero di processi, e m = numero di tipi di risorse.
•
•
•
•
Available: Vettore di lunghezza m. Se Available[j] = k, ci sono k
istanze disponibili del tipo di risorsa Rj.
Max: matrice n x m. Se Max [i,j] = k, allora il processo Pi può
richiedere al più k istanze del tipo di risorsa Rj.
Allocation: matrice n x m. Se Allocation[i,j] = k allora a Pi sono
allocate correntemente k istanze di Rj.
Need: matrice n x m. Se Need[i,j] = k, allora Pi può richiedere k
ulteriori istanze di Rj per completare il suo task.
Need [i,j] = Max[i,j] – Allocation [i,j].
Sistemi Operativi
7.19
Algoritmo di verifica della sicurezza
1. Siano Work e Finish due vettori di lunghezza m e n,
rispettivamente. Si inizializzi:
Work := Available
Finish [i] = false per i = 1,2, …, n.
2. Cerca un i tale che valgano contemporaneamente le seguenti
relazioni:
(a) Finish [i] = false
(b) Needi  Work
Se non esiste un tale i, andare al passo 4.
3. Work := Work + Allocationi
Finish[i] := true
andare al passo 2.
4. Se Finish [i] = true per tutti gli i, allora il sistema è in uno stato
sicuro.
Sistemi Operativi
7.20
Algoritmo di richiesta delle risorse per processo Pi
Sia Requesti il vettore delle richieste per il processo Pi. Se
Requesti [j] = k allora il processo Pi vuole k istanze del tipo di
risorsa Rj.
1. Se Requesti  Needi vai al passo 2. Altrimenti, riporta una
condizione di errore, dato che il processo ha ecceduto il
massimo numero di richieste.
2. Se Requesti  Available, vai al passo 3. Altrimenti Pi deve
attendere, dato che le risorse non sono disponibili.
3. Il sistema simula l’allocazione al processo Pi modificando lo
stato di allocazione delle risorse:
Available := Available – Requesti;
Allocationi := Allocationi + Requesti;
Needi := Needi – Requesti;;
• Se stato sicuro  le risorse sono allocate a Pi.
• Se stato non sicuro  Pi deve attendere, e viene
ripristinato il vecchio stato di allocazione delle risorse.
Sistemi Operativi
7.21
Esempio
•
•
5 processi da P0 a P4; 3 tipi di risorse A (10 istanze),
B (5 istanze), e C (7 istanze).
Fotografia al tempo T0:
Sistemi Operativi
Allocation
Max
Available
ABC
ABC
ABC
P0
010
753
332
P1
200
322
P2
302
902
P3
211
222
P4
002
433
7.22
Esempio
•
Il contenuto della matrice Need è definito come Max – Allocation.
Need
ABC
•
P0
743
P1
122
P2
600
P3
011
P4
431
Il sistema è in uno stato sicuro dato che la sequenza < P1, P3, P4, P2,
P0> soddisfa i criteri di sicurezza.
Sistemi Operativi
7.23
Esempio: P1 richiede (1,0,2)
•
•
•
•
Verificare che Requesti  Available (cioè, (1,0,2)  (3,3,2)  vero).
Allocation
Need
Available
ABC
ABC
ABC
P0
010
743
230
P1
302
020
P2
301
600
P3
211
011
P4
002
431
L’esecuzione dell’algoritmo di sicurezza mostra che la sequenza <P1,
P3, P4, P0, P2> soddisfa i requisiti di sicurezza.
Può essere soddisfatta la richiesta di P4 per (3,3,0)?
Può essere soddisfatta la richiesta di P4 per (0,2,0)?
Sistemi Operativi
7.24
Rilevamento dei deadlock
•
•
Si permette al sistema di entrare in uno stato di deadlock
Sono necessari
– Algoritmo di rilevamento
– Schema di recupero
Sistemi Operativi
7.25
Istanza singola di ciascun tipo di risorsa
•
•
•
Impiega un grafo di attesa
– I nodi sono processi.
– Pi  Pj se Pi è in attesa che Pj rilasci una risorsa che gli
occorre.
Periodicamente viene richiamato un algoritmo che ricerca un
ciclo nel grafo.
Un algoritmo per trovare un ciclo in un grafo richiede un numero
di operazioni dell’ordine di n2, dove n è il numero di vertici del
grafo.
Sistemi Operativi
7.26
Grafo di allocazione risorse e grafo di attesa
Grafo di allocazione delle risorse
Sistemi Operativi
7.27
Corrispondente grafo di attesa
Più istanze di ciascun tipo di risorsa
•
•
•
Available: vettore di lunghezza m, indica il numero di risorse
disponibili di ciascun tipo.
Allocation: matrice n x m, definisce il numero di risorse di
ciascun tipo correntemente allocate a ciascun processo.
Request: matrice n x m, indica la richiesta corrente di ciascun
processo. Se Request [i,j] = k, allora il processo Pi richiede k
istanze supplementari della risorsa Rj.
Sistemi Operativi
7.28
Algoritmo di rilevamento
1. Siano Work e Finish due vettori di lunghezza m e n, rispettivamente
Inizializzazione:
(a) Work := Available
(b) Per i = 1,2, …, n, se Allocationi  0, allora
Finish[i] := false; altrimenti, Finish[i] := true.
2. Si trovi un indice i tale che valgano entrambe le condizioni:
(a) Finish[i] = false
(b) Requesti  Work.
Se non esiste un tale i vai al passo 4.
Sistemi Operativi
7.29
Algoritmo di rilevamento
3. Work := Work + Allocationi
Finish[i] := true
vai al passo 2.
4. Se Finish[i] = false, per qualche i, 1  i  n, allora il sistema è in
uno stato di deadlock. Inoltre, se Finish[i] = false, allora Pi è in
deadlock.
L’algoritmo richiede un numero di operazioni dell’ordine di m x n2
per determinare se il sistema è in uno stato di deadlock.
Sistemi Operativi
7.30
Esempio di algoritmo di rilevamento
•
•
•
Cinque processi, da P0 a P4; tre tipi di risorse
A (7 istanze), B (2 istanze), e C (6 istanze).
Stato al tempo T0:
Allocation
Request
Available
ABC
ABC
ABC
P0
010
000
000
P1
200
202
P2
303
000
P3
211
100
P4
002
002
La sequenza <P0, P2, P3, P1, P4> porta a Finish[i] = true per tutti gli i.
Sistemi Operativi
7.31
Esempio
•
P2 richiede un’istanza supplementare della risorsa C.
Request
ABC
•
P0
000
P1
202
P2
001
P3
100
P4
002
Stato del sistema?
– Può reclamare risorse possedute dal processo P0, ma il
numero di risorse disponibili non è sufficiente a soddisfare
gli altri processi  deadlock: processi P1, P2, P3, e P4.
Sistemi Operativi
7.32
Impiego dell’algoritmo di rilevamento
•
Quando e quanto spesso chiamare l’algoritmo di rilevamento
dipende da:
– Frequenza (presunta) con la quale si verifica un deadlock
– Numero di processi che vengono eventualmente influenzati
da tale deadlock
•
Se l’algoritmo viene richiamato in momenti arbitrari ci possono
essere vari cicli nel grafo delle risorse e quindi non si può dire
quale dei processi coinvolti nel ciclo abbia causato il deadlock.
•
Un’alternativa è quella di richiamare l’algoritmo ogni volta che
una richiesta non può essere soddisfatta immediatamente.
Questo approccio può essere dispendioso.
Sistemi Operativi
7.33
Ripristino dai deadlock: Terminazione di processi
•
•
•
Terminazione in abort di tutti i processi in deadlock.
Terminare un processo alla volta fino all’eliminazione del ciclo di
deadlock.
In quale ordine si decide di terminare i processi?
– La priorità del processo.
– Il tempo di computazione trascorso e il tempo ancora
necessario al suo completamento.
– Quantità e tipo di risorse impiegate.
– Risorse di cui ha ancora bisogno per terminare l’esecuzione.
– Numero di processi che devono essere terminati.
– Tipo di processo: interattivo o batch?
Sistemi Operativi
7.34
Prelazione di risorse
•
Selezione di una vittima – È necessario stabilire l’ordine di
prelazione per minimizzare i costi.
•
Rollback – Un processo a cui sia stata prelazionata una risorsa
deve ritornare ad uno stato sicuro, da cui ripartire.
•
Starvation – Alcuni processi possono essere sempre vittime
della prelazione. Si può includere il numero di rollback nel fattore
di costo.
Sistemi Operativi
7.35
Approccio combinato
•
Si combinano i tre approcci di base
– prevenzione
– evitare i deadlock
– rilevazione
permettendo l’uso dell’approccio ottimale per ciascuna risorsa del
sistema.
•
•
Si suddividono le risorse in classi gerarchicamente ordinate.
Si impiegano le tecniche più appropriate per gestire i deadlock in
ciascuna classe.
Sistemi Operativi
7.36