Java Deadlock: Cause e Prevenzione

Un deadlock è la modalità di fallimento del blocco. Due o più thread detengono ciascuno un lock di cui l'altro ha bisogno; nessuno può procedere; non viene lanciata alcuna eccezione; nulla nel log dice "siamo bloccati." Dall'esterno, il programma sembra non fare nulla — esattamente lo stesso sintomo esterno di un busy loop o di una chiamata di rete lunga.

I deadlock si verificano in qualsiasi programma che acquisisce più di un lock alla volta. Sono spaventosamente facili da scrivere e spaventosamente difficili da riprodurre — la pianificazione che li innesca potrebbe presentarsi una volta a settimana in produzione e mai nei test. La strategia giusta non è "eseguire il debug quando accadono" ma "strutturare il codice in modo che non possano accadere."

Le quattro condizioni (condizioni di Coffman)

Un deadlock richiede che tutte e quattro queste condizioni siano vere contemporaneamente:

Esclusione reciproca. Alcune risorse (un lock) possono essere detenute da un solo thread alla volta.
Hold and wait. Un thread detiene almeno una risorsa mentre aspetta di acquisirne un'altra.
Nessuna prelazione. Le risorse non possono essere sottratte al thread che le detiene; il thread deve rilasciarle volontariamente.
Attesa circolare. C'è un ciclo nel grafo delle attese — A aspetta il lock di B, B aspetta il lock di C, ..., Z aspetta il lock di A.

Rompendone una sola, i deadlock diventano impossibili. Le tecniche di prevenzione standard rompono ciascuna una delle quattro:

Ordinamento dei lock (più comune): rompere l'attesa circolare acquisendo sempre i lock in un ordine globalmente concordato.
tryLock con timeout: rompere l'hold-and-wait rinunciando se non si riesce a ottenere il secondo lock abbastanza rapidamente.
Singolo lock grande: eliminare completamente la struttura a più lock. Grezzo ma funziona per una contesa ridotta.
Dati lock-free / immutabili: rompere l'esclusione reciproca rimuovendo la risorsa. Gli atomici e le collezioni concorrenti trattati più avanti in questa parte del libro adottano questo approccio.

L'esempio dei due conti

La dimostrazione canonica:

void transfer(Account from, Account to, int amount) {
  synchronized (from) {
    synchronized (to) {
      from.debit(amount);
      to.credit(amount);
    }
  }
}

// Thread A: transfer(accountX, accountY, 100)
// Thread B: transfer(accountY, accountX, 100)

Pianificazione:

Il Thread A acquisisce il monitor di accountX.
Il Thread B acquisisce il monitor di accountY.
Il Thread A tenta di acquisire accountY — bloccato, detenuto da B.
Il Thread B tenta di acquisire accountX — bloccato, detenuto da A.

Nessun thread verrà mai rilasciato. Entrambi rimangono BLOCKED per sempre. La soluzione:

void transfer(Account from, Account to, int amount) {
  Account first  = from.id() < to.id() ? from : to;
  Account second = from.id() < to.id() ? to   : from;
  synchronized (first) {
    synchronized (second) {
      from.debit(amount);
      to.credit(amount);
    }
  }
}

Entrambi i thread acquisiscono ora accountX e poi accountY indipendentemente dalla direzione del trasferimento. L'attesa circolare non può formarsi.

La chiave di ordinamento non deve essere necessariamente un id — System.identityHashCode(obj) funziona come tiebreaker stabile per qualsiasi oggetto, ma le collisioni sono possibili, quindi il codice in produzione utilizza tipicamente una chiave reale (l'ID del database, l'ID utente, ecc.) e ricade su un lock tiebreaker quando le chiavi coincidono.

Ordinamento dei lock in tutto il programma

L'ordinamento dei lock funziona solo se ogni percorso di codice che acquisisce due lock dello stesso tipo li acquisisce nello stesso ordine. Un singolo metodo ribelle che fa synchronized (b) { synchronized (a) { ... } } è sufficiente a ripristinare il deadlock.

Il modo per garantire ciò in modo coerente in una codebase più grande:

Documentare l'ordine. "Acquisire sempre parent prima di child." Aggiungere un commento sulla classe.
Convogliare attraverso un unico helper. Tutte le chiamate di "trasferimento" passano attraverso un metodo che esegue l'ordinamento — in modo che un singolo call site non possa sbagliare.
-XX:+PrintConcurrentLocks in un thread dump è un modo per ispezionare i grafi effettivi di acquisizione dei lock in produzione.

La disciplina è importante quanto la regola.

`tryLock` con timeout

Quando non si può garantire l'ordinamento — librerie diverse, team diversi, grafi di oggetti complessi — ReentrantLock.tryLock(timeout, unit) offre una via d'uscita:

boolean done = false;
while (!done) {
  if (firstLock.tryLock(100, TimeUnit.MILLISECONDS)) {
    try {
      if (secondLock.tryLock(100, TimeUnit.MILLISECONDS)) {
        try {
          doWork();
          done = true;
        } finally { secondLock.unlock(); }
      }
    } finally { firstLock.unlock(); }
  }
  // back off briefly, retry — eventually we'll get both
}

Se il secondo lock non può essere ottenuto entro 100 ms, il thread rilascia il primo lock e riprova più tardi. La condizione di hold-and-wait è rotta — nessun thread rimane bloccato per sempre, anche se entrambi tentano gli stessi lock in ordini opposti.

Il costo è dato dai tentativi ripetuti e dal codice di back-off circostante. Usare l'ordinamento dei lock quando possibile; ricorrere a tryLock quando non è possibile.

Come rilevare un deadlock a runtime

Due strumenti principali.

Thread dump. jstack <pid> o kill -3 <pid> stampa lo stato e lo stack di ogni thread. Un deadlock appare chiaramente: due thread con stato BLOCKED, ciascuno - waiting to lock <0x...> su un oggetto che l'altro mostra come - locked <0x...>. La JVM di Java è anche abbastanza gentile da segnalare i cicli ovvi in fondo al dump:

Found one Java-level deadlock:
=============================
"thread-2":
  waiting to lock monitor 0x00007fcd0e..., which is held by "thread-1"
"thread-1":
  waiting to lock monitor 0x00007fcd0e..., which is held by "thread-2"

ThreadMXBean.findDeadlockedThreads(). Una versione programmatica — utile per incorporarla in un endpoint di health-check:

ThreadMXBean mx = ManagementFactory.getThreadMXBean();
long[] deadlocked = mx.findDeadlockedThreads();
if (deadlocked != null) log.error("deadlock detected: {} threads", deadlocked.length);

Questo trova solo i deadlock sui monitor intrinseci e su ReentrantLock. Non trova i livelock o i casi generici di "il thread è solo lento".

Livelock e starvation — i cugini del deadlock

Due modalità di fallimento che sembrano deadlock ma non lo sono:

Livelock. I thread continuano a cambiare stato ma non fanno progressi. Il caso classico: due chiamanti tryLock riprovano per sempre perché nessuno dei due cede per primo. La CPU è occupata; il lavoro non viene portato a termine.
Starvation. Un thread è tecnicamente RUNNABLE o risvegliabile ma lo scheduler / la politica di lock non lo lascia mai eseguire effettivamente. I lock non equi sotto forte contesa possono affamare uno scrittore mentre i lettori scorrono senza sosta.

Entrambi hanno lo stesso sintomo superficiale del deadlock ("nulla sembra fare progressi") ma la diagnosi è diversa — il thread dump non mostra BLOCKED su un ciclo reciproco; mostra thread che si agitano o solo uno in perenne attesa.

Un esempio concreto: deadlock creato e poi prevenuto

Il programma seguente esegue il pattern di trasferimento in entrambe le direzioni — prima con la versione a lock annidati non corretta (che andrà in deadlock sotto contesa), e poi con la correzione tramite ordinamento dei lock che lo previene. La versione non corretta è avvolta in un timeout watchdog in modo che la demo non rimanga bloccata per sempre.

java— editable, runs on the server

import java.lang.management.ManagementFactory;
import java.lang.management.ThreadMXBean;
import java.util.concurrent.atomic.AtomicInteger;

public class DeadlockDemo {
  static class Account {
    final int id;
    int balance;
    Account(int id, int balance) { this.id = id; this.balance = balance; }
    int id() { return id; }
    void debit(int x) { balance -= x; }
    void credit(int x) { balance += x; }
  }

static void transferBroken(Account from, Account to, int x) {
    synchronized (from) {
      try { Thread.sleep(1); }                            // increase deadlock probability
      catch (InterruptedException e) { Thread.currentThread().interrupt(); }
      synchronized (to) {
        from.debit(x);
        to.credit(x);
      }
    }
  }

static void transferSafe(Account from, Account to, int x) {
    Account first  = from.id() < to.id() ? from : to;
    Account second = first == from ? to : from;
    synchronized (first) {
      synchronized (second) {
        from.debit(x);
        to.credit(x);
      }
    }
  }

public static void main(String[] args) throws InterruptedException {
    runVariant("BROKEN  (nested locks, no ordering)", true);
    System.out.println();
    runVariant("FIXED   (locks in stable id order)", false);
  }

static void runVariant(String label, boolean broken) throws InterruptedException {
    Account a = new Account(1, 1000);
    Account b = new Account(2, 1000);
    AtomicInteger completed = new AtomicInteger();

Thread t1 = new Thread(() -> {
      for (int i = 0; i < 50; i++) {
        if (broken) transferBroken(a, b, 10); else transferSafe(a, b, 10);
        completed.incrementAndGet();
      }
    }, "t1");
    Thread t2 = new Thread(() -> {
      for (int i = 0; i < 50; i++) {
        if (broken) transferBroken(b, a, 10); else transferSafe(b, a, 10);
        completed.incrementAndGet();
      }
    }, "t2");

long t0 = System.nanoTime();
    t1.start(); t2.start();

// watchdog: if work isn't done in 3 seconds, dump deadlock info and bail
    boolean done = false;
    long deadline = t0 + 3_000_000_000L;
    while (System.nanoTime() < deadline) {
      if (completed.get() == 100) { done = true; break; }
      Thread.sleep(50);
    }

long elapsedMs = (System.nanoTime() - t0) / 1_000_000;
    System.out.println(label + ":");
    System.out.println("  completed: " + completed.get() + "/100  in " + elapsedMs + " ms");

if (!done) {
      ThreadMXBean mx = ManagementFactory.getThreadMXBean();
      long[] dl = mx.findDeadlockedThreads();
      if (dl != null) {
        System.out.println("  ThreadMXBean: deadlock detected, threads=" + dl.length);
      } else {
        System.out.println("  ThreadMXBean: no deadlock (threads may just be slow)");
      }
      // Don't actually wait forever — interrupt and move on
      t1.interrupt(); t2.interrupt();
    }
    t1.join(500); t2.join(500);
  }
}

Cosa trarre dall'esecuzione:

La variante BROKEN non ha completato tutti i 100 trasferimenti. Sotto contesa, t1 si è ritrovato a detenere a e ad aspettare b mentre t2 deteneva b e aspettava a. Il watchdog ha raggiunto il suo limite di 3 secondi; findDeadlockedThreads() ha confermato il ciclo. Questo è un deadlock — nessuna eccezione, nessun log, nulla di sbagliato in nessuna singola riga di codice.
La variante FIXED è terminata correttamente. La regola di ordinamento (first = id-min, second = id-max) significa che entrambi i thread acquisiscono prima a e poi b, indipendentemente dalla direzione del trasferimento. Il ciclo non può formarsi perché entrambi i thread percorrono il grafo dei lock nella stessa direzione.
Thread.sleep(1) all'interno del primo synchronized della versione non corretta rende il deadlock altamente riproducibile. Nel codice reale, raramente si vede questo tipo di sleep esplicito — ma I/O, GC o un context switch possono produrre la stessa finestra temporale. Ecco perché i deadlock si riproducono in modo intermittente in produzione e mai nei test.
ThreadMXBean.findDeadlockedThreads() ha restituito un array non null per la variante non corretta e ha confermato il conteggio dei thread coinvolti nel ciclo. Quella chiamata è la rete di sicurezza per il rilevamento in-process — integrarla in un endpoint di health e si verrà informati del deadlock prima dell'utente.
Dopo che il watchdog ha dichiarato bloccata la variante non corretta, il programma ha interrotto entrambi i thread. interrupt() non sveglia un thread bloccato su un monitor synchronized — sveglia solo i thread in sleep, wait, join o LockSupport.park. Ecco perché interrompere un deadlock non lo sblocca; bisognerebbe terminare la JVM (o usare ReentrantLock.lockInterruptibly).

Cosa c'è dopo

Il prossimo capitolo, Java volatile, si occupa della metà visibilità della storia della sicurezza — la parola chiave che risolve il problema "un thread scrive, un altro thread legge per sempre il vecchio valore" senza coinvolgere i lock.

Esercizi

Pratica

Quale strategia rompe direttamente la condizione di Coffman 'attesa circolare' ed è la tecnica più comune di prevenzione dei deadlock in Java?

Acquisire sempre più lock in un ordine globalmente concordato (ad es. per id stabile) in modo che il grafo delle attese non possa formare un cicloImpostare tutti i thread in contesa alla stessa priorità in modo che lo scheduler del SO non possa scegliere quello sbagliatoRacchiudere ogni blocco `synchronized` in un `try`/`finally` in modo che i lock vengano rilasciati in caso di eccezioneUsare `notifyAll` invece di `notify` in modo che tutti i thread bloccati abbiano la possibilità di fare progressi