Deadlock Handling
Deadlock handling means the techniques used by an operating system to prevent, avoid, detect, and recover from deadlocks.
You already learned what a deadlock is. Now we focus specifically on:
Deadlock Handling | +---------------+---------------+ | | | ↓ ↓ ↓ Prevention Avoidance Detection | ↓ Recovery
1. Why Deadlock Handling Is Needed
Consider:
P1 holds R1 → waits for R2 P2 holds R2 → waits for R1
Now:
P1 ───── waits for ─────→ R2 ↑ │ │ ↓ R1 ←──── held by ─────── P2
Neither process can continue.
The OS therefore needs a strategy for dealing with such situations.
2. Four Main Deadlock Handling Strategies
There are four major approaches:
1. Deadlock Prevention
Make deadlock impossible by breaking one necessary condition.
2. Deadlock Avoidance
Carefully allocate resources so the system stays in a safe state.
3. Deadlock Detection and Recovery
Allow deadlocks to occur, detect them, and recover.
4. Ignore the Problem
Some general-purpose systems may not continuously perform expensive deadlock handling for every possible resource situation. Instead, certain applications or resource managers handle the issue themselves.
3. Deadlock Prevention
The idea is:
Prevent at least one of the four necessary conditions for deadlock.
The four conditions are:
1. Mutual Exclusion 2. Hold and Wait 3. No Preemption 4. Circular Wait
If any one is permanently prevented, the classical deadlock cannot occur.
4. Prevention of Mutual Exclusion
Deadlock requires at least one non-shareable resource.
So, where possible, make resources shareable.
For example:
Shared Read-only File ↑ P1 + P2 + P3
Multiple processes can read the same data simultaneously.
However, some resources inherently cannot be shared safely.
For example:
Physical Printer
Two processes cannot safely control a printer's output simultaneously without coordination.
So this method has limitations.
5. Prevention of Hold and Wait
A process should not hold one resource while waiting for another.
One approach is:
Require a process to request all resources it needs before beginning execution.
Example:
P1 needs: R1 + R2 + R3 ↓ Request all three ↓ If all available: Allocate ↓ Execute ↓ Release
Problem
Suppose P1 needs:
R1 + R2
but only R1 is currently available.
Instead of taking R1 and waiting for R2, P1 waits without holding R1.
Disadvantages
- Resources may remain unused.
- A process may not know all required resources in advance.
- Processes may hold resources longer than necessary.
6. Prevention of No Preemption
The third condition is:
No Preemption
To prevent it, the OS may allow resources to be taken away from a process under suitable circumstances.
Example:
P1 holds R1 P1 requests R2 R2 unavailable ↓ OS may preempt/release R1 ↓ P1 waits
Later:
P1 gets R1 + R2 ↓ Continues
Important limitation
This works only for resources where preemption is meaningful and safe.
For example:
CPU → can be preempted Memory pages → can often be moved/swapped
But:
Printer operation → cannot always be safely preempted
7. Prevention of Circular Wait
This is one of the most practical methods.
Assign an order to resources.
Example:
R1 < R2 < R3 < R4
Require every process to request resources in increasing order.
Allowed:
P1: R1 → R2 → R3
Not allowed:
P2: R3 → R1
because it violates the resource ordering.
Why Does This Prevent Deadlock?
Suppose:
P1 holds R1 → requests R2 P2 holds R2 → requests R1
This creates:
P1 → R2 ↑ ↓ R1 ← P2
But if every process must request resources in increasing order:
R1 < R2
P2 cannot hold R2 and then request R1.
Therefore the circular wait cannot form.
8. Deadlock Prevention Summary
| Condition | Prevention Method |
|---|---|
| Mutual Exclusion | Make resources shareable where possible |
| Hold and Wait | Request all resources together |
| No Preemption | Allow resource preemption where possible |
| Circular Wait | Impose resource ordering |
Memory trick:
Break M-H-N-C
9. Deadlock Avoidance
Prevention is relatively strict.
Avoidance is more dynamic.
The OS examines each resource request and asks:
"If I give this resource to the process, will the system remain safe?"
Process requests resource ↓ Safety check ↓ +---+---+ | | Safe Unsafe | | ↓ ↓ Grant Wait
10. Safe State
A system is in a safe state if there is some order in which all processes can obtain the resources they still need and eventually finish.
Example:
Safe Sequence: P2 → P1 → P3 → P4
This means:
P2 finishes ↓ Releases resources ↓ P1 finishes ↓ Releases resources ↓ P3 finishes ↓ P4 finishes
11. Unsafe State
An unsafe state means the OS cannot guarantee that all processes can finish safely based on the current allocation information.
Important:
Unsafe does not necessarily mean deadlocked.
Safe ↓ No guaranteed deadlock Unsafe ↓ Deadlock may become possible
12. Banker's Algorithm
The most famous deadlock avoidance algorithm is:
Banker's Algorithm
It determines whether granting a request keeps the system in a safe state.
The main data structures are:
Available
Resources currently available.
Maximum
Maximum resources each process may need.
Allocation
Resources currently allocated to each process.
Need
Remaining resources required.
Formula:
Need = Max − Allocation
13. Banker's Algorithm Example
Suppose:
Available = 3
Processes require:
P1 → Need 4 P2 → Need 2 P3 → Need 1
The OS checks which process can finish with the currently available resources.
P3 needs 1:
1 ≤ 3
So P3 can potentially finish.
After P3 finishes, it releases its allocated resources.
Suppose it releases 2:
Available = 3 + 2 = 5
Now:
P1 → Need 4 ≤ 5
So P1 can finish too.
This continues until the OS finds a safe sequence.
14. Banker's Algorithm Steps
Conceptually:
1. Find a process whose Need ≤ Available 2. Assume it finishes 3. Add its allocated resources back: Available = Available + Allocation 4. Mark that process finished 5. Repeat 6. If all processes can finish: SAFE Otherwise: UNSAFE
15. Deadlock Detection
Another strategy is:
Allow deadlocks to occur, then detect them.
The system periodically or when appropriate checks whether processes are stuck in a deadlock.
Processes ↓ Resource allocation ↓ Possible deadlock ↓ Detection algorithm ↓ Deadlock? / \ No Yes ↓ ↓ Continue Recovery
16. Deadlock Detection for Single Resource Instance
If every resource type has only one instance, a resource-allocation graph can be used.
Example:
P1 → R2 R2 → P2 P2 → R1 R1 → P1
There is a cycle:
P1 → R2 → P2 → R1 → P1
With one instance per resource type, such a cycle indicates deadlock.
17. Detection with Multiple Resource Instances
When resources have multiple instances, a cycle alone is not enough.
For example:
Resource R1 ↓ 3 instances
Several processes may hold or request different instances.
In such cases, the OS uses a detection algorithm based on information similar to:
- Available
- Allocation
- Request
The algorithm tries to determine whether the remaining requests can be satisfied in some completion sequence.
18. Deadlock Recovery
After detecting a deadlock, the OS must recover.
The major methods are:
Deadlock Detected | +── Terminate Process | +── Resource Preemption | +── Rollback
19. Recovery Method 1 — Process Termination
The OS can terminate one or more processes involved in the deadlock.
Example:
P1 ↔ P2 ↔ P3
Terminate P2:
P1 P3 \ / Resources ↑ Released from P2
Once P2 releases its resources, other processes may continue.
20. Which Process Should Be Terminated?
The OS should consider factors such as:
- Process priority
- How long the process has executed
- How many resources it holds
- How many resources it still needs
- Cost of restarting it
- Importance of its work
- Number of processes that must be terminated
The goal is to recover with minimal cost.
21. Recovery Method 2 — Resource Preemption
The OS can take a resource from one process and give it to another.
Example:
P1 owns R1 P2 needs R1 ↓ OS preempts R1 from P1 ↓ P2 gets R1
However, this creates additional problems:
- Which process should lose the resource?
- How should it be rolled back?
- How do we prevent starvation?
22. Recovery Method 3 — Rollback
The OS can return a process to an earlier safe state.
Process state Checkpoint 1 ↓ Checkpoint 2 ↓ Current state ↓ Deadlock ↓ Rollback ↓ Checkpoint 2
The process can then restart from the earlier checkpoint.
This is especially useful when applications support checkpointing.
23. Starvation During Recovery
Suppose the same process repeatedly loses resources:
P1 ↓ Resource taken ↓ P1 restarts ↓ Resource taken again ↓ P1 restarts ↓ ...
P1 may never finish.
This creates starvation.
Therefore, recovery mechanisms must consider fairness.
24. Prevention vs Avoidance vs Detection
This comparison is extremely important.
| Feature | Prevention | Avoidance | Detection |
|---|---|---|---|
| Basic idea | Make deadlock impossible | Stay in safe states | Find deadlock after it occurs |
| Timing | Before allocation | At every relevant allocation decision | After/periodically |
| Approach | Restrictive | Dynamic | Reactive |
| Uses safe-state check? | Not necessarily | Yes | No |
| Example | Resource ordering | Banker's Algorithm | Detection algorithm |
| Recovery needed? | No | Usually no | Yes |
25. Prevention vs Avoidance
These two are often confused.
Prevention
The OS says:
"I will structure resource allocation so at least one deadlock condition cannot happen."
Example:
Always request: R1 → R2 → R3
Avoidance
The OS says:
"I will examine each request and grant it only if the resulting state remains safe."
Example:
Request ↓ Safety Check ↓ Safe? → Grant Unsafe? → Wait
26. Deadlock Handling in Real Systems
Different systems use different strategies.
A system may combine:
Lock ordering + Timeouts + Detection + Recovery
For example, database systems often use deadlock detection and then abort/rollback one transaction.
27. Deadlock vs Starvation vs Livelock
Very important comparison:
| Deadlock | Starvation | Livelock |
|---|---|---|
| Processes are blocked | Process keeps waiting | Processes are active |
| Processes may wait for each other | Other processes keep getting resources | Processes repeatedly react |
| No useful progress | Some processes may continue | No useful progress |
| Circular wait may exist | Circular wait not required | Circular wait not required |
Easy memory:
Deadlock → Stuck Starvation → Ignored Livelock → Moving but not progressing
28. Practical Deadlock Prevention: Lock Ordering
Consider:
Thread A: Lock A Lock B Thread B: Lock B Lock A
Potential deadlock:
Thread A → holds A → waits B Thread B → holds B → waits A
Better:
Always acquire: Lock A → Lock B
Then:
Thread A: A → B Thread B: A → B
Circular wait is prevented.
This is a common practical synchronization technique.
29. Timeout-Based Handling
Some applications use a timeout.
Example:
Process requests lock ↓ Wait for limited time ↓ Lock acquired? / \ Yes No ↓ ↓ Continue Abort/retry
A timeout can help avoid waiting forever, although it does not mathematically eliminate every possible deadlock situation.
30. Complete Deadlock Handling Diagram
Deadlock | ↓ Deadlock Handling | +-------------+-------------+ | | | ↓ ↓ ↓ Prevention Avoidance Detection | | | ↓ ↓ ↓ Break one of Safe-state Detect cycle/ 4 conditions check unsafe state | | | ↓ | Recovery | | | +------+------+ | | | | | ↓ ↓ ↓ | Terminate Preempt Rollback | ↓ Banker's Algorithm
31. Exam-Oriented Short Notes
Deadlock Prevention
Prevents deadlock by ensuring that at least one of the four necessary conditions—mutual exclusion, hold and wait, no preemption, or circular wait—cannot hold.
Deadlock Avoidance
Dynamically allocates resources only when doing so keeps the system in a safe state.
Banker's Algorithm
A deadlock-avoidance algorithm that checks whether a resource allocation can leave the system in a safe state.
Deadlock Detection
Allows resource allocation to proceed and periodically or when appropriate checks whether a deadlock exists.
Deadlock Recovery
The process of restoring the system after detecting deadlock, using methods such as process termination, resource preemption, or rollback.
🧠 Final Revision
Remember:
DEADLOCK HANDLING | +------------+------------+ | | | ↓ ↓ ↓ PREVENTION AVOIDANCE DETECTION | | | ↓ ↓ ↓ Break one Safe state Find deadlock condition checking | | ↓ ↓ RECOVERY Banker's / | \ Algorithm Kill Preempt Rollback
The most important things to remember:
- Prevention → break at least one deadlock condition.
- Avoidance → never enter an unsafe state.
- Banker's Algorithm → classic deadlock-avoidance algorithm.
- Detection → find deadlock after it can occur.
- Recovery → terminate, preempt, or rollback.
- Resource ordering → practical way to prevent circular wait.
- Safe state ≠ deadlock.
- Unsafe state ≠ necessarily deadlock, but deadlock may become possible.
- Deadlock = stuck, starvation = continuously waiting, livelock = active but no progress.