# Peterson's Solution

> Peterson's Solution is a classic software-only algorithm that solves the critical section problem for exactly two processes using two shared variables: a flag array marking who wants to enter and a turn variable. It achieves mutual exclusion, progress and bounded waiting without special hardware instructions, though modern CPUs need memory barriers for it to stay correct.

Canonical: https://devsunite.com/resources/core-subjects/operating-systems/petersons-solution
Last updated: 2026-11-22

Subject: Operating Systems · Category: Process Synchronization · 4 min read

Peterson's Solution is one of the earliest and cleanest correct answers to the critical section problem for exactly two processes, and it's taught specifically because it proves mutual exclusion, progress, and bounded waiting can all be achieved using nothing more than ordinary shared variables, no special hardware instructions needed at all.

## The two shared variables

Peterson's Solution uses exactly two pieces of shared state between the two processes (call them P0 and P1):

- **`flag[2]`**: a boolean array, where `flag[i]` being true means "process i wants to enter its critical section."
- **`turn`**: an integer indicating whose turn it is to enter, if both processes want in at the same time.

## The algorithm itself

Each process Pi (where the other process is Pj) runs this entry and exit protocol around its critical section:

```
flag[i] = true;       // I want to enter
turn = j;             // but I'll politely let you go first if we both want in
while (flag[j] && turn == j) {
    // busy-wait: keep checking until it's safe to proceed
}

// --- critical section ---

flag[i] = false;      // I'm done, release my claim
```

## Why this actually works

If only P0 wants to enter, `flag[1]` is false, so P0's while-loop condition is immediately false and it enters right away, no unnecessary waiting. If both P0 and P1 try to enter at nearly the same time, both set their own flag to true and both set `turn` to point at the other process, but `turn` is a single shared variable, whichever process's write to `turn` happens to execute last is the value that actually sticks, and that determines who politely waits and who proceeds. This guarantees mutual exclusion (only one can pass its while-loop condition at a time), progress (the one who proceeds does actually get to run its critical section), and bounded waiting (the waiting process gets in as soon as the other exits and clears its flag, at most one turn of waiting).

## A concrete example

Suppose P0 and P1 both attempt to enter within microseconds of each other. P0 sets `flag[0] = true` and `turn = 1`. Almost simultaneously, P1 sets `flag[1] = true` and `turn = 0`. Since `turn` is one shared variable, only one of these two writes is the final value, say P1's write happens fractionally later, so `turn` ends up as 0. Now P0 checks its while condition: `flag[1]` is true, but `turn == 1` is false (turn is 0), so P0's loop condition is false and P0 proceeds into its critical section. P1 checks its own condition: `flag[0]` is true and `turn == 0` is true, so P1's loop condition holds and P1 correctly waits until P0 finishes and clears `flag[0]`.

## Where this matters in real systems

Peterson's Solution itself isn't used directly in modern production systems, it only works cleanly for exactly two processes, and, more importantly, modern CPUs and compilers can reorder memory operations in ways that can silently break the assumptions this algorithm relies on unless the code adds specific memory barrier instructions, something the classic textbook version doesn't include. Its real value today is conceptual and educational: it's the clearest possible proof that pure software, with no special hardware support, can correctly solve the critical section problem, which sets up why hardware-assisted primitives like atomic test-and-set instructions and semaphores (the actual mechanisms real systems use) are built the way they are.

## What interviewers actually ask about Peterson's Solution

- **"What two variables does Peterson's Solution use, and what does each mean?"** `flag[i]`, whether process i wants to enter its critical section, and `turn`, whose turn it is to proceed if both processes want in simultaneously.
- **"Walk through why Peterson's Solution guarantees mutual exclusion."** Both processes set their flag and defer `turn` to the other; since `turn` is one shared variable, only one process's while-loop condition can be false at a time, so only one can proceed.
- **"Why isn't Peterson's Solution used in real production systems today?"** It only works for two processes, and modern CPU/compiler memory reordering can silently break its correctness guarantees without explicit memory barriers, which the classic algorithm doesn't include.
- **"What is Peterson's Solution's real educational value, then?"** It proves the critical section problem can be solved with pure software and ordinary shared variables, no special hardware instructions required, which frames why real hardware-assisted primitives were later built.

## Key takeaways

- Peterson's Solution solves the critical section problem for two processes using only two shared variables, `flag` and `turn`.
- It correctly guarantees mutual exclusion, progress, and bounded waiting with no special hardware support.
- It's not used directly in real modern systems due to being limited to two processes and vulnerable to modern CPU/compiler memory reordering.
- Its lasting value is proving pure software can solve this problem at all, setting up the case for hardware-assisted primitives like semaphores.

## Related

- [Previous: The Critical Section Problem](https://devsunite.com/resources/core-subjects/operating-systems/critical-section-problem)
- [Next: Semaphores](https://devsunite.com/resources/core-subjects/operating-systems/semaphores)
- [More in Process Synchronization: The Need for Process Synchronization](https://devsunite.com/resources/core-subjects/operating-systems/need-of-process-synchronization)
- [More in Process Synchronization: Data Inconsistency and Race Conditions](https://devsunite.com/resources/core-subjects/operating-systems/data-inconsistency-and-race-condition)
- [More in Process Synchronization: Busy Waiting and Spinlocks](https://devsunite.com/resources/core-subjects/operating-systems/busy-waiting-and-spinlocks)
- [All 205 OS interview questions](https://devsunite.com/resources/core-subjects/operating-systems)
