Necessary Conditions for Deadlocks
Learning Goals
- Define a deadlock and understand its impact on system performance and resource utilization.
- Identify and explain the four necessary conditions for a deadlock: Mutual Exclusion, Hold and Wait, No Preemption, and Circular Wait.
- Construct and interpret Resource-Allocation Graphs (RAG) to detect potential deadlock states.
- Differentiate between deadlock, starvation, and livelock.
What is a Deadlock?
A deadlock is a state in which every process in a set is waiting for an event (typically the release of a resource) that can only be caused by another process within the same set. In other words, the processes are stuck in a cycle of waiting — none of them can proceed, and none of them can release the resources they hold because they are blocked waiting for other resources.
Real-World Analogy: Imagine two cars approaching a narrow one-lane bridge from opposite ends. Car A crosses the bridge halfway but finds Car B coming from the other side. Both cars stop. Car A cannot proceed because Car B is blocking the way; Car B cannot proceed because Car A is blocking the way. Neither will back up. This is a deadlock — both are stuck forever.
In an operating system, the "cars" are processes, and the "bridge" is a resource (e.g., a printer, a file handle, a memory region). Just like the cars, processes hold some resources and wait for others, creating a circular chain of dependency.
System Model: A system consists of a finite number of resource types (R₁, R₂, ..., Rₘ). Each resource type Rᵢ has a certain number of identical instances. A process must request a resource before using it, and must release it when done. Under normal operation, a process follows this sequence:
- Request — The process asks for the resource. If unavailable, it must wait.
- Use — The process operates on the resource (e.g., writes to a file).
- Release — The process voluntarily gives up the resource.
Deadlocks arise when the request step cannot be satisfied because the requested resource is held by another waiting process.
Deadlock in Operating Systems — Visual Explanation
The Four Necessary Conditions (Coffman Conditions)
For a deadlock to occur, all four of the following conditions must hold simultaneously. If even one condition is absent, the system cannot be in a deadlock state. These are known as the Coffman Conditions (after E. G. Coffman, who formalized them in 1971).
Condition 1: Mutual Exclusion
At least one resource must be held in a non-sharable mode. That is, only one process at a time can use the resource. If another process requests that resource, it must wait until the resource is released.
| Aspect | Detail |
|---|---|
| Meaning | The resource cannot be shared concurrently. Only exclusive access is allowed. |
| Example | A printer allocated to Process P₁. Process P₂ cannot print until P₁ releases the printer. |
| Non-Example | A shared read-only file — multiple processes can read it simultaneously, so mutual exclusion does not apply. |
| Key Insight | If all resources were sharable, deadlocks would never occur. However, many resources (printers, tape drives, mutex locks) are inherently non-sharable. |
Condition 2: Hold and Wait
A process is holding at least one resource and is waiting to acquire additional resources that are currently held by other processes.
| Aspect | Detail |
|---|---|
| Meaning | Processes hold on to what they already have while asking for more. |
| Example | Process P₁ holds a tape drive and is waiting for a printer held by P₂. |
| Non-Example | A process that requests all resources at once at startup (and gets them all or none) does not exhibit hold-and-wait. |
| Key Insight | This condition can be broken by forcing processes to request all resources before execution begins (starvation may still occur, but deadlock is prevented). |
Condition 3: No Preemption
Resources cannot be forcibly taken away from a process. A resource can only be released voluntarily by the process that holds it, after that process has finished using it.
| Aspect | Detail |
|---|---|
| Meaning | The OS cannot snatch a resource from a process mid-operation. Only the holding process can release it. |
| Example | If Process P₁ has locked a database row, the OS cannot force P₁ to unlock it — P₁ must commit or abort its transaction. |
| Non-Example | CPU registers can be preempted by the scheduler (context switch). CPU registers are not a "resource" that is subject to no-preemption in deadlock terms. |
| Key Insight | Preemptable resources (like CPU) cannot cause deadlock. Only non-preemptable resources (like mutex locks, printers, tape drives) are problematic. |
Condition 4: Circular Wait
There exists a set of processes {P₀, P₁, ..., Pₙ} such that P₀ is waiting for a resource held by P₁, P₁ is waiting for a resource held by P₂, ..., Pₙ₋₁ is waiting for a resource held by Pₙ, and Pₙ is waiting for a resource held by P₀.
| Aspect | Detail |
|---|---|
| Meaning | The waiting forms a cycle. Each process is waiting for a process that is waiting for another, eventually looping back to the first. |
| Example | P₁ holds Resource A, waits for Resource B (held by P₂). P₂ holds Resource B, waits for Resource A (held by P₁). This is a 2-process circular wait. |
| Visualization | Think of a circular chain: P₁ → R₂ → P₂ → R₁ → P₁ (where → means "waiting for" or "holds"). |
| Key Insight | Circular wait is the only condition that implies a cycle. The other three are "environmental" conditions; circular wait is the topological condition that directly signals deadlock. |
Important: All four conditions must be present. For example, you can have Mutual Exclusion, Hold and Wait, and No Preemption — but if there is no Circular Wait, no deadlock exists. Resources may be tied up, but processes aren't waiting on each other in a cycle, so the system can still make progress.
Visualizing the Circular Wait with a Resource-Allocation Graph
The diagram below shows a classic two-process deadlock using a Resource-Allocation Graph (RAG). Process P₁ holds Resource R₁ and requests R₂, while Process P₂ holds R₂ and requests R₁. The cycle P₁ → R₂ → P₂ → R₁ → P₁ is clearly visible.
Each resource rectangle represents a single-instance resource. The cycle P₁ → R₂ → P₂ → R₁ → P₁ satisfies the Circular Wait condition — and since all four conditions hold, deadlock exists.
How to Construct and Analyze a Resource-Allocation Graph
- 1Step 1
List every active process (P₁, P₂, ..., Pₙ) and every resource type (R₁, R₂, ..., Rₘ). For each resource type, count the number of identical instances available (e.g., R₁ has 2 identical printers).
- 2Step 2
For each process, draw a circle (○). For each resource type, draw a rectangle (▭). Inside the rectangle, place dots (●) equal to the number of instances of that resource type.
- 3Step 3
If a resource instance is allocated to a process, draw a directed arrow from the resource dot to the process (R → P). This is called an assignment edge.
- 4Step 4
If a process is waiting for a resource, draw a directed arrow from the process to the resource rectangle (P → R). This is called a request edge.
- 5Step 5
Examine the graph for cycles (closed loops). If the graph has no cycles, no deadlock exists. If the graph contains a cycle: (a) For single-instance resource types — a cycle means deadlock. (b) For multi-instance resource types — a cycle means deadlock is possible but not certain. You must check if there are other free instances that can break the cycle.
- 6Step 6
For multi-instance resources, use the reduction method: repeatedly remove (reduce) any process that can finish (i.e., whose resource requests can all be satisfied). If you can reduce all processes, no deadlock exists. If some processes remain unreduced, they are deadlocked.
Deadlock vs. Starvation vs. Livelock
These three terms describe different kinds of "stuck" processes, but they have fundamentally different mechanisms.
| Aspect | Deadlock | Starvation | Livelock |
|---|---|---|---|
| Process State | Processes are blocked (waiting). | Process is runnable but never scheduled. | Processes are running but making no progress. |
| Root Cause | Circular dependency of resources. | Unfair scheduling policy (e.g., low priority process never gets CPU). | Processes keep yielding to each other without advancing. |
| Resource Utilization | Resources are tied up and unusable. | Resources may be idle because the starved process is holding them while waiting for CPU. | Resources are actively used but wasted (no useful work done). |
| Can it resolve on its own? | No — deadlock is permanent unless external action (OS intervention) is taken. | Possibly — if system load decreases, the starved process may eventually run. | No — processes keep reacting to each other, never escaping the loop. |
| Real-world Analogy | Two cars blocking each other on a narrow bridge. | A slow car in the right lane that never gets a gap to merge left. | Two people trying to pass each other in a hallway — both keep stepping to the same side. |
Key Distinction: In deadlock, nothing is happening — processes are blocked and waiting. In livelock, something is happening — processes are executing instructions — but no useful progress is being made.
Examples and Case Studies
Example 1: Two-Process Deadlock (Minimal Case)
- System has: 1 printer (R₁), 1 tape drive (R₂)
- Process P₁ holds printer (R₁), requests tape drive (R₂)
- Process P₂ holds tape drive (R₂), requests printer (R₁)
- Result: Both are deadlocked. All four conditions are satisfied.
Example 2: Three-Process Deadlock (Chain)
- P₁ holds R₁, requests R₂
- P₂ holds R₂, requests R₃
- P₃ holds R₃, requests R₁
- Result: Circular chain from P₁ → R₂ → P₂ → R₃ → P₃ → R₁ → P₁. Deadlock.
Example 3: Database Transaction Deadlock
- Transaction T₁ locks Row A, waits for Row B
- Transaction T₂ locks Row B, waits for Row A
- Result: Classic database deadlock. DBMS typically detects this and aborts one transaction (breaking the cycle).
Example 4: Spooling and Deadlock — A Subtle Case
- A print spooler accepts print jobs into a disk queue and prints them one by one.
- If the spooler itself runs out of disk space for new spool entries, and it is waiting for a printer to become free, while the printer is waiting for the spooler to provide a job...
- Result: This is actually a different kind of bottleneck (resource exhaustion), not a true circular-wait deadlock, because the spooler can abort/reject new jobs. True deadlock requires the circular-wait condition.
Example 5: Single-Resource Deadlock Scenario
- System has: 1 resource instance (R₁) — e.g., a single printer.
- Process P₁ holds R₁ and is waiting for R₂ (some other resource held by P₂).
- Process P₂ holds R₂ and is waiting for R₁.
- Result: Deadlock! Even with a single-instance resource, deadlock occurs when processes hold different resources and wait for each other's. The key insight: the single resource alone doesn't cause deadlock — it's the circular dependency between resources.
Example 6: RAG with a Cycle but NO Deadlock (Multi-Instance Resource)
- System has: 1 resource type R₁ with 2 instances (two identical printers).
- Process P₁ holds one instance of R₁ and requests another instance of R₁.
- Process P₂ holds the other instance of R₁ and requests another instance of R₁.
Notice that both processes request the same resource type R₁. There is a cycle in the graph, but no deadlock exists! Why? Because neither process is waiting for a resource held by the other. They are both waiting for additional instances of the same resource. If P₁ finishes first, it releases its instance, and P₂ can acquire it.
Example 7: Max n for Deadlock-Free (Recurring Numerical Pattern)
- Problem [2019, 2023]: System contains R units of a resource. There are n processes, each requiring up to K units. What is max n for deadlock-free operation?
- Logic: Worst case for deadlock = each process holds (K−1) units and waits for the last one. If n × (K−1) < R, at least one process can get its Kth unit and finish. After finishing, it releases K units, allowing others to proceed.
- Formula:
n_max = floor((R − 1) / (K − 1)) - Example A [2023]: R = 6 tape drives, each process needs K = 2. n_max = (6 − 1) / (2 − 1) = 5. So max 5 processes — answer to 2023 PYQ.
- Example B [2019]: R = 6 units, each process needs K = 3. n_max = (6 − 1) / (3 − 1) = 5 / 2 = 2.5 → floor = 2. So max 2 processes — answer to 2019 14-mark PYQ.
Knowledge Check
Which of the following is NOT one of the four necessary conditions for deadlock?