Concurrency, enumerated
A concurrent program does not have a behaviour. It has a set of them, one per valid interleaving of its threads — and the bug is almost never in the ordering you imagined. Every concept here enumerates that set and marks the members that are wrong.
28 concepts · every one runnable · start with the lost update · or break one yourself
Races and atomicity
What an increment actually is, why a question can go stale between asking and acting, and the outcome space that appears the moment two threads touch one variable.
- The lost updatefoundational`count++` is three operations, not one. Only two of its twenty interleavings produce 2; the failure is the common case, and an atomic increment removes the orderings rather than making them rarer.
- Atomic operationsfoundationalAtomicity is not speed and not a lock. It is indivisibility: no interleaving can slot between the read and the write, so the orderings that lost updates cease to exist.
- Check-then-actfoundationalThe window is between the check and the act. A lock that begins after the check protects nothing; the fix is to ask and act in one indivisible operation.
- Compare-and-swapintermediateCAS turns check-then-act into one indivisible operation. A thread that loses the race loses nothing but a lap — it never blocks anybody, which is the whole appeal and the whole cost.
- The ABA problemadvancedCAS compares values, not histories. Two changes are indistinguishable from none, and the fix is a tag packed into the same word so the pointer and its version swap together.
Mutual exclusion
Locks, and what they do to the set of possible orderings. Granularity, deadlock and its cycle, livelock, starvation, and the reentrancy that stops a lock deadlocking against itself.
- MutexesfoundationalA lock removes orderings from the space. The critical section must span the whole read-modify-write — guarding only the write leaves the window exactly where it was.
- DeadlockintermediateA cycle in the wait-for graph is the deadlock. Lock ordering removes it by construction, and it is only a policy when it is a total order over every lock.
- LivelockintermediateLivelock is not deadlock: every thread is runnable throughout, so a deadlock detector sees nothing and the process looks busy. Symmetry is the cause, and breaking it is the fix.
- ReentrancyintermediateA non-reentrant mutex does not recognise its own owner, so a thread can block waiting for a lock it is already holding. Whether that happens is a property of the primitive, and the two kinds sit side by side in most ecosystems.
- Starvation and fairnessintermediateAn ordinary mutex makes no promise about who gets in next — a released lock can go straight back to the thread that released it. Fairness is a feature you opt into, and it costs throughput.
- Lock granularityintermediateA lock makes its critical section a serial fraction, so this is Amdahl’s law with a mutex in it. Splitting the lock widens the queue; shortening the critical section is usually cheaper and always simpler.
Coordination
Making threads wait for each other on purpose. Bounded buffers, condition variables and the while loop that is not optional, semaphores, barriers and reader-writer locks.
- Condition variablesintermediateA woken thread does not resume holding the lock — it queues for it, and the condition it was promised can be false again by the time it gets in. `while` asks at the only moment the answer counts.
- The bounded bufferintermediateTwo semaphores facing opposite directions keep the invariant without either side counting the other. A producer that cannot take a slot cannot proceed, and being unable to proceed is the flow control.
- Reader-writer locksintermediateReaders cannot corrupt each other, so excluding them from each other is throughput given away. Skipping the lock on the read side is a different matter: a reader lands mid-update and sees half of it.
- BarriersfoundationalA barrier makes a phase boundary real. It costs what the slowest participant costs, and without it the wrong answer is computed silently — nothing in the program knows phase one was unfinished.
Async and event loops
One thread, many tasks, and a queue discipline with exactly one valid schedule. Why a promise beats a zero-delay timer, what a blocking call costs everyone else, and what await actually suspends.
- The event loopfoundationalThe loop finishes what it started, drains every microtask, then takes one macrotask. That discipline has no choices in it — which is why the outcome space has exactly one member.
- Blocking the event loopfoundationalRun-to-completion is the guarantee that removes races and the guarantee that makes one slow function everybody else problem. The queue stalls for exactly as long as your function runs.
- Promise.all against sequential awaitfoundationalSequential await does not merely take longer — the second request has not been sent, because await suspended the function that would have sent it. The saving is overlap, not speed.
- Concurrency against parallelismfoundationalConcurrency is a property of the program — several things in progress. Parallelism is a property of the machine — several executing at once. Adding cores divides only the computing part, and most tasks are waiting.
- Structured concurrencyintermediateA task that outlives its scope writes to state its caller has moved past and reports errors to a handler that is gone. Structured concurrency makes lifetime a property of the code shape rather than of remembering to await.
Memory and hardware
Where the interleaving model runs out. Store buffers producing outcomes no ordering explains, the barriers that forbid them, false sharing, and the ceiling Amdahl puts on all of it.
- Visibility and store buffersadvancedA write is not visible when it happens, it is visible when it is published. This is where the interleaving model runs out and a memory model is required.
- Memory barriersadvancedA barrier does not make anything atomic. It forces publication, which is a different guarantee and the one the reordering was violating.
- Amdahl's lawfoundationalThe speedup ceiling is 1 divided by the serial fraction, and the core count does not appear in it. Most of what parallelism will ever give you has arrived long before you run out of cores.
- False sharingadvancedCoherence works in cache lines, not variables. Two counters that share a line serialise on it, so independent work contends on a resource neither thread was told about.
Patterns in practice
Thread pools and the deadlock they invite, work stealing against a shared queue, actors that share nothing, and immutability as a way to make the whole problem not apply.
- Thread pool deadlockadvancedNo lock is involved and neither task is wrong on its own. The bug is the shape — a dependency from a resource back onto itself — so the fix is a second pool, not a bigger number.
- The actor modelintermediateAn actor owns its state and nobody else can reach it, so the interleaving space stops mattering. The mutual exclusion has not gone away — it lives in the mailbox, in one place you can point at.
- ImmutabilityfoundationalA reader takes one reference and what it is looking at can no longer change. The intermediate half-updated state that every torn read depends on simply has no way to exist.
- Work stealingintermediateA shared queue is one contended operation per task, so the pool flattens however many workers you add. Per-worker deques keep the common case local and charge the cost only to workers that have run dry.