Part 1 of 7 · 1 min read
Why this page comes second
In this module you will
- Draw a resource-allocation graph for threads and resources, with single or multiple instances.
- Turn it into a wait-for graph and find a cycle in it.
- Say when a cycle means a deadlock and when it does not.
- Write a short C function that finds a cycle among threads that each wait for one other thread.
- Tell the threads inside a cycle from the threads that are only stuck behind it.
Page 1 defined a deadlock and showed that the cycle of waiting is the heart of it. A cycle is something a computer can search for, once it is written down as a graph. This page gives the drawing and the search. Pages 3 and 4 then use the same pictures to prevent and avoid deadlocks, and page 5 uses the search to detect them. The sources are OSC chapter 8, MOS chapter 6 and the chapter on deadlock in Anderson and Dahlin (AD). The code was compiled with gcc -Wall -Wextra and run on a two-processor Linux machine.
About this example About this example
Real: The C programs, commands and outputs on this page were compiled with gcc -Wall -Wextra -pthread and run on a Linux test machine (2 processors, kernel 6.18, glibc 2.39).
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.