Part 1 of 8 · 1 min read
Why this page comes sixth
In this module you will
- Tell a deadlock, a livelock and starvation apart by what the threads are doing.
- Show a livelock with
trylock, and cure it with random back-off. - Reproduce priority inversion on one processor, and cure it with priority inheritance.
- Show a deadlock caused by full pipes, and compute the exact point where it appears.
- Explain two deadlocks that use only one lock:
forkwith a held lock, and a signal handler.
Pages 1 to 5 studied the classic deadlock: threads asleep in a cycle. A program can also stop making progress in other ways, and a person who sees "the program hangs" must find out which one it is. The cures differ. This page covers the five most common cousins. Three of them (livelock, starvation and priority inversion) are about scheduling and fairness, and the last two are deadlocks in disguise, which no lock graph of the kind drawn on page 2 would show. The sources are OSC chapters 5 and 8, MOS chapter 6, TLPI chapters 20 to 24 and 44, and the Mars Pathfinder reports by Jones and Reeves (1997). All programs were compiled with gcc -O2 -pthread on a two-processor Linux machine, with root rights where real-time priorities were used.
About this example About this example
Real: The facts, definitions and algorithms on this page come from the books named in the text. No program on this page was timed.
Scripted: The worked traces use small numbers chosen so they can be followed by hand.
Not real: The page simplifies real systems. Actual kernels add more cases, limits and tuning than a short page can show.