Deadlocks
What is a Deadlock?
A deadlock is a situation in an operating system where two or more processes are permanently blocked because each process is waiting for a resource held by another process.
Deadlock = Processes waiting for each other forever.
Simple example
Suppose:
Process P1 has Resource R1 Process P2 has Resource R2
Now:
P1 → waiting for R2 P2 → waiting for R1
Neither can continue.
R1 ↑ │ P2 │ ↓ R2 ↑ │ P1
So:
P1 waits for P2 P2 waits for P1
This is a deadlock.
1. Real-Life Example
Imagine two people:
Person A has Pen Person B has Paper
Person A says:
"Give me the paper; I won't release the pen."
Person B says:
"Give me the pen; I won't release the paper."
Person A │ │ wants Paper ↓ Person B Person B │ │ wants Pen ↓ Person A
Both wait forever.
That is similar to a process deadlock.
2. Operating System Example
Suppose there are two resources:
R1 = Printer R2 = Scanner
And two processes:
P1 needs Printer + Scanner P2 needs Scanner + Printer
Execution:
P1 → gets Printer P2 → gets Scanner
Then:
P1 → waits for Scanner P2 → waits for Printer
Result:
P1 ─────waits────→ Scanner ↑ │ │ ↓ Printer ←────waits── P2
Neither process can proceed.
3. Resource
A resource is anything a process needs to perform its work.
Examples:
- CPU
- Memory
- Printer
- Scanner
- Files
- Database locks
- I/O devices
- Network resources
- Mutex/locks
- Semaphores
Resources can be:
Reusable Resources
Resources that can be reused after being released.
Examples:
Printer CPU Memory Mutex
Consumable Resources
Resources that are produced and consumed.
Examples can include:
Messages Signals Certain communication buffers
Deadlock discussions in classical OS theory commonly focus on reusable resources.
4. Resource Allocation
A process usually follows:
Request ↓ Allocate ↓ Use ↓ Release
For example:
Process P1 ↓ Request Printer ↓ Printer allocated ↓ Use Printer ↓ Release Printer
Deadlock can occur when processes hold some resources while waiting for others.
5. Resource Allocation Graph
A Resource Allocation Graph (RAG) is used to represent relationships between processes and resources.
There are two types of nodes:
Process
Represented as:
(P1)
Resource
Represented as:
[R1]
6. Two Important Types of Edges
Request Edge
A process is requesting a resource.
P1 ─────→ R1
Meaning:
P1 is waiting for R1.
Assignment Edge
A resource has been allocated to a process.
R1 ─────→ P1
Meaning:
R1 is currently allocated to P1.
7. Resource Allocation Graph Example
Suppose:
R1 → P1 P1 → R2 R2 → P2 P2 → R1
Graph:
[R1] ─────→ (P1) │ ↓ [R2] │ ↓ (P2) │ ↓ [R1]
There is a cycle:
P1 → R2 → P2 → R1 → P1
This indicates a possible deadlock.
For the special case where every resource type has exactly one instance, a cycle in the resource-allocation graph indicates deadlock.
With multiple instances of resource types, a cycle alone does not necessarily prove deadlock.
8. Four Necessary Conditions for Deadlock
This is one of the most important OS exam topics.
A deadlock can occur only if all four of these conditions hold simultaneously:
1. Mutual Exclusion 2. Hold and Wait 3. No Preemption 4. Circular Wait
Memory trick:
M H N C
Or:
"Mutual Hold, No Circular"
Let's understand each.
9. Condition 1 — Mutual Exclusion
At least one resource must be non-shareable.
Only one process can use it at a time.
Example:
Printer ↓ P1 is using it
P2 cannot use the same exclusive resource simultaneously.
P1 → Printer ← P2
But only one can get it.
10. Condition 2 — Hold and Wait
A process is holding at least one resource while waiting for another resource.
Example:
P1 | ├── Holds R1 | └── Waiting for R2
This is:
Hold and Wait
11. Condition 3 — No Preemption
A resource cannot simply be forcibly taken away from a process.
Example:
P1 → owns R1
The OS cannot arbitrarily take R1 away while P1 is using it.
P1 must normally release it voluntarily.
12. Condition 4 — Circular Wait
There must be a circular chain of processes waiting for resources.
Example:
P1 → R2 → P2 → R3 → P3 → R1 → P1
Or simply:
P1 waits for P2 P2 waits for P3 P3 waits for P1
This creates a cycle.
13. The Four Conditions Together
A deadlock requires:
DEADLOCK | +-----------+-----------+ ↓ ↓ ↓ Mutual Hold & No Exclusion Wait Preemption | ↓ Circular Wait
If any one of the four conditions is prevented, deadlock can be prevented.
This is the basic idea behind deadlock prevention.
14. Deadlock vs Starvation
These are different.
Deadlock
Processes are stuck waiting for each other.
P1 → waits for P2 P2 → waits for P1
Neither progresses.
Starvation
A process waits for a very long time because other processes keep getting resources/CPU.
P1 → waiting P2 → gets resource P3 → gets resource P4 → gets resource P5 → gets resource ... P1 → still waiting
Difference
| Deadlock | Starvation |
|---|---|
| Processes may wait for each other | One process may continuously lose access |
| No involved process can make progress | Other processes may continue |
| Circular waiting can exist | Circular waiting is not required |
| System can become stuck | System may continue operating |
15. Deadlock vs Livelock
Another important concept is livelock.
Deadlock
Processes don't make progress and remain blocked.
P1 → waiting P2 → waiting
Livelock
Processes keep changing their state/responding to each other but still don't make useful progress.
Example:
P1 → moves aside P2 → moves aside P1 → moves back P2 → moves back ...
They are active but not progressing.
16. Deadlock Handling
Operating systems can deal with deadlocks using several approaches.
Deadlock Handling | +------------+------------+ ↓ ↓ ↓ Prevention Avoidance Detection ↓ Recovery
The main approaches are:
- Deadlock Prevention
- Deadlock Avoidance
- Deadlock Detection and Recovery
- Ignoring the problem in some systems/workloads
17. Deadlock Prevention
Deadlock prevention ensures that at least one of the four necessary conditions can never hold.
Deadlock ↓ Break one necessary condition ↓ Deadlock cannot occur
Prevent Mutual Exclusion
Make resources shareable where possible.
For example, some data can be shared by multiple processes.
However, this isn't possible for inherently exclusive resources such as certain device operations.
Prevent Hold and Wait
Require a process to request all resources before it starts.
P1 ↓ Request R1 + R2 ↓ Gets both ↓ Execute ↓ Release
Problem:
Resources may remain unused while the process waits.
Prevent No Preemption
Allow resources to be taken back under suitable conditions.
For example:
P1 holds R1 P1 requests R2 R2 unavailable ↓ System may release/preempt resources held by P1
This approach isn't practical for every resource.
Prevent Circular Wait
Assign an ordering to resources.
Example:
R1 < R2 < R3 < R4
Require processes to request resources only in increasing order.
Then:
P1: R1 → R2 P2: R2 → R3
but a process cannot request:
R3 → R1
This prevents circular dependencies.
18. Deadlock Avoidance
Deadlock avoidance doesn't simply forbid a condition permanently.
Instead, the OS examines resource requests and asks:
If I grant this request, will the system remain in a safe state?
If yes:
Grant request
If no:
Delay request
The most famous deadlock-avoidance algorithm is:
Banker's Algorithm
19. Safe State
A system is in a safe state if there is at least one sequence in which all processes can obtain their required resources and complete.
Example:
Safe sequence: P2 → P1 → P3 → P4
This means the system can schedule/resource-allocate processes in an order that allows all of them to finish.
20. Unsafe State
An unsafe state means the system cannot guarantee that all processes can complete without deadlock.
Important:
Unsafe state does not necessarily mean deadlock has already occurred.
It means deadlock could become possible depending on future requests.
Safe State ↓ Requests granted safely ↓ Safe State Unsafe State ↓ Deadlock may become possible
21. Banker's Algorithm
The Banker's Algorithm is a classic deadlock-avoidance algorithm.
It is called "Banker's" because it resembles a bank deciding whether it can safely grant a customer's loan without running out of resources needed to satisfy everyone.
The OS considers:
- Available resources
- Resources currently allocated
- Maximum resource needs
- Remaining needs
22. Banker's Algorithm Data
Typically, we use:
Available
Resources currently available.
Max
Maximum resources each process may need.
Allocation
Resources currently allocated to each process.
Need
Remaining resources required.
Formula:
Need = Max − Allocation
Example:
| Process | Max | Allocation | Need |
|---|---|---|---|
| P1 | 7 | 3 | 4 |
| P2 | 5 | 2 | 3 |
The system checks whether processes can finish in some safe order.
23. Simple Banker's Example
Suppose:
Available = 3
Processes need:
P1 → Need 4 P2 → Need 2 P3 → Need 1
P3 can finish because:
1 ≤ 3
After P3 finishes, it releases its resources.
Suppose it releases 2:
Available = 3 + 2 = 5
Now P1 and P2 may become executable.
The OS searches for a:
Safe sequence
24. Deadlock Detection
Another approach is to allow deadlocks to occur and detect them.
Processes run ↓ Deadlock may occur ↓ Detection algorithm ↓ Deadlock found?
If a deadlock is detected:
Yes ↓ Recovery
25. Deadlock Recovery
Once a deadlock is detected, the OS needs to recover.
Common approaches include:
1. Terminate Processes
Terminate one or more processes involved in the deadlock.
P1 ↔ P2 ↔ P3 ↓ Terminate P2 ↓ Resources released ↓ Others continue
2. Resource Preemption
Take resources away from some processes and give them to others, when the resource and application semantics permit it.
P1 owns R1 ↓ Preempt R1 ↓ Give R1 to another process
This is not possible for every resource.
3. Rollback
Return a process to an earlier safe state/checkpoint and restart it later.
Current state ↓ Rollback ↓ Previous safe state
26. Deadlock Detection vs Prevention vs Avoidance
| Prevention | Avoidance | Detection |
|---|---|---|
| Stops deadlock conditions from forming | Makes allocation decisions to stay safe | Allows possibility of deadlock |
| Breaks at least one necessary condition | Checks safe/unsafe state | Searches for deadlock |
| Conservative | Dynamic | Reactive |
| Example: resource ordering | Banker's Algorithm | Detection algorithm |
| Deadlock prevented | Deadlock avoided if assumptions hold | Recovery required if detected |
27. Deadlock Recovery Comparison
| Method | Idea |
|---|---|
| Process termination | Stop one or more processes |
| Resource preemption | Take resources from processes |
| Rollback | Return process to earlier state |
| Restart | Restart selected process/processes |
28. Resource Ordering
Resource ordering is a very useful practical technique.
Suppose:
R1 < R2 < R3
Processes must request resources in that order.
Allowed:
P1: R1 → R2 P2: R2 → R3 P3: R1 → R3
Not allowed:
P1: R2 → R1
because it violates the ordering.
This prevents circular wait.
29. Practical Programming Example
Suppose two threads/processes use two locks.
Thread 1
Lock A Lock B
Thread 2
Lock B Lock A
Possible situation:
Thread 1 → holds A → waits for B Thread 2 → holds B → waits for A
Deadlock!
A common solution is to establish a consistent lock order:
Always acquire: A → B
Then both threads follow:
Thread 1: A → B Thread 2: A → B
This avoids the circular wait.
30. Deadlock Example with Database Locks
Imagine:
Transaction T1 ↓ Locks Account A ↓ Waiting for Account B
Meanwhile:
Transaction T2 ↓ Locks Account B ↓ Waiting for Account A
Result:
T1 ──waits──→ B ↑ │ │ ↓ A ←──waits── T2
This is a classic resource deadlock.
31. Important Deadlock Terms
| Term | Meaning |
|---|---|
| Deadlock | Processes permanently wait for resources |
| Resource | Something required by a process |
| Mutual Exclusion | Resource can be used by only one process at a time |
| Hold and Wait | Process holds one resource while waiting for another |
| No Preemption | Resource cannot be forcibly taken |
| Circular Wait | Processes form a circular waiting chain |
| Safe State | System can find a safe completion sequence |
| Unsafe State | System cannot guarantee safe completion |
| Starvation | Process waits indefinitely because others are favored |
| Livelock | Processes remain active but make no useful progress |
| Banker's Algorithm | Deadlock avoidance algorithm |
32. Most Important Diagram
Remember this:
DEADLOCK | +---------------+---------------+ | | | ↓ ↓ ↓ Mutual Exclusion Hold & Wait No Preemption | | | +---------------+---------------+ | ↓ Circular Wait | ↓ DEADLOCK
All four conditions must be present for the classical deadlock situation.
Break any one:
Break one condition ↓ No deadlock
33. Deadlock Complete Flow
Processes | ↓ Request Resources | ↓ Resources Allocated | ↓ Process Holds Resources | ↓ Requests More Resources | ↓ +----------+----------+ | | Safe Unsafe | | ↓ ↓ Continue Deadlock possible | ↓ Detection | ↓ Recovery
🧠 Quick Revision
Four necessary conditions:
M H N C
M → Mutual Exclusion H → Hold and Wait N → No Preemption C → Circular Wait
Three main approaches:
Prevention ↓ Break one condition Avoidance ↓ Stay in safe state ↓ Banker's Algorithm Detection + Recovery ↓ Detect deadlock ↓ Recover
Most important exam definitions
Deadlock:
A deadlock is a condition in which a set of processes are permanently blocked because each process is waiting for a resource held by another process in the set.
Deadlock Prevention:
A technique that prevents deadlock by ensuring that at least one of the four necessary conditions for deadlock cannot hold.
Deadlock Avoidance:
A technique in which the operating system dynamically examines resource allocation requests and grants them only when the system remains in a safe state.
Banker's Algorithm:
A deadlock-avoidance algorithm that checks whether granting a resource request leaves the system in a safe state.