Part 4 of 7 · 2 min read
Several instances
In plain words: If a resource type has several instances, the argument of section 2 breaks. A thread that waits for "a printer" can get any free one, so the wait does not name one owner. The edge goes to the type, and the type may have an instance that is held by a thread outside the cycle.
Here is a made-up example, built to show the idea. There are two resource types: R1 has 2 instances and R2 has 1 instance. Three threads are present:
| Thread | Holds | Waits for |
|---|---|---|
| T1 | 1 of R1 | R2 |
| T2 | R2 | 1 of R1 |
| T3 | 1 of R1 | nothing |
The graph has a cycle: T1 → R2 → T2 → R1 → T1. Yet this is not a deadlock. T3 is not waiting for anything, so it will finish and release its instance of R1. Then T2 gets that instance, finishes, and releases R2. Then T1 gets R2 and finishes. A trace of the end of the run, computed by the detection method of page 5:
free instances at the start: R1 = 0, R2 = 0
T3 can finish (it waits for nothing) -> free: R1 = 1, R2 = 0
T2 can finish (it wants 1 of R1) -> free: R1 = 1, R2 = 1
T1 can finish (it wants 1 of R2) -> free: R1 = 2, R2 = 1
Now change one fact. Let T3 wait for R2 instead. Nobody can finish: T1, T2 and T3 all wait, and the only free instances are none. The same script reports all three as deadlocked. The graph has the same cycle as before. What changed is that the thread outside the cycle can no longer release anything.
So with several instances, the rule is:
- No cycle: no deadlock.
- A cycle and every type has one instance: deadlock.
- A cycle and some type has several instances: a deadlock is possible, but not certain. The graph alone does not decide it.
Cycle in a resource-allocation graph
A cycle in a resource-allocation graph is a path of edges that returns to its starting node; it is necessary for a deadlock, and it is sufficient only if every resource type on the cycle has a single instance.
Example: the cycle T1 → R2 → T2 → R1 → T1 is not a deadlock while thread T3 can still release an instance of R1.
Common mistake
"A cycle means deadlock" is only true for single-instance resources. Pools of identical resources, such as database connections or memory pages, can show a cycle that clears by itself.
Check yourself:
1. In the table, why will T3 finish?
2. Why does making T3 wait for R2 turn the cycle into a deadlock?
3. For which kind of resource is a cycle always a deadlock?