Concurrency: When Threads Collide

The bug that only happens sometimes#

You write a counter. Two threads each increment it once. It starts at zero, so it should end at two. You run the program a thousand times and it prints 2 every time. You ship it. In production, under load, it occasionally prints 1, and no amount of staring at the single line count++ reveals why.

The line looks atomic. It is one statement, one token of intent: add one. But the CPU does not have a single instruction that reads memory, adds, and writes back as one indivisible act. Underneath, count++ is three steps:

load   r ← count     # read the current value into a register
add    r ← r + 1      # compute the new value privately
store  count ← r      # write the register back to memory

Between any two of those steps the scheduler is free to pause this thread and run the other one. That gap is where the update goes to die.

Interleaving and the lost update#

Call the threads T1 and T2. If T1 runs all three of its steps before T2 starts, everything is fine: T1 reads 0, writes 1; T2 reads 1, writes 2. But nothing forces that ordering. Consider this interleaving:

T1: load  r1 ← count   (r1 = 0)
T2: load  r2 ← count   (r2 = 0)   ← T2 reads the SAME stale 0
T1: add   r1 ← 1
T2: add   r2 ← 1
T1: store count ← 1
T2: store count ← 1               ← overwrites T1's 1 with 1

Both threads read zero before either wrote back. Both computed one. The second store does not add to the first — it overwrites it with the identical value. Two increments happened; only one survived. This is a data race: two threads access the same location concurrently, at least one of them writing, with no ordering between them. The result depends on timing the program does not control.

Step through the widget and watch the registers. In the safe interleaving each thread's store reflects the other's work. In the bad one, the two registers both hold 1 at the same time, and the shared count never climbs past it. The reason your local test passed a thousand times is that on an unloaded machine the scheduler rarely splits an increment — the odds only turn against you under contention. This is the cruelty of concurrency bugs: they are non-deterministic. The same binary, same input, can give different answers run to run, so they hide from the exact testing that would catch an ordinary bug.

Concurrency is not parallelism#

It is worth pausing on a distinction people blur. Concurrency is a structuring property: the program is composed of tasks whose steps can interleave in any order. Parallelism is an execution property: two things literally happen at the same instant on two cores. You can have concurrency without parallelism — a single core time-slicing between threads still interleaves their steps, and the lost-update race above happens on one core just fine. The bug is not that two things run at once; it is that one thread's three steps are not protected from being split by another. Concurrency is about correctness under interleaving. Parallelism is about speed. This article is entirely about the first. (The same reasoning underlies why agreement across machines is hard — see distributed consensus.)

The fix: mutual exclusion#

The region of code that must not be interleaved — here, the whole load-modify-store — is a critical section. The classic tool for protecting one is a lock (a mutex). A thread must acquire the lock before entering the critical section and release it after. While one thread holds the lock, any other thread that tries to acquire it waits.

lock.acquire()
count = count + 1     # critical section — now indivisible in effect
lock.release()

The lock provides mutual exclusion: at most one thread is inside the critical section at any time. The interleaving that lost an update is now impossible, because T2 cannot even begin its load until T1 has released the lock, by which point T1's store is done. Toggle the lock in the widget above and the "bad interleaving" option disappears — the section is forced to run serially. Note the lock does not make count++ atomic in the CPU; it makes the agreed protocol around it exclusive. Every thread must cooperate by taking the lock. A single thread that touches count without it reintroduces the race. Locks that fall back on primitive Boolean tests recall the humble logic gate: the guarantee is only as strong as the discipline enforcing it.

Locks are not free: deadlock#

Adding a lock feels like a clean win, and for a single lock it usually is. The trouble starts with two. Suppose you protect two accounts with two locks, A and B, and you need both to transfer money. Thread 1 grabs A then reaches for B. Thread 2, doing a transfer the other direction, grabs B then reaches for A. Now:

• T1 holds A, waits for B.
• T2 holds B, waits for A.

Neither will release what it holds until it gets what it wants, and neither will ever get it. This is a deadlock: a set of threads each blocked forever, waiting on a resource another one holds.

Toggle the widget to "inconsistent order" and watch the wait-for edges close into a cycle: T1 → B → T2 → A → T1. That loop is the signature of the failure.

Deadlock requires four conditions to hold simultaneously — the Coffman conditions:

1. Mutual exclusion — the resources cannot be shared; a lock is held by one thread at a time.
2. Hold and wait — a thread holds one resource while requesting another.
3. No preemption — a resource cannot be forcibly taken; it is only released voluntarily.
4. Circular wait — there is a cycle of threads each waiting for the next.

Break any one and deadlock cannot occur. The most practical break is the fourth. Impose a global lock order: number the locks and require every thread to acquire them in increasing order. If everyone takes A before B, no thread can ever hold B while waiting for A, so the cycle cannot form. Switch the widget to "global lock order" and the second thread simply waits for the first to finish, then proceeds — slower, but never stuck. Detecting a cycle after the fact is possible too, much like walking a table for an entry in hash tables, but preventing the cycle by construction is cheaper and simpler.

There is a deeper lesson lurking here. You might wish for a tool that inspects your program and warns you of every possible deadlock. In full generality that is as hopeless as the halting problem: reasoning perfectly about all interleavings of an arbitrary program is undecidable. Which is why we lean on disciplines — consistent ordering, minimal critical sections, holding one lock at a time — rather than after-the-fact proofs.