Peterson’s Solution for Mutual Exclusion
Learn Peterson’s algorithm for two-process mutual exclusion — flag array, turn variable, and its limits — with OS interview questions.
Expected Interview Answer
Peterson’s solution is a software-only algorithm for two processes that guarantees mutual exclusion, progress, and bounded waiting using only two shared variables — a flag array and a turn variable — with no hardware atomic instructions.
Each process i sets flag[i] = true to declare intent to enter the critical section, then sets turn = j to politely yield priority to the other process, and finally busy-waits while (flag[j] && turn == j). Because turn can only hold one value at a time, whichever process wrote turn last is the one that waits, so the other is guaranteed to proceed — this is what forces mutual exclusion even though both processes race to set shared variables. On exit, the process resets flag[i] = false, which frees the other process’s busy-wait condition immediately. It is a landmark result because it proves mutual exclusion is achievable in software alone, but it is considered impractical today: it only handles two processes, it assumes sequentially consistent memory (which real CPUs and compilers do not guarantee without explicit memory barriers), and busy-waiting wastes CPU cycles compared to hardware-assisted primitives like test-and-set or compare-and-swap.
- Proves mutual exclusion is achievable with pure software, no hardware support
- Satisfies mutual exclusion, progress, and bounded waiting simultaneously
- Foundational teaching tool for reasoning about shared-variable races
- Motivates why modern systems moved to atomic hardware instructions instead
AI Mentor Explanation
Peterson’s solution is like two batters both wanting to face the next ball at the non-striker’s end: each raises a hand (flag[i] = true) to say they want it, then each politely says "you go first" (turn = j) to the other. Whoever said it last is bound by their own courtesy and waits, so the other batter is free to walk through. The moment the first batter is done, they lower their hand, instantly releasing the other from waiting.
Step-by-Step Explanation
Step 1
Declare intent
Process i sets flag[i] = true to signal it wants to enter the critical section.
Step 2
Yield turn
Process i sets turn = j, politely offering the other process priority.
Step 3
Busy-wait check
Process i loops while (flag[j] && turn == j) — it proceeds once either condition is false.
Step 4
Exit and release
On leaving the critical section, process i sets flag[i] = false, freeing any waiting process.
What Interviewer Expects
- A correct walk-through of flag[] and turn and why they force mutual exclusion
- Recognition that it satisfies mutual exclusion, progress, and bounded waiting
- Awareness it only works for two processes without generalization tricks
- Knowledge that it is largely a theoretical/teaching tool, not production code
Common Mistakes
- Forgetting the order of setting flag[i] before turn = j matters
- Claiming it works for more than two processes without modification
- Ignoring that modern compilers/CPUs reorder memory without barriers, breaking it in practice
- Confusing it with a hardware-based primitive like test-and-set
Best Answer (HR Friendly)
“Peterson’s solution is a classic algorithm that lets two processes take turns safely using just two shared variables, no special hardware needed. Each process says it wants in and then politely offers the other process to go first, and the clever trick with the shared turn variable makes sure exactly one of them actually waits. It is mostly taught today to build intuition, since real systems use hardware instructions instead for reliability and performance.”
Code Example
volatile int flag[2] = {0, 0};
volatile int turn;
void enter_critical_section(int i) {
int j = 1 - i;
flag[i] = 1;
turn = j;
while (flag[j] && turn == j) {
/* busy-wait */
}
}
void leave_critical_section(int i) {
flag[i] = 0;
}Follow-up Questions
- Why does Peterson’s solution not scale beyond two processes?
- What breaks in real hardware without a memory barrier?
- How does test-and-set avoid the busy-waiting overhead differently?
- What are mutual exclusion, progress, and bounded waiting formally?
MCQ Practice
1. In Peterson’s solution, what forces exactly one process to wait?
Because turn holds a single value, whichever process set it last is the one whose busy-wait condition remains true.
2. Peterson’s solution is designed for how many processes?
The classic algorithm’s flag array and turn variable are structured for exactly two competing processes.
3. Why is Peterson's solution considered impractical on modern hardware?
Without memory barriers, out-of-order execution and compiler optimizations can violate the ordering the algorithm depends on.
Flash Cards
What is Peterson’s solution? — A software-only two-process mutual exclusion algorithm using a flag array and a turn variable.
What guarantees does it satisfy? — Mutual exclusion, progress, and bounded waiting.
Why is it rarely used in production? — It only handles two processes and assumes memory ordering that modern hardware/compilers do not guarantee without barriers.
What replaces it in practice? — Hardware atomic instructions like test-and-set or compare-and-swap.