3.2Software and hardware solutions
The idea
Peterson's algorithm lets two processes share a critical section using two flags and a turn variable, in software. Hardware offers atomic instructions like test-and-set.
Think of it like this: Two people at a narrow door: each raises a hand (flag) and says "after you" (turn). The one who spoke last waits.
Why it exists
It shows how subtle the problem is: every simpler protocol you can invent breaks one of the three requirements.
How it works
- Process i sets flag[i] = true (I want in).
- It sets turn = j (you go first if we both want).
- It waits while flag[j] is true and turn == j.
- After the critical section it sets flag[i] = false.
Worked example: Why does turn = j make it correct?
If both want in, both set their flag and then write turn. The last writer's value stays, so exactly one of them sees turn pointing to the other and waits. Mutual exclusion, progress and bounded waiting all hold.
Now play with it
- →Choose "Flags only" and step P0 and P1 once each: both wait forever (deadlock).
- →Choose "Check flag first, then set it" and make both enter.
Peterson: both flags up, so only the turn decides, and the turn belongs to the process that gave it away last. Flags only can deadlock (both wait). Strict alternation is safe but forces taking turns even when the other process does not want in. Checking the flag before setting it breaks mutual exclusion: step P0 check, P1 check, then both set and enter.
| Method | Mutual exclusion | Progress | Bounded waiting | Notes |
|---|---|---|---|---|
| Peterson | yes | yes | yes | two processes, busy waiting |
| Strict alternation | yes | no | yes | forces turns |
| Flags only | yes | deadlock possible | - | both can wait forever |
| Test-and-set lock | yes | yes | no (no queue) | atomic instruction, busy waiting |
| Disable interrupts | yes (one CPU only) | yes | yes | kernel use only |
Check yourself
Strict alternation (a shared turn variable only) violates
Exam notes (the dense version)
Peterson's algorithm (two processes): set flag[i] = true, set turn = j, wait while flag[j] and turn == j. It satisfies all three requirements. Strict alternation (turn only) gives mutual exclusion but violates progress. Flags only can deadlock. Hardware: test-and-set and compare-and-swap are atomic; a spinlock built on them gives mutual exclusion but not bounded waiting by itself, and spins (busy waiting). Disabling interrupts works on a single CPU only.
Previous year questions: Synchronization & Concurrency (10)
PYQs are grouped by topic, so this is the full set for Synchronization & Concurrency; try the ones that match this subtopic. Open all 10 on the topic page.