Deadlock
 Modello del sistema
 Caratterizzazione dei deadlock
 Metodi per la gestione dei deadlock
 Prevenire i deadlock
 Evitare i deadlock
 Rilevare i deadlock
 Ripristino da situazioni di deadlock
 Approccio combinato alla gestione dei deadlock
Oggi c’è un
traffico
tremendo…
Operating System Concepts
8.1
Silberschatz, Galvin and Gagne 2002
Il problema del deadlock
 In un ambiente multiprogrammato più processi possono
entrare in competizione per ottenere un numero finito di
risorse.
 Deadlock — insieme di processi bloccati: ciascun
processo “possiede” una risorsa ed attende di acquisire
una risorsa allocata ad un altro processo dell’insieme.
 Esempio 1
 Nel sistema sono presenti 2 unità a nastri.
 P1 e P2 posseggono una unità a nastri ciascuno ed
entrambi richiedono anche la seconda.
 Esempio 2
 Semafori A e B, inizializzati a 1:
P0
wait(A);
wait(B);
Operating System Concepts
P1
wait(B);
wait(A);
8.2
Silberschatz, Galvin and Gagne 2002
Esempio: attraversamento di un ponte
 In ogni istante, sul ponte possono transitare autoveicoli




solo in una direzione.
Ciascuna sezione del ponte può essere immaginata
come una risorsa.
Se si verifica un deadlock, il recovery può essere
effettuato se un’auto torna indietro (rilascia la risorsa ed
esegue un rollback ).
In caso di deadlock, può essere necessario che più auto
debbano tornare indietro.
È possibile si verifichi starvation (attesa indefinita).
Operating System Concepts
8.3
Silberschatz, Galvin and Gagne 2002
Esempio: leggi ferroviarie in Kansas
 Testo della legge approvata dalla legislazione del Kansas
(inizi XX secolo):
“Quando due treni convergono ad un incrocio, ambedue
devono arrestarsi, e nessuno dei due può ripartire prima
che l’altro si sia mosso”.
Operating System Concepts
8.4
Silberschatz, Galvin and Gagne 2002
Modello di sistema
 Tipi di risorse R1, R2, . . ., Rm
Cicli di CPU, spazio di memoria, file, dispositivi di I/O
 Ciascun tipo di risorsa Ri ha Wi istanze.
 Il protocollo di accesso alle risorse da parte dei processi
prevede…
 Richiesta — se la richiesta non può essere soddisfatta
immediatamente, causa diverso utilizzo della risorsa, il
processo richiedente deve attendere fino all’acquisizione
della risorsa.
 Utilizzo
 Rilascio
 Richiesta/rilascio realizzati con apposite system call:
request/release device, open/close file, allocate/free
memory.
Operating System Concepts
8.5
Silberschatz, Galvin and Gagne 2002
Caratterizzazione dei deadlock
Una situazione di deadlock può verificarsi solo se valgono
simultaneamente le seguenti condizioni:
 Mutua
esclusione: esiste almeno una
risorsa non
condivisibile, cioè un solo processo alla volta può usare quella
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 di una risorsa che è posseduta
da P1, P1 è in attesa di una risorsa posseduta da P2, …, Pn–1 è
in attesa di una risorsa posseduta da Pn, e Pn è in attesa di
una risorsa posseduta da P0.
Operating System Concepts
8.6
Silberschatz, Galvin and Gagne 2002
Grafo di allocazione risorse
Un grafo è costituito da un insieme di vertici (o nodi) V
variamente connessi per mezzo di un insieme di archi E.
Nel grafo di allocazione risorse:
 L’insieme V è partizionato in due sottoinsiemi:
 P = {P1, P2, …, Pn } è l’insieme costituito da tutti i processi
del sistema.
 R = {R1, R2, …, Rm } è l’insieme di tutti i tipi di risorse del
sistema.
 Arco di richiesta: Pi  Rj
 Arco di assegnazione: Rj  Pi
Operating System Concepts
8.7
Silberschatz, Galvin and Gagne 2002
Grafo di allocazione risorse
 Processo
 Tipo di risorsa con 4 istanze
 Pi richiede un’istanza di Rj
Arco di richiesta
Pi
Rj
 Pi possiede un’istanza di Rj
Arco di assegnazione
Pi
Rj
Operating System Concepts
8.8
Silberschatz, Galvin and Gagne 2002
Esempi di grafo di allocazione risorse
Grafo di allocazione risorse
Operating System Concepts
Grafo di allocazione risorse con deadlock
8.9
Silberschatz, Galvin and Gagne 2002
Grafo di allocazione risorse
 Se il grafo non contiene cicli 
no ci sono deadlock.
 Se il grafo contiene un ciclo 
 Se vi è 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 (ma non
certo).
Il ciclo c’è, ma il
deadlock no…
Operating System Concepts
8.10
Silberschatz, Galvin and Gagne 2002
Metodi per la gestione dei deadlock
 Assicurare che il sistema non entri mai in uno stato di
deadlock.
 Prevenzione dei deadlock: evitare che si verifichino
contemporaneamente mutua esclusione, possesso e attesa,
impossibiltà di prelazione e attesa circolare  basso utilizzo
risorse e throughput ridotto.
 Evitare i deadlock: evitare gli stati del sistema a partire
dai quali si può evolvere verso il deadlock.
 Permettere al sistema di entrare in uno stato di deadlock,
quindi ripristinare il sistema.
 Determinare la presenza di un deadlock.
 Ripristinare il sistema da un deadlock.
 Ignorare il problema e fingere che i deadlock non
avvengano mai nel sistema; impiegato dalla maggior
parte dei SO, incluso UNIX.
Operating System Concepts
8.11
Silberschatz, Galvin and Gagne 2002
Prevenire i deadlock
Limitare le modalità di richiesta/accesso delle risorse.
 Mutua esclusione —
non è richiesta per risorse
condivisibili; deve valere invece per risorse che non
possono essere condivise.
 Possesso e attesa — occorre garantire che, quando un
processo richiede una risorsa, non ne possieda altre.
 Richiedere ad un processo di stabilire ed allocare tutte le
risorse necessarie prima che inizi l’esecuzione, o consentire
la richiesta di risorse solo quando il processo non ne
possiede alcuna.
 Basso impiego delle risorse. È possibile che si verifichi
l’attesa indefinita.
Operating System Concepts
8.12
Silberschatz, Galvin and Gagne 2002
Prevenire i 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 al processo) vengono
aggiunte alla lista delle risorse che il processo sta
attendendo.
 Il processo viene avviato nuovamente solo quando può
ottenere sia le vecchie che le nuove risorse.
 Attesa circolare — si impone un ordinamento totale su
tutti i tipi di risorsa e si pretende che ciascun processo
richieda le risorse in ordine crescente.
Operating System Concepts
8.13
Silberschatz, Galvin and Gagne 2002
Evitare i deadlock
Presuppone che il sistema conosca a priori informazioni addizionali
sulle richieste future dei processi.
 Il modello più semplice e utile richiede che ciascun
processo dichiari il numero massimo di risorse di
ciascun tipo di cui può usufruire.
 L’algoritmo
di
deadlock–avoidance
esamina
dinamicamente lo stato di allocazione delle risorse per
assicurare che non si possa verificare mai 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.
Operating System Concepts
8.14
Silberschatz, Galvin and Gagne 2002
Stato sicuro
 Quando un processo richiede una risorsa disponibile, il sistema
deve decidere se l’allocazione immediata lasci il sistema in
stato sicuro.
 Il sistema si trova 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 essergli allocate
sfruttando le risorse disponibili + le risorse possedute da tutti i
Pj, con j < i.
 Se le richieste di
Pi non possono essere soddisfatte
immediatamente, 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, etc.
Operating System Concepts
8.15
Silberschatz, Galvin and Gagne 2002
Stato sicuro
 Se un sistema è in stato
sicuro  non si evolve
verso il deadlock.
 Se un sistema è in stato
non sicuro  si può
evolvere in deadlock.
 In stato non sicuro, il SO
non può impedire ai
processi di richiedere
risorse la cui allocazione
porta al deadlock.
 Deadlock–avoidance 
garantisce
che
un
sistema non entri mai in
stato non sicuro.
Operating System Concepts
8.16
Silberschatz, Galvin and Gagne 2002
Algoritmo con grafo di allocazione risorse
 Un arco di reclamo Pi  Rj
(rappresentato da una linea
tratteggiata) indica che il processo Pi può richiedere la risorsa Rj.
 Un arco di reclamo viene convertito in un arco di richiesta quando
il processo Pi richiede effettivamente la risorsa Rj.
 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.
Operating System Concepts
8.17
Silberschatz, Galvin and Gagne 2002
Grafo di allocazione risorse
Stato non sicuro in un grafo di
allocazione risorse
Grafo di allocazione risorse per
evitare i deadlock
Operating System Concepts
8.18
Silberschatz, Galvin and Gagne 2002
Algoritmo del banchiere
 Permette di gestire istanze multiple di una risorsa (a
differenza dell’algoritmo con grafo di allocazione risorse).
 Ciascun processo deve dichiarare a priori il massimo
impiego di risorse.
 Quando un processo richiede una risorsa può non venir
servito istantaneamente.
 Quando ad un processo vengono allocate tutte le risorse
deve restituirle in un tempo finito.
Operating System Concepts
8.19
Silberschatz, Galvin and Gagne 2002
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, il processo Pi può
richiedere al più k istanze del tipo di risorsa Rj .
 Allocation: matrice n x m. Se Allocation[ i,j ] = k, a Pi
sono attualmente allocate k istanze di Rj .
 Need: matrice n x m. Se Need [ i,j ] = k, Pi può richiedere
k ulteriori istanze di Rj per completare il proprio task.
Need [ i,j ] = Max [ i,j ] – Allocation [ i,j ]
Operating System Concepts
8.20
Silberschatz, Galvin and Gagne 2002
Algoritmo di verifica della sicurezza
1. Siano Work e Finish vettori di lunghezza m e n,
rispettivamente. Si inizializzi:
a) Work = Available
b) Finish[i ] = false per i = 1,2, …, n
2. Si cerchi i tale che valgano contemporaneamente:
a) Finish[i ] = false
b) Needi  Work
Se tale i non esiste, si esegua il passo 4.
3.
Work = Work + Allocationi
Finish[i ] = true
si torni al passo 2.
4. Se Finish [i ] == true per ogni i, il sistema è in stato sicuro.
Operating System Concepts
8.21
Silberschatz, Galvin and Gagne 2002
Algoritmo di richiesta delle risorse per il processo Pi
Sia Requesti il vettore delle richieste per il processo Pi . Se
Requesti [j ] = k, il processo Pi richiede k istanze del tipo
di risorsa Rj .
1. Se Requesti  Needi , si vada al passo 2. Altrimenti, si
riporti una condizione di errore, poiché il processo ha
ecceduto il massimo numero di richieste.
2. Se Requesti  Available, si vada al passo 3. Altrimenti Pi
deve attendere, poiché le risorse non sono disponibili.
3. Il sistema simula l’allocazione al processo Pi delle risorse
richieste, modificando lo stato di allocazione delle risorse
come segue:
Available = Available – Requesti
Allocationi = Allocationi + Requesti
Needi = Needi – Requesti
•
•
Operating System Concepts
Se lo stato è sicuro  le risorse vengono definitivamente
allocate a Pi .
Se lo stato è non sicuro  Pi deve attendere, e viene
ripristinato il vecchio stato di allocazione delle risorse.
8.22
Silberschatz, Galvin and Gagne 2002
Esempio di applicazione dell’algoritmo del banchiere
 5 processi, da P0 a P4; 3 tipi di risorse: A (10 instanze),
B (5 instanze), e C (7 instanze).
 Istantanea al tempo T0:
Allocation
Max
ABC
ABC
P0
010
753
P1
200
322
P2
302
902
P3
211
222
P4
002
433
Operating System Concepts
8.23
Available
ABC
332
Silberschatz, Galvin and Gagne 2002
Esempio di applicazione dell’algoritmo del banchiere
 Il contenuto della matrice Need è definito come Max – Allocation.
Need
ABC
P0
743
P1
122
P2
600
P3
011
P4
431
 Il sistema è in stato sicuro poiché la sequenza
< P1, P3, P4, P2, P0 >
soddisfa i criteri di sicurezza.
Operating System Concepts
8.24
Silberschatz, Galvin and Gagne 2002
Esempio (cont.): P1 richiede (1,0,2)
 Verificare che Requesti  Available (cioè, (1,0,2)  (3,3,2)  true ).
Allocation
Need
Available
ABC
ABC
ABC
P0 0 1 0
743
230
P1 3 0 2
020
P2 3 0 1
600
P3 2 1 1
011
P4 0 0 2
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) ?
Operating System Concepts
8.25
Silberschatz, Galvin and Gagne 2002
Rilevamento del deadlock
 Si permette al sistema di entrare in uno stato di deadlock
 Sono necessari:
 Algoritmo di rilevamento del deadlock
 Algoritmo di ripristino dal deadlock
Operating System Concepts
8.26
Silberschatz, Galvin and Gagne 2002
Istanza singola di ciascun tipo di risorsa
 Impiega un grafo di attesa:
 I nodi rappresentano i processi.
 L’arco Pi  Pj esiste se Pi è in attesa che Pj rilasci una
risorsa che gli occorre.
 Periodicamente viene richiamato un
algoritmo che
verifica la presenza di cicli nel grafo.
 Un algoritmo per rilevare cicli in un grafo richiede un
numero di operazioni dell’ordine di n2, dove n è il numero
di vertici del grafo.
Operating System Concepts
8.27
Silberschatz, Galvin and Gagne 2002
Grafo di allocazione risorse e grafo di attesa
Un arco Pi  Pj
esiste nel grafo di
attesa, se e solo se
il
corrispondente
grafo di allocazione
risorse contiene i
due archi Pi  Rq ,
Rq  Pj , per una
qualche risorsa Rq .
Grafo di allocazione risorse
Operating System Concepts
8.28
Grafo di attesa corrispondente
Silberschatz, Galvin and Gagne 2002
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 attualmente allocate a ciascun processo.
 Request: matrice n x m, indica la richiesta corrente di
ciascun processo. Se Request [i,j ] = k, il processo Pi
richiede k istanze supplementari della risorsa Rj .
Operating System Concepts
8.29
Silberschatz, Galvin and Gagne 2002
Algoritmo di rilevamento
1. Siano Work e Finish due vettori di lunghezza m e n,
rispettivamente. Inizialmente si ponga:
Work = Available
b) Per i = 1,2, …, n, se Allocationi  0, Finish[ i ] = false;
altrimenti, Finish[ i ] = true
a)
2. Si trovi un indice i tale che valgano entrambe le
condizioni:
Finish[ i ] = false
b) Requesti  Work
a)
Se tale i non esiste si vada al passo 4.
Operating System Concepts
8.30
Silberschatz, Galvin and Gagne 2002
Algoritmo di rilevamento
3.
Work = Work + Allocationi
Finish[i] = true
si vada al passo 2.
4. Se Finish[ i ] == false, per qualche i, 1  i  n, il sistema è in
uno stato di deadlock. Inoltre, se Finish[ i ] == false, Pi è in
deadlock.
L’algoritmo richiede un numero di operazioni dell’ordine di
(m x n 2 ) per determinare se il sistema è in uno stato di
deadlock.
Operating System Concepts
8.31
Silberschatz, Galvin and Gagne 2002
Esempio di applicazione dell’algoritmo di rilevamento
 Cinque processi, da P0 a P4; tre tipi di risorse: A (7 instanze),
B (2 instanze), e C (6 instanze).
 Istantanea al tempo T0:
Allocation Request
ABC
ABC
P0 0 1 0
000
P1 2 0 0
202
P2 3 0 3
000
P3 2 1 1
100
P4 0 0 2
002
Available
ABC
000
 La sequenza
<P0, P2, P3, P1, P4 >
conduce a Finish[ i ] = true per tutti gli i.
Operating System Concepts
8.32
Silberschatz, Galvin and Gagne 2002
Esempio di applicazione dell’algoritmo di rilevamento
 P2 richiede un’istanza supplementare della risorsa C.
P0
P1
P2
P3
P4
Request
ABC
000
202
001
100
002
 Stato del sistema?
 Può reclamare le 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.
Operating System Concepts
8.33
Silberschatz, Galvin and Gagne 2002
Impiego dell’algoritmo di rilevamento
 Quando e quanto
spesso richiamare l’algoritmo di
rilevamento dipende da:
 Frequenza (presunta) con la quale si verificano i deadlock;
 Numero di processi che vengono eventualmente influenzati
dal deadlock (e sui quali deve essere effettuato un rollback ):
 Almeno un processo per ciascun ciclo.
 Se l’algoritmo viene richiamato in momenti arbitrari,
possono essere presenti molti cicli nel grafo delle risorse
 non si può stabilire quale dei processi coinvolti nel
ciclo abbia “causato” il deadlock.
 Alternativamente, l’algoritmo può essere richiamato ogni
volta che una richiesta non può essere soddisfatta
immediatamente o quando l’utilizzo della CPU scende al
di sotto del 40%.
Operating System Concepts
8.34
Silberschatz, Galvin and Gagne 2002
Ripristino dal deadlock: Terminazione di processi
 Terminazione in abort di tutti i processi in deadlock.
 Terminazione in abort di un processo alla volta fino
all’eliminazione del ciclo di deadlock.
 In quale ordine si decide di terminare i processi? I fattori
significativi sono:
 La priorità del processo.
 Il tempo di computazione trascorso e il tempo ancora




Operating System Concepts
necessario al completamento del processo.
Quantità e tipo di risorse impiegate.
Risorse ulteriori necessarie al processo per terminare il
proprio compito.
Numero di processi che devono essere terminati.
Tipo di processo: interattivo o batch.
8.35
Silberschatz, Galvin and Gagne 2002
Ripristino dal deadlock: 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
selezionati come vittime della prelazione: includere il
numero di rollback nel fattore di costo.
Operating System Concepts
8.36
Silberschatz, Galvin and Gagne 2002
Approccio combinato alla gestione del deadlock
 Si combinano i tre approcci di base:
 prevenzione
 evitare i deadlock
 rilevamento
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.
Operating System Concepts
8.37
Silberschatz, Galvin and Gagne 2002