Skip to content
Tutorials Center
My learning

Topics

Lesson 31 of 66 ยท Deadlocks

Deadlock: Definition and the Four Necessary Conditions

What a deadlock is, the four Coffman conditions that must all hold, how a two-lock deadlock happens, and how many resources make a system deadlock-free.

A deadlock is a situation in which a set of processes is blocked forever, each holding a resource and waiting for another resource held by a different process in the set. Nobody can proceed, and nobody can release what they hold, because releasing happens only after finishing, and finishing needs the thing the other one holds.

An everyday picture: two cars meet on a one-lane bridge from opposite sides. Each needs the part of the bridge occupied by the other. Neither will back up. The cars did nothing wrong individually, yet together they are stuck.

You have already seen a deadlock appear when the producer took the mutex first and when all philosophers held their left chopstick. This chapter treats the problem systematically: what makes it possible, how to prevent or avoid it, and how to detect and repair it.

The system model

A process uses a resource in three steps:

  1. Request: ask for the resource; if it is not available, wait.
  2. Use: operate on it.
  3. Release: give it back.

Resources can be physical (printers, tape drives, memory) or logical (files, locks, semaphores, database rows). Resources come in types; a type may have several identical instances (three identical printers). Deadlocks can involve any of them, even a single lock.

The four necessary conditions

In 1971 Coffman, Elphick and Shoshani showed that a deadlock can arise only if all four of these hold at the same time:

Four conditions for a deadlock

Mutual exclusion A resource has one user at a time
Hold and wait Keep what you have while asking for more
No preemption Resources cannot be taken away
Circular wait A ring of processes each waiting on the next

Break any one condition and deadlock is impossible.

1 / 2
Condition Meaning Example
Mutual exclusion At least one resource is non-sharable: only one process can use it at a time A mutex, a printer
Hold and wait A process holds at least one resource and waits for others Holds lock A, requests lock B
No preemption A resource can only be released voluntarily by its holder You cannot rip a lock away from a thread safely
Circular wait There is a cycle P0 waits for P1 waits for ... waits for P0 Two threads waiting for each other's lock

The conditions are necessary, not sufficient: all four can be true while no process is actually stuck yet. But if you can make one of them impossible, deadlock cannot happen. The prevention lesson takes exactly that route.

A deadlock in a few lines

Two threads need the same two locks, but take them in opposite orders. The simulation below uses the semaphore kernel from the previous chapter: ("P", lock) takes a lock (or blocks), ("V", lock) releases it. When the run ends, any thread that is still blocked is deadlocked.

Python Opposite lock orders

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

When both threads lock in the same order, a deadlock is impossible: the circular-wait condition cannot arise. With opposite orders, a large share of schedules freeze. This is also why deadlocks are hard to test: the bad interleaving may occur once in a million runs.

flowchart LR
    T1(("T1")) -- "holds" --> A["Lock A"]
    T2(("T2")) -- "holds" --> B["Lock B"]
    T1 -. "waits for" .-> B
    T2 -. "waits for" .-> A

Solid arrows show ownership, dashed arrows show waiting: together they form a cycle.

How many resources avoid deadlock?

Suppose P processes each need R units of the same resource type (at most), and the system has T identical units in total. In the worst case every process holds R - 1 units and asks for one more. That blocks everyone only if all those units are used up, i.e. if T <= P * (R - 1). So the system is deadlock-free whenever

T >= P x (R - 1) + 1

Example: 3 processes each needing 4 units need at least 3 x 3 + 1 = 10 units. With 9 units, a deadlock is possible. The program below checks the formula by brute force: it enumerates every distribution of units where each process holds less than its maximum and looks for a state with no free units left.

Python Brute-force check of the deadlock-free formula

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The brute-force minimum matches the formula in every case.

Four ways to deal with deadlock

Operating systems choose one of these strategies, covered in the rest of the chapter:

  1. Prevention: design so at least one of the four conditions can never hold (next lessons).
  2. Avoidance: allow all conditions but check each request against future needs, like the banker's algorithm.
  3. Detection and recovery: let it happen, find it with a graph and fix it (detection).
  4. Ignorance (the "ostrich algorithm"): assume it is rare enough to ignore, which most general-purpose systems do.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Which set lists all four necessary conditions for deadlock?

    These are the Coffman conditions. All four must hold simultaneously for a deadlock to be possible.
  2. 2. Two threads always acquire lock A before lock B. Which condition is impossible?

    A global lock order means a waiting chain always goes from lower to higher locks, so it can never close into a cycle.
  3. 3. Three processes each need up to 3 units of a resource. What is the smallest number of units that makes the system deadlock-free?

    P x (R - 1) + 1 = 3 x 2 + 1 = 7. With 6 units, each could hold 2 and wait for one more.
  4. 4. Are the four conditions sufficient for a deadlock?

    The conditions describe what makes a deadlock possible. An actual deadlock also needs an unlucky sequence of requests.

Summary

  • A deadlock is a permanent blocking of processes, each waiting for a resource held by another in the set.
  • It needs all four conditions: mutual exclusion, hold and wait, no preemption, circular wait.
  • Opposite lock orders are the classic cause; a global order removes circular wait.
  • With P processes needing R units each, T >= P(R - 1) + 1 units guarantee freedom from deadlock.
  • Strategies: prevention, avoidance, detection with recovery, or ignoring the problem.

Next: Resource Allocation Graphs