Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

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:

  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 — a resource can't be taken away; it's released only voluntarily.
  4. Circular wait — P1 waits for P2, P2 for P3, …, Pn for P1. Break any one and deadlock is impossible.

Resource allocation graph (RAG)

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.

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

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

Interview one-liners

More Operating Systems notes