07 - Race Condition and Deadlock: How to Recognize, Diagnose and Prevent Them

Two different failures that get confused

Imagine two cashiers updating the same paper ledger: both read "100", both write "101", and one payment vanishes. This is a data race: two threads access the same memory, at least one writes, and no synchronization orders them. Now imagine the cashiers use a padlock for the ledger, but each one, before writing, checks the balance and then queues up to write: the padlock protects every single access, and the balance goes negative anyway. This is a race condition in the broad sense: the result depends on the order in which events interleave, even though there is no data race at all. They are two different failures, with different tools.

The deadlock is the third: two threads each hold a resource the other is waiting for, and nobody advances any more. This article tests them all with code that was run: Java (OpenJDK 21.0.13) for the counters, the balance and the locks; C with gcc and ThreadSanitizer for a genuine data race report. The outcomes depend on timing, so where a number changes from one run to another I say so. For Go's detector see the section dedicated to it in goroutines and channels.

The simplest data race: counter++

contatore++ is not a single instruction: it is a read, an addition and a write. If two threads read the same value before either writes, an increment is lost. The listing increments a counter from eight threads, a hundred thousand times each, and does it three ways: a plain int, a synchronized block and an 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++;                              // read, add, write
                    synchronized (lock) { sincronizzato++; } // one section at a time
                    atomico.incrementAndGet();               // a single atomic instruction
                }
            });
        }
        exec.shutdown();
        exec.awaitTermination(30, TimeUnit.SECONDS);
        System.out.println("expected:       800000");
        System.out.println("plain int:      " + semplice);
        System.out.println("synchronized:   " + sincronizzato);
        System.out.println("AtomicInteger:  " + atomico.get());
    }
}

// Output:
// expected:       800000
// plain int:      790395
// synchronized:   800000
// AtomicInteger:  800000

The expected result is 800,000. The plain int loses nearly 10,000 in the run shown (790,395; in three other trials I got 793,117, 792,635 and 793,850); the figure changes with every run, the loss does not. The synchronized and the AtomicInteger always give 800,000. The difference between the two is in cost and scope: the atomic covers a single variable and uses a hardware instruction, the synchronized block can protect several fields together but serializes the threads. The number of cores matters: rerunning the same program pinned to a single core (taskset -c 0) the plain int gave 800,000 in all three trials, that is, no loss. It is one of the reasons these bugs "work in development" and fail in production.

ThreadSanitizer: letting the machine find it

Looking at the wrong result does not tell you where the bug is. ThreadSanitizer (TSan) is a compile-time tool that records memory accesses and flags those not ordered by synchronization. With gcc it is enabled with -fsanitize=thread. The listing is the C counterpart of the counter, with two threads.

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

int contatore = 0;                       // shared, unprotected

void *incrementa(void *arg) {
    for (int i = 0; i < 100000; i++)
        contatore++;                     // read, add, write: three steps
    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("expected 200000, got %d\n", contatore);
    return 0;
}

// Output:
// $ gcc -g -O1 -pthread contatore.c && ./a.out   (five runs)
// expected 200000, got 100000
// expected 200000, got 100000
// expected 200000, got 100000
// expected 200000, got 200000
// expected 200000, got 200000
//
// $ gcc -fsanitize=thread -g -O1 -pthread contatore.c && ./a.out   (main lines of the report)
// 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
// (the program prints) expected 200000, got 200000

First observation, a surprising one: compiled without TSan, the program printed 100,000 in three runs out of five, not a value slightly below 200,000. With -O1 the compiler loaded contatore into a register before the loop (you can see it in the assembly produced by gcc -S: a single movl contatore(%rip) before .L2) and writes it just once at the end, because in a program free of data races that would be a legitimate optimization: each thread starts from 0 and writes its own 100,000, and the last one wins. A data race in C is undefined behavior, and the compiler takes advantage of it.

Second observation: with TSan the report states the kind of access (a read against a previous write), the address, the line (contatore.c:7) and the variable (global 'contatore'). I removed pid and build ids from the output and abbreviated the addresses, for readability: I reported the main lines of the report, not the full text. TSan makes the program slower and heavier in memory, so it is used in development and in CI. The same goes for Go: the race detector documentation says that for a typical program memory can grow 5-10 times and execution time 2-20 times.

Race condition without a data race: check-then-act

The most insidious failure is the one that no data race detector finds, because there is no unsynchronized access. The listing has an account with two synchronized methods, and a withdrawal written as "read the balance; if it is enough, withdraw". Eight threads try to withdraw 100 from a balance of 100: with sound logic, at most one should succeed.

import java.util.concurrent.*;

// No data race: every method is synchronized. Yet the invariant "saldo >= 0" breaks.
public class Saldo {
    private int saldo = 100;

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

    // WRONG check-then-act: the lock is released between the check and the action
    void prelevaSeCapiente(int x, boolean lavoroIntermedio) {
        if (leggi() >= x) {
            if (lavoroIntermedio) Thread.yield();   // in reality: a log, a call, a computation
            preleva(x);
        }
    }

    // CORRECT: check and action under the same 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);       // starts the 8 withdrawals together
        for (int i = 0; i < 8; i++) {
            exec.submit(() -> {
                try { via.await(); } catch (InterruptedException e) { return; }
                switch (modo) {
                    case "narrow" -> conto.prelevaSeCapiente(100, false);
                    case "wide" -> 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[] {"narrow", "wide", "atomic"}) {
            int negativi = 0;
            for (int r = 0; r < 1000; r++) if (prova(modo) < 0) negativi++;
            System.out.println("check-then-act " + modo + ": negative balance in " + negativi + " trials out of 1000");
        }
    }
}

// Output:
// check-then-act narrow: negative balance in 2 trials out of 1000
// check-then-act wide: negative balance in 238 trials out of 1000
// check-then-act atomic: negative balance in 0 trials out of 1000

In the three scenarios there are a thousand trials. In the first, "narrow", the window between the check and the withdrawal is minimal and the negative balance appears 2 times out of 1,000: this is exactly what makes the bug dangerous, because in testing one case in a thousand goes unseen. In the second I simulated work between the two steps with Thread.yield() (in reality: a log, a network call) and the cases rose to 238 out of 1,000 in the first run and 106 in the second. In the third, the check and the action are under the same lock and the cases are zero. The rule is that the lock must cover the invariant, not the single access.

Deadlock: the four conditions

A deadlock requires four conditions to hold together, whose classic formulation is attributed to Coffman and colleagues (1971). I could not reach the original paper: the list follows the standard form of operating systems textbooks.

1. Mutual exclusion: the resource is held by only one thread at a time.
2. Hold and wait: a thread holds a resource while waiting for another.
3. No preemption: the resource cannot be taken away from whoever holds it.
4. Circular wait: there is a cycle of threads, each waiting for the next one's resource.

Here the order is a list, but the four conditions are all necessary: eliminating one is enough to prevent the deadlock. In practice it is almost always the fourth that is attacked, by imposing an order on lock acquisition, because the first three are properties of the resource or of the algorithm and hard to change.

A deadlock reproduced, detected and prevented

The classic is the transfer between two accounts: one thread moves money from X to Y, another from Y to X. If each locks the source account first, each holds one account and waits for the other. The listing implements the naive version and the one with a global order (the account with the lower identifier is always locked first), and uses ThreadMXBean.findDeadlockedThreads() to notice it. The 50 ms pause in the code serves to make the window wide enough to be reproducible.

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; }
    }

    // INCONSISTENT ORDER: locks 'da' first, then 'a'. Two opposite transfers cross each other.
    static void trasferisciNaive(Conto da, Conto a, int importo) {
        synchronized (da) {
            pausa();                      // makes the race window wide and reproducible
            synchronized (a) {
                da.saldo -= importo;
                a.saldo += importo;
            }
        }
    }

    // GLOBAL ORDER: always lock the account with the lower id first.
    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-to-y");
        Thread t2 = new Thread(() -> { if (ordinato) trasferisciOrdinato(y, x, 10); else trasferisciNaive(y, x, 10); }, "T2-y-to-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 ? "no deadlock, balances " + x.saldo + "+" + y.saldo + "=" + (x.saldo + y.saldo)
            : "DEADLOCK between " + morti.length + " thread"));
        if (morti != null) {
            for (ThreadInfo ti : mx.getThreadInfo(morti)) {
                System.out.println("  " + ti.getThreadName() + " waits for a monitor held by " + ti.getLockOwnerName());
            }
        }
    }

    public static void main(String[] args) throws Exception {
        boolean ordinato = args.length > 0 && args[0].equals("ordered");
        prova(ordinato ? "global order      " : "inconsistent order", ordinato);
        System.exit(0);   // if there is a deadlock the threads stay blocked: we exit this way
    }
}

// Output:
// $ java Deadlock
// inconsistent order: DEADLOCK between 2 thread
//   T1-x-to-y waits for a monitor held by T2-y-to-x
//   T2-y-to-x waits for a monitor held by T1-x-to-y
// $ java Deadlock ordered
// global order      : no deadlock, balances 1000+1000=2000

Run with no arguments, the program reports the deadlock with the names of the two threads and of whoever holds the monitor they are waiting for. With the argument ordered (ordinato in the code) the two transfers serialize and the balances come back consistent: 1,000 + 1,000 = 2,000. I ran the two cases in two separate JVMs, because after a deadlock the threads stay blocked and findDeadlockedThreads reports them in later trials too. The JVM's detector is documented (findDeadlockedThreads also considers the locks of java.util.concurrent), but it serves to discover the failure: the remedy is the order.

A variant of the ordering uses System.identityHashCode instead of an identifier. Use it with caution: the hash code is not guaranteed unique, so two different objects can have the same value and the order is no longer total. You need a unique identifier, like the account's id, or an extra lock that breaks ties. The tryLock(timeout) alternative does not prevent deadlock: it turns it into a failure you must know how to handle, with a retry or an error return.

Livelock and starvation

Two variants need naming. In livelock the threads keep acting but do not advance: two people in a corridor who both step aside to the same side. It often appears when a deadlock is resolved with tryLock and a symmetric retry: if the two threads retry with the same timing, they obstruct each other forever. The cure is a random delay. In starvation a thread never gets the resource. The ReentrantLock accepts a fairness parameter: the documentation says fair locks favor the thread that has waited longest and guarantee freedom from starvation, but can have lower overall throughput, "often much lower". I did not measure how much, because it depends on the load.

A checklist that can be verified

• Every shared resource has a clearly associated lock, written in the comment next to the field.
• Every invariant involving several values is protected by a single lock, for the whole duration of the check and the action.
• All locks are acquired in a documented global order, based on a unique identifier.
• Locks are released in finally (or defer in Go).
• Concurrent code passes under a detector (TSan, Go's race detector) in CI.

The list has two levels: the first two items prevent race conditions, the third and fourth prevent deadlock and lock leaks, the last tells you when you got it wrong. If you must pick just one to begin with, pick the last: none of the others can be verified by eye, and as seen, a race condition that appears 2 times in 1,000 beats any review.

What you can do now

You can tell a data race from a check-then-act race condition and reproduce both, use a detector (TSan, ThreadMXBean) to find them, and write the transfer code with a lock order that rules out deadlock. You also know that a concurrency bug that "cannot be seen" often shows up only with more cores, more load or a wider window.

The next article removes locks altogether: lock-free data structures, with CAS and memory ordering. For the version of the problem that arises from a producer that is too fast, see backpressure. For the concurrency models in which these failures arise, see the comparison of concurrency models. The case of virtual threads that stay pinned to their carrier thread is in the article on Java virtual threads. When concurrency crosses the network, failures change nature: see distributed systems.

The counts (793,117 out of 800,000, 2 and 238 out of 1,000) come from single runs on one machine; they change with every run. The C outputs were obtained with gcc with ThreadSanitizer enabled.