Deadlocks in OS: Conditions, Prevention, Banker's Algorithm & Examples
What is a Deadlock?
A deadlock is a situation where a set of processes are blocked because each process is holding a resource and waiting for a resource held by another process in the set. None of the processes can proceed.
Classic Example: Two processes P1 and P2, two resources R1 and R2:
- P1 holds R1, waiting for R2
- P2 holds R2, waiting for R1
- Neither can proceed -> deadlock
Necessary Conditions for Deadlock
All four conditions must hold simultaneously for a deadlock to occur (Coffman conditions):
| Condition |
Description |
| Mutual Exclusion |
At least one resource must be held in a non-shareable mode. Only one process can use the resource at a time. |
| Hold and Wait |
A process must be holding at least one resource and waiting to acquire additional resources held by other processes. |
| No Preemption |
Resources cannot be forcibly taken from a process. A process must voluntarily release resources. |
| Circular Wait |
A circular chain of processes exists where each process holds a resource needed by the next process in the chain. |
Resource Allocation Graph
A Resource Allocation Graph (RAG) is used to detect deadlocks:
- Nodes: Processes (circles) and Resources (rectangles)
- Request Edge: P -> R (process P is requesting resource R)
- Assignment Edge: R -> P (resource R is assigned to process P)
- Deadlock Detection: If the graph contains a cycle, there may be a deadlock. If each resource has only one instance, a cycle means deadlock. If resources have multiple instances, a cycle may or may not mean deadlock.
Deadlock Prevention
Prevent deadlock by ensuring at least one of the four necessary conditions cannot hold:
- Eliminate Mutual Exclusion: Make resources shareable (not always possible - e.g., printers must be exclusive)
- Eliminate Hold and Wait: Require processes to request all resources at once before starting. Or release all resources before requesting new ones. Leads to low resource utilization.
- Allow Preemption: If a process holding resources requests a resource that cannot be immediately allocated, preempt all its resources. Works for resources whose state can be saved (CPU registers, memory).
- Eliminate Circular Wait: Impose a total ordering on resource types. Processes must request resources in increasing order. Prevents circular chains.
Deadlock Avoidance - Banker's Algorithm
The Banker's Algorithm (Dijkstra, 1965) is a deadlock avoidance algorithm. Before granting a resource request, it checks if the resulting state is safe.
A safe state is one where there exists a safe sequence - an ordering of processes such that each process can obtain all its needed resources, execute, and release them, allowing the next process to proceed.
Data structures:
- Available: Number of available instances of each resource type
- Max: Maximum demand of each process for each resource
- Allocation: Currently allocated resources for each process
- Need: Remaining resource need = Max - Allocation
Deadlock Detection and Recovery
Detection: Allow deadlocks to occur, then detect them using a wait-for graph (simplified RAG). Periodically run a detection algorithm to find cycles.
Recovery:
- Process Termination: Abort one or more deadlocked processes. Either abort all deadlocked processes (expensive) or abort one at a time until deadlock is resolved.
- Resource Preemption: Preempt resources from some processes and give them to others. Must handle rollback (return process to a safe state) and starvation (same process may always be chosen as victim).
