A Taxonomy of Concurrency Bugs

A race condition is any outcome that depends on the relative timing of threads (or processes, or requests) when the program did nothing to control that timing. The simplest carrier is a lost update: thread A reads balance = 100, thread B reads balance = 100, A writes 90, B writes 80; one withdrawal has vanished. Nothing crashed, no error was raised — the only evidence is that the number is wrong. Race Conditions takes this apart instruction by instruction.

Races hide behind anything that is read-then-written: counter++, if (!cache.has(k)) cache.set(k, compute()), if (!exists(path)) create(path), "check the balance then debit it". The database domain calls the same shape by the same name — the lost update anomaly (Concurrency Anomalies) — and the cure is the same family: make the read-modify-write atomic (a lock, an atomic instruction, UPDATE … SET n = n + 1, or compare-and-swap).

In production a race looks like drift: a metric slightly under the true count, a duplicate row a few times a week, a cache entry computed twice. In test suites it looks like flakiness — the interleaving that loses the update is rare, so the test passes on the laptop (two cores, light load) and fails on CI (many cores, heavy load, different timing). "Works on my machine" is often a literal description of the scheduler on that machine.

The second family has no interleaving at all — the program is "correct" if you assume every write is instantly seen by every thread in the order written. Hardware and compilers do not promise that. A visibility bug: thread A loops while (!done) {}; thread B sets done = true; A never exits. The compiler, seeing that nothing in the loop writes done, hoisted the load out of it; or the CPU keeps the stale value in a register. In C++ this is a data race and formally undefined behaviour; in Java the fix is volatile; in Go the race detector flags it; in every language the real fix is an atomic or a lock, which carry the ordering guarantees.

An ordering bug is subtler. Thread A writes data = 42 then ready = true; thread B reads ready == true then reads data and sees 0. On x86 that specific pattern cannot happen (stores are not reordered with other stores), but the compiler may reorder the two stores, and on ARM and POWER the CPU itself may — their memory models are weaker. The store-buffer reordering that x86 *does* permit (a store followed by a load to a different address may become visible in the other order) breaks Dekker-style mutual exclusion, which is why lock implementations end with a full fence. Atomic Operations covers acquire/release, the vocabulary for stating what order you need.

Symptom in production: works on x86 developer laptops and CI, fails on ARM servers (Graviton, Apple Silicon); or works at -O0 and fails at -O2. Tests almost never catch it because the reordering window is nanoseconds wide. Tools do: ThreadSanitizer (-fsanitize=thread) reports data races in C++ and Go; Java’s JCStress hunts reorderings; perf shows nothing because nothing is slow.

Deadlock: thread A holds lock 1 and waits for lock 2; thread B holds lock 2 and waits for lock 1; neither can proceed, ever. The process is alive, uses no CPU, and answers nothing. Deadlocks gives the four conditions and the cycle-detection view. Signature: a hang with 0% CPU; every thread in futex_wait or pthread_cond_wait in a stack dump; jstack literally prints "Found one Java-level deadlock". The cure is to break one condition — usually by imposing a global lock order.

Livelock is deadlock with motion. Two threads each detect the conflict, back off, retry at the same moment, conflict again. Two people in a corridor stepping the same way. Symptom: 100% CPU, no progress, no lock held long enough to show in a dump. Real cases: optimistic retries with fixed delays, two transactions repeatedly aborting each other, try_lock loops without randomised backoff. The fix is asymmetry — randomised or exponential backoff, or a priority rule so one side yields.

Starvation: a thread that is always eligible to run or acquire a lock but never does, because others keep winning. A reader-writer lock with a steady stream of readers never lets the writer in; a low-priority thread never gets the CPU on a saturated box; a lock without FIFO fairness lets a thread that just released it re-acquire it while a waiter is still waking (the "barging" that makes unfair locks fast and occasionally cruel). Symptom: one request’s latency is unbounded while the median is fine; one background job never completes. Fixes: fair queues, writer preference, bounded spinning, aging.

A low-priority thread L holds a lock. A high-priority thread H needs it and blocks. A medium-priority thread M, needing nothing, becomes runnable and — being higher priority than L — runs instead of L. H, the most important thread in the system, now waits on M, which has no relationship to it at all. This is priority inversion, and it is not academic: the Mars Pathfinder lander in 1997 kept resetting because a high-priority bus-management task missed its deadline waiting on a low-priority meteorological task that a medium-priority communications task kept preempting; the watchdog concluded the system had hung.

The fix Pathfinder received by remote patch is priority inheritance: while L holds a lock that H wants, L temporarily runs at H’s priority so M cannot preempt it. POSIX exposes it as PTHREAD_PRIO_INHERIT on mutex attributes; the Linux real-time patches and futex support it (FUTEX_LOCK_PI); the alternative, priority ceiling, raises any lock holder to the highest priority of any thread that may take the lock. General-purpose servers rarely hit this because they rarely use strict priorities — but anything with real-time threads (audio, control loops, SCHED_FIFO on Linux) can, and the symptom is deadline misses that correlate with *unrelated* load.

Most of the diagnostic value of the taxonomy is that the symptoms barely overlap. Wrong numbers with no errors: a race or lost update. Works on x86, fails on ARM, or works unoptimised: visibility/ordering. Hang at 0% CPU with all threads waiting: deadlock. Hang at 100% CPU with no progress: livelock, or a spinlock convoy (Mutexes). Median latency fine, tail unbounded, one job never finishes: starvation. Deadline misses under unrelated load in a real-time system: priority inversion.

The same catalogue exists one floor up. Database transactions suffer lost updates, write skew and deadlocks (Locks and Deadlocks) for identical reasons, and the database’s remedies — locks, versioning, deadlock detection, retries with backoff — are the same remedies with different names. If you can name the shape in one domain you can name it in the other.