Part 5 of 7 · 3 min read
Peterson
In plain words: Two people reach a narrow doorway at the same moment. Each says "after you". The one who says it last, and so lets the other go first, waits. The analogy stops in one place: people hear each other, and the threads must communicate only by shared variables.
Peterson's algorithm (1981) solves the problem for two threads, numbered 0 and 1. It combines attempt 3 (flags) with attempt 2 (turn). The shared data are flag[2] and turn. Thread me (the other is 1 - me) runs:
void lock(int me) {
int other = 1 - me;
flag[me] = 1; /* I want in */
turn = other; /* but you go first */
while (flag[other] && turn == other) ; /* wait while you want in and it is your turn */
}
void unlock(int me) { flag[me] = 0; } /* I no longer want in */
Trace the hard case, in which both threads want in at the same time:
| Step | Thread 0 | Thread 1 | flag |
turn |
|---|---|---|---|---|
| 1 | flag[0] = 1 |
1, 0 | ||
| 2 | flag[1] = 1 |
1, 1 | ||
| 3 | turn = 1 |
1, 1 | 1 | |
| 4 | turn = 0 |
1, 1 | 0 | |
| 5 | test: flag[1] is 1 and turn == 1? turn is 0, so no: enters |
0 | ||
| 6 | test: flag[0] is 1 and turn == 0? Yes: waits |
0 |
Thread 1 wrote turn last, so it gave way, and thread 0 goes first. When thread 0 leaves, it clears flag[0], and thread 1's test fails, so thread 1 enters. If only one thread wants in, the other's flag is 0, and the test fails at once: no waiting.
Check the three requirements:
- Mutual exclusion. For both to be inside, thread 0 must have passed its test (
flag[1]is 0 orturnis 0) and thread 1 must have passed its test (flag[0]is 0 orturnis 1). Both flags are 1 when both are inside, soturnwould have to be both 0 and 1. The last write ofturndecides, and the thread that wrote last is the one that waits. - Progress. A thread that does not want in has its flag at 0, so it cannot hold back the other.
- Bounded waiting. A thread that waits is let in after at most one entry of the other, because after leaving, the other thread must set
turnto the waiting thread again if it tries to re-enter.
Peterson's algorithm
Peterson's algorithm is a software solution to the critical-section problem for two threads that uses a flag array, in which each thread announces that it wants to enter, and a turn variable, in which the thread that wrote last gives way to the other.
Example: when both threads set their flags at the same moment, the one that writes turn last waits, and the other enters.
Check yourself:
1. In the trace, which thread waits, and why?
2. What does flag[other] == 0 mean for the waiting test?
3. Why does Peterson's algorithm satisfy progress when attempt 3 does not?