Part 3 of 7 · 3 min read
Wait-for graph
In plain words: When every resource has exactly one instance, the graph can be made simpler. A thread that waits for a lock really waits for the thread that owns it. Remove the resource boxes and draw an arrow straight from the waiting thread to the owner. What remains is a graph of threads only.
For the two-lock deadlock, the wait-for graph is just T1 → T2 → T1. For a ring of three threads, T1 waits for the lock held by T2, T2 for the one held by T3, and T3 for the one held by T1, so the graph is T1 → T2 → T3 → T1.
In a graph with single-instance resources, a cycle is both necessary and sufficient for a deadlock. It is necessary because circular wait is one of the four conditions. It is sufficient because every thread on the cycle waits for a thread on the cycle, and none of them can release anything while it waits. So finding a cycle is the same as proving a deadlock.
Finding a cycle is a standard graph search. OSC states that an algorithm that searches a graph for a cycle needs about n² operations, where n is the number of nodes. For a lock graph, there is a very cheap special case. A blocked thread waits for exactly one lock, and a lock has exactly one owner, so every thread has at most one outgoing arrow. Then it is enough to follow the arrows from a thread, and see whether the chain ends or comes back to a thread already visited.
/* waits_for[i] = the thread whose lock thread i wants, or -1 if i is not blocked */
static int find_cycle(const int waits_for[], int start, int out[]){
int slow = start, fast = start;
for (;;) { /* two walkers, one twice as fast */
if (fast < 0 || waits_for[fast] < 0) return 0;
fast = waits_for[fast];
if (fast < 0 || waits_for[fast] < 0) return 0;
fast = waits_for[fast]; slow = waits_for[slow];
if (slow == fast) break; /* they met: there is a cycle */
}
int n = 0, x = slow; /* walk once around it */
do { out[n++] = x; x = waits_for[x]; } while (x != slow);
return n; /* length of the cycle, 0 if none */
}
The function sends two walkers along the chain, one twice as fast as the other. If the chain ends, there is no cycle. If the walkers meet, they are both inside a cycle. Its cost is a number of steps proportional to the number of threads. Section 4 runs it.
Wait-for graph
A wait-for graph is a directed graph whose nodes are threads, with an edge from thread X to thread Y when X is blocked waiting for a resource that Y holds; it is made from a resource-allocation graph with single-instance resources by removing the resource nodes.
Example: if T1 waits for a lock owned by T2, the wait-for graph has the edge T1 → T2.
Check yourself: 1. Why does each blocked thread have at most one outgoing edge when all resources are single-instance locks? 2. Why is a cycle in a single-instance graph enough to prove a deadlock? 3. What does the two-walker function return for a chain that ends at an unblocked thread?