Part 3 of 8 · 3 min read
Detection
In plain words: Page 2 showed that with several instances per resource type, a cycle in the graph is not proof of a deadlock. The detection algorithm solves this with tables, like the banker's safety check on page 4. There is one difference, and it matters. The banker's algorithm asks about the worst case: each thread may ask for its full maximum claim. The detection algorithm asks about the present: each thread is assumed to ask for no more than it is asking for now.
The tables are:
| Name | Meaning |
|---|---|
| Available | Free units of each type |
| Allocation | What each thread holds now |
| Request | What each thread is waiting for now (a row of zeros for a thread that is not waiting) |
The algorithm starts with a work vector equal to Available. It marks as finished every thread that holds nothing, since such a thread cannot be part of a cycle. Then it repeats: find an unfinished thread whose Request is at most the work vector, assume it will get what it wants, finish and return its Allocation, and add that to the work vector. When no thread fits, every thread still unfinished is deadlocked.
Here is a made-up example with 4 units of type 1 and 3 units of type 2:
| Thread | Allocation | Request |
|---|---|---|
| P0 | (1, 0) | (0, 0) |
| P1 | (1, 1) | (1, 0) |
| P2 | (1, 1) | (0, 2) |
| P3 | (1, 1) | (0, 2) |
| P4 | (0, 0) | (0, 0) |
Units held: (4, 3). Available is (0, 0). Trace:
start: work = (0,0). P4 holds nothing: marked finished.
P0 wants (0,0) <= (0,0): finishes, work = (0,0) + (1,0) = (1,0)
P1 wants (1,0) <= (1,0): finishes, work = (1,0) + (1,1) = (2,1)
P2 wants (0,2) <= (2,1)? No. P3 wants (0,2) <= (2,1)? No.
No thread fits. Deadlocked: P2 and P3.
P2 and P3 each wait for 2 units of type 2, and only 1 is free, so neither can ever get its request. Now change one fact: let P3 request only (0, 1). After P1, the work vector is (2, 1). P3 fits, finishes, and returns its units: work becomes (3, 2). Then P2 wants (0, 2) ≤ (3, 2), and finishes. The result is no deadlock, and the finishing order is P4, P0, P1, P3, P2. The only change was one unit in a request.
The optimism in the method is deliberate. If a thread's Request fits, the algorithm assumes the thread will finish and give back everything. In real life the thread may ask for more later. If it does, and a deadlock appears then, the next run of the algorithm finds it. For this reason, the algorithm detects deadlocks that exist now, and does not predict future ones.
The cost is the same order as the safety check: m × n² operations for n threads and m types (OSC).
Request matrix
The request matrix is a table that holds, for each thread, the number of units of each resource type it is waiting for at this moment; detection uses it in place of the maximum claim used by avoidance.
Example: the row (0, 2) means the thread is waiting for 0 units of type 1 and 2 units of type 2.
Check yourself:
1. Why does the algorithm mark a thread that holds nothing as finished at the start?
2. What changes when P3 asks for (0, 1) instead of (0, 2)?
3. How does the detection algorithm differ from the banker's safety check in what it assumes?