Definition:
A deadlock is a situation in which two or more processes are waiting for resources that are held by each other, and none of them can proceed.
In short, it is a state of permanent waiting.
Example:
- Process P1 holds Resource R1 and waits for R2.
- Process P2 holds Resource R2 and waits for R1.
Both are waiting forever — this is a deadlock.
Four Necessary Conditions for Deadlock (Coffman Conditions):
- Mutual Exclusion:
Each resource can be used by only one process at a time. - Hold and Wait:
A process is holding at least one resource and waiting for others. - No Preemption:
A resource cannot be forcibly taken from a process. - Circular Wait:
A circular chain of processes exists, each waiting for a resource held by the next process.
Deadlock occurs only if all four conditions hold simultaneously.
Deadlock Handling Methods
There are three main strategies to deal with deadlocks:
1. Deadlock Prevention
Definition:
Deadlock prevention means designing the system in such a way that at least one of the four necessary conditions cannot occur.
How it works:
We prevent deadlock by breaking one or more Coffman conditions:
| Condition | Prevention Method |
|---|---|
| Mutual Exclusion | Make resources sharable (where possible) |
| Hold and Wait | Process must request all resources at once before execution |
| No Preemption | Allow preemption – take resource from a process if needed |
| Circular Wait | Impose a strict ordering of resources (e.g., number them and request in increasing order) |
✅ Advantage:
- Prevents deadlock completely
❌ Disadvantage:
- May cause low resource utilization and process starvation
2. Deadlock Avoidance
Definition:
Deadlock avoidance means the system dynamically examines resource allocation and decides whether to grant or wait for a request so that deadlock never occurs.
Technique:
The most common method is the Banker’s Algorithm (used for multiple instances of resources).
- The system checks whether allocating a resource will keep it in a “safe state”.
- A safe state means there is at least one sequence of processes where each can finish execution.
If the system stays safe, it grants the resource;
if not, the process must wait.
✅ Advantage:
- Ensures system will never enter a deadlock.
❌ Disadvantage:
- Requires prior knowledge of maximum resource needs.
- Adds runtime overhead due to constant checking.
3. Deadlock Detection and Recovery
Definition:
In this method, the system does not prevent or avoid deadlocks.
Instead, it allows them to occur and then detects and recovers from them.
How it works:
- Detection:
- The system uses algorithms to periodically check for circular waits among processes.
- A wait-for graph is often used (especially in single-instance systems).
- If a cycle exists in the graph → deadlock detected.
- Recovery:
- Once detected, the system recovers using one of these methods:
- Terminate processes (one or more) to break the cycle.
- Preempt resources and give them to other processes.
- Once detected, the system recovers using one of these methods:
✅ Advantage:
- Efficient use of resources (no restrictions upfront)
❌ Disadvantage:
- Overhead in detection and recovery
- May cause data loss or process restart