Deadlock: resource graphs and safe states
Goals and model
Recognize deadlock, reason carefully about graph cycles, and test a small resource-allocation state for safety. Prerequisite: locks and blocking. Resources here are reusable, processes declare maximum simultaneous demands when the safety test requires them, and a completing process releases its allocations. The arithmetic model ignores process failures and assumes resources are not lost. Safety is evaluated under these declared maximum claims, not a guess about likely future requests.
1. Two keys and no progress
Imagine two technicians. A holds the only cabinet key and waits for the only workshop key. B holds the workshop key and waits for the cabinet key. Neither returns a key until receiving the other. Each depends on an action that the other cannot perform. This is deadlock, not merely a long wait.
Four necessary conditions for classical resource deadlock are mutual exclusion, hold-and-wait, no forced preemption of held resources, and circular wait. Necessary does not mean that the mere possibility of these policies proves a particular current state is deadlocked. Inspect actual allocations and outstanding requests.
Starvation is different: one process may keep losing access while others progress. Deadlock concerns a group that cannot progress under the allowed transitions. A temporarily blocked process waiting for a device that will finish is not necessarily either deadlocked or starved.
2. Read the arrow before finding a cycle
In a resource-allocation graph, process P→resource R is a request; resource instance R→process P is an assignment. With exactly one instance of each resource type, a directed cycle indicates deadlock under the usual blocking model. If there is no cycle, there is no resource deadlock in this model.
Worked single-instance graph: R1→P1, P1→R2, R2→P2, P2→R1. P1 cannot get R2 until P2 releases it; P2 cannot get R1 until P1 releases it. Both are blocked, so the cycle certifies deadlock.
Multiple instances change the conclusion. Let A have two instances and B one. P1 holds one A and requests B. P2 holds B and requests one A. P3 holds the other A and needs nothing more. There is a type-level cycle P1→B→P2→A→P1, yet P3 can finish and release A. P2 can then acquire A, finish and release B; P1 can finish. The cycle is not sufficient for deadlock when resource types have multiple instances. Account for every instance and every process outside the apparent cycle.
3. Prevention, avoidance, detection
Prevention breaks a necessary condition by design. Requiring all locks to be acquired in a common strict order prevents circular wait: along a cycle the lock order would have to increase strictly and return to its start, which is impossible. Asking for all resources together can remove hold-and-wait, but may reduce utilization. Making a genuinely shareable resource nonexclusive removes mutual exclusion for that resource; some resources cannot safely be shared.
Avoidance evaluates requests to stay in safe states, using information such as maximum claims. Detection allows allocations and later looks for deadlock; recovery may terminate processes or reclaim resources where safe. These policies are not synonyms. Lock ordering does not itself guarantee fair scheduling or prevent every form of starvation.
4. Safety algorithm with two resource types
Let Allocation_i be currently held resources and Max_i the declared maximum. Need_i=Max_i−Allocation_i componentwise. Start Work=Available. Find an unfinished process with Need_i≤Work in every component. Pretend it obtains the additional resources, completes and releases everything. The net update is Work=Work+Allocation_i, because the temporary Need grant is returned too. Repeat. If all processes can finish, the state is safe and the chosen order is a safe sequence. If stuck, no safe sequence exists under the claims; that is unsafe, not automatically a current deadlock.
Worked state with resources (A,B):
| Process | Allocation | Max | Need |
|---|---|---|---|
| P0 | (1,0) | (3,2) | (2,2) |
| P1 | (1,1) | (2,1) | (1,0) |
| P2 | (1,1) | (3,2) | (2,1) |
Available=(1,1); total resources are (4,3). Initially only P1 fits. Finish P1: Work=(1,1)+(1,1)=(2,2). P0 now fits; finishing it gives Work=(3,2). P2 fits and returns (1,1), giving final Work=(4,3), equal to total. Thus P1,P0,P2 is a safe sequence. P1,P2,P0 also works; a safe sequence need not be unique. Do not add Max directly to Work, and do not compare only the sum of components.
5. A request can fit and still be unsafe
For the same state, P0 requests (1,0). The request is within Need=(2,2) and within Available=(1,1), so the basic bounds pass. Tentatively grant it: Available becomes (0,1), P0 Allocation=(2,0), Need=(1,2). P1 still needs (1,0) and P2 needs (2,1). No process's Need fits (0,1), so the tentative state is unsafe. An avoidance algorithm must defer this request, even though the requested resource is physically free.
Unsafe means there is no guaranteed completion order if processes exercise their maximum claims. They might request less or release early and still finish; therefore unsafe is not identical to already deadlocked. Conversely, a safe-state certificate depends on the model and accurate maximum claims; it is not a guarantee against arbitrary software bugs.
Exam method
List instance counts and define graph arrows. For a safety test, verify nonnegative Need, sum Allocation+Available to check totals, and compare vectors componentwise. Write every Work update and the final sequence. For a request, check Request≤Need and Request≤Available before simulating the allocation and running the full safety test. Never grant solely because Available is large enough.
Original practice: six single-correct MCQs
Choose exactly one option. Each question states its own required assumptions.
DL01. Each of R1 and R2 has one instance. P1 holds R1 and waits for R2; P2 holds R2 and waits for R1. Neither can release before obtaining the other. What is the state?
A. Safe because each holds one resource B. Deadlocked C. Only P1 has terminated D. Guaranteed to resolve by rescheduling alone
Answer: B
A: Both still require a resource held by the other.
B: Each waits on the other with no enabled release.
C: No termination is stated.
D: CPU scheduling cannot create the missing release.
DL02. A resource-allocation graph contains a directed cycle, but resource types may have multiple instances. What follows from the cycle alone?
A. Deadlock is certain B. Deadlock is impossible C. Further allocation and request information is needed D. Every process has terminated
Answer: C
A: Outside instances may be released and break the wait.
B: A cycle can still be part of a real deadlock.
C: With multiple instances, a cycle alone is not sufficient.
D: A graph cycle does not establish termination.
DL03. All threads acquire distinct locks in the same strict increasing global order and never request a lower lock while holding a higher one. Which necessary condition is directly prevented?
A. Mutual exclusion B. Hold-and-wait C. No preemption D. Circular wait
Answer: D
A: Locks may still be exclusive.
B: A thread may hold a lower lock while requesting a higher one.
C: Resources may still be nonpreemptible.
D: Strictly increasing order cannot form a cycle returning to its start.
DL04. Available=(1,1). Allocations of P0,P1,P2 are (1,0),(1,1),(1,1); maxima are (3,2),(2,1),(3,2). Which is a safe completion sequence?
A. P0,P1,P2 B. P2,P0,P1 C. P1,P0,P2 D. None
Answer: C
A: P0 initially needs (2,2), which does not fit (1,1).
B: P2 initially needs (2,1), which does not fit (1,1).
C: P1 needs (1,0); Work becomes (2,2), then (3,2), then (4,3).
D: The sequence P1,P0,P2 succeeds.
DL05. Available=(1,1), Allocation=(1,0),(1,1),(1,1), Max=(3,2),(2,1),(3,2) for P0,P1,P2. Should a safety-based avoidance algorithm immediately grant P0 request (1,0)?
A. Yes, because it is available B. No, the tentative state has no safe sequence C. No, it exceeds P0 maximum claim D. Yes, because every need becomes zero
Answer: B
A: Availability is necessary but not sufficient.
B: After grant Work=(0,1), while needs are (1,2),(1,0),(2,1); none fits.
C: The request is within P0 remaining need (2,2).
D: All three processes still need resources.
DL06. What does an unsafe state mean in the maximum-claim safety model?
A. All processes are already blocked forever B. No safe sequence exists under the declared remaining maximum needs C. Every process has exceeded its maximum D. A physical resource has disappeared
Answer: B
A: Unsafe is not identical to current deadlock; actual requests can be smaller.
B: This is the safety-test conclusion.
C: Unsafe allocation need not violate any individual maximum.
D: Unsafety is about completion guarantees, not lost resources.
Sources and scope
This original lesson extends the existing OS foundations in the GATE 2026 course. It maps to Section 8 of the official 2026 syllabus; it is not a claim of complete OS coverage or GATE 2027 completeness. Practice questions are original, not past-exam questions.
Sources checked 2026-10-14.
Sign in to keep your progress. Sign in