CSE Roadmap

Core tier · about 5 hours · 7 parts

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 or turn is 0) and thread 1 must have passed its test (flag[0] is 0 or turn is 1). Both flags are 1 when both are inside, so turn would have to be both 0 and 1. The last write of turn decides, 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 turn to 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?