Deadlock

1. Deadlock, starvation, livelock

Un deadlock è una situazione in cui due o più azioni in competizione aspettano ciascuna che l'altra finisca, e quindi nessuna finisce. Il caso più semplice con i lock è l'abbraccio mortale (deadly embrace): il thread A tiene il lock L e chiede M, mentre B tiene M e chiede L. Entrambi aspettano per sempre. Nel diagramma di stato (capitolo 4) è uno stato raggiungibile da cui i processi coinvolti non hanno più transizioni, e nessun evento esterno può sbloccarli.

Il deadlock è il più grave dei liveness hazard, ma non l'unico:

Il livelock si rompe introducendo un po' di casualità nei tentativi, per esempio un'attesa casuale prima di riprovare, così i processi smettono di muoversi in sincronia. Le priorità dei thread Java sono sconsigliate proprio perché dipendono dalla piattaforma e causano problemi di liveness.

Tra safety e liveness c'è una tensione. I lock garantiscono la thread safety, ma usati senza criterio creano deadlock di ordinamento dei lock. Semafori e thread pool limitano le risorse, ma se non si capisce che cosa limitano creano deadlock di risorse: cento task che si aspettano su una barriera, eseguiti da un pool di sedici thread, bloccano tutti i thread e gli altri task non partono mai (capitolo 10). All'estremo opposto, troppe sezioni critiche o troppo lunghe serializzano il programma (poor concurrency): vanno tenute brevi, senza però barattare la safety con le prestazioni.

2. I filosofi a cena

Il problema nasce da una domanda d'esame di Dijkstra del 1971 (cinque computer in competizione per cinque unità a nastro); Hoare lo ha raccontato come i filosofi a cena, e oggi è il banco di prova per confrontare formalismi concorrenti. Cinque filosofi pensano e mangiano, a un tavolo con cinque piatti, cinque forchette e una zuppiera di spaghetti sempre piena. Gli spaghetti sono così aggrovigliati che servono due forchette, e ogni filosofo può prendere solo quella alla sua sinistra e quella alla sua destra, una alla volta. Rispetto alla sezione critica, ogni processo ha bisogno di due risorse, condivise in cerchio.

Bisogna progettare un pre-protocollo e un post-protocollo intorno a eat che garantiscano cinque proprietà:

• un filosofo mangia solo se ha entrambe le forchette;
• mutua esclusione: nessuna forchetta è tenuta da due filosofi insieme;
• assenza di deadlock;
• assenza di starvation;
• comportamento efficiente in assenza di contesa.

Il primo tentativo modella ogni forchetta con un semaforo binario: wait la prende, signal la posa.

semaphore array[0..4] fork := [1, 1, 1, 1, 1]

philosopher i: loop forever
p1: think
p2: wait(fork[i])              -- sinistra
p3: wait(fork[(i+1) mod N])    -- destra
p4: eat
p5: signal(fork[i])
p6: signal(fork[(i+1) mod N])

Si dimostra che nessuna forchetta è mai tenuta da due filosofi. Però la soluzione va in deadlock: basta un interleaving in cui tutti prendono la forchetta sinistra prima che qualcuno provi a prendere la destra. A quel punto F0 aspetta f1, tenuta da F1, che aspetta f2, e così via fino a F4, che aspetta f0, tenuta da F0. Si è formato un ciclo di attese che nessun evento può sciogliere.

3. Quando può esserci un deadlock: le condizioni di Coffman

Coffman (1971) ha individuato quattro condizioni necessarie. Un deadlock può verificarsi solo in un sistema in cui valgono tutte e quattro:

1. Mutua esclusione: una risorsa non può essere usata da più processi alla volta.
2. Possesso e attesa (hold and wait): un processo che tiene già delle risorse può chiederne altre.
3. Nessuna prelazione (no preemption): una risorsa non può essere tolta a chi la tiene, e si libera solo con un'azione esplicita del processo.
4. Attesa circolare (circular wait): due o più processi formano una catena circolare, in cui ciascuno aspetta una risorsa tenuta dal successivo.

Sono necessarie, non sufficienti: nel primo tentativo dei filosofi valgono tutte, ma molti interleaving non si bloccano mai. Il valore pratico è l'altra direzione: per prevenire il deadlock basta rompere una delle quattro. Le soluzioni di questo capitolo rompono l'attesa circolare. Con i lock di Java si può anche rompere il possesso e attesa, prendendo un lock alla volta oppure rinunciando a quelli già presi quando un tryLock fallisce. Mutua esclusione e assenza di prelazione, invece, di solito sono proprio ciò che si vuole da un lock.

4. Due soluzioni per i filosofi

semaphore array[0..4] fork := [1, 1, 1, 1, 1]
semaphore ticket := (4, {})

philosopher i: loop forever
p1: think
p2: wait(ticket)
p3: wait(fork[i])
p4: wait(fork[(i+1) mod N])
p5: eat
p6: signal(fork[i])
p7: signal(fork[(i+1) mod N])
p8: signal(ticket)

semaphore array[0..4] fork := [1, 1, 1, 1, 1]
integer first  := min(i, (i+1) mod N)
integer second := max(i, (i+1) mod N)

philosopher i: loop forever
p1: think
p2: wait(fork[first])
p3: wait(fork[second])
p4: eat
p5: signal(fork[first])
p6: signal(fork[second])

L'ordinamento non costa nulla, ma richiede di poter ordinare le risorse. Se le risorse sono dinamiche, cioè le forchette vanno e vengono, un ordine globale può non esistere, e resta il ticket.

Simulatore

Ogni pulsante esegue un'istruzione atomica di un filosofo. Una wait su una forchetta occupata non si può eseguire finché la forchetta non torna libera. Il simulatore cerca a ogni passo i cicli nel grafo delle attese, e le tracce precaricate mostrano il deadlock del primo tentativo e perché ticket e ordine totale lo evitano.

5. La regola generale, in Java

Con N processi che condividono e acquisiscono più lock, la regola per evitare il deadlock è:

1. assegnare un ordine totale ai lock;
2. acquisirli sempre nello stesso ordine.

Funziona perché rende impossibile l'attesa circolare. In un ciclo ogni processo tiene un lock e ne chiede uno di rango maggiore, quindi percorrendo il ciclo si avrebbe r₀ < r₁ < … < r₀, che è assurdo. Un programma che non tiene mai più di un lock alla volta non può avere deadlock di ordinamento. Se deve prenderne più di uno, l'ordine va progettato: si minimizzano le interazioni tra lock e si documenta il protocollo d'ordinamento. Verificare che un programma rispetti un ordine coerente richiede infatti un'analisi globale di tutti i punti in cui prende lock.

L'esempio delle slide è il trasferimento di denaro tra conti. transferMoney(from, to, amount) prende il lock di from e poi quello di to. Con venti thread che fanno trasferimenti casuali, prima o poi uno esegue transfer(a, b) mentre un altro esegue transfer(b, a): è l'abbraccio mortale. La correzione ordina i lock in base all'indice del conto:

public void transferMoney(int from, int to, int amount) throws InsufficientBalanceException {
    int first = Math.min(from, to), last = Math.max(from, to);   // ordine globale
    synchronized (accounts[first]) {
        synchronized (accounts[last]) {
            if (accounts[from].getBalance() < amount) throw new InsufficientBalanceException();
            accounts[from].debit(amount);
            accounts[to].credit(amount);
        }
    }
}

Più insidiosi sono i deadlock tra oggetti che cooperano, in cui nessun metodo prende esplicitamente due lock. Nel pattern Observer delle slide, changeState è synchronized sull'osservato e chiama notifyStateChanged, che è synchronized sull'osservatore. Intanto un altro thread esegue getOverallState, synchronized sull'osservatore, che chiama getState, synchronized sull'osservato. Sono due lock presi in ordine opposto, nascosti in due chiamate di metodo. È lo stesso rischio delle chiamate annidate tra monitor (capitolo 7), e riguarda ogni implementazione a eventi in un linguaggio a oggetti, come l'MVC.

L'alternativa all'ordinamento sono i lock temporizzati. tryLock di ReentrantLock, con o senza timeout, permette di accorgersi che un lock non arriva, rilasciare quelli già presi e riprovare più tardi. In questo modo si rompe il possesso e attesa. Con i lock intrinseci di synchronized questo non è possibile. Le attese prima di riprovare vanno rese casuali, altrimenti i thread rischiano di ritentare in sincronia per sempre: sarebbe un livelock.

6. Si può rilevare e recuperare un deadlock?

In generale sì, ed è ciò che fanno i database. Una transazione accumula lock fino al commit, quindi non è raro che due transazioni finiscano in deadlock. Il DBMS mantiene il grafo delle attese («chi aspetta chi»), vi cerca cicli e, se ne trova uno, sceglie una vittima e ne abortisce la transazione. I lock della vittima vengono rilasciati, le altre proseguono, e la transazione abortita può essere rieseguita.

La JVM no: non ha alcun meccanismo automatico di rilevamento e recupero. Se dei thread vanno in deadlock su synchronized, restano lì: non si possono nemmeno interrompere, e l'unica via d'uscita è chiudere l'applicazione. Resta la diagnosi post-mortem con il thread dump. Su Unix si ottiene inviando SIGQUIT al processo (kill -3) o premendo Ctrl-\; su Windows con Ctrl-Break. Il dump contiene lo stack di ogni thread e le informazioni sui lock: quali tiene ciascun thread, in quale frame li ha presi, e quale lock aspetta chi è bloccato. La JVM vi segnala anche i deadlock trovati. Strumenti come jstack, JConsole e VisualVM mostrano le stesse informazioni.

Verifica le tue conoscenze