07 - Race Condition e Deadlock: Come Riconoscerli, Diagnosticarli e Prevenirli

Due guasti diversi che si confondono

Immagina due cassieri che aggiornano lo stesso registro cartaceo: entrambi leggono «100», entrambi scrivono «101», e un incasso sparisce. Questo è un data race: due thread accedono alla stessa memoria, almeno uno scrive, nessuna sincronizzazione li ordina. Ora immagina che i cassieri usino un lucchetto per il registro, ma che ognuno, prima di scrivere, controlli il saldo e poi si metta in coda per scrivere: il lucchetto protegge ogni singolo accesso, e il saldo diventa comunque negativo. Questa è una race condition in senso lato: il risultato dipende dall'ordine in cui gli eventi si intrecciano, anche se non c'è alcun data race. Sono due guasti diversi, con strumenti diversi.

Il deadlock è il terzo: due thread tengono ciascuno una risorsa che l'altro aspetta, e nessuno avanza più. Questo articolo li prova tutti con codice eseguito: Java (OpenJDK 21.0.13) per i contatori, il saldo e i lock; C con gcc e ThreadSanitizer per un rapporto vero di data race. Gli esiti dipendono dal timing, quindi dove un numero cambia da una esecuzione all'altra lo dico. Per il rilevatore di Go vedi la sezione dedicata in goroutine e channel.

Il data race più semplice: counter++

contatore++ non è una istruzione sola: è una lettura, una somma e una scrittura. Se due thread leggono lo stesso valore prima che uno dei due scriva, un incremento va perso. Il listato incrementa un contatore da otto thread, cento mila volte ciascuno, e lo fa in tre modi: un int semplice, un blocco synchronized e un AtomicInteger.

import java.util.concurrent.*;
import java.util.concurrent.atomic.AtomicInteger;

public class Contatore {
    static int semplice = 0;
    static int sincronizzato = 0;
    static final AtomicInteger atomico = new AtomicInteger();
    static final Object lock = new Object();

    public static void main(String[] args) throws Exception {
        ExecutorService exec = Executors.newFixedThreadPool(8);
        for (int t = 0; t < 8; t++) {
            exec.submit(() -> {
                for (int i = 0; i < 100_000; i++) {
                    semplice++;                              // leggi, somma, scrivi
                    synchronized (lock) { sincronizzato++; } // una sola sezione alla volta
                    atomico.incrementAndGet();               // un'unica istruzione atomica
                }
            });
        }
        exec.shutdown();
        exec.awaitTermination(30, TimeUnit.SECONDS);
        System.out.println("atteso:         800000");
        System.out.println("int semplice:   " + semplice);
        System.out.println("synchronized:   " + sincronizzato);
        System.out.println("AtomicInteger:  " + atomico.get());
    }
}

// Output:
// atteso:         800000
// int semplice:   790395
// synchronized:   800000
// AtomicInteger:  800000

Il risultato atteso è 800.000. L'int semplice ne perde quasi 10.000 nell'esecuzione mostrata (790.395; in altre tre prove ho ottenuto 793.117, 792.635 e 793.850); la cifra cambia a ogni esecuzione, la perdita no. Il synchronized e l'AtomicInteger danno sempre 800.000. La differenza fra i due è nel costo e nella portata: l'atomico copre una sola variabile e usa una istruzione hardware, il blocco synchronized può proteggere più campi insieme ma serializza i thread. Il numero di core conta: rilanciando lo stesso programma vincolato a un solo core (taskset -c 0) l'int semplice ha dato 800.000 in tutte e tre le prove, cioè nessuna perdita. È uno dei motivi per cui questi bug «funzionano in sviluppo» e falliscono in produzione.

ThreadSanitizer: farlo trovare alla macchina

Guardare il risultato sbagliato non dice dove sta il bug. ThreadSanitizer (TSan) è uno strumento di compilazione che registra gli accessi alla memoria e segnala quelli non ordinati da una sincronizzazione. Con gcc si abilita con -fsanitize=thread. Il listato è il corrispondente in C del contatore, con due thread.

#include <pthread.h>
#include <stdio.h>

int contatore = 0;                       // condiviso, senza protezione

void *incrementa(void *arg) {
    for (int i = 0; i < 100000; i++)
        contatore++;                     // leggi, somma, scrivi: tre passi
    return NULL;
}

int main(void) {
    pthread_t a, b;
    pthread_create(&a, NULL, incrementa, NULL);
    pthread_create(&b, NULL, incrementa, NULL);
    pthread_join(a, NULL);
    pthread_join(b, NULL);
    printf("atteso 200000, ottenuto %d\n", contatore);
    return 0;
}

// Output:
// $ gcc -g -O1 -pthread contatore.c && ./a.out   (cinque esecuzioni)
// atteso 200000, ottenuto 100000
// atteso 200000, ottenuto 100000
// atteso 200000, ottenuto 100000
// atteso 200000, ottenuto 200000
// atteso 200000, ottenuto 200000
//
// $ gcc -fsanitize=thread -g -O1 -pthread contatore.c && ./a.out   (righe principali del rapporto)
// WARNING: ThreadSanitizer: data race
//   Read of size 4 at 0x...ADDR by thread T2:
//     #0 incrementa contatore.c:7
//   Previous write of size 4 at 0x...ADDR by thread T1:
//     #0 incrementa contatore.c:7
//   Location is global 'contatore' of size 4 at 0x...ADDR
// SUMMARY: ThreadSanitizer: data race contatore.c:7 in incrementa
// (il programma stampa) atteso 200000, ottenuto 200000

Prima osservazione, che stupisce: compilato senza TSan, il programma ha stampato 100.000 in tre esecuzioni su cinque, non un valore leggermente inferiore a 200.000. Con -O1 il compilatore ha caricato contatore in un registro prima del ciclo (si vede nell'assembly prodotto da gcc -S: una sola movl contatore(%rip) prima di .L2) e lo scrive una volta sola alla fine, perché in un programma privo di data race sarebbe una ottimizzazione lecita: ogni thread parte da 0 e scrive il proprio 100.000, e l'ultimo vince. Un data race in C è comportamento indefinito, e il compilatore ne approfitta.

Seconda osservazione: con TSan il rapporto indica il tipo di accesso (lettura contro una scrittura precedente), l'indirizzo, la riga (contatore.c:7) e la variabile (global 'contatore'). Ho tolto dall'uscita pid e id di build e abbreviato gli indirizzi, per leggibilità: ho riportato le righe principali del rapporto, non il testo completo. TSan rende il programma più lento e più pesante in memoria, quindi si usa in sviluppo e in CI. Lo stesso vale per Go: la documentazione del race detector dice che per un programma tipico la memoria può crescere di 5-10 volte e il tempo di esecuzione di 2-20 volte.

Race condition senza data race: check-then-act

Il guasto più insidioso è quello che nessun rilevatore di data race trova, perché non c'è un accesso non sincronizzato. Il listato ha un conto con due metodi synchronized, e un prelievo scritto come «leggi il saldo; se basta, preleva». Otto thread tentano di prelevare 100 da un saldo di 100: a posto la logica, al massimo uno dovrebbe riuscire.

import java.util.concurrent.*;

// Nessun data race: ogni metodo e' synchronized. Eppure l'invariante "saldo >= 0" si rompe.
public class Saldo {
    private int saldo = 100;

    synchronized int leggi() { return saldo; }
    synchronized void preleva(int x) { saldo -= x; }

    // check-then-act SBAGLIATO: il lock si rilascia fra il controllo e l'azione
    void prelevaSeCapiente(int x, boolean lavoroIntermedio) {
        if (leggi() >= x) {
            if (lavoroIntermedio) Thread.yield();   // nella realta': un log, una chiamata, un calcolo
            preleva(x);
        }
    }

    // CORRETTO: controllo e azione sotto lo stesso lock
    synchronized void prelevaSeCapienteAtomico(int x) {
        if (saldo >= x) {
            saldo -= x;
        }
    }

    static int prova(String modo) throws Exception {
        Saldo conto = new Saldo();
        ExecutorService exec = Executors.newFixedThreadPool(8);
        CountDownLatch via = new CountDownLatch(1);       // fa partire gli 8 prelievi insieme
        for (int i = 0; i < 8; i++) {
            exec.submit(() -> {
                try { via.await(); } catch (InterruptedException e) { return; }
                switch (modo) {
                    case "stretto" -> conto.prelevaSeCapiente(100, false);
                    case "largo" -> conto.prelevaSeCapiente(100, true);
                    default -> conto.prelevaSeCapienteAtomico(100);
                }
            });
        }
        via.countDown();
        exec.shutdown();
        exec.awaitTermination(5, TimeUnit.SECONDS);
        return conto.leggi();
    }

    public static void main(String[] args) throws Exception {
        for (String modo : new String[] {"stretto", "largo", "atomico"}) {
            int negativi = 0;
            for (int r = 0; r < 1000; r++) if (prova(modo) < 0) negativi++;
            System.out.println("check-then-act " + modo + ": saldo negativo in " + negativi + " prove su 1000");
        }
    }
}

// Output:
// check-then-act stretto: saldo negativo in 2 prove su 1000
// check-then-act largo: saldo negativo in 238 prove su 1000
// check-then-act atomico: saldo negativo in 0 prove su 1000

Nei tre scenari le prove sono mille. Nel primo, «stretto», la finestra fra controllo e prelievo è minima e il saldo negativo compare 2 volte su 1.000: è proprio ciò che rende il bug pericoloso, perché in test un caso su mille non si vede. Nel secondo ho simulato lavoro fra i due passi con Thread.yield() (nella realtà: un log, una chiamata di rete) e i casi sono saliti a 238 su 1.000 nella prima esecuzione e 106 nella seconda. Nel terzo, controllo e azione stanno sotto lo stesso lock e i casi sono zero. La regola è che il lock deve coprire l'invariante, non il singolo accesso.

Deadlock: le quattro condizioni

Un deadlock richiede che si verifichino insieme quattro condizioni, la cui formulazione classica è attribuita a Coffman e colleghi (1971). Non ho potuto raggiungere l'articolo originale: la lista segue la forma standard dei testi di sistemi operativi.

1. Mutua esclusione: la risorsa è tenuta da un solo thread alla volta.
2. Hold and wait: un thread tiene una risorsa mentre ne aspetta un'altra.
3. Nessuna prelazione: la risorsa non può essere tolta a chi la tiene.
4. Attesa circolare: esiste un ciclo di thread, ciascuno in attesa della risorsa del successivo.

Qui l'ordine è un elenco, ma le quattro condizioni sono tutte necessarie: basta eliminarne una per impedire il deadlock. In pratica si attacca quasi sempre la quarta, imponendo un ordine nell'acquisizione dei lock, perché le prime tre sono proprietà della risorsa o dell'algoritmo e difficili da cambiare.

Un deadlock riprodotto, rilevato e prevenuto

Il classico è il trasferimento fra due conti: un thread sposta denaro da X a Y, un altro da Y a X. Se ognuno blocca prima il conto di partenza, ciascuno tiene un conto e aspetta l'altro. Il listato implementa la versione ingenua e quella con ordine globale (si blocca sempre per primo il conto con identificativo minore), e usa ThreadMXBean.findDeadlockedThreads() per accorgersene. La pausa di 50 ms nel codice serve a rendere la finestra così larga da essere riproducibile.

import java.lang.management.*;
import java.util.concurrent.*;

public class Deadlock {
    static class Conto {
        final int id;
        int saldo = 1000;
        Conto(int id) { this.id = id; }
    }

    // ORDINE INCOERENTE: blocca prima 'da', poi 'a'. Due trasferimenti opposti si incrociano.
    static void trasferisciNaive(Conto da, Conto a, int importo) {
        synchronized (da) {
            pausa();                      // rende la finestra di race larga e riproducibile
            synchronized (a) {
                da.saldo -= importo;
                a.saldo += importo;
            }
        }
    }

    // ORDINE GLOBALE: blocca sempre prima il conto con id minore.
    static void trasferisciOrdinato(Conto da, Conto a, int importo) {
        Conto primo = da.id < a.id ? da : a;
        Conto secondo = primo == da ? a : da;
        synchronized (primo) {
            pausa();
            synchronized (secondo) {
                da.saldo -= importo;
                a.saldo += importo;
            }
        }
    }

    static void pausa() { try { Thread.sleep(50); } catch (InterruptedException e) { } }

    static void prova(String nome, boolean ordinato) throws Exception {
        Conto x = new Conto(1), y = new Conto(2);
        Thread t1 = new Thread(() -> { if (ordinato) trasferisciOrdinato(x, y, 10); else trasferisciNaive(x, y, 10); }, "T1-x-verso-y");
        Thread t2 = new Thread(() -> { if (ordinato) trasferisciOrdinato(y, x, 10); else trasferisciNaive(y, x, 10); }, "T2-y-verso-x");
        t1.setDaemon(true); t2.setDaemon(true);
        t1.start(); t2.start();
        t1.join(1000); t2.join(1000);

        ThreadMXBean mx = ManagementFactory.getThreadMXBean();
        long[] morti = mx.findDeadlockedThreads();
        System.out.println(nome + ": " + (morti == null ? "nessun deadlock, saldi " + x.saldo + "+" + y.saldo + "=" + (x.saldo + y.saldo)
            : "DEADLOCK fra " + morti.length + " thread"));
        if (morti != null) {
            for (ThreadInfo ti : mx.getThreadInfo(morti)) {
                System.out.println("  " + ti.getThreadName() + " attende un monitor tenuto da " + ti.getLockOwnerName());
            }
        }
    }

    public static void main(String[] args) throws Exception {
        boolean ordinato = args.length > 0 && args[0].equals("ordinato");
        prova(ordinato ? "ordine globale   " : "ordine incoerente", ordinato);
        System.exit(0);   // se c'e' un deadlock i thread restano bloccati: chiudiamo cosi'
    }
}

// Output:
// $ java Deadlock
// ordine incoerente: DEADLOCK fra 2 thread
//   T1-x-verso-y attende un monitor tenuto da T2-y-verso-x
//   T2-y-verso-x attende un monitor tenuto da T1-x-verso-y
// $ java Deadlock ordinato
// ordine globale   : nessun deadlock, saldi 1000+1000=2000

Eseguito senza argomenti, il programma segnala il deadlock con i nomi dei due thread e di chi tiene il monitor che aspettano. Con l'argomento ordinato i due trasferimenti si serializzano e i saldi tornano coerenti: 1.000 + 1.000 = 2.000. Ho eseguito i due casi in due JVM separate, perché dopo un deadlock i thread restano bloccati e findDeadlockedThreads li segnala anche nelle prove successive. Il rilevatore della JVM è documentato (findDeadlockedThreads considera anche i lock di java.util.concurrent), ma serve a scoprire il guasto: il rimedio è l'ordine.

Una variante dell'ordinamento usa System.identityHashCode invece di un identificativo. Va usata con cautela: il codice hash non è garantito univoco, quindi due oggetti diversi possono avere lo stesso valore e l'ordine non è più totale. Serve un identificatore univoco, come l'id del conto, oppure un lock aggiuntivo che spezzi i pareggi. L'alternativa tryLock(timeout) non previene il deadlock: lo trasforma in un fallimento che devi saper gestire, con un rilancio o un ritorno di errore.

Livelock e starvation

Due varianti vanno nominate. Nel livelock i thread continuano ad agire ma non avanzano: due persone in un corridoio che si scostano entrambe dalla stessa parte. Si presenta spesso quando si risolve un deadlock con tryLock e un riprovare simmetrico: se i due thread ritentano con gli stessi tempi, si ostacolano per sempre. La cura è un ritardo casuale. Nella starvation un thread non ottiene mai la risorsa. Il ReentrantLock accetta un parametro di equità: la documentazione dice che i lock equi favoriscono il thread in attesa da più tempo e garantiscono l'assenza di starvation, ma possono avere un throughput complessivo inferiore, «spesso molto inferiore». Non ho misurato quanto, perché dipende dal carico.

Una lista di controllo che si può verificare

• Ogni risorsa condivisa ha un lock chiaramente associato, scritto nel commento accanto al campo.
• Ogni invariante che coinvolge più valori è protetto da un solo lock, per tutta la durata del controllo e dell'azione.
• Tutti i lock si acquisiscono in un ordine globale documentato, basato su un identificatore univoco.
• I lock si rilasciano in finally (o defer in Go).
• Il codice concorrente passa sotto un rilevatore (TSan, race detector di Go) in CI.

L'elenco ha due livelli: le prime due voci prevengono le race condition, la terza e la quarta prevengono il deadlock e le perdite di lock, l'ultima ti dice quando hai sbagliato. Se devi sceglierne una sola per iniziare, scegli l'ultima: nessuna delle altre si verifica a occhio, e come visto la race condition che compare 2 volte su 1.000 supera qualunque revisione.

Che cosa sai fare adesso

Sai distinguere un data race da una race condition di check-then-act e riprodurre entrambi, usare un rilevatore (TSan, ThreadMXBean) per trovarli, e scrivere il codice di trasferimento con un ordine dei lock che esclude il deadlock. Sai anche che un bug di concorrenza che «non si vede» spesso si vede solo con più core, più carico o una finestra più larga.

Il prossimo articolo toglie i lock del tutto: strutture dati lock-free, con CAS e memory ordering. Per la versione del problema che nasce da un producer troppo veloce, vedi backpressure. Per i modelli di concorrenza in cui questi guasti nascono, vedi il confronto fra i modelli di concorrenza. Il caso dei virtual thread che restano agganciati al loro thread portante è nell'articolo sui virtual thread di Java. Quando la concorrenza attraversa la rete i guasti cambiano natura: vedi i sistemi distribuiti.

Le conte (793.117 su 800.000, 2 e 238 su 1.000) vengono da esecuzioni singole su una macchina; cambiano a ogni esecuzione. Le uscite del C sono state ottenute con gcc con ThreadSanitizer abilitato.