Lo stallo: condizioni, prevenzione ed elusione
Le quattro condizioni di Coffman, grafo di allocazione e criterio del ciclo dimostrato, ordinamento delle risorse dimostrato, algoritmo del banchiere con esempio, filosofi a cena.
Uno stallo (deadlock) è una situazione in cui un gruppo di processi resta bloccato per sempre, perché ciascuno aspetta una risorsa tenuta da un altro del gruppo. È l’incrocio con quattro auto ferme, ognuna in attesa che passi quella alla sua destra. In questa lezione vediamo le quattro condizioni necessarie, il grafo di allocazione delle risorse con il criterio del ciclo, la prevenzione con l’ordinamento delle risorse e la sua dimostrazione, l’algoritmo del banchiere con un esempio, il rilevamento e il problema dei filosofi a cena.
Le quattro condizioni
Coffman (1971) ha mostrato che uno stallo può verificarsi solo se valgono contemporaneamente quattro condizioni:
- mutua esclusione: le risorse non sono condivisibili (una stampante, un lock);
- possesso e attesa: un processo tiene risorse mentre ne aspetta altre;
- nessuna prelazione: le risorse non si possono togliere a forza, solo rilasciare volontariamente;
- attesa circolare: esiste una catena di processi in cui ciascuno aspetta una risorsa del successivo, e l’ultimo una del primo.
Basta impedirne una per rendere lo stallo impossibile.
Il grafo di allocazione
Le relazioni tra processi e risorse si rappresentano con un grafo: un arco da una risorsa a un processo indica che la risorsa è assegnata a quel processo; un arco da un processo a una risorsa indica una richiesta in attesa.
Teorema. Se ogni risorsa ha una sola istanza, il sistema è in stallo se e solo se il grafo di allocazione contiene un ciclo.
Dimostrazione. Se c’è un ciclo, ogni processo del ciclo aspetta una risorsa, che ha una sola istanza ed è assegnata al processo successivo del ciclo, anch’esso in attesa: nessuno può proseguire né rilasciare, quindi sono in stallo. Viceversa, se c’è uno stallo, si parte da un processo bloccato: aspetta una risorsa, assegnata a un altro processo, che è a sua volta bloccato (altrimenti finirebbe e la rilascerebbe); seguendo la catena nel grafo finito si deve prima o poi tornare su un processo già visitato, e si chiude un ciclo. ∎
Con risorse a più istanze il ciclo è necessario ma non sufficiente: un’altra istanza può liberarsi e rompere l’attesa.
La prevenzione
Si nega una delle quattro condizioni. La più pratica è l’attesa circolare.
Teorema. Se le risorse sono numerate e ogni processo le richiede solo in ordine crescente di numero, l’attesa circolare non può verificarsi.
Dimostrazione. Supponiamo per assurdo un ciclo 
, in cui 
tiene la risorsa 
e aspetta 
, tenuta da 
(e 
aspetta 
). Poiché tiene e chiede , per la regola 
. Lungo il ciclo si ottiene 
, impossibile. ∎
È la regola usata nei kernel: i lock hanno un ordine documentato, e in Linux uno strumento di verifica (lockdep) segnala a tempo di esecuzione ogni violazione dell’ordine, anche se lo stallo non si è ancora verificato. Le altre condizioni si negano richiedendo tutte le risorse insieme all’inizio (contro possesso e attesa, ma spreca risorse) o permettendo la prelazione per le risorse il cui stato si può salvare, come la CPU e la memoria.
L’algoritmo del banchiere
L’elusione concede una richiesta solo se lo stato che ne risulta è sicuro: esiste un ordine in cui tutti i processi possono ottenere il massimo dichiarato e terminare. L’algoritmo del banchiere (Dijkstra) fa questa verifica.
Esempio. Una risorsa con 14 istanze e tre processi:
| Processo | Massimo | Assegnate | Fabbisogno residuo |
|---|---|---|---|
| P1 | 10 | 6 | 4 |
| P2 | 5 | 3 | 2 |
| P3 | 8 | 2 | 6 |
Sono disponibili 
istanze. Lo stato è sicuro: P2 (fabbisogno 2) può finire e restituire 3, disponibili 6; poi P1 (4), disponibili 12; poi P3. Se ora P3 chiede 2 istanze e gliele si concede, ne resta 1 disponibile e il fabbisogno di P3 diventa 4: nessun processo può più essere sicuro di finire (P2 ne chiede 2, P1 4, P3 4). Lo stato non sarebbe sicuro, e la richiesta viene rimandata, anche se non provocherebbe necessariamente uno stallo.
L’algoritmo richiede di conoscere in anticipo il massimo di ogni processo e costa 
per ogni richiesta, con 
tipi di risorsa: si usa in sistemi specializzati, non nei sistemi operativi generali.
Rilevamento e recupero
Molti sistemi lasciano che lo stallo avvenga, lo rilevano cercando cicli nel grafo di attesa e poi recuperano: terminano uno dei processi o gli tolgono una risorsa e lo riportano a un punto precedente. È la strategia dei database, che annullano una transazione e la rieseguono (lezione sulle transazioni di Sistemi informativi). I sistemi operativi generali, per i lock delle applicazioni, spesso non fanno nulla: ignorano il problema, lasciando alle applicazioni il compito di evitarlo.
I filosofi a cena
Cinque filosofi siedono a un tavolo rotondo con una forchetta tra ciascuna coppia; per mangiare ne servono due. Se tutti prendono contemporaneamente la forchetta a sinistra, ciascuno aspetta per sempre quella a destra: è un’attesa circolare. La soluzione con l’ordinamento: numerare le forchette e prendere sempre prima quella con il numero più basso. Così un filosofo, quello tra la forchetta 5 e la 1, prende prima la destra, e il ciclo si rompe.
