Notes › Operating Systems
Deadlocks
A deadlock is when a set of processes are all waiting for each other, so none of them can ever continue.
Example: P1 holds the printer and waits for the scanner; P2 holds the scanner and waits for the printer. Both wait forever.
In code:
// Thread 1 // Thread 2
synchronized (a) { synchronized (b) {
synchronized (b) { ... } synchronized (a) { ... }
} }
If T1 takes a and T2 takes b at the same time → deadlock.
The four necessary conditions (Coffman)
A deadlock can happen only if all four hold at the same time:
- Mutual exclusion — a resource can be used by only one process at a time.
- Hold and wait — a process holds one resource while waiting for another.
- No preemption — a resource can't be taken away; it's released only voluntarily.
- Circular wait — P1 waits for P2, P2 for P3, …, Pn for P1. Break any one and deadlock is impossible.
Resource allocation graph (RAG)
- Circle = process, square = resource (dots = instances).
- Request edge: P → R. Assignment edge: R → P.
- No cycle → no deadlock.
- Cycle with single-instance resources → deadlock.
- Cycle with multi-instance resources → maybe a deadlock (check further).
Ways to handle deadlocks
| Strategy | Idea |
|---|---|
| Prevention | make one of the four conditions impossible |
| Avoidance | only grant requests that keep the system in a safe state (Banker's) |
| Detection & recovery | let deadlocks happen, find them, then fix |
| Ignore (ostrich algorithm) | used by most OSes (Windows, Linux) for user resources — deadlocks are rare and prevention is costly |
1. Prevention
| Condition | How to break it | Downside |
|---|---|---|
| Mutual exclusion | make resources shareable (read-only files) | not possible for printers etc. |
| Hold and wait | request all resources at once, or release before requesting | low utilisation, starvation |
| No preemption | if a request fails, release what you hold | only for resources whose state can be saved (CPU, memory) |
| Circular wait | number the resources and always request in increasing order | needs discipline — the most practical fix |
The lock-ordering rule fixes the Java example above: always lock a before b.
2. Avoidance — Banker's algorithm
The system knows each process's maximum need. It grants a request only if the resulting state is safe — there's an order in which every process can finish.
- Need = Max − Allocation
- Safe sequence: find a process whose Need ≤ Available, pretend it finishes (Available += its Allocation), repeat.
Solved example
5 processes, resources A, B, C. Total = (10, 5, 7).
| Process | Allocation (A B C) | Max (A B C) | Need = Max − Alloc |
|---|---|---|---|
| P0 | 0 1 0 | 7 5 3 | 7 4 3 |
| P1 | 2 0 0 | 3 2 2 | 1 2 2 |
| P2 | 3 0 2 | 9 0 2 | 6 0 0 |
| P3 | 2 1 1 | 2 2 2 | 0 1 1 |
| P4 | 0 0 2 | 4 3 3 | 4 3 1 |
Allocated total = (7, 2, 5) → Available = (3, 3, 2).
| Step | Pick (Need ≤ Available) | Available after it finishes |
|---|---|---|
| 1 | P1 (1 2 2 ≤ 3 3 2) | 3 3 2 + 2 0 0 = 5 3 2 |
| 2 | P3 (0 1 1) | 5 3 2 + 2 1 1 = 7 4 3 |
| 3 | P4 (4 3 1) | 7 4 3 + 0 0 2 = 7 4 5 |
| 4 | P0 (7 4 3) | 7 4 5 + 0 1 0 = 7 5 5 |
| 5 | P2 (6 0 0) | 7 5 5 + 3 0 2 = 10 5 7 |
Safe sequence: P1 → P3 → P4 → P0 → P2. The state is safe.
Resource request algorithm: for a request, check Request ≤ Need and Request ≤ Available, pretend to grant it, and run the safety check — grant only if still safe.
Banker's needs maximum needs in advance and a fixed number of processes, so real OSes rarely use it, but it's a favourite exam question.
3. Detection and recovery
- Single-instance resources: look for a cycle in the wait-for graph (processes only).
- Multi-instance: a Banker's-like detection algorithm on current requests. Recovery: kill all deadlocked processes, kill them one by one until the cycle breaks (pick the cheapest victim), or preempt resources and roll a process back to a safe checkpoint. Databases do this: they abort one transaction (Concurrency Control).
Deadlock vs starvation vs livelock
| Deadlock | Starvation | Livelock | |
|---|---|---|---|
| What | everyone waits forever | one process never gets the resource | processes keep reacting to each other but make no progress |
| CPU busy? | no | others run | yes |
| Example | two locks taken in opposite order | low priority never scheduled | two people stepping aside in a corridor forever |
| Fix | prevention/avoidance | aging | randomised back-off |
Deadlock-free code checklist
- Acquire locks in a global order.
- Use
tryLockwith a timeout and back off. - Hold locks for as short a time as possible; never call unknown code while holding a lock.
- Prefer higher-level tools (concurrent collections, message passing).
Interview one-liners
- Four conditions: mutual exclusion, hold and wait, no preemption, circular wait — all needed.
- Breaking circular wait with lock ordering is the most practical prevention.
- Banker's algorithm avoids deadlock by staying in safe states.
- A RAG cycle means deadlock only if each resource has a single instance.
- Related: Process Synchronization, CPU Scheduling Algorithms.