1. Introduction
So far, we have studied two proactive approaches to deadlock handling:
Deadlock Prevention → Prevent deadlock by breaking one of the necessary conditions.
Deadlock Avoidance → Dynamically avoid unsafe states.
Both approaches attempt to stop deadlocks before they occur.
Deadlock Detection takes a fundamentally different approach.
Instead of restricting resource allocation or continuously checking for safe states, the operating system allows resources to be allocated freely and periodically checks whether a deadlock has occurred.
The philosophy behind detection is:
"Allow deadlocks to occur, but be able to identify them accurately and recover from them."
This approach is particularly useful in systems where deadlocks are rare and the overhead of prevention or avoidance would be unnecessarily expensive.
2. Core Idea
Deadlock detection follows a simple strategy:
Allocate Resources Freely
↓
Processes Execute Normally
↓
Periodically Check System State
↓
Deadlock Found ?
↓ ↓
No Yes
↓ ↓
Continue Recover
Unlike prevention and avoidance:
Deadlock May Occur
The operating system accepts this possibility and focuses on detecting deadlocks after they happen.
3. Why Use Deadlock Detection?
In many practical systems:
Deadlocks occur infrequently.
Resource usage patterns are unpredictable.
Maximum future resource requirements are unknown.
Avoidance algorithms are expensive.
In such environments:
Detection
+
Recovery
may be more efficient than continuously preventing deadlocks.
Example
Consider a large database server.
Thousands of transactions execute every second.
Most complete normally.
Deadlocks may occur only occasionally.
Running expensive avoidance checks on every request would be inefficient.
Instead:
Allow Execution
and periodically:
Detect Deadlocks
if they arise.
4. Detection Approaches
The detection technique depends on the resource model being used.
Two major cases exist:
Case 1
Single Instance
Per Resource Type
Example:
One printer
One scanner
One tape drive
Use:
Resource Allocation Graph
(RAG)
Case 2
Multiple Instances
Per Resource Type
Example:
Five printers
Ten memory blocks
Twenty database connections
Use:
Deadlock Detection Algorithm
which is similar to Banker's safety algorithm.
5. Detection Using Resource Allocation Graph (Single Instance)
When every resource type has only one instance:
Cycle Detection
is sufficient.
Rule
A deadlock exists:
If And Only If
A Cycle Exists
in the Resource Allocation Graph.
5.1 Example
Suppose:
P1 Holds R1
and requests:
R2
while:
P2 Holds R2
and requests:
R1
The graph becomes:
P1 → R2 → P2 → R1 → P1
This forms a cycle.
Therefore:
Deadlock Exists
Why?
Each process waits for a resource held by another process in the cycle.
No process can proceed.
No resource can be released.
System progress stops completely.
5.2 No Cycle
Suppose:
P1 → R1
P2 → R2
with no circular dependency.
Then:
No Deadlock
because at least one process can eventually continue execution.
6. Detection with Multiple Resource Instances
When multiple instances of resources exist:
Cycle Detection Alone
Is Not Sufficient
A cycle may exist without deadlock.
Therefore, a more sophisticated algorithm is required.
The operating system uses a deadlock detection algorithm that resembles the safety algorithm used in Banker’s Algorithm.
7. Data Structures Used
The algorithm maintains three important structures.
7.1 Available
Available[j]
Number of currently available instances of resource type j.
Example:
Printer = 2
Scanner = 1
7.2 Allocation Matrix
Allocation[i][j]
Resources currently allocated to process i.
Example:
P1 Holds:
1 Printer
2 Scanners
7.3 Request Matrix
Request[i][j]
Additional resources process i still needs.
Example:
P2 Requests:
1 Printer
These structures describe the complete state of resource allocation.
8. Deadlock Detection Algorithm
The algorithm attempts to determine whether all processes can eventually complete.
Step 1: Initialization
Set:
Work = Available
and for every process:
Finish[i] = false
Initially, assume no process has completed.
Step 2: Search for Executable Process
Find a process satisfying:
Finish[i] = false
and:
Request[i] ≤ Work
Meaning:
The currently available resources are enough for that process to proceed.
Step 3: Simulate Completion
Assume the process finishes.
Release its resources:
Work = Work + Allocation[i]
Mark:
Finish[i] = true
Step 4: Repeat
Continue searching for more processes that can complete.
Step 5: Final Decision
After no further process can be found:
If
Finish[i] = true
for every process:
No Deadlock
Otherwise
Processes with:
Finish[i] = false
are deadlocked.
9. Intuition Behind the Algorithm
The algorithm essentially asks:
Can We Find
A Completion Sequence?
If a completion sequence exists:
System Not Deadlocked
If no completion sequence exists:
Deadlock Exists
This is conceptually similar to searching for a safe sequence in Banker’s Algorithm.
10. Example Concept
Suppose:
Processes:
P1, P2, P3
Current state:
P1 waits
P2 waits
P3 waits
None can obtain required resources.
The detection algorithm finds:
No Process Can Proceed
Therefore:
Deadlock Detected
11. When Should Detection Run?
Running the detection algorithm continuously would be expensive.
The operating system must decide:
When To Check?
Several strategies are used.
11.1 Periodic Detection
Run every fixed interval.
Example:
Every 30 Seconds
11.2 Resource Utilization Trigger
Run when:
CPU Utilization Drops
unexpectedly.
A sudden drop may indicate blocked processes.
11.3 Long Waiting Time
Run when processes wait unusually long.
Example:
Process Waiting
> Threshold
11.4 On Demand
Administrator explicitly requests detection.
12. Advantages of Deadlock Detection
12.1 No Resource Allocation Restrictions
Processes request resources freely.
Maximum Flexibility
12.2 Better Resource Utilization
Resources are allocated whenever available.
Higher Utilization
than prevention.
12.3 No Need for Maximum Resource Claims
Unlike avoidance:
Future Resource Requirements
Not Needed
12.4 Suitable for Dynamic Systems
Works well when process behavior is unpredictable.
13. Disadvantages of Deadlock Detection
13.1 Detection Overhead
The OS must periodically analyze:
Processes
Resources
Requests
This consumes CPU time.
13.2 Deadlock Has Already Occurred
When detection finds a deadlock:
System Already Stuck
Some work may already be affected.
13.3 Recovery Required
Detection alone is not enough.
After finding deadlock:
Recovery Necessary
The OS must break the deadlock.
13.4 Possible Performance Impact
Frequent detection runs can become expensive in large systems.
14. Comparison with Prevention and Avoidance
| Feature | Prevention | Avoidance | Detection |
|---|---|---|---|
| Strategy | Break conditions | Avoid unsafe states | Detect after occurrence |
| Deadlock Possible? | No | No | Yes |
| Resource Utilization | Low | Medium | High |
| Flexibility | Low | Medium | High |
| Runtime Overhead | Low | High | Medium |
| Requires Future Knowledge | No | Yes | No |
Key Observation
Prevention → Restrict
Avoidance → Analyze
Detection → Observe
15. Real-World Analogy
Consider city traffic.
Prevention
Road rules prohibit certain movements entirely.
No Dangerous Pattern Allowed
Avoidance
Traffic controller predicts congestion and redirects vehicles.
Avoid Traffic Jam
Detection
Vehicles move freely.
If a traffic jam forms:
Detect Congestion
and then:
Take Corrective Action
Deadlock detection follows this third approach.