CSE Roadmap

Core tier · about 4 hours · 7 parts

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.