In Peterson's algorithm for two processes, what is the purpose of setting `turn` to the *other* process's ID when a process wants to enter the critical section?
AIt signals that the other process should get out of the critical section immediately
BIt claims priority — whoever sets turn to the other's ID gets to go first
CIt is an act of deference — 'you go first if you want to' — so that whoever defers last is the one that waits
DIt resets the other process's flag variable to false
Setting turn = other is the opposite of claiming priority — it is yielding. If both processes try to enter simultaneously, both set their flags and both set turn to the other's ID. Turn can only hold one value, so the process that wrote last 'wins' the deference: its write stuck, making it the one that waits. The process whose turn write was overwritten is the one that proceeds. This asymmetry through a single shared variable is the elegant core of Peterson's algorithm.
Question 2 Multiple Choice
A colleague tells you Peterson's algorithm fails reliably on modern x86 and ARM hardware, even though it is provably correct under sequential consistency. What is the most likely cause?
AModern CPUs execute instructions too quickly for the flag mechanism to have effect
BPeterson's algorithm only handles two processes, but modern kernels always schedule more
CCPUs and compilers reorder memory reads and writes for performance, so the flag write may not be visible to the other process before the turn read occurs
DThe algorithm assumes processes run at the same speed, which hardware cannot guarantee
Peterson's algorithm depends on a specific memory ordering: the write to `flag[i]` must be visible to the other process before the read of `turn`. Modern CPUs and compilers routinely reorder stores and loads for performance. Under weak memory models (which all major architectures use), both processes can read stale values of the other's flag, both see turn == the other's ID, and both enter the critical section simultaneously — breaking mutual exclusion. This is not theoretical; it is reproducible. Fixing it requires memory barriers (fence instructions), which are hardware support — defeating the purpose of a software-only solution.
Question 3 True / False
A mutual exclusion solution that uses primarily a `flag` array (with no `turn` variable) can satisfy most three critical section requirements: mutual exclusion, progress, and bounded waiting.
TTrue
FFalse
Answer: False
Without a tiebreaker like `turn`, a flags-only approach can fail mutual exclusion. If both processes read each other's flag before either sets its own, both see the flag as false and both proceed into the critical section simultaneously. This race condition is not a corner case — it happens reliably when processes interleave at exactly the wrong moment. The `turn` variable is not redundant; it is precisely what resolves the tie and ensures at most one process proceeds.
Question 4 True / False
Peterson's algorithm guarantees bounded waiting — no process waiting to enter the critical section will wait indefinitely.
TTrue
FFalse
Answer: True
Bounded waiting holds in Peterson's algorithm because a process that exits the critical section resets its flag and sets turn to the other process's ID. If the other process was waiting, its wait condition (flag[me] == true AND turn == my_id) is now satisfied — it can proceed. A process can be made to wait at most one full cycle by the other process before getting its turn. This is a finite bound, satisfying the bounded waiting requirement.
Question 5 Short Answer
Explain why Peterson's algorithm, which is provably correct under sequential consistency, fails on modern hardware, and what this implies about the need for hardware support for mutual exclusion.
Think about your answer, then reveal below.
Model answer: Peterson's algorithm assumes that writes to shared variables are immediately visible to all processors in the order they were issued — this is called sequential consistency. Modern CPUs use weak memory models: they reorder reads and writes, use store buffers, and propagate cache updates asynchronously. The critical operation in Peterson's — 'write flag, then read turn' — can be reordered to 'read turn, then write flag,' causing both processes to read stale values and both enter the critical section. To restore the correct ordering you would need memory barrier (fence) instructions between the flag write and the turn read. But memory barriers are hardware instructions, which contradicts the premise of a software-only solution. This reveals that correct mutual exclusion on real hardware inherently requires hardware cooperation — either atomic read-modify-write instructions (like test-and-set or compare-and-swap) or OS-provided synchronization that issues the necessary memory barriers.
This is the central lesson of software-only solutions: they establish that mutual exclusion is *logically* solvable with pure reads and writes, but modern hardware's performance optimizations break the sequential consistency assumption that makes them correct. Peterson's algorithm lives on as a theoretical landmark and an exam standard, while real systems use atomic hardware primitives.