Part 5 of 7 · 2 min read
Interleavings
In plain words: The program in section 1 used a 0.1 s pause to force the deadlock. Without the pause, the same code usually works. The table shows two interleavings (the order in which the steps of the threads happen) of the same two threads, with no pause:
| Step | Interleaving 1 (works) | Interleaving 2 (deadlock) |
|---|---|---|
| 1 | T1 locks A |
T1 locks A |
| 2 | T1 locks B |
T2 locks B |
| 3 | T1 unlocks B, then A |
T1 asks for B, and blocks |
| 4 | T2 locks B |
T2 asks for A, and blocks |
| 5 | T2 locks A |
Both are blocked forever |
| 6 | T2 unlocks both |
In interleaving 1, T1 finishes before T2 starts, so there is no overlap and no cycle. In interleaving 2, each thread gets its first lock before either gets its second. The window for this is tiny: the time between a thread's first and second lock. On a fast machine, that may be a few nanoseconds.
A second experiment shows how this plays out in a real program. Four bank accounts each have a mutex. Each thread repeatedly picks two accounts at random and moves 1 unit between them, taking the first-named account's lock and then the second's. A watchdog reports "stuck" if a second lock takes more than 1 s. Five runs on the test machine got stuck after 9, 125, 196, 388 and 703 transfers. The program had run perfectly for hundreds of steps before the unlucky pair of threads met. A test that ran only 5 transfers would have passed.
This is why deadlocks are dangerous in practice. The code is wrong from the start, yet it passes many tests. A deadlock appears when the load is higher, the machine is faster, or a rare timing occurs, which is often after release.
Interleaving
An interleaving is one particular order in which the steps of several threads are carried out on the machine; the same program can have many interleavings, and a bug that appears in only a few of them is called timing-dependent.
Example: in the table above, "T1 locks A, T2 locks B, T1 asks for B, T2 asks for A" is the interleaving that deadlocks.
Check yourself: 1. In the table, why is there no deadlock in interleaving 1? 2. Why did the bank program run for up to 703 transfers before it got stuck? 3. Why does a deadlock often show up only on a heavily loaded production machine?