Operating System
Deadlocks
Deadlock is a situation in an Operating System where two or more processes wait indefinitely for resources held by each other. Since none of the processes can proceed, the entire system or a part of it becomes stuck.
Deadlocks are one of the most important concepts in Operating Systems because they directly affect system performance, multitasking, and resource management.
Real Life Example of Deadlock
Imagine two cars meeting on a narrow bridge. Both drivers wait for the other to move first. Since neither moves backward, traffic becomes blocked.
Deadlock Analogy
Both cars wait forever → Deadlock
Necessary Conditions for Deadlock
Deadlock occurs only if all four conditions are true simultaneously.
1. Mutual Exclusion
Only one process can use a resource at a time.
2. Hold and Wait
Process holds one resource while waiting for another.
3. No Preemption
Resources cannot be forcefully removed.
4. Circular Wait
Processes form a circular chain waiting for resources.
Resource Allocation Graph (RAG)
A Resource Allocation Graph visually represents processes and resources in the system.
- Circle → Process
- Rectangle → Resource
- Arrow from Process to Resource → Request
- Arrow from Resource to Process → Allocation
Resource Allocation Graph
Deadlock Prevention
Deadlock prevention ensures that at least one of the four necessary conditions never occurs.
| Condition | Prevention Method |
|---|---|
| Mutual Exclusion | Make resources sharable where possible |
| Hold and Wait | Request all resources at once |
| No Preemption | Force release resources if needed |
| Circular Wait | Assign resource ordering |
Deadlock Avoidance
Deadlock avoidance dynamically checks resource allocation to ensure the system never enters an unsafe state.
- Requires advance information about resource needs
- Uses Safe State concept
- Most famous algorithm: Banker’s Algorithm
Safe State
Processes can complete execution safely.
Unsafe State
System may eventually enter deadlock.
Banker’s Algorithm
Banker’s Algorithm is used for deadlock avoidance. It checks whether resource allocation leaves the system in a safe state.
- Developed by Edsger Dijkstra
- Based on maximum resource demand
- Allocates resources only if system remains safe
Deadlock Detection
Instead of preventing deadlocks, some systems allow deadlocks to occur and later detect them.
- System periodically checks for cycles
- Used when deadlocks are rare
- Requires additional overhead
Deadlock Recovery
Once deadlock is detected, the system must recover from it.
Process Termination
- Abort all deadlocked processes
- Abort one process at a time
Resource Preemption
- Temporarily remove resources
- Rollback process state
Prevention vs Avoidance
| Prevention | Avoidance |
|---|---|
| Blocks one deadlock condition | Checks safe state dynamically |
| Simpler approach | More complex |
| Lower resource utilization | Better resource utilization |
Important Exam Points
- All four conditions are necessary for deadlock.
- Banker’s Algorithm is the most important avoidance algorithm.
- Resource Allocation Graph is frequently asked in exams.
- Difference between prevention and avoidance is important.
Summary
Deadlocks occur when processes wait indefinitely for resources held by each other. Operating Systems use prevention, avoidance, detection, and recovery techniques to manage deadlocks. Proper resource allocation and synchronization help ensure smooth and efficient system execution.
Ready to test your Chapter V: Deadlock knowledge?
Chapter V: Deadlock
Test your understanding of deadlock conditions, Resource Allocation Graphs, Banker's Algorithm, and deadlock handling strategies.