Concurrency — Interleavings, Deadlock, and TOCTOU

Every edge so far — numbers, strings, collections, dates, and absence — lived inside a value. Feed the value, watch the output, and a passing test told you something durable: the same input gives the same output next time. This page attacks a different dimension entirely. The bug isn’t in the value; it’s in the schedule — the order in which two or more threads happen to run relative to each other.

That one word, “happen,” is why concurrency is the hardest edge on this whole shelf. The scheduler is not yours to control. Two threads that pass a million times can fail the millionth-and-first because the OS sliced time one instruction earlier. A concurrency test that goes green proves that one interleaving works; it says almost nothing about the interleaving that actually breaks. This page is about making the bad schedule visible and reproducible instead of hoping the scheduler is kind.

Why the schedule is an input you forgot you had

A single-threaded function has one input: its arguments. A concurrent one has a hidden second input — the interleaving, the specific way the runtime shuffled the instructions of each thread together. You never wrote it, you can’t see it, and there are astronomically many of them.

  Thread A:  read x   ─┐        ┌─  x = x+1
  Thread B:            └─ read x ─┘           x = x+1

  Two threads, one shared x. Their instructions can be interleaved
  many ways. MOST orders give the right answer. A FEW do not:

    A: read x (0)
    B: read x (0)      ← both read the same 0 before either wrote
    A: write x = 1
    B: write x = 1     ← B's write clobbers A's — one increment LOST

  Final x = 1, not 2. This order occurs maybe 1 run in 10,000.

The final line is the whole problem. Most schedules give 2; a rare one gives 1. A test that runs the two threads once will almost certainly hit a good schedule and pass — and it will keep passing on your laptop, in CI, in the demo, right up until the one production request where the timing lines up. A green concurrency test is weak evidence. The failing schedule exists in the space of possible runs; your test just didn’t sample it. This changes the goal of the whole page: not “does it pass once?” but “can I force the bad schedule, and does it still pass?”

The classic races

Almost every concurrency bug you’ll meet is a variation on two patterns. Learn to recognize the shape and you’ll spot them in code review before they ship.

Lost update — read-modify-write without protection

The counter above is the archetype. Any operation of the form read a value, compute a new one from it, write it back is a lost-update waiting to happen if two threads run it on the same data. Between one thread’s read and its write, another thread can read the same stale value; whichever writes last wins, and the other’s work vanishes.

This exact race lives in the repo’s own kvlite tests, documented on purpose:

// From rust/kvlite/tests/concurrency.rs — many threads, ONE key.
thread::spawn(move || {
    for _ in 0..PER_THREAD {
        let current = store.get(&"hits".to_string()).unwrap().unwrap();
        store.set("hits".into(), current + 1).unwrap();   // read, then write
    }
})

Each get and each set is individually locked and safe. But the gap between them is not: thread A’s get reads 41, thread B’s get reads 41 before A’s set lands, both write 42, and one of the two increments is gone. The test’s own comment is the lesson — it asserts only that the total is in range (total <= THREADS * PER_THREAD), because get-then-set across two lock acquisitions cannot promise an exact count. The neighbouring test that writes distinct keys per thread can assert an exact length, because those writes never contend for the same slot. Same store, same locks; the difference is entirely in whether two operations share a read-modify-write on one value.

Check-then-act (TOCTOU) — the state moved between look and leap

The second pattern is subtler and more dangerous because it often wears the costume of a safety check. Time-of-check to time-of-use is any code that inspects a condition and then acts on the assumption the condition still holds — when, between the check and the use, another thread (or process) changed it.

  if (!file.exists()) {        ← CHECK: file is absent
        // ... another thread/process creates the file here ...
      file.create();           ← USE: acts on stale "absent" — clobbers!
  }

  if (account.balance >= 100) { ← CHECK: enough funds
        // ... a concurrent withdrawal drains the account here ...
      account.withdraw(100);   ← USE: overdraws — the balance moved
  }

The check was true when you looked. By the time you acted, it was a lie. The window between check and use is often nanoseconds — which is exactly why it’s so rarely hit in testing and so reliably hit at scale. TOCTOU is behind duplicate-order bugs (“check no order exists, then create one” — two clicks create two orders), inventory oversells (two buyers each see “1 in stock”), and a whole family of security holes where a permission is checked and then a different file is used. The fix is never “check harder”; it’s to make the check and the act one atomic step that nothing can interleave — a topic we return to below.

Deadlock — everyone waiting, no one moving

Races corrupt data. Deadlock does the opposite: nothing corrupts because nothing happens. Two threads each hold a lock the other needs, and both wait forever.

  Thread A                    Thread B
  ────────                    ────────
  lock(accounts)              lock(ledger)
  ... work ...                ... work ...
  lock(ledger)   ◄── waits    lock(accounts)  ◄── waits
       for B to release            for A to release

  A holds accounts, wants ledger.  B holds ledger, wants accounts.
  Neither will ever release. The system hangs, using 0% CPU.

A deadlock requires four conditions to hold at once (the Coffman conditions) — break any one and it cannot occur:

Mutual exclusion — a resource is held by one thread at a time (that’s what a lock is).
Hold-and-wait — a thread holds one resource while waiting for another.
No preemption — you can’t forcibly yank a lock away from the thread holding it.
Circular wait — a cycle exists: A waits for B, B waits for A (or a longer loop).

The cheapest, most practical one to break is circular wait, and the tool is consistent lock ordering: agree on a global order for locks (e.g. always acquire the lower account ID before the higher) and require every thread to acquire them in that order. If everyone locks in the same sequence, no cycle can form — because a cycle needs someone to have grabbed them in the opposite order.

  Rule: always lock the lower ID first.

  Transfer(1 → 2):  lock(1) then lock(2)
  Transfer(2 → 1):  lock(1) then lock(2)   ← NOT lock(2) then lock(1)!

  Both threads now queue for lock(1) first; the loser simply waits.
  No cycle → no deadlock.

The Therac-25 radiation therapy machine delivered massive overdoses to at least six patients between 1985 and 1987, several fatal. A central cause, as reconstructed in the investigations that followed, was a race condition: when a skilled operator edited the treatment parameters unusually fast, a concurrent-programming flaw let the machine’s software act on inconsistent state — a check-then-act window where the high-power configuration hadn’t been reconciled with the safety interlock. Crucially, the earlier Therac-20 had the same software defect but a hardware interlock that physically prevented the overdose; the Therac-25 removed the hardware guard and trusted the software alone.

The testing lessons are permanent even though the machine is history. First, the bug appeared only under a specific timing (fast keystrokes) — the kind of interleaving that ordinary testing never reproduces, because testers don’t type that fast on purpose. Second, “it passed in testing” meant nothing: the failing schedule was simply never sampled. Treat exact keystroke sequences as illustrative; the rule is firm — a race that can maim someone must be forced in a test, not left to the scheduler.

Making races testable

The core insight: you cannot fix what you cannot reproduce, and you cannot reproduce a race by running it once. So stop hoping the scheduler cooperates and instead attack the schedule.

Force the bad interleaving

If a race lives in the window between two operations, widen the window under test. Inject a delay or a synchronization barrier at the exact point where the interleaving matters, so the bad order becomes the guaranteed order rather than a one-in-ten-thousand accident.

# Deterministically FORCE the lost-update race with a barrier.
import threading

balance = {"v": 100}
after_read = threading.Barrier(2)     # both threads must reach here

def withdraw():
    current = balance["v"]            # READ
    after_read.wait()                 # ← both threads read BEFORE any write
    balance["v"] = current - 100      # WRITE (both computed from 100)

t1, t2 = threading.Thread(target=withdraw), threading.Thread(target=withdraw)
t1.start(); t2.start(); t1.join(); t2.join()

assert balance["v"] == -100   # PROVES the bug: two withdrawals, one seen

The barrier removes the randomness: both threads are made to read before either writes, so the lost update happens every single run. Now you have a deterministic, always-red test for the bug — the prerequisite for fixing it and knowing it stays fixed.

Run many iterations, and stress

When you can’t cleanly inject a barrier, tilt the odds. Run the concurrent operation thousands of times in a loop, with many threads, so a rare interleaving becomes a likely one across the aggregate. This is what the kvlite test does: 8 threads × 1_000 iterations hammering one store is enough contention that the safe operations (distinct keys, atomic methods) reliably prove exact counts, and the unsafe one (get-then-set) reliably fails to. A stress test doesn’t guarantee the bug shows — but ten thousand tries beat one.

  Suppose the bad schedule occurs 1 run in 10,000 (p = 0.0001).
  Probability a stress loop of N runs samples it at least once
  is 1 - (1 - p)^N :

  ITERATIONS      P(catch the 1-in-10,000 bad schedule)
  ─────────────────────────────────────────────────────
        1          0.0001    (0.01%)  — a single run proves ~nothing
      100          0.00995   (~1%)
    1,000          0.0952    (~10%)
   10,000          0.6321    (~63%)
  100,000          0.99995   — now you'll almost certainly catch it

  A single-run concurrency test isn't "weak" — it is ~0.01% of a test.

Use a sanitizer instead of luck

Even 100,000 runs can miss a race — and worse, they only catch observable corruption, not the underlying data race that happens to produce a benign result this time. The right tool is a thread sanitizer (TSan) or the equivalent (Go’s -race, Java’s tooling, Rust’s loom for exhaustive interleaving search). These instrument every memory access and detect a data race — two threads touching the same memory with at least one write and no synchronization — even on a run where the output happened to come out right. They flag the race at its cause, not its symptom, so you don’t need to be lucky enough to hit the bad schedule.

  Approach          catches...                          needs the bad
                                                        schedule to occur?
  ────────────────────────────────────────────────────────────────────────
  single run        almost nothing                      yes (and won't)
  stress loop       observable corruption               yes (probably)
  barrier/inject    one specific interleaving           no (you forced it)
  thread sanitizer  the data race itself, at its cause  no

Reach for the sanitizer first in CI; reach for the barrier when you need a deterministic regression test that pins one specific bug.

The fix: atomicity and idempotency

Testing surfaces the race; the cure is to make the dangerous sequence un-interleaveable. Two ideas do almost all the work.

Atomic operations — one indivisible step

Collapse read-modify-write into a single operation that the hardware or database guarantees nothing can split. A compare-and-swap (CAS) says “write new only if the value is still expected” in one instruction — if another thread changed it, CAS fails and you retry from the fresh value, so no update is ever lost. In a database, wrap the check and the act in one transaction with the right isolation (or a single UPDATE ... WHERE balance >= 100) so the DB refuses to let another writer slip between them. In kvlite’s terms, the fix for the lost-update counter is a single write-locked increment method, not get then set across two lock acquisitions — one lock held across the whole read-modify-write closes the window.

  RACY (two steps, a window between them):
      x = get(k);  put(k, x + 1)       ← another thread interleaves here

  SAFE (one atomic step, no window):
      compare_and_swap(k, x, x + 1)     ← succeeds or retries; never lost
      -- or --
      UPDATE t SET n = n + 1 WHERE k=?  ← the DB serializes it for you

Idempotency — make a repeat harmless

The TOCTOU sibling: instead of preventing a duplicate act, make the act safe to apply more than once, so a retry or a doubled request converges to the same state. Key the operation by a unique client-supplied token (“process payment idem-abc123”) and have the server record it — the second arrival of the same token is recognized and returns the first result instead of charging twice. This turns a race into a safe retry: it no longer matters how many times or in what order the request lands, only that the end state is correct. Idempotency is why “at-least-once delivery” networks can still bill you exactly once.

Together they cover both classic races: atomic operations close the lost-update window; idempotency neutralizes the check-then-act duplicate.

The architect’s lens

Why does it exist? Because concurrency introduces a hidden input — the schedule — that you didn’t write and can’t see, and most schedules hide a bug that a rare one exposes. These techniques exist to make that hidden input controllable and testable.
What problem does it solve? It converts “passes once, fails one time in a thousand in production” into a bug you can force, reproduce, and regression-test — and then eliminate with atomicity or idempotency so the failing schedule is no longer failing.
What are the trade-offs? Locks and transactions add contention and can deadlock; sanitizers and stress loops are slow and CPU-hungry; idempotency needs a stored token and a dedup path. You pay throughput and complexity to buy determinism and correctness.
When should I avoid it? When there is genuinely no shared mutable state — immutable data, message-passing with no aliasing, or per-request isolation — there’s no race to force, and adding locks just invents contention and deadlock risk where none existed. Don’t lock what nothing shares.
What breaks if I remove it? You get a green test suite that only ever sampled good schedules, lost updates that silently drop money or clicks, TOCTOU duplicates and oversells, and deadlocks that hang the system at 0% CPU — all invisible until the exact production timing that your single-run test never explored.

Check your understanding

Why does a concurrency test that passes prove almost nothing about whether the code is correct? Use the word “interleaving” in your answer.
Explain the lost-update race in the kvlite get-then-set counter. Why can the distinct-keys test assert an exact count while the shared-counter test can only assert a range?
What is a TOCTOU (check-then-act) bug? Give one concrete example and explain why “checking harder” doesn’t fix it.
Name the four conditions required for deadlock, and explain how consistent lock ordering breaks one of them.
You suspect a lost-update race but a single test run always passes. Describe two different ways to make the bug reliably detectable, and then the fix that turns the race into a safe operation.

Show answers

A concurrent function has a hidden second input — the interleaving, the specific order the runtime shuffled each thread’s instructions together — and there are astronomically many of them. A single run samples one interleaving; if it passes, it proves that one schedule works, not that the rare bad one does. The failing schedule still exists in the space of possible runs; the test just didn’t happen to hit it, so a green result is weak evidence.
The counter does current = get(k) then set(k, current + 1) across two lock acquisitions. Between the get and the set, another thread can get the same stale value; both write current + 1, and one increment is lost. The distinct-keys test has each thread write its own key range, so no two threads ever read-modify-write the same slot — no contention, so the final length is exactly THREADS * PER_THREAD. The shared-counter test contends on one key, so it can only assert total <= THREADS * PER_THREAD (and > 0), because lost updates make the exact total unpredictable.
TOCTOU is code that checks a condition and then acts assuming it still holds, when another thread/process changed it in the gap between check and use — e.g. if (balance >= 100) withdraw(100) where a concurrent withdrawal drains the account after the check, causing an overdraw. Checking harder doesn’t help because the check is true when you look; the problem is the window between look and leap. The fix is to make check and act one atomic step nothing can interleave.
Mutual exclusion (a resource is held by one thread at a time), hold-and-wait (hold one resource while waiting for another), no preemption (locks can’t be forcibly taken back), and circular wait (a cycle of threads each waiting on the next). Consistent lock ordering breaks circular wait: if every thread acquires locks in the same global order (e.g. lower ID first), no cycle can form, because a cycle requires two threads to have grabbed the locks in opposite orders.
(a) Inject a barrier or delay at the point between read and write so both threads are forced to read before either writes, making the lost update happen deterministically every run. (b) Run a stress loop with many threads and thousands of iterations so the rare bad interleaving becomes likely in aggregate — or run a thread sanitizer that flags the data race at its cause even when the output happens to come out right. The fix is to make the read-modify-write atomic — a compare-and-swap, a single write-locked increment method, or an UPDATE ... WHERE in one transaction — so no update can ever be lost.