CSE Roadmap

Core tier · about 4 hours · 7 parts

Part 5 of 7 · 2 min read

Live graph

In plain words: In a real program, the edges come from two facts for every blocked thread: which lock it waits for, and which thread owns that lock. A debugger or a tool gives both (page 1, section 5, printed the owner of each mutex). Write them down as pairs, and the wait-for graph follows.

Take a made-up server with five threads, where T0 to T4 are thread numbers:

Thread Waits for a lock owned by
T0 T1
T1 T2
T2 T0
T3 T0
T4 nobody (it is running)

The array waits_for = {1, 2, 0, 0, -1} holds exactly this. Running the function of section 2 from each thread printed:

T0: reaches a cycle: T0 T1 T2
T1: reaches a cycle: T1 T2 T0
T2: reaches a cycle: T2 T0 T1
T3: reaches a cycle: T2 T0 T1
T4: no cycle ahead

T0, T1 and T2 lie on the cycle. T3 is blocked too, but it is not on the cycle: it waits for T0, and T0 never releases anything. The cycle that T3 reaches is the same one. T4 is free, so it is not part of the problem.

The difference matters when the program recovers. Killing T3 would not help, since T3 is not the cause. The thread to act on must be on the cycle. Page 5 returns to this when it chooses a victim.

The real cost of watching for cycles is the cost of keeping the data. To know who owns each lock, the system must record the owner when the lock is taken. The Linux lock-checking tool called lockdep (OSC, chapter 8) does this for every lock in the kernel, and can also be used for pthread mutexes. It keeps the lock order as a graph, and it reports a possible deadlock when a lock is taken in an order that closes a cycle. The designers note it slows the system a lot, so it is for development and not for production machines. Page 3 shows a small user-space version of the same idea, and page 7 shows two real tools.

Deadlocked set

A deadlocked set is a set of blocked threads in which every thread waits for a resource that only another thread of the set can release; threads that merely wait behind the set are stuck too, but they are not members of it.

Example: in the table, T0, T1 and T2 are the deadlocked set, and T3 is stuck behind it.

Check yourself: 1. Which two facts must be known for each blocked thread to build a wait-for graph? 2. Why is T3 not part of the deadlocked set? 3. Why would killing T3 leave the deadlock in place?