Peterson's Software Solution

Two threads share a bank account balance. Both want to update it at once. Without coordination, one thread's update can silently overwrite the other's. This corrupts the balance. This is the classic Race Condition problem. Any correct fix must guarantee something important. The two threads must never execute their sensitive update code — the critical section — at the same time. The question this article answers is startling in its ambition. Can two threads achieve this guarantee using only ordinary shared memory variables? They must do so with no special hardware instructions and no help from the operating system. Peterson's Algorithm, published by Gary L. Peterson in 1981, answers yes. It is a two-thread mutual exclusion protocol. It is built from two boolean flags and one shared turn variable. It uses nothing but reads and writes to memory. It matters not because production systems use it directly — they mostly do not. It matters because it is the cleanest possible demonstration that synchronization is solvable in principle. It crystallizes exactly what properties any synchronization mechanism must provide: mutual exclusion, progress, and bounded waiting. The big picture is historical and pedagogical at once. Before hardware vendors added atomic instructions like test-and-set, researchers wrestled with a hard question. Could pure software solve mutual exclusion at all? Earlier attempts existed, including naive flag-only schemes and the more elaborate but clumsy solutions by Dekker and Knuth. These showed it was possible but complicated. Peterson's contribution was to find the simplest correct construction. It is short enough to fit on one blackboard. Yet it is subtle enough that many "obvious simplifications" break it. This article gives you several things. It offers the algorithm in precise pseudocode. It includes a state-machine-style diagram of how the two threads interleave. It provides a rigorous correctness argument based on a shared invariant. It walks through a genuinely tricky interleaving. It also tables the mistakes students make when they try to reprove or "simplify" it. It closes by pointing toward why real systems abandoned pure-software solutions. They moved instead to hardware-assisted Test-and-Set and Atomic Instructions, the next step in the story.

Key takeaways

Peterson's Algorithm gives two threads mutual exclusion using only two boolean flags and one shared turn variable — no special hardware needed.
Each thread signals intent to enter (`flag[i] = true`), then politely yields priority to the other (`turn = j`) before waiting.
The double condition `while (flag[j] && turn == j)` is the crux: it lets the last thread to defer actually get to go first.
It provably satisfies all three requirements of a correct critical-section solution: mutual exclusion, progress, and bounded waiting.
It works only for exactly two threads and relies on sequential consistency of memory — a subtlety that modern relaxed hardware memory models violate.
It is a beautiful, provably correct construction, but real operating systems use hardware atomic instructions instead, for speed and because of memory-reordering issues.

The core insight

By combining a private intent flag with a shared turn variable that each thread voluntarily hands to the other, two threads can guarantee mutual exclusion using ordinary memory alone.

The idea

A critical section is a block of code that accesses shared data and must not be executed by more than one thread at a time. Any correct solution to the Requirements for a Correct Critical Section Solution problem must guarantee three properties simultaneously: mutual exclusion (no two threads are ever in their critical sections concurrently), progress (if no thread is in the critical section, some waiting thread eventually gets to enter — the decision cannot be postponed forever by threads outside the section), and bounded waiting (a thread waiting to enter is not overtaken infinitely many times by others). Peterson's algorithm achieves all three for exactly two threads using two pieces of shared state: an array `flag[2]` of booleans, where `flag[i]` means "thread i wants to enter its critical section," and a single shared integer `turn`, which holds the index of the thread whose turn it is to wait if there is a conflict. The elegant trick is the order of operations: a thread first raises its own flag (declares interest), then gives away the turn to its rival (`turn = other`), and only then checks whether it must wait. This ordering means that if both threads race to enter at the same moment, the one whose `turn` write executed last is the one that ends up waiting — the other proceeds. There is no possibility of a "double win," because the shared `turn` variable can only hold one value at a time, and whichever thread wrote to it last determines who yields. The genius of the construction lies in the combined wait condition, `while (flag[j] && turn == j)`. Neither `flag[j]` alone nor `turn == j` alone would suffice — you need both terms to encode "the other thread is really interested and it is genuinely their turn." This is what separates Peterson's clean two-line solution from the more convoluted multi-flag approaches (such as Dekker's algorithm) that preceded it.

How it works

The algorithm is a busy-wait (spinlock) protocol: a thread trying to enter its critical section may spin in a loop rather than blocking. Below, `i` denotes the calling thread's own index and `j = 1 - i` denotes the other thread. ``` shared boolean flag[2] = [false, false] shared int turn // no initial value required, but any valid index is fine // Thread i executes this to enter and leave the critical section. // j is the other thread's index (j = 1 - i for two threads 0 and 1). procedure ENTER_CRITICAL_SECTION(i): j = 1 - i flag[i] = true // Step 1: declare intent to enter turn = j // Step 2: politely offer the turn to the other thread while (flag[j] == true) and (turn == j): // Step 3: busy-wait only if the other thread wants in // AND it is genuinely their turn spin() // do nothing, just loop // ---- CRITICAL SECTION ---- // access shared resource // --------------------------- procedure EXIT_CRITICAL_SECTION(i): flag[i] = false // Step 4: withdraw interest, allow the other thread in ``` Walking through the mechanism: 1. Declare intent. Thread i sets `flag[i] = true`. This alone does not block anyone — it merely records that thread i wants in. 2. Yield the turn. Thread i immediately writes `turn = j`, handing priority to the other thread. This is the crucial "politeness" step: even though thread i wants to go, it offers the other thread first refusal. 3. Wait conditionally. Thread i spins only while both `flag[j]` is true (the other thread also wants in) and `turn == j` (it is genuinely the other thread's turn). If the other thread is not interested (`flag[j] == false`), thread i proceeds immediately. If both threads want in, exactly one of them wrote `turn` last — that value determines who waits. 4. Exit and release. After finishing the critical section, thread i clears `flag[i] = false`, signalling it no longer wants access, which frees the other thread's wait loop (or lets a future entry attempt proceed).

Figure

Peterson's Algorithm: state machine for one thread, and the shared variables that couple the two threads

Complexity & correctness

Time complexity. Entering and exiting the section, absent contention, is $O(1)$ — a constant number of reads and writes. Under contention, a thread may busy-wait, but the wait itself is bounded: a waiting thread performs at most one full pass of the other thread's critical section plus its entry/exit protocol before proceeding (this is proven below), so waiting time is bounded by a constant multiple of one critical-section execution, not by the number of threads (there are only two) and not unbounded. Space complexity is $O(1)$ : three shared variables total (`flag[0]`, `flag[1]`, `turn`), independent of critical-section size.

Correctness — the invariant. Assume the underlying memory model is sequentially consistent: all reads and writes from both threads appear to occur in some single global sequential order consistent with each thread's own program order. (This assumption is essential and is revisited below.) We argue the three required properties. Mutual exclusion. Suppose, for contradiction, both threads 0 and 1 are simultaneously inside their critical sections. For each thread i to have exited its wait loop, at the moment it last checked the condition, either `flag[j] == false` or `turn == i`. Consider the last write to `turn` before both threads entered — WLOG say it was `turn = 1` (written by thread 0 when entering, as thread 0's protocol sets `turn = j = 1`). Since `turn` is a single variable, `turn == 1` (i.e., `turn == j`) holds for thread 0's own wait check unless thread 0's write happened after thread 1's last check. Trace carefully: thread 0 sets `flag[0]=true` then `turn=1`; thread 1 sets `flag[1]=true` then `turn=0`. These two writes to `turn` are totally ordered (sequential consistency), so exactly one of them is the last write before both loops are entered. Say thread 1's write `turn=0` happens last. Then when thread 0 evaluates its guard `flag[1] && turn==1`, it sees `turn==0` is false only if thread 1's write already landed — meaning `turn==1` is false for thread 0, so thread 0 proceeds regardless of `flag[1]`. But then thread 1 evaluates its own guard `flag[0] && turn==0`: since `turn==0` is true (it wrote it last) and `flag[0]==true` (thread 0 already set it and hasn't cleared it, as thread 0 is presently in or about to enter its critical section), thread 1's condition holds and thread 1 must remain in the loop — contradicting the assumption that thread 1 is also inside the critical section. By symmetry the same contradiction arises if thread 0's write to `turn` is last. Hence both threads being inside simultaneously is impossible. Progress. If only one thread wants to enter (`flag[j] == false`), its own wait condition is false immediately, so it proceeds without delay — no indefinite deferral by an uninterested thread. If both want to enter, the argument above shows the one whose `turn`-write happened last is the one who waits, and the other is guaranteed to proceed — the decision of who goes is made, not postponed, so the system never livelocks with both threads endlessly spinning. Bounded waiting. Suppose thread i is waiting. Thread j is either in its critical section (in which case it will exit, set `flag[j] = false`, releasing thread i), or thread j has not yet re-entered the protocol. Because with only two threads, thread j can enter its critical section at most once more before thread i is guaranteed to break out of its loop: as soon as thread j tries to re-enter after exiting, it must again write `turn = i`, which restores `turn == i` — false for its own guard relative to `j` — and if thread i is still waiting when `flag[i]` was already true and `turn` alternates, the last writer to `turn` wins the race for entry, so thread i is bypassed by thread j at most once before being let in. This gives a strict bound (one critical-section execution of the rival) on how many times thread i is overtaken — satisfying bounded waiting.

The honest caveat. This proof relies critically on sequential consistency: every processor sees writes to `flag[]` and `turn` in the same global order, and no write is reordered relative to another. Modern multicore CPUs with relaxed memory models (e.g., store buffers, out-of-order execution, compiler reordering) can violate this assumption unless explicit memory fences are inserted. This is precisely why real systems moved to hardware-provided atomic instructions rather than relying on plain loads and stores — a story continued in Test-and-Set and Atomic Instructions.

Worked example

Consider two threads, T0 and T1, both wanting to increment a shared counter. We trace a genuinely tricky near-simultaneous interleaving where both threads attempt entry almost at once.

Step	Action	flag[0]	flag[1]	turn	Result
0	initial state	false	false	—	idle
1	T0: `flag[0] = true`	true	false	—	T0 declares interest
2	T1: `flag[1] = true`	true	true	—	T1 also declares interest
3	T0: `turn = 1`	true	true	1	T0 offers turn to T1
4	T1: `turn = 0`	true	true	0	T1 overwrites turn — this write is last
5	T0 checks `flag[1] && turn==1`	true	true	0	`turn==1` is false → T0's guard is false → T0 enters immediately
6	T1 checks `flag[0] && turn==0`	true	true	0	`flag[0]` true and `turn==0` true → T1's guard holds → T1 spins
7	T0 runs critical section	—	—	—	increments counter
8	T0: `flag[0] = false`	false	true	0	T0 exits, releases lock
9	T1 re-checks guard: `flag[0]` now false	false	true	0	guard false → T1 exits loop, enters
10	T1 runs critical section	—	—	—	increments counter
11	T1: `flag[1] = false`	false	false	0	T1 exits

Note the pivotal moment at Step 4–6: even though T0 wrote `turn` first (Step 3), T1's later write (Step 4) is what actually determines the outcome — the last writer to `turn` loses the race and must wait, while the other proceeds. This is the mechanism's core cleverness: whichever thread's turn-write is overwritten by the rival's later write is the one guaranteed not to wait, since its own guard condition (`turn == j`) becomes false. If we ran this trace with the order of Steps 3 and 4 swapped, the roles of who waits would simply flip — but exactly one thread always proceeds immediately, and the other spins for a bounded time.

Common pitfalls & traps

Pitfall	Why it breaks the algorithm
Swapping the order of `flag[i] = true` and `turn = j`	If `turn` is set before `flag[i]`, a race window opens where the other thread's guard reads a stale `flag[i]`, allowing both threads into the critical section
Using only `flag[j]` as the wait condition (dropping `turn`)	Both threads can set their own flags simultaneously and then both wait forever on each other — violates progress (deadlock)
Using only `turn == j` as the wait condition (dropping `flag[j]`)	Threads would strictly alternate even when only one wants entry, so a single thread cannot re-enter without the other going first — violates progress for the uncontended case
Assuming it generalizes trivially to N threads by array replication	Peterson's two-thread proof does not extend directly; the N-thread generalization (the "tournament" or "filter" algorithm) requires $O(\log N)$ levels of Peterson instances, not a flat extension
Ignoring compiler/CPU instruction reordering	On real hardware with relaxed memory models, loads/stores to `flag` and `turn` can be reordered, breaking mutual exclusion unless memory barriers are inserted
Treating this as production-ready code	Busy-waiting wastes CPU cycles; real synchronization primitives use blocking plus hardware atomics for efficiency

Pioneers & history

Origins · 1 minGary L. Peterson and how this was discovered

Gary L. Peterson

born 1950s, active from late 1970s · American computer scientist, University of Rochester and University of Central Florida

Gary Peterson worked in distributed computing and concurrency theory, and is best known for the compact 1981 mutual-exclusion algorithm that bears his name — a dramatic simplification of prior software-only solutions such as Dekker's algorithm.

History

1965

— Edsger Dijkstra publishes the first general software solution to mutual exclusion for N processes.

1966

— Dekker's algorithm (attributed via Dijkstra) is recognized as the earliest two-process software mutual exclusion solution.

1974

— Leslie Lamport introduces the Bakery Algorithm, generalizing software mutual exclusion to N processes.

1981

— Gary L. Peterson publishes "Myths About the Mutual Exclusion Problem," presenting the two-process algorithm now bearing his name.

1980

s–1990s — hardware vendors add atomic test-and-set and compare-and-swap instructions, shifting practical synchronization away from pure-software algorithms.

Where this matters

Peterson's algorithm is rarely, if ever, deployed directly in production operating systems or databases — its assumptions about sequential memory consistency and its two-thread limit make it impractical for real multicore hardware. Its real importance is pedagogical and foundational: it is the standard proof-of-concept every operating systems course uses to demonstrate that the Requirements for a Correct Critical Section Solution (mutual exclusion, progress, bounded waiting) are jointly achievable, and it trains students to reason rigorously about interleavings, races, and invariants before encountering hardware primitives. Understanding exactly why it needs sequential consistency also motivates the design of modern memory models and the Happens-Before Relation used in language memory model specifications (Java, C++, Rust). Its logical descendants — Lamport's Bakery Algorithm for N processes and the tournament-tree generalization of Peterson's own idea — are used to illustrate scalable software mutual exclusion. Ultimately, the limitations of Peterson's algorithm (busy-waiting inefficiency, fragility under relaxed memory models, and lack of scalability beyond two threads) are the exact motivations that drove processor designers to add hardware-supported atomic read-modify-write instructions, the subject of Test-and-Set and Atomic Instructions.

:::quiz[Why is the wait condition `while (flag[j] && turn == j)` rather than just `while (flag[j])`?]

Using only flag[j] would cause a compile error
The combined condition is required to avoid deadlock: without checking turn, both threads could wait on each other forever ✓
flag[j] alone is actually sufficient and turn is unnecessary
turn is only used for debugging, not correctness

:::quiz[Which property would break if a thread forgot to execute `flag[i] = false` when exiting its critical section?]

Bounded waiting only
Progress — the other thread could wait forever even though no one is in the critical section ✓
Mutual exclusion only
Nothing; flag[i] is optional

Ask the tutor: How would you extend Peterson's algorithm to work correctly for three or more threads?

Does Peterson's algorithm work for more than two threads?

Not directly. The classic two-variable, two-flag version is specifically constructed around exactly two threads and the single shared `turn` variable that can hold only one of two values. Extending it naively — say, adding a `flag[]` array of size N and a `turn` that cycles through N values — does not preserve the mutual exclusion proof, because the "last writer to turn wins the wait" argument depends on there being only one rival. Real N-thread generalizations exist, such as Lamport's Bakery Algorithm (which uses ticket numbers) or a tournament-tree construction that arranges $O(\log N)$ pairwise Peterson instances in a binary tree, letting pairs of threads compete round by round.

Why don't real operating systems use Peterson's algorithm?

Two reasons: efficiency and hardware memory models. Busy-waiting wastes CPU cycles that could be given to other runnable threads, which matters enormously with many threads and long critical sections — real systems prefer blocking primitives (mutexes, semaphores) built on top of hardware atomic instructions, which can put a waiting thread to sleep instead of spinning. Second, and more fundamentally, Peterson's correctness proof assumes sequentially consistent memory: every core observes writes in the same global order. Modern multicore CPUs reorder memory operations for performance, so plain loads and stores are not sufficient without explicit memory barriers, which the naive pseudocode does not include.

What exactly does 'bounded waiting' mean, and how does Peterson's algorithm guarantee it?

Bounded waiting means a thread that wants to enter its critical section is not overtaken by other threads infinitely many times — there is a finite limit on how many times it can be bypassed before its turn comes. In Peterson's two-thread case, once thread i is waiting, the rival thread j can enter its own critical section and re-attempt entry at most once more before being forced to write `turn = i` again, which will make thread i's own guard false and let it proceed. This gives a strict bound of essentially one rival critical-section execution, rather than an unbounded number of overtakes.

What is the role of the turn variable, intuitively?

The `turn` variable acts as a tie-breaker specifically for the case where both threads want to enter at nearly the same instant. Each thread's flag alone tells you interest, not priority — if both flags are true, you need some additional mechanism to decide who actually goes first, otherwise both could wait on each other forever, or both could barge in together. By having each thread voluntarily write `turn` to point at its rival right before checking the loop condition, the algorithm ensures that whichever write happens last is the one that "sticks," and that thread is the one required to wait, while the other is guaranteed a clear path.

Is Peterson's algorithm considered a form of a spinlock?

Yes — the waiting thread does not yield the CPU or sleep; it repeatedly re-checks the loop condition in a tight busy-wait loop, which is exactly the definition of a spinlock. This makes it appropriate conceptually for very short critical sections on multiprocessor systems where the overhead of a context switch would exceed the wait time, but in practice, production spinlocks are built using hardware atomic instructions (like compare-and-swap) rather than the pure load/store approach of Peterson's algorithm, both for performance and correctness under relaxed memory models.

How does Peterson's algorithm relate to Dekker's algorithm?

Dekker's algorithm, generally credited as the earliest published software-only two-process mutual exclusion solution, also uses flags and a turn-like variable, but its logic is considerably more intricate: it requires a thread that finds the other interested to repeatedly check turn, temporarily lower its own flag, wait, and re-raise it, cycling through several extra steps. Peterson's 1981 paper showed that the same guarantees — mutual exclusion, progress, and bounded waiting — could be achieved with a dramatically simpler combined condition (`flag[j] && turn == j`), replacing Dekker's more convoluted control flow with two straight-line writes and a single while-loop check.

Can Peterson's algorithm be implemented correctly in a modern high-level language like Java or C++ without extra care?

Not safely, without explicit synchronization primitives such as `volatile` (Java) or atomics with proper memory ordering (`std::atomic` in C++, with at least acquire-release semantics). Compilers are permitted to reorder or cache reads/writes to ordinary variables across threads unless told otherwise, and CPUs can reorder memory operations at runtime. A literal transcription of the pseudocode using plain variables in these languages can fail on real hardware even though it is provably correct under the idealized sequential-consistency assumption — a gap that is precisely why the industry moved toward hardware atomic instructions with well-defined memory-ordering guarantees.