Peterson's Algorithm Visualization

The idea: a lock from plain loads and stores

Two threads share a critical section: code that only one of them may run at a time. Real locks use an atomic instruction such as test-and-set. Peterson's algorithm (Gary Peterson, 1981) shows that two threads can do it with nothing but ordinary loads and stores of three shared words.

Each thread has a flag: flag[i] = 1 means "I want to enter". There is one shared turn word: turn = j means "if we both want in, you go first". To enter, a thread raises its flag, gives the turn away, and then waits only while the other thread wants in and it is the other thread's turn.

// thread i (0 or 1); j = 1 - i
flag[i] = 1;                     // I want in
turn = j;                        // but you go first
while (flag[j] && turn == j) ;   // wait while you want in and it is your turn
// critical section
flag[i] = 0;                     // I am done

How to use the animation

T1 is thread 0 and T2 is thread 1; each runs on its own CPU and repeats the listing: enter, add 1 to counter through its register tmp, leave. A coloured marker shows the line each thread runs next. Every step runs one line, and any thread may run between two steps. Pick a thread and press Step Thread to build any order by hand, or let the round-robin or random scheduler choose. Every load or store flies between the thread and the word in memory. Under the separator, three lines check after every step that no update was lost, that at most one thread is inside, and that the threads are not stuck. The tabs switch between Peterson's algorithm and two broken versions.

Why a flag alone is not enough

The first idea is to raise your flag and wait until the other flag is down. Open Bug: flags only and run Demo: wait forever. T1 raises flag[0], T2 raises flag[1], and now each waits for the other's flag to drop. Neither will ever drop it, so both spin forever. Mutual exclusion holds, but nobody gets in: the algorithm has no progress.

The opposite idea, a turn word alone (while (turn != i) ; and turn = j on the way out), does keep threads apart, but it forces strict alternation: T1, T2, T1, T2. If T2 never wants in again, T1 can enter once more and then waits forever for a turn that never comes back.

Both together: Peterson's algorithm

Demo: both at once runs the two threads in lock step. Both raise their flags, then T1 writes turn = 1 and T2 writes turn = 0. The second write wins, so turn ends up 0: T2 politely gave way last. At the test, T1 sees turn = 0 and enters; T2 sees flag[0] = 1 and turn = 0 and waits. When T1 lowers its flag, T2's test fails and T2 enters. The counter ends at 2.

Why can both never be inside? Say both passed the test. A thread passes only if the other's flag was 0 or turn pointed at itself. Both flags were 1 while they tested (each raised its own flag first), so each must have seen turn pointing at itself. But turn holds one value: the one written last. So the thread that wrote last saw turn point at the other thread and waited. This argument still works if the two reads in the while happen one after the other; the page does them in one step only to keep the animation short.

Property	What it means	Peterson
Mutual exclusion	at most one thread in the critical section	✓ turn breaks the tie
Progress	if nobody is inside, someone who wants in gets in	✓ the test is false for at least one thread
Bounded waiting	a waiting thread gets in before the other enters twice	✓ wait at most one turn

Demo: taking turns shows bounded waiting. T1 is inside and T2 waits. T1 leaves and comes straight back, but on its way in it writes turn = 1, so now T1 waits and T2 goes in. A plain test-and-set spinlock gives no such promise: the same thread can win again and again.

The order of the two writes matters

Swap the first two lines and the algorithm breaks. Open Bug: turn first and run Demo: both get in. T1 writes turn = 1 and T2 writes turn = 0. T2 raises its flag and tests: flag[0] is still 0, so T2 enters. Now T1 raises its flag and tests turn == 1; it is 0, so T1 enters too. Both read counter = 0 and both write 1: one update is lost. The proof above needed "each raised its own flag first"; here T1 gave the turn away while T2 could not yet see that T1 wanted in.

Why it breaks on real CPUs

The page assumes sequential consistency: every load sees the latest store, in program order. Real CPUs do not promise that. Each core puts its stores in a store buffer and lets later loads go ahead before the stores reach memory. Then T1's load of flag[1] can run before T2's store of flag[1] = 1 is visible, and the other way round: both read 0 and both enter. Even x86, which keeps most orders, allows exactly this store-then-load reordering. Compilers may also keep the flags in registers or reorder the lines.

The fix is a full memory fence between the stores and the loads, or atomic variables with sequentially consistent ordering:

Where	Make Peterson correct
x86	MFENCE after turn = j (or write turn with XCHG)
C / C++	atomic_int / std::atomic<int> with the default memory_order_seq_cst
Java	declare flag and turn volatile (see the Java memory model)

Once a fence is needed anyway, an atomic instruction is simpler and works for any number of threads, so real locks use test-and-set, compare-and-swap or a spinlock built on xchg. Peterson's algorithm stays the classic proof that software alone can give mutual exclusion, and the standard example of why memory ordering matters.

More than two threads

Peterson's algorithm is for exactly two threads. The filter lock generalises it to n threads with n − 1 levels, each level a two-way Peterson-style tie-break. Lamport's bakery algorithm gives each thread a ticket number and serves them in order. Both still use only loads and stores, and both need n shared words, which is one reason hardware atomics won.

What the page leaves out

• Dekker's algorithm (1965), the first correct two-thread solution, which Peterson's simplifies.
• Memory reordering is only in the text and figure: the animation is sequentially consistent.
• Busy waiting cost: the waiting thread spins and burns its CPU; there is no sleeping, as in a mutex.
• Caches are drawn as one bus to one memory.

References

OSTEP, chapter 28: Locks (Peterson's algorithm, test-and-set)

Peterson's algorithm (Wikipedia)

Jeff Preshing: Memory reordering caught in the act (store-load reordering on x86)

cppreference: std::memory_order