Deadlock - condizioni, prevenzione, evitamento e rilevamento

In questa pagina 9

Quando i processi condividono risorse e le richiedono in modo concorrente (Semafori, monitor e problemi classici di sincronizzazione) può accadere che ognuno aspetti una risorsa tenuta da un altro, e che nessuno possa più andare avanti. Questa nota definisce lo stallo (deadlock), lo caratterizza con il grafo di allocazione delle risorse, e presenta i quattro approcci: prevenire, evitare (con l'algoritmo del banchiere), rilevare e ripristinare, ignorare. Gli esercizi numerici (banchiere e grafi) sono nell'elenco in fondo.

Modello di sistema

Un sistema ha risorse di vari tipi $R_1, R_2, \dots, R_m$ (cicli di CPU, spazio di memoria, file, dispositivi di I/O, ma anche mutex e semafori), e ogni tipo $R_i$ ha una o più istanze identiche. Ogni processo usa una risorsa in tre passi: richiesta (se non è disponibile, aspetta), uso, rilascio.

Un primo esempio con due semafori $S_1 = S_2 = 1$ e due thread:

T1:  wait(S1)  wait(S2)  ...        T2:  wait(S2)  wait(S1)  ...

Se $T_1$ ottiene $S_1$ , poi $T_2$ ottiene $S_2$ , poi $T_1$ chiede $S_2$ e $T_2$ chiede $S_1$ , nessuno può continuare: è un deadlock. Si vede in pratica nel laboratorio 6 (Esercizio - Deadlock con semafori e thread (laboratorio 6)).

Definizione (deadlock). Un insieme di processi è in deadlock (stallo, blocco critico) se ogni processo dell'insieme sta aspettando un evento (il rilascio di una risorsa) che può essere causato solo da un altro processo dello stesso insieme.

Caratterizzazione: le quattro condizioni

Un deadlock può verificarsi solo se valgono contemporaneamente quattro condizioni (condizioni di Coffman):

condizione	significato
mutua esclusione	almeno una risorsa è non condivisibile: un solo processo alla volta la usa
hold and wait (possesso e attesa)	un processo che possiede almeno una risorsa aspetta di ottenerne altre, possedute da altri
no preemption (assenza di prelazione)	una risorsa può essere rilasciata solo volontariamente dal processo che la possiede, dopo aver finito
attesa circolare (circular wait)	esiste un insieme $\{T_0, \dots, T_n\}$ tale che $T_0$ aspetta una risorsa di $T_1$ , $T_1$ una di $T_2$ , ..., $T_{n-1}$ una di $T_n$ , e $T_n$ una di $T_0$

Grafo di allocazione delle risorse

Definizione (grafo di allocazione delle risorse). È un grafo diretto con insieme di vertici $V = T \cup R$ , dove $T = \{T_1, \dots, T_n\}$ sono i processi (nodi circolari) e $R = \{R_1, \dots, R_m\}$ i tipi di risorse (nodi rettangolari, con un punto per ogni istanza). Un arco di richiesta $T_i \to R_j$ dice che $T_i$ ha chiesto un'istanza di $R_j$ e la attende; un arco di assegnazione $R_j \to T_i$ dice che un'istanza di $R_j$ è assegnata a $T_i$ .

Per i grafi diretti, i cicli e la loro ricerca si rimanda a Grafi diretti e ordinamento topologico, Grafi - definizioni e proprietà e Visite di grafi - BFS e DFS. Come si legge un grafo:

caso	conclusione
il grafo non ha cicli	nessun deadlock
ha un ciclo e ogni risorsa ha una sola istanza	deadlock (il ciclo è necessario e sufficiente)
ha un ciclo e alcune risorse hanno più istanze	deadlock possibile, non certo (il ciclo è necessario ma non sufficiente)

Esempio: sistema con 3 processi e 4 tipi di risorse ( $R_1$ : 1 istanza, $R_2$ : 2, $R_3$ : 1, $R_4$ : 3). $T_1$ possiede un'istanza di $R_2$ e aspetta $R_1$ ; $T_2$ possiede $R_1$ e un'istanza di $R_2$ e aspetta $R_3$ ; $T_3$ possiede $R_3$ . Gli archi sono $R_2 \to T_1$ , $T_1 \to R_1$ , $R_1 \to T_2$ , $R_2 \to T_2$ , $T_2 \to R_3$ , $R_3 \to T_3$ : nessun ciclo, quindi niente stallo ( $T_3$ finisce, libera $R_3$ , $T_2$ prosegue, e così via). Se anche $T_3$ chiedesse $R_2$ (arco $T_3 \to R_2$ ) si avrebbe il ciclo $T_2 \to R_3 \to T_3 \to R_2 \to T_2$ e i processi $T_1$ , $T_2$ , $T_3$ sarebbero in stallo; se invece un ciclo passa per una risorsa con più istanze, può esserci un'istanza posseduta da un processo fuori dal ciclo che prima o poi la rilascerà, e il ciclo si scioglie.

Come trattare i deadlock

Garantire che il sistema non entri mai in deadlock: prevenzione (negare almeno una delle quattro condizioni) oppure evitamento (usare informazioni in più per scegliere le assegnazioni).
Lasciare entrare il sistema in deadlock e poi rilevarlo e ripristinarlo.
Ignorare il problema, fingendo che non capiti (è la scelta di Linux e Windows: il costo di prevenire è maggiore di quello di un riavvio raro, e la responsabilità è dei programmatori).

Prevenzione

Si invalida una delle quattro condizioni.

condizione negata	come	svantaggi
mutua esclusione	non serve per le risorse condivisibili (file in sola lettura); non si può negare per quelle non condivisibili (una stampante)
hold and wait	un processo chiede una risorsa solo quando non ne possiede nessuna, oppure se le fa assegnare tutte all'inizio	bassa utilizzazione delle risorse, possibile starvation
no preemption	se un processo chiede una risorsa non disponibile, rilascia tutte quelle che possiede (che finiscono nella sua lista d'attesa); riparte solo quando riottiene le vecchie più la nuova	adatto a risorse il cui stato si salva (registri, memoria), non a una stampante o un mutex
attesa circolare	si impone un ordinamento totale dei tipi di risorsa e si chiede ogni processo di richiedere le risorse in ordine crescente ( $R_1$ , poi $R_2$ , ...)	sceglie l'ordine ma non lo fa rispettare da solo

Perché l'ordinamento nega l'attesa circolare? Un'attesa circolare richiederebbe che l'ultimo processo chieda una risorsa del primo, cioè con un indice minore di quella che già possiede: contro la regola. È la soluzione dei filosofi a cena con l'indice minore per primo (Semafori, monitor e problemi classici di sincronizzazione) e la correzione dei laboratori di deadlock1.c.

Evitamento

L'evitamento richiede informazioni a priori: il modello più semplice vuole che ogni processo dichiari il numero massimo di risorse di ciascun tipo che userà. Lo stato di allocazione è definito dalle risorse disponibili, da quelle assegnate e dalle richieste massime. Un algoritmo di evitamento esamina dinamicamente lo stato per garantire che non si possa mai creare un'attesa circolare.

Stato sicuro

Definizione (stato sicuro). Uno stato è sicuro se esiste una sequenza sicura $\langle T_1, \dots, T_n \rangle$ di tutti i processi tale che, per ogni $T_j$ , le risorse che può ancora chiedere si possono soddisfare con le risorse disponibili ora più quelle possedute da tutti i $T_i$ con $i < j$ .

Cioè: se $T_j$ non ha subito ciò che gli serve, aspetta che i $T_i$ precedenti finiscano; allora ottiene le risorse, esegue, restituisce tutto e termina; poi tocca a $T_{j+1}$ , e così via.

stato sicuro $\Rightarrow$ nessun deadlock;
stato non sicuro $\Rightarrow$ deadlock possibile (non certo);
l'evitamento garantisce che il sistema non entri mai in uno stato non sicuro.

Evitamento con il grafo (una sola istanza per risorsa)

Si aggiunge l'arco di rivendicazione (claim edge) $T_i \to R_j$ , tratteggiato: $T_i$ potrebbe chiedere $R_j$ in futuro. Quando $T_i$ la chiede diventa arco di richiesta; quando gliela si assegna diventa arco di assegnazione; quando la rilascia torna di rivendicazione. Le risorse vanno dichiarate in anticipo. Una richiesta si può soddisfare solo se la conversione dell'arco di richiesta in arco di assegnazione non crea un ciclo (contando anche gli archi di rivendicazione): altrimenti il processo attende.

L'algoritmo del banchiere (istanze multiple)

Si usa quando i tipi hanno più istanze. Ogni processo dichiara in anticipo il massimo; quando chiede una risorsa potrebbe dover aspettare; quando ottiene tutto deve restituirlo in tempo finito. Con $n$ processi e $m$ tipi di risorse:

struttura	dimensioni	significato
`Available`	vettore di $m$	`Available[j] = k`: $k$ istanze di $R_j$ libere
`Max`	matrice $n \times m$	`Max[i][j] = k`: $T_i$ può chiedere al più $k$ istanze di $R_j$
`Allocation`	$n \times m$	`Allocation[i][j] = k`: $T_i$ possiede ora $k$ istanze di $R_j$
`Need`	$n \times m$	`Need[i][j] = Max[i][j] - Allocation[i][j]`: quante ne potrebbe ancora chiedere

Il confronto tra vettori è componente per componente: $X \le Y$ vuol dire $X_j \le Y_j$ per ogni $j$ .

Algoritmo di sicurezza (è sicuro lo stato?):

Work = Available;   Finish[i] = false per ogni i
finché esiste i con Finish[i] == false  e  Need[i] <= Work:
        Work = Work + Allocation[i];  Finish[i] = true
se Finish[i] == true per ogni i  ->  stato SICURO     altrimenti  ->  NON sicuro

Work è la quantità di risorse che si renderebbe disponibile se i processi già "finiti" restituissero quanto possiedono. La sequenza in cui i processi vengono marcati è la sequenza sicura (non è unica).

Algoritmo di richiesta. Sia Request[i] il vettore con cui $T_i$ chiede risorse:

se Request[i] <= Need[i] si va al passo 2, altrimenti errore (il processo supera il massimo dichiarato);
se Request[i] <= Available si va al passo 3, altrimenti $T_i$ attende (risorse non disponibili);
si simula l'assegnazione: Available -= Request[i], Allocation[i] += Request[i], Need[i] -= Request[i]; si esegue l'algoritmo di sicurezza: se lo stato è sicuro si assegna davvero, se non sicuro $T_i$ attende e lo stato precedente viene ripristinato.

Complessità. L'algoritmo di sicurezza ha un ciclo esterno al più $n$ volte; in ogni passata si scorrono gli $n$ processi e per ciascuno si confrontano $m$ componenti: $O(m \cdot n^2)$ (v. Esercizio - Implementare il banchiere e calcolarne la complessità (eserciziario, esercizio 3 e laboratorio 6)).

Esempio svolto

Cinque thread $T_0..T_4$ , tre tipi di risorse: $A$ (10 istanze), $B$ (5), $C$ (7). Fotografia all'istante $t_0$ :

	Allocation $A\,B\,C$	Max $A\,B\,C$	Need $=$ Max $-$ Alloc
$T_0$	0 1 0	7 5 3	7 4 3
$T_1$	2 0 0	3 2 2	1 2 2
$T_2$	3 0 2	9 0 2	6 0 0
$T_3$	2 1 1	2 2 2	0 1 1
$T_4$	0 0 2	4 3 3	4 3 1

Totale assegnato: $(7, 2, 5)$ ; Available $= (10,5,7) - (7,2,5) = (3,3,2)$ .

Il sistema è sicuro? Si prova la sequenza $\langle T_1, T_3, T_4, T_2, T_0 \rangle$ :

passo	processo scelto	$Need_i \le Work$ ?	$Work$ dopo ( $+\,Alloc_i$ )
inizio			$(3,3,2)$
1	$T_1$	$(1,2,2) \le (3,3,2)$ sì	$(5,3,2)$
2	$T_3$	$(0,1,1) \le (5,3,2)$ sì	$(7,4,3)$
3	$T_4$	$(4,3,1) \le (7,4,3)$ sì	$(7,4,5)$
4	$T_2$	$(6,0,0) \le (7,4,5)$ sì	$(10,4,7)$
5	$T_0$	$(7,4,3) \le (10,4,7)$ sì	$(10,5,7)$

Tutti finiscono: stato sicuro. (Alla fine Work è uguale al totale delle risorse, come deve essere.)

$T_1$ chiede $(1,0,2)$ . Controllo: $(1,0,2) \le Need_1 = (1,2,2)$ sì; $(1,0,2) \le Available = (3,3,2)$ sì. Nuovo stato: Available $= (2,3,0)$ , $Alloc_1 = (3,0,2)$ , $Need_1 = (0,2,0)$ . La sequenza $\langle T_1, T_3, T_4, T_0, T_2 \rangle$ è sicura ( $T_1$ : $(0,2,0)\le(2,3,0)$ , $Work=(5,3,2)$ ; $T_3$ : $Work = (7,4,3)$ ; $T_4$ : $(7,4,5)$ ; $T_0$ : $(7,5,5)$ ; $T_2$ : $(10,5,7)$ ): la richiesta si accetta.

Poi $T_4$ chiede $(3,3,0)$ : $(3,3,0) > Available = (2,3,0)$ (la $A$ non basta): $T_4$ attende.

Poi $T_0$ chiede $(0,2,0)$ : è $\le Need_0$ e $\le Available$ . Dopo l'assegnazione Available $= (2,1,0)$ e i bisogni sono $T_0$ : $(7,2,3)$ , $T_1$ : $(0,2,0)$ , $T_2$ : $(6,0,0)$ , $T_3$ : $(0,1,1)$ , $T_4$ : $(4,3,1)$ . Nessuno ha $Need \le (2,1,0)$ ( $T_1$ vuole 2 di $B$ ma ce n'è 1; $T_3$ vuole 1 di $C$ e ce ne sono 0; gli altri vogliono più di 2 di $A$ ): stato non sicuro, la richiesta non si accetta anche se le risorse ci sono.

Rilevamento

L'altra strategia: lasciar entrare il sistema in deadlock, rilevarlo con un algoritmo e ripristinarlo.

Una sola istanza per risorsa: grafo wait-for

Si mantiene un grafo wait-for (di attesa): i nodi sono solo i processi e c'è un arco $T_i \to T_j$ se $T_i$ aspetta una risorsa posseduta da $T_j$ . Si ottiene dal grafo di allocazione togliendo i nodi risorsa e collassando gli archi $T_i \to R \to T_j$ in $T_i \to T_j$ . Periodicamente si cerca un ciclo: se c'è, c'è deadlock. La ricerca di un ciclo costa $O(n^2)$ nel numero di archi, come in Visite di grafi - BFS e DFS.

Più istanze per risorsa

Si usa un algoritmo analogo a quello del banchiere, con Allocation e una matrice Request (le richieste correnti di ogni processo, invece di Need). Si parte da Work = Available; i processi senza risorse assegnate (Allocation[i] = 0) sono considerati finiti; poi si cerca un $i$ non finito con Request[i] <= Work: lo si "completa" e si somma Allocation[i] a Work. Alla fine, i processi non finiti sono in deadlock.

Esempio: cinque thread, tipi $A$ (7 istanze), $B$ (2), $C$ (6); Available $= (0,0,0)$ .

	Allocation $A\,B\,C$	Request $A\,B\,C$
$T_0$	0 1 0	0 0 0
$T_1$	2 0 0	2 0 2
$T_2$	3 0 3	0 0 0
$T_3$	2 1 1	1 0 0
$T_4$	0 0 2	0 0 2

Svolgimento: $T_0$ può finire ( $Request = 0 \le Work$ ): $Work = (0,1,0)$ ; $T_2$ pure: $Work = (3,1,3)$ ; ora $T_3$ ( $(1,0,0)$ ): $Work = (5,2,4)$ ; $T_4$ ( $(0,0,2)$ ): $Work = (5,2,6)$ ; $T_1$ ( $(2,0,2)$ ): $Work = (7,2,6)$ . La sequenza $\langle T_0, T_2, T_3, T_4, T_1 \rangle$ completa tutti: nessun deadlock.

Se ora $T_2$ chiede un'altra istanza di $C$ ( $Request_2 = (0,0,1)$ ): si recuperano le risorse di $T_0$ , ma $Work = (0,1,0)$ non basta per nessun altro ( $T_2$ chiede 1 di $C$ , ce ne sono 0; $T_1$ chiede $A$ e $C$ ; $T_3$ chiede $A$ ; $T_4$ chiede $C$ ): i processi $T_1$ , $T_2$ , $T_3$ , $T_4$ sono in deadlock.

Quando eseguire il rilevamento

Dipende da quanto spesso è probabile un deadlock e da quanti processi vanno annullati (uno per ogni ciclo disgiunto). Se l'algoritmo è lanciato a caso ci possono essere molti cicli nel grafo e non si saprebbe quale dei processi bloccati ha "causato" lo stallo.

Ripristino

Terminare i processi: si abortiscono tutti i processi in deadlock, oppure uno alla volta finché il ciclo sparisce. Si sceglie secondo: priorità, quanto ha già calcolato e quanto manca, risorse usate e risorse che ancora servono, quanti processi vanno terminati, se è interattivo o batch.

Prelazione delle risorse: (1) scegliere una vittima minimizzando un costo; (2) rollback: riportare il processo a uno stato sicuro e farlo ripartire da lì; (3) evitare la starvation: la stessa vittima potrebbe essere scelta sempre, quindi si include il numero di rollback nel costo.

Esercizi collegati

Domande d'esame

1. Elencare le quattro condizioni del deadlock e dire quale si nega ordinando le risorse. Perché funziona? Traccia. Mutua esclusione, hold and wait, no preemption, attesa circolare. L'ordinamento totale nega l'attesa circolare: se ogni processo chiede le risorse in ordine crescente di indice, un ciclo richiederebbe che qualcuno chieda una risorsa di indice minore di una che già possiede, contro la regola.

2. Cos'è uno stato sicuro? Uno stato non sicuro è sempre un deadlock? Traccia. Esiste una sequenza di tutti i processi in cui ognuno può finire con le risorse disponibili più quelle liberate dai precedenti. Se è sicuro non ci sarà deadlock. Non sicuro non significa deadlock, solo che esiste la possibilità: alcuni processi potrebbero non chiedere il loro massimo. L'evitamento (banchiere) lo impedisce comunque.

3. Dato un grafo di allocazione con un ciclo, si può concludere che c'è deadlock? Traccia. Solo se ogni risorsa del ciclo ha una sola istanza. Con più istanze il ciclo è necessario ma non sufficiente: un'istanza posseduta da un processo fuori dal ciclo può liberarsi e sciogliere l'attesa; si verifica con l'algoritmo del banchiere o di rilevamento.

Versione ripasso

Deadlock: insieme di processi in attesa di eventi (rilasci di risorse) causabili solo da processi dell'insieme. Uso di una risorsa: richiesta, uso, rilascio.
Quattro condizioni insieme: mutua esclusione, hold and wait, no preemption, attesa circolare.
Grafo di allocazione: processi (cerchi), risorse (rettangoli con un punto per istanza), arco di richiesta $T\to R$ , di assegnazione $R\to T$ . Senza cicli: niente deadlock; ciclo + istanza singola: deadlock; ciclo + più istanze: possibile. Rimandi: Grafi diretti e ordinamento topologico.
Strategie: prevenire, evitare, rilevare e ripristinare, ignorare (Linux, Windows).
Prevenzione: nega mutua esclusione (impossibile per risorse non condivisibili), hold and wait (tutte insieme: bassa utilizzazione), no preemption (rilascia tutto, riparte), attesa circolare: ordine totale delle risorse e richieste crescenti.
Stato sicuro: esiste una sequenza sicura di tutti i processi; sicuro $\Rightarrow$ no deadlock, non sicuro $\Rightarrow$ deadlock possibile. Grafo con archi di rivendicazione (istanza singola): si concede solo se non si forma un ciclo.
Banchiere: Available, Max, Allocation, Need = Max - Allocation. Sicurezza: Work=Available; cerca $i$ con Finish[i]=false e Need[i]<=Work, Work+=Allocation[i]; sicuro se finiscono tutti. Richiesta: Request<=Need (altrimenti errore), Request<=Available (altrimenti attende), simula e verifica la sicurezza. Complessità $O(m\,n^2)$ .
Esempio: $A10,B5,C7$ , Available $(3,3,2)$ : sicuro con $\langle T_1,T_3,T_4,T_2,T_0\rangle$ ; $T_1:(1,0,2)$ concessa; poi $T_4:(3,3,0)$ attende, $T_0:(0,2,0)$ rifiutata (non sicuro).
Rilevamento: istanza singola = grafo wait-for (ciclo = deadlock); più istanze = come il banchiere con Request al posto di Need (processi senza risorse sono finiti); i non finiti sono in deadlock. Esempio $A7,B2,C6$ : nessun deadlock; con $T_2$ che chiede un altro $C$ : deadlock di $T_1..T_4$ .
Ripristino: terminare tutti o uno alla volta (criteri di scelta); prelazione con vittima, rollback, attenzione alla starvation (contare i rollback nel costo).
Esempio di grafo senza stallo: $R_1$ (1), $R_2$ (2), $R_3$ (1); $T_1$ ha $R_2$ e attende $R_1$ ; $T_2$ ha $R_1$ , $R_2$ e attende $R_3$ ; $T_3$ ha $R_3$ : nessun ciclo. Se $T_3$ chiede anche $R_2$ : ciclo $T_2\to R_3\to T_3\to R_2\to T_2$ e le due istanze di $R_2$ sono di $T_1$ e $T_2$ $\Rightarrow$ deadlock.
Prevenzione, svantaggi: hold and wait (tutte all'inizio) $\to$ bassa utilizzazione e starvation; no preemption $\to$ solo per risorse salvabili; circular wait $\to$ ordine totale e richieste crescenti (l'ultimo dovrebbe chiedere un indice minore di quello che possiede).
Stato sicuro: sequenza $\langle T_1,\dots,T_n\rangle$ di tutti i processi con $Need_j\le Available+\sum_{i<j}Allocation_i$ . Sicuro $\Rightarrow$ no deadlock; non sicuro $\Rightarrow$ deadlock possibile.
Esempio del banchiere ( $A10,B5,C7$ , Available $(3,3,2)$ ): Need $T_0(7,4,3)$ , $T_1(1,2,2)$ , $T_2(6,0,0)$ , $T_3(0,1,1)$ , $T_4(4,3,1)$ ; sequenza $\langle T_1,T_3,T_4,T_2,T_0\rangle$ con Work $(5,3,2)$ , $(7,4,3)$ , $(7,4,5)$ , $(10,4,7)$ , $(10,5,7)$ . $T_1:(1,0,2)$ concessa; poi $T_4:(3,3,0)$ attende (Available $(2,3,0)$ ); $T_0:(0,2,0)$ rifiutata (dopo: Available $(2,1,0)$ , nessun Need $\le$ ).
Rilevamento, esempio ( $A7,B2,C6$ ): Allocation $T_0(0,1,0)$ , $T_1(2,0,0)$ , $T_2(3,0,3)$ , $T_3(2,1,1)$ , $T_4(0,0,2)$ ; Request $0$ , $(2,0,2)$ , $0$ , $(1,0,0)$ , $(0,0,2)$ ; Available $(0,0,0)$ ; sequenza $T_0,T_2,T_3,T_4,T_1$ $\Rightarrow$ nessun deadlock. Se $T_2$ chiede un altro $C$ : Work $(0,1,0)$ non basta, deadlock di $T_1,T_2,T_3,T_4$ .
Grafo wait-for (istanza singola): nodi solo i processi, $T_i\to T_j$ se $T_i$ attende una risorsa di $T_j$ ; un ciclo = deadlock; ricerca del ciclo $O(n^2)$ . Quando eseguire il rilevamento: dipende da quanto spesso capita e da quanti processi vanno annullati (uno per ciclo disgiunto).
Ripristino: terminare tutti i processi coinvolti o uno alla volta (criteri: priorità, tempo già calcolato e residuo, risorse usate e necessarie, quanti da terminare, interattivo o batch); prelazione: scegliere la vittima (costo minimo), rollback a uno stato sicuro, evitare la starvation contando i rollback nel costo.
Complessità del banchiere: al più $n$ giri $\times$ $n$ processi $\times$ $m$ componenti = $O(m\,n^2)$ ; si paga a ogni richiesta.
Errori tipici: confondere stato non sicuro e deadlock; dimenticare Request <= Need (errore) prima di Available; confrontare vettori sul totale invece che componente per componente; dire che un ciclo implica sempre deadlock; scambiare Need con Allocation.