Part 4 of 7 · 3 min read
Failures
A first guess is rarely right. Three natural attempts show how each fails, and what the next solution needs.
Attempt 1: a lock variable. A shared variable locked is 0 when the section is free. A thread waits until it is 0, sets it to 1, enters, and sets it to 0 on leaving:
while (locked) ; /* step 1: wait until free */
locked = 1; /* step 2: take it */
/* critical section */
locked = 0;
The trace shows the flaw. Both threads see 0 before either sets 1:
| Step | Thread A | Thread B | locked |
|---|---|---|---|
| 1 | reads 0, leaves the loop | 0 | |
| 2 | reads 0, leaves the loop | 0 | |
| 3 | sets 1, enters | 1 | |
| 4 | sets 1, enters | 1 |
In plain words: Both are inside. Mutual exclusion fails, because testing and setting are two separate steps. A run of two threads, each adding 1 to a shared counter a million times inside this "lock", gave:
expected 2000000, got 1258599
expected 2000000, got 1163568
expected 2000000, got 1255884
Nearly 40 per cent of the updates were lost. The lock gives the feeling of safety and little of it.
Attempt 2: strict alternation. A variable turn says whose turn it is. Thread 0 enters only when turn is 0 and then sets it to 1. Thread 1 does the reverse. Mutual exclusion holds. But if thread 1 stays a long time in its remainder section, thread 0 enters once, sets turn to 1, and then waits at its entry section until thread 1 comes back. Progress fails: a thread outside its critical section holds back a thread that wants to enter. The threads also run at the speed of the slower one.
Attempt 3: two flags. Each thread sets its own flag (flag[me] = 1) to say "I want in", then waits while the other flag is set. Mutual exclusion holds. But if both set their flags at the same moment, each sees the other's flag and waits for ever. Progress fails again, with both threads stuck.
The pattern: a lock variable fails on the gap between test and set, alternation fails because it ignores who wants to enter, and flags fail because both defer to each other. A correct solution needs to combine a statement of interest (flags) with a way to break ties (turn).
Progress
Progress is the requirement that when no thread is in its critical section and some want to enter, the choice of which one enters is made only among those wanting to enter and is not postponed indefinitely, so a thread in its remainder section cannot block the others.
Example: strict alternation violates it, because a thread that stays in its remainder section blocks the other thread's entry.
Check yourself: 1. Which two steps does the lock variable of attempt 1 leave open to interleaving? 2. Which requirement does strict alternation break? 3. What happens in attempt 3 when both flags are set at once?