A topic in the Open Knowledge Graph — a free, open map of 15,290 topics and the order to learn them in.
Peterson's and Dekker's algorithms solve the two-process critical section problem using only shared variables (flags, turn). While theoretically important, they are impractical on modern CPUs due to weak memory ordering; hardware support is essential in practice.
From the critical section problem, you know the three requirements any solution must satisfy: mutual exclusion (at most one process in the critical section at a time), progress (if no process is in the critical section and some want to enter, one must be allowed in), and bounded waiting (no process waits forever). The challenge of software-only solutions is meeting all three requirements using nothing but ordinary shared variables — no special hardware instructions, no OS support, just reads and writes to memory.
Peterson's algorithm for two processes uses two shared variables: a boolean array `flag[2]` where `flag[i]` means "process i wants to enter," and a `turn` variable that breaks ties. When process 0 wants to enter, it sets `flag[0] = true` (announcing interest), then sets `turn = 1` (yielding priority to the other process), then waits in a loop while `flag[1] == true AND turn == 1`. The key insight is the combination: setting your flag shows intent, but setting turn to the *other* process's ID is an act of deference. If both processes try to enter simultaneously, both set their flags and both set turn — but turn can only hold one value, so whoever wrote to it *last* will be the one who waits. This guarantees mutual exclusion. Progress holds because a process only waits when the other is genuinely interested and has priority. Bounded waiting holds because after the other process exits and re-enters, it resets turn, giving priority back.
Dekker's algorithm is historically the first correct software solution, predating Peterson's. It uses the same flag array but handles tie-breaking differently — the losing process must retract its flag, wait, then re-announce interest. Peterson's algorithm is simpler and more elegant, which is why it is the version taught in most courses. Both algorithms extend the failed attempts you may have seen: using just a turn variable (violates progress — a process that does not want to enter blocks the other), or using just flags without turn (allows both to enter simultaneously if they set flags at the same time).
The fatal limitation of these algorithms on modern hardware is memory reordering. Modern CPUs and compilers aggressively reorder reads and writes for performance. Peterson's algorithm depends on a specific ordering: the flag write must become visible to the other process *before* the turn read. If the CPU reorders these operations, both processes can read stale values and both enter the critical section — mutual exclusion breaks. This is not a theoretical concern; it happens reliably on x86, ARM, and other architectures. To fix this, you would need memory barriers (fence instructions) — but those are hardware support, which defeats the purpose of a software-only solution. This is why Peterson's and Dekker's algorithms are taught for their theoretical elegance in proving that mutual exclusion *can* be solved without hardware support, while real systems use atomic instructions like test-and-set, compare-and-swap, or OS-provided synchronization primitives.