Peterson's solution
/ PEE-ter-son /
Before hardware gave us 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? Peterson's solution (published by Gary Peterson in 1981) is the famous, elegant answer for two threads. It uses just two shared variables and a moment of polite deference, and it provably satisfies all three critical-section requirements. It is taught not because you should ship it, but because it crisply shows what those requirements really demand.
The trick combines an intention flag with a turn variable. Each thread i sets flag[i] = true to announce 'I want in', then sets turn = j to politely give the other thread the first chance. It then waits as long as the other thread also wants in AND it is the other's turn: while (flag[j] && turn == j) spin. Whoever set turn last loses the tie and waits; the other proceeds. On exit, the thread clears flag[i] = false. The genius is the combination: the flags alone deadlock (both insist), and the turn alone fails progress (strict alternation), but together the flag says 'I am interested' and the turn breaks ties, giving mutual exclusion, progress, and bounded waiting all at once.
Here is the crucial honest caveat: Peterson's solution is correct only on an idealized machine where memory operations happen in program order and are immediately visible to other cores. Real CPUs and compilers reorder reads and writes for speed, so on modern multicore hardware Peterson's algorithm can break unless you insert memory barriers to forbid the reordering. So its practical lesson is twofold: software-only mutual exclusion is possible in principle, and the reason we reach for hardware atomic instructions in practice is that they sidestep exactly the memory-ordering minefield that makes pure-software solutions so fragile.
Two threads both want in. Thread 0 sets flag[0]=true, turn=1. Thread 1 sets flag[1]=true, turn=0. Whichever wrote turn last sees its own id stored and waits; the other sees the turn favors it and enters. They never collide, and neither waits more than one turn.
Flag = 'I want in'; turn = polite tie-break. Together: all three requirements.
On real reordering hardware Peterson's solution needs memory barriers to be correct. It is a teaching device, not production code; in practice use hardware atomics or library locks.