Mutual Exclusion Without Hardware Support

Symptom

Two threads increment a shared counter a million times each. The final value is 1,374,522.

You know why: the increment is a read, an add, and a write, and the interleavings lose updates. The fix is a lock. But a lock is provided by your runtime, which gets it from the OS, which gets it from a hardware instruction — lock xchg, cmpxchg, ldrex/strex.

So where does mutual exclusion come from? If every lock is built on an atomic instruction, and atomic instructions are built by hardware, is mutual exclusion a hardware feature? Could you have it on a machine offering only plain loads and stores?

Dijkstra posed this in 1965 and the answer is yes, with a caveat that has become much larger than the original result: the algorithms are correct, and on your actual CPU they do not work, and the reason they do not work is more instructive than the algorithms themselves.

Statement

A mutual exclusion algorithm using only atomic reads and writes of shared variables must provide:

• Mutual exclusion. At most one thread in the critical section.
• Progress (deadlock freedom). If threads want in and none is inside, one gets in.
• Bounded waiting (starvation freedom). A thread waiting to enter is overtaken at most a bounded number of times.

Peterson (1981). Two threads achieve all three using two boolean flags and one shared turn variable, with atomic reads and writes only.

Lamport (1974). The bakery algorithm achieves all three for $n$ threads, and remains correct even if reads overlapping writes return arbitrary values.

Argument

Peterson’s algorithm, and why each line is needed.

// thread i, other thread j
flag[i] = true;          // I want in
turn = j;                // but you go first
while (flag[j] && turn == j)
    ;                    // wait
// critical section
flag[i] = false;

The mutual exclusion proof is short. Suppose both are inside. Each passed its loop, so for thread $i$ either flag[j] was false or turn != j. Both set their flag before checking, so if both are inside, both flags are true, meaning both must have seen turn differ from the other. But turn holds a single value, so at most one of those can be true. Contradiction. $\blacksquare$

The elegance is in turn = j, the deference. Each thread says after you, and because both write to the same variable, the second write wins and breaks the symmetry. If instead each set turn = i, both could see their own value and both enter. If the two lines were swapped, a thread could set turn before raising its flag and both could pass. Every line is load-bearing, and reordering any pair breaks it — which is the foreshadowing.

Lamport’s bakery, generalizing to $n$.

choosing[i] = true;
number[i] = 1 + max(number[0..n-1]);
choosing[i] = false;
for (j = 0; j < n; j++) {
    while (choosing[j]) ;
    while (number[j] != 0 &&
           (number[j], j) < (number[i], i)) ;
}
// critical section
number[i] = 0;

The metaphor is a bakery counter: take a ticket, wait until every lower ticket has been served. The max is not atomic, so two threads can take the same number, and the tie is broken by thread ID, which is the lexicographic comparison (number[j], j) < (number[i], i). FIFO order follows, so waiting is bounded by $n-1$, which is optimal.

The choosing flag handles the window where a thread has begun computing its number but not stored it, during which another thread reading number[i] would see a stale zero and wrongly skip it.

What Lamport was really defending against. The bakery algorithm is correct even if a read that overlaps a write returns an arbitrary value — not the old value, not the new one, anything. That is a far weaker assumption than atomic registers, and it is why the algorithm looks over-engineered until you see the model. Lamport was designing for real hardware where a multi-word read racing a write can return a torn value, and it makes the bakery the only algorithm here that survives contact with genuinely non-atomic memory.

And now the part that matters: they do not work on your CPU. Peterson’s proof assumes sequential consistency, that all threads observe one consistent global order of memory operations. x86 provides TSO, which permits a store to be buffered and a subsequent load to a different address to complete before it drains. ARM and POWER are weaker still and reorder much more aggressively.

The concrete failure: thread 0 writes flag[0] = true into its store buffer, then reads flag[1], which is still false because thread 1’s write is likewise sitting in its store buffer. Both reads see false. Both enter. The proof is valid and the hardware does not implement the machine the proof is about.

Nor does the compiler. Without volatile or atomics, the loop body is empty and flag[j] is loop-invariant, so an optimizer is entitled to hoist the load out of the loop and produce an infinite loop, or to delete the wait entirely. Both are legal under the C and C++ memory models, because a data race is undefined behaviour.

The repair is explicit fences. In C11 or C++11, declare the variables atomic_bool and place a seq_cst fence, or equivalently a store(seq_cst), between the flag write and the flag read. On x86 that compiles to mfence or a locked instruction, which costs on the order of 20 to 100 cycles — the same order as the lock cmpxchg you were trying to avoid. Peterson’s algorithm avoids atomic instructions in the source and reintroduces their cost in the fence, and this is the practical verdict on the whole family.

Why hardware provides CAS anyway. Beyond correctness, atomic registers are weak in a precise sense: Herlihy’s hierarchy (T053) shows read/write registers have consensus number 1, so they cannot solve wait-free consensus even for two threads, while compare-and-swap has consensus number infinity. Mutual exclusion is achievable with registers; wait-free coordination is not. That is the deeper reason your CPU has cmpxchg, and it is not about convenience.

Forbids

Mutual exclusion for $n$ threads with fewer than $n$ registers. Burns and Lynch, unconditional.

Correctness of these algorithms under a weak memory model without fences. Not a subtlety to be tested away; the failures are reproducible on ARM within seconds.

Compiling them correctly without volatile or atomics. The race is undefined behaviour and the compiler is permitted to assume it does not occur.

Wait-free consensus from registers alone. No amount of algorithmic ingenuity substitutes for CAS here.

Does not forbid

It does not mean these algorithms are museum pieces. This is the misreading that makes the topic feel like trivia. Linux’s seqlock is register-only synchronization, letting readers proceed without locking and retry on a version change. The Dekker pattern appears in JVM biased locking and in Go’s runtime. The reasoning style — establish an invariant over what each thread can observe — is what you need whenever you write lock-free code.

It does not mean spinning is always wrong. For very short critical sections, spinning beats blocking, because a context switch costs a few microseconds while a contended spin may cost a few hundred nanoseconds. Linux spinlock_t and adaptive mutexes in glibc spin briefly before parking, and that hybrid is the usual right answer.

It does not mean you should implement Peterson’s in production. Use std::mutex, sync.Mutex, or pthread_mutex_t. They use the right instructions, handle contention by parking rather than burning cycles, cooperate with the scheduler, and are debuggable by your tools.

It does not mean fences are always expensive. Acquire/release ordering is free on x86 and cheap on ARM; only seq_cst requires a full barrier. Choosing the weakest sufficient ordering is real optimization, and the reason C++ exposes six of them.

It does not mean the memory model makes reasoning impossible. C11/C++11 formalized it, Java’s JSR-133 preceded them, and the models are precise enough to verify against. The tools exist: ThreadSanitizer finds races dynamically, and CDSChecker and herd7 explore weak-memory executions exhaustively.

Boundary

• Sequential consistency required. Every real CPU is weaker; fences are mandatory, and their cost is comparable to the atomic instructions being avoided.
• Assumes atomic single-word reads and writes. Bakery survives even this being false; Peterson’s does not.
• Unbounded numbers in bakery. Ticket values grow without bound; in practice 64-bit counters make wraparound irrelevant, and bounded variants are substantially more complex.
• Blocking, not wait-free. A thread that halts inside the critical section blocks everyone forever. Wait-free algorithms need stronger primitives.
• $O(n)$ per entry for bakery. Scanning all $n$ tickets does not scale; production locks use queues (MCS, CLH) for $O(1)$ handoff and better cache behaviour.

The thing to carry: mutual exclusion does not require special hardware, and on real hardware you need special instructions anyway — because the machine your proof describes is not the machine you are running on, and the fence that reconciles them costs what you were trying to save.

Read next