1. Introduction
In a multiprogramming operating system, multiple processes execute concurrently and compete for a limited set of system resources such as:
CPU
Main Memory
Files
Printers
Disk Drives
I/O Devices
Network Connections
Efficient resource sharing is one of the primary responsibilities of the operating system. However, under certain circumstances, processes may become permanently blocked while waiting for resources held by other processes.
When such a situation occurs, the system may enter a state where progress becomes impossible.
This condition is known as a Deadlock.
Deadlocks are among the most important and challenging problems in operating systems because they can cause applications, services, or even entire systems to become unresponsive.
Formally:
A deadlock is a situation in which a group of processes are permanently blocked because each process is waiting for a resource that is currently held by another process in the same group.
Understanding deadlocks is essential because operating systems must either:
Prevent them
Avoid them
Detect and recover from them
2. Definition
A deadlock can be defined as:
A state in which a set of processes are unable to proceed because each process is waiting for one or more resources held by another process within the set.
In a deadlock:
Processes Continue Existing
but:
No Process Makes Progress
The processes are not terminated.
The resources are not released.
The waiting continues indefinitely.
As a result:
System Progress Stops
for the affected processes.
3. Basic Example
Consider two processes:
Process P1
and
Process P2
and two resources:
Resource A
Resource B
Step 1
P1 acquires Resource A.
P1 Holds A
Step 2
P2 acquires Resource B.
P2 Holds B
Step 3
P1 requests Resource B.
P1 Waiting For B
Step 4
P2 requests Resource A.
P2 Waiting For A
Current situation:
P1 Holds A
↓
Waiting For B
P2 Holds B
↓
Waiting For A
Neither process can continue.
Neither process can release its resource.
Result:
Deadlock
4. Conceptual Visualization
The dependency relationship can be represented as:
P1 → Waiting For B
P2 → Waiting For A
while:
A Held By P1
B Held By P2
This creates:
Circular Dependency
which prevents progress.
A more complete representation:
P1
↓
Needs B
↓
P2
↓
Needs A
↓
P1
The cycle repeats forever.
5. Key Characteristics of Deadlock
Deadlocks exhibit several important characteristics.
5.1 Processes Are Blocked
Every process involved is waiting.
Example:
P1 Waiting
P2 Waiting
P3 Waiting
No process is executing useful work.
5.2 Resources Are Held
Processes already possess resources.
Example:
P1 Holds Resource R1
P2 Holds Resource R2
These resources remain unavailable to others.
5.3 No Progress Occurs
The operating system cannot advance the affected processes.
Waiting Continues Forever
unless external action is taken.
5.4 Resources Are Not Released
Because processes are blocked:
Resources Remain Locked
which may affect other processes as well.
5.5 Indefinite Duration
Unlike normal waiting:
Deadlock Has No Natural End
The processes remain stuck forever.
6. Important Terminology
Several concepts are essential for understanding deadlocks.
6.1 Resource
A resource is any entity required by a process to perform its work.
Examples:
CPU Time
Main Memory
Files
Printers
Disk Drives
Network Sockets
Semaphores
Database Locks
Resources are generally classified as:
Reusable Resources
Can be used repeatedly.
Examples:
Printer
Memory
File
Consumable Resources
Destroyed after use.
Examples:
Messages
Signals
Packets
6.2 Process State in Deadlock
A process involved in a deadlock usually satisfies both conditions:
Holding Resources
Already Owns Resource
Waiting for More Resources
Requests Additional Resource
Example:
P1 Holds A
P1 Waiting For B
6.3 Waiting Chain
A waiting chain is a sequence of dependencies among processes.
Example:
P1 Waiting For P2
P2 Waiting For P3
P3 Waiting For P4
If the chain eventually returns to the starting process:
P4 Waiting For P1
then a cycle exists.
6.4 Circular Dependency
A circular dependency occurs when:
P1 → P2 → P3 → ... → P1
This is the core structure underlying most deadlocks.
7. Real-World Analogy
Consider four cars approaching a four-way intersection.
Each car enters part of the intersection and waits for another car to move.
Situation:
Car A Waiting For B
Car B Waiting For C
Car C Waiting For D
Car D Waiting For A
Since every car is waiting:
Nobody Moves
Result:
Traffic Deadlock
The situation remains unchanged until external intervention occurs.
This is exactly analogous to a process deadlock.
8. Deadlock vs Normal Waiting
Not all waiting is a deadlock.
A process frequently waits for resources during normal execution.
Examples:
Waiting for I/O completion
Waiting for network response
Waiting for user input
These are temporary situations.
The key differences are:
| Feature | Normal Waiting | Deadlock |
|---|---|---|
| Duration | Temporary | Indefinite |
| Resource Availability | Eventually Available | Never Available |
| System Progress | Continues | Stops |
| Cause | Resource Delay | Circular Dependency |
| Resolution | Automatic | Requires Intervention |
Example of Normal Waiting
Process Requests Printer
Printer finishes current job.
Printer Becomes Available
Process proceeds.
No deadlock exists.
Example of Deadlock
P1 Waiting For P2
P2 Waiting For P1
Neither can proceed.
Deadlock exists.
9. Key Insight
The most important observation is:
Deadlock is not simply waiting for a resource.
Processes frequently wait during normal execution.
Deadlock occurs only when:
Circular Waiting
+
No Possibility Of Progress
exist simultaneously.
Therefore:
All Deadlocks Involve Waiting
But Not All Waiting Is Deadlock
This distinction is extremely important in exams and interviews.
10. Why Deadlocks Are Dangerous
Deadlocks can have severe consequences.
10.1 Resource Wastage
Resources remain allocated but unused.
Example:
Memory Locked
Files Locked
Devices Locked
Other processes cannot use them.
10.2 Processes Never Complete
Affected processes remain blocked forever.
Execution Never Finishes
10.3 Reduced System Performance
Resources become unavailable.
This decreases:
Throughput
CPU Utilization
Resource Utilization
10.4 Application Freezes
Users may experience:
Application Not Responding
errors.
10.5 System Crashes
In severe cases:
Entire System May Freeze
requiring administrator intervention.
10.6 Difficult Debugging
Deadlocks often involve:
Multiple processes
Multiple resources
Complex timing conditions
Therefore:
Deadlocks Are Difficult To Reproduce
and diagnose.
11. Conditions for Deadlock (Preview)
A deadlock does not occur randomly.
For a deadlock to exist, four specific conditions must hold simultaneously.
These are known as the Coffman Conditions.
11.1 Mutual Exclusion
At least one resource must be non-shareable.
Example:
Printer
can only be used by one process at a time.
11.2 Hold and Wait
A process holds resources while requesting additional resources.
Example:
Hold A
Wait For B
11.3 No Preemption
Resources cannot be forcibly taken away.
Example:
OS Cannot Remove Printer
from a process.
11.4 Circular Wait
A circular dependency exists.
Example:
P1 → P2 → P3 → P1
Critical Observation
Deadlock occurs only when:
Mutual Exclusion
+
Hold and Wait
+
No Preemption
+
Circular Wait
are all present simultaneously.
Removing even one condition prevents deadlock.
These conditions form the foundation for:
Deadlock Prevention
Deadlock Avoidance
Deadlock Detection
Deadlock Recovery
which are studied in subsequent topics.