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.
7 concepts · every one runnable · start with the lost update
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.
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.
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.