# Deadlocks — The 4 Conditions, Prevention, Avoidance and Banker's Algorithm

Source: https://skills101.in/learn/operating-systems/deadlocks — Skills101 free tutorial (Operating Systems). Updated 2026-11-09.

A **deadlock** is when a set of processes are all waiting for each other, so **none** can ever continue.

![P1 holds R1 and wants R2; P2 holds R2 and wants R1 — a circular wait that never ends](https://skills101.in/learn-img/operating-systems/deadlock.svg)

Real-life version: two cars meet on a one-lane bridge from opposite ends; neither will reverse.

## 1. The four necessary conditions (Coffman)

A deadlock can happen **only if all four** hold at the same time:

1. **Mutual exclusion** — a resource can be used by only one process at a time.
2. **Hold and wait** — a process holds one resource while waiting for another.
3. **No preemption** — resources can't be taken away forcibly.
4. **Circular wait** — P1 waits for P2, P2 waits for … Pn, Pn waits for P1.

Break **any one** and deadlock is impossible.

## 2. Handling deadlocks: four strategies

| Strategy | Idea |
|---|---|
| **Prevention** | design the system so one condition can never hold |
| **Avoidance** | check each request; grant only if the system stays **safe** (Banker's) |
| **Detection & recovery** | let deadlocks happen, detect cycles, then recover |
| **Ignore it** | "ostrich algorithm" — reboot if it happens (most desktop OSes) |

### Prevention examples

- Break **hold and wait**: request all resources at once.
- Break **no preemption**: if a request fails, release what you hold.
- Break **circular wait**: number resources and always request them in increasing order (the most practical fix — also used with database locks).

## 3. Avoidance: the Banker's algorithm

The system is **safe** if there's some order (a **safe sequence**) in which every process can get its maximum need and finish.

**Need = Max − Allocation.** Available resources (A, B, C) = **(3, 3, 2)**.

| Process | Allocation (A B C) | Max (A B C) | Need (A B C) |
|---|---|---|---|
| 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 |

**Find a safe sequence:** repeatedly pick a process whose Need ≤ Available; it finishes and **returns its allocation**.

| 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 system is in a **safe state**. (Other safe sequences may exist.)

When a new request arrives, the OS pretends to grant it, runs this check, and grants it **only if** the state stays safe.

## 4. Detection and recovery

- Draw a **wait-for graph**; a **cycle** means deadlock (for single-instance resources).
- Recover by **terminating** a process (or all deadlocked ones) or **preempting** resources and rolling back.

## 5. Deadlock vs starvation

| | Deadlock | Starvation |
|---|---|---|
| What | processes wait for each other forever | a process waits indefinitely while others progress |
| System progress | stuck for those processes | others keep running |
| Fix | prevent/avoid/detect | aging, fair scheduling |

## Common mistakes

- Saying one condition is enough for deadlock — all **four** are needed.
- Thinking an unsafe state is always a deadlock. Unsafe means a deadlock **may** happen.
- Forgetting to add back the finished process's allocation in the Banker's table.

## Quick recap

- Four conditions: mutual exclusion, hold and wait, no preemption, circular wait.
- Prevention breaks a condition; avoidance (Banker's) keeps the state safe.
- Need = Max − Allocation; find a safe sequence by finishing processes one by one.
- Detection: cycles in the wait-for graph; recover by killing or preempting.


Practice quiz and free certificate: https://skills101.in/learn/operating-systems/deadlocks