From 'count++ is dangerous' to 'what must a fix promise?'
In the previous guide you saw the villain up close: a race condition, where the harmless-looking line count++ is really three machine steps (read, add, write) and an unlucky interleaving lets two threads lose an update. The diagnosis was clear. But a diagnosis is not a cure. This guide is about the cure's blueprint — not a particular lock yet, but the exact promise any lock must keep. Engineers gave the dangerous stretch of code a name and the requirements a precise form, and that precision is what lets us tell a real solution from one that merely looks safe.
First, the name. The exact stretch of code where a thread reads and modifies shared data — the part that must never overlap with another thread doing the same — is called the critical section. Think of a single-occupancy office bathroom: the room itself is the shared resource, and being inside it is the slice of your day that must not overlap with anyone else's. By contrast, everything else a thread does (computing on its own local variables, sleeping, talking to the user) is the remainder section and is perfectly safe to run concurrently. The whole art of synchronization is bracketing each critical section with an entry step (ask to go in) and an exit step (signal you are out), so the dangerous middle is never shared.
The contract: three rules, not one
Now, what must a good entry/exit protocol actually guarantee? It is tempting to answer with a single rule — 'keep threads out of each other's way' — but that is not enough, and the reason is funny. A scheme that simply welded the bathroom door shut forever would technically prevent all collisions, while being completely useless. So Dijkstra framed the critical-section problem as three separate requirements that a correct solution must satisfy all at once. Miss any one and you have a real bug, not a minor imperfection.
Rule one is mutual exclusion: if one thread is inside its critical section, no other thread may be inside its own critical section at the same time — at most one occupant of the bathroom, ever. This is the rule that directly defeats the race condition: if A's read-add-write cannot interleave with B's, no update is lost. Mutual exclusion is a safety property, the formal way of saying 'nothing bad ever happens'. It is necessary — but, crucially, it is not sufficient. A scheme can have flawless mutual exclusion and still be broken in two other ways, which is exactly why the other two rules exist.
Rule two is the progress requirement: if no thread is currently inside the critical section and one or more threads want in, the decision about who goes next cannot be postponed forever — and only the threads actually contending may take part in that decision. A thread idling far away in its remainder section must not be able to block the others. Picture the bathroom standing empty, someone waiting outside, but the door system insisting on consulting an employee who left the building an hour ago before it will let anyone in. The room is free, someone needs it, yet nobody gets in. That is a progress failure, and it is the classic flaw of a naive 'take strict turns' lock.
Rule three is bounded waiting: once a thread has requested entry, there is a fixed limit on how many times other threads may enter ahead of it before its own request is granted. The key word is bounded — it does not promise you go next, only that the number of times you can be overtaken is finite and known in advance (for n threads, at most n-1 times). This is what rules out starvation: the situation where one unlucky thread waits forever while a steady stream of others keeps cutting the line. Progress alone forbids the room sitting idle; only bounded waiting forbids a particular person being passed over again and again.
Why three? Because each missing rule is a different disaster
It is worth feeling how easy it is to satisfy one rule and quietly violate another. Consider the most obvious 'fair' lock you might invent — strict alternation: a shared variable turn, where thread 0 spins until turn is 0 before entering and thread 1 spins until turn is 1, each handing turn to the other on the way out. This scheme has airtight mutual exclusion — the two can literally never both be inside. But trace it: thread 0 enters, leaves and sets turn to 1, then loops forever in its remainder section, never wanting back in. Thread 1 enters once, leaves and sets turn back to 0, and now wants in again — but turn is stuck at 0 forever, because the only thread that would flip it has gone home. The room sits empty, thread 1 is frozen outside it. Mutual exclusion held perfectly; progress collapsed.
That is one rule satisfied and another wrecked. Now imagine a different scheme that does grant progress but, under load, lets the same lucky thread win the entry race over and over — it satisfies mutual exclusion and progress, yet an unlucky thread can be overtaken without limit, violating bounded waiting and starving forever. Three rules, three distinct ways to fail: mutual exclusion broken corrupts your data; progress broken freezes the system with the resource idle; bounded waiting broken starves an individual thread. That is why the contract has three clauses, not one — each guards against a disaster the others do not catch.
A pure-software answer: Peterson's solution
Before hardware gave us special atomic instructions, people asked a pure puzzle: can two threads coordinate access to a critical section using nothing but ordinary reads and writes of shared variables? The famous, elegant yes is Peterson's solution (Gary Peterson, 1981) for two threads. It is taught not because you should ship it, but because it crisply shows what those three rules really demand — and, in a moment, why hardware reality complicates everything.
The trick combines two ideas neither of which works alone. Each thread keeps an intention flag (flag[i] = true means 'I want in') and the two share a single turn variable to break ties. The flags alone deadlock — both threads insist 'I want in' and neither yields. The turn alone is just strict alternation, which we already saw fails progress. The genius is putting them together: a thread announces interest with its flag, then politely sets turn to the other thread, giving the other the first chance. Then it waits only as long as the other both wants in and it is the other's turn.
Peterson's solution (two threads, i and j = the other):
// ENTRY section for thread i
flag[i] = true; // "I want in"
turn = j; // "but you go first"
while (flag[j] && turn == j) // wait only if the
; // other wants in
// AND it's their turn
// ---- CRITICAL SECTION ----
// EXIT section
flag[i] = false; // "I'm done"
Whoever writes turn LAST loses the tie and waits;
the other proceeds. Result: all three rules at once.Walk the tie. Both threads want in at once. Thread 0 sets flag[0]=true then turn=1; thread 1 sets flag[1]=true then turn=0. Whichever wrote turn last finds turn holding its own id, so its wait condition is true and it spins; the other finds turn favouring it and enters. They never collide (mutual exclusion); the loser proceeds the instant the winner clears its flag (progress); and the loser waits at most one turn (bounded waiting). All three rules, from two booleans and an integer. It is genuinely beautiful — which makes the next caveat sting all the more.
The honest caveat: real hardware reorders memory
Here is the catch that every honest course must state: Peterson's solution is correct only on an idealized machine where memory operations happen in the exact order you wrote them and each write is instantly visible to every other core. Real CPUs and compilers do neither. For speed they freely reorder reads and writes, and each core may hold its recent writes in a private buffer before they become visible elsewhere. This freedom is memory ordering, and on a single thread it is invisible — but across threads it can quietly demolish a proof that looked airtight on paper.
Concretely, Peterson's proof assumes that after thread 0 does flag[0]=true; turn=1; another core reading those variables sees both updates, in that order. But a real core might let the read of flag[1] float up ahead of the write to flag[0], or keep flag[0]=true sitting in its store buffer unseen by the other core. Now both threads can pass the wait loop and enter together — mutual exclusion silently violated, even though the source code is letter-perfect. The algorithm did not change; the machine's promises did.
The fix is to insert a memory barrier (a fence) — a special instruction that tells the CPU and compiler 'do not reorder across this line; make the earlier writes visible before the later reads'. Drop the right barriers into Peterson's entry section and it works again on real hardware. But notice what that admits: the pure-software dream needs hardware help after all. This is exactly why, in practice, we reach past Peterson for the hardware atomic instructions of the next guide — they bundle the indivisible read-modify-write and the necessary ordering into one operation, sidestepping the memory-ordering minefield instead of tiptoeing through it.
What you now hold, and where it leads
Step back and you have the whole skeleton of synchronization. A critical section is the dangerous stretch of code; the critical-section problem is the precise demand that any guard around it provide mutual exclusion (safety: never two inside), progress (liveness: a free room is not left idle), and bounded waiting (fairness: no one is overtaken without limit). Peterson's solution proves all three are achievable in pure software for two threads — and the memory-ordering caveat proves why pure software is too fragile to ship, sending us toward hardware. Every lock, semaphore, and monitor in the rest of this rung is, underneath, just one more attempt to honour these same three rules cheaply and correctly.
There is one more honest thing to carry forward. Mutual exclusion is never free: while one thread is inside, every other thread that needs the resource is blocked, which serializes that slice of the program and caps how much parallel speedup you can get. That is why good designs keep critical sections tiny — only the few lines that genuinely touch shared state — and why some read-heavy workloads use weaker schemes that admit many readers but a single writer. Keep the room small. The next guide opens the toolbox: the hardware atomic instructions (test-and-set, compare-and-swap) that finally let us build a real, fast lock that honours all three rules even on a reordering multicore machine.