Deadlock in Operating System: System Model, Conditions & Characterization
Imagine Process P1 already has Resource R1 and is waiting for Resource R2. At the same time, Process P2 already has R2 and is waiting for R1. Neither process wants to release the resource it already holds, and neither can continue until it receives the other resource. Both processes can now remain blocked forever. This situation is called a deadlock in Operating System.
Deadlock becomes much easier when you study it in the correct order: first understand the deadlock system model, then the four necessary conditions of deadlock, and finally deadlock characterization using a Resource Allocation Graph. This chapter explains all three with simple examples and visual diagrams.
What Is Deadlock in Operating System?
A deadlock in Operating System occurs when two or more processes cannot continue because each process is waiting for something that another blocked process is holding.
Deadlock is a condition in which a group of processes waits forever because each process is waiting for a resource held by another process in the same group.
Why Does Deadlock Happen?
The basic problem is not simply that a process is waiting. Waiting is normal in an operating system.
Deadlock becomes dangerous when processes form a dependency that nobody inside the group can break.
Simple Deadlock Example With Two Processes
Suppose the system has two non-shareable resources: R1 and R2.
Needs R2
Needs R1
P1 cannot continue until P2 releases R2. But P2 cannot continue until P1 releases R1.
Neither process can reach the point where it releases its resource. So both can remain blocked indefinitely.
Deadlock System Model in Operating System
To understand deadlock formally, we first need a system model for resources and processes.
Suppose an operating system has processes:
P1, P2, P3, ... Pn
and resource types:
R1, R2, R3, ... Rm
Each resource type can have one or more instances.
What Can Be a Resource in a Deadlock?
A resource is anything limited that a process or thread may need to continue.
Resource Usage Sequence: Request, Use and Release
A process normally interacts with a reusable resource in three basic stages.
If the requested resource is available, the system may allocate it.
If the resource is not available, the process may have to wait.
Shareable vs Non-Shareable Resources
Shareable Resource
Several processes may be able to use the resource without exclusive ownership.
A read-only file is a simple example where several processes can often read the same data.
Non-Shareable Resource
Only one process or thread may use an instance at a particular time.
Locks and exclusively controlled devices are common deadlock examples.
Deadlock is especially important when resources cannot simply be shared by all requesting processes at the same time.
Four Necessary Conditions for Deadlock in Operating System
Deadlock is associated with four important conditions. They are often called the Coffman conditions or the four necessary conditions of deadlock.
All four must be present for deadlock to occur.
Mutual Exclusion
At least one required resource is non-shareable. Only one process can use a particular resource instance at a time.
If P1 is using the resource, another process must wait for it.
Simple idea:One resource → one owner at a time.
Hold and Wait
A process is holding at least one resource while waiting to obtain another resource.
Example: P1 holds R1 but waits for R2.
Simple idea:Keep what you have while asking for more.
No Preemption
A resource cannot simply be forcibly taken away from its current owner whenever another process wants it.
The holding process releases it according to the resource-management rules, normally after completing the relevant work.
Simple idea:OS cannot just snatch the resource away safely.
Circular Wait
A circular chain of waiting processes exists.
P1 waits for something held by P2, P2 waits for something held by P3, and eventually another process waits for something held by P1.
Simple idea:Everyone in the circle waits for the next process.
How the Four Deadlock Conditions Work Together
Four Deadlock Conditions in One Example
Again consider:
P1 holds R1 and waits for R2.
P2 holds R2 and waits for R1.
| Condition | How It Appears in the Example |
|---|---|
| Mutual Exclusion | R1 and R2 can each be used by only one process at that moment. |
| Hold and Wait | P1 holds R1 while waiting for R2; P2 holds R2 while waiting for R1. |
| No Preemption | The resources are not simply taken away from P1 or P2. |
| Circular Wait | P1 waits for P2, while P2 waits for P1. |
Resource Allocation Graph in Operating System
Deadlock can be represented visually using a Resource Allocation Graph, commonly written as RAG.
A Resource Allocation Graph is a directed graph that represents processes, resource types, resource requests and resource assignments in a system.
It contains two main types of vertices:
- Process vertices
- Resource-type vertices
Process and Resource Nodes in a Resource Allocation Graph
Process Node
A process is commonly shown as a circle.
Resource Node
A resource type is commonly shown as a rectangle or square.
Multiple dots inside it may represent multiple instances.
Request Edge and Assignment Edge in RAG
Request Edge
P1 → R1
Means Process P1 has requested an instance of resource R1 and is waiting for it.
Assignment Edge
R1 → P1
Means an instance of R1 has already been allocated to P1.
Deadlock Characterization Using Resource Allocation Graph
The most important question is: What does a cycle in a Resource Allocation Graph mean?
Single-Instance Resource Allocation Graph Example
Suppose R1 and R2 each have only one instance.
Conceptually the cycle is:
P1 → R2 → P2 → R1 → P1
P1 waits for R2, which belongs to P2. P2 waits for R1, which belongs to P1.
Because every relevant resource has only one instance, neither process can obtain what it needs.
Why a Cycle Does Not Always Mean Deadlock With Multiple Instances
This is one of the most important deadlock characterization points.
Single Instance
R1 = 1 instance
R2 = 1 instance
If P1 and P2 form the circular dependency described earlier, nobody has another available instance to break the cycle.
Cycle → DeadlockMultiple Instances
Suppose R1 has two instances.
P1 may hold one R1 and wait for R2, while P2 holds R2 and requests R1.
If another R1 instance is still available, P2 can receive it, finish, release R2, and then P1 can continue.
Cycle exists, but deadlock may not exist.No cycle → no deadlock.
Cycle + single instance per resource type → deadlock.
Cycle + multiple instances → deadlock may or may not exist.
What Is a Wait-for Graph?
A Wait-for Graph is another way to represent waiting relationships.
Unlike a Resource Allocation Graph, it contains only process nodes.
An edge:
Pi → Pj
means Pi is waiting for a resource currently held by Pj.
If these relationships form:
P1 → P2 → P3 → P1
then a circular waiting dependency exists.
Resource Allocation Graph vs Wait-for Graph
| Point | Resource Allocation Graph | Wait-for Graph |
|---|---|---|
| Nodes | Processes and resource types | Only processes |
| Shows | Requests and assignments | Which process waits for which process |
| Edge Example | P1 → R1 or R1 → P1 | P1 → P2 |
| Main Use | Visualize resource allocation and deadlock relationships | Simplify process dependency analysis |
Deadlock Example With Two Locks
Deadlock is very common to explain using threads and mutex locks.
Deadlock Logic With Locks in Simple Form
Imagine two threads following these orders:
Thread T1
1. Lock A
2. Lock B
3. Do work
4. Unlock B
5. Unlock A
Thread T2
1. Lock B
2. Lock A
3. Do work
4. Unlock A
5. Unlock B
If T1 gets A first and T2 gets B first, both may wait forever for the other's lock.
The opposite lock order creates the circular wait.
Deadlock vs Starvation vs Livelock
These terms are related to lack of useful progress, but they are not the same.
Deadlock vs Starvation
| Point | Deadlock | Starvation |
|---|---|---|
| Main Problem | Circular resource dependency | Process repeatedly fails to get service |
| Other Processes | Deadlocked group blocks each other | Other processes may continue normally |
| Progress | Deadlocked processes cannot progress | Starved process may eventually progress if conditions change |
| Common Example | Two processes waiting for each other's locks | Low-priority process repeatedly delayed |
How to Characterize a Possible Deadlock Step by Step
Which processes or threads are involved?
How many instances of each resource exist?
Which process currently holds each resource?
What is each blocked process waiting for?
Add request and assignment edges.
No cycle means no deadlock.
A cycle with single-instance resource types proves deadlock, while multiple instances require more analysis.
Easy Trick to Remember the Four Deadlock Conditions
M = Mutual Exclusion
H = Hold and Wait
N = No Preemption
C = Circular Wait
Situations That Are Not Automatically Deadlock
What Happens After Deadlock Is Characterized?
Once we understand how deadlock occurs, operating systems can use different strategies to deal with it.
Common Mistakes Students Make About Deadlock
Normal resource waiting is common and may finish normally.
Deadlock requires all four necessary conditions to be present.
Process → Resource means request. Resource → Process means assignment.
That conclusion is safe for the relevant single-instance case, not automatically for multiple-instance resources.
Here it refers to the relevant resource not being forcibly taken away from the holding process.
Deadlock is a circular dependency problem; starvation is prolonged denial of service.
They describe conditions required for deadlock to arise, not proof that every current allocation state is deadlocked.
Deadlock in Operating System: Complete Flow
Deadlock in Operating System Exam Preparation
For a 2-Mark Question
Answer: Deadlock is a state in which a group of processes remains permanently blocked because every process is waiting for a resource held by another process in the same group.
Four Conditions – Short Answer
- Mutual Exclusion
- Hold and Wait
- No Preemption
- Circular Wait
For a 5-Mark Question
Write:
- definition of deadlock
- system model
- resource request-use-release sequence
- four necessary conditions
- simple two-process example
For a 10-Mark Question
Explain in this order:
- meaning of Deadlock in Operating System
- deadlock system model
- resource types and resource instances
- request, use and release sequence
- Mutual Exclusion
- Hold and Wait
- No Preemption
- Circular Wait
- Resource Allocation Graph
- request and assignment edges
- cycle characterization
- single-instance vs multiple-instance case
- simple deadlock example
Important Exam Diagram
Draw:
P1 → R2 → P2 → R1 → P1
Then explain why a cycle proves deadlock when each resource type involved has only one instance.
Deadlock Practice Questions
Deadlock Quick Revision
Frequently Asked Questions About Deadlock in Operating System
What is deadlock in Operating System?
Deadlock is a situation in which a group of processes remains blocked because each process is waiting for a resource or event that depends on another blocked process in the same group.
What are the four necessary conditions for deadlock?
The four necessary conditions are Mutual Exclusion, Hold and Wait, No Preemption and Circular Wait.
What is Mutual Exclusion in deadlock?
Mutual Exclusion means at least one required resource cannot be shared freely and can be used by only one process at a time.
What is Hold and Wait condition?
Hold and Wait means a process is holding one or more resources while waiting for additional resources.
What is No Preemption condition?
No Preemption means a relevant held resource cannot simply be forcibly removed from the process that owns it; it must be released according to the resource rules.
What is Circular Wait?
Circular Wait means a circular chain exists in which each process waits for a resource held by the next process in the chain.
What is the system model for deadlock?
The deadlock system model considers a set of processes competing for a set of resource types, where each resource type can contain one or more instances. Processes request, use and release resource instances.
What is Resource Allocation Graph in OS?
A Resource Allocation Graph is a directed graph that represents processes, resource types, resource requests and resource assignments.
What is a request edge in Resource Allocation Graph?
A request edge goes from a process to a resource type and shows that the process is requesting an instance of that resource.
What is an assignment edge in Resource Allocation Graph?
An assignment edge goes from a resource instance or resource type representation to a process and shows that the resource has been allocated to the process.
Does a cycle in Resource Allocation Graph always mean deadlock?
No. If every resource type involved has only one instance, a cycle indicates deadlock. When resource types have multiple instances, a cycle indicates that deadlock is possible but does not alone prove that deadlock exists.
What happens if a Resource Allocation Graph has no cycle?
If the Resource Allocation Graph has no cycle, the system is not deadlocked.
What is a Wait-for Graph?
A Wait-for Graph contains process nodes only. An edge from Pi to Pj means Pi is waiting for a resource held by Pj.
What is the difference between deadlock and starvation?
Deadlock involves a circular dependency that stops all processes in the deadlocked group from progressing. Starvation means one process waits for a very long time because other processes repeatedly receive the required service.
Is every blocked process deadlocked?
No. A blocked process may simply be waiting for I/O, a resource or an event that will later become available. Deadlock requires a dependency that prevents the involved group from making progress.
Can threads also enter deadlock?
Yes. Threads can deadlock when they hold locks or other resources and form circular waiting dependencies.
How can deadlock be handled?
Major approaches include deadlock prevention, avoidance, detection and recovery. These techniques are studied after understanding deadlock conditions and characterization.
Conclusion
Deadlock in Operating System becomes much easier when you stop treating it as just a definition and follow the full resource story. A process requests resources, receives some of them, keeps them while asking for more, and may become blocked if another process owns what it needs.
Deadlock can arise when the four necessary conditions are present: Mutual Exclusion, Hold and Wait, No Preemption and Circular Wait. Remember them using M-H-N-C.
Deadlock characterization becomes visual through the Resource Allocation Graph. A process-to-resource edge represents a request, while a resource-to-process edge represents an assignment.
The most important cycle rule is: no cycle means no deadlock; a cycle with single-instance resource types means deadlock; with multiple resource instances, a cycle alone is not enough to prove deadlock.
Once these concepts are clear, the next deadlock topics— prevention, avoidance, Banker's Algorithm, detection and recovery— become much easier to understand.
