Skip to content
Tutorials Center
My learning

Topics

Lesson 33 of 66 ยท Deadlocks

Deadlock Prevention: Breaking One of the Four Conditions

Prevent deadlocks by making one Coffman condition impossible: spooling, all-at-once requests, preemption and global lock ordering, with runnable Python experiments.

Since a deadlock needs all four Coffman conditions, a system that makes one of them impossible can never deadlock. That is deadlock prevention: a design-time guarantee, with no detection and no recovery needed. The cost is that each approach restricts how processes may use resources, so prevention trades some performance or convenience for safety.

Attacking each condition

Condition to break Technique Cost
Mutual exclusion Make resources sharable where possible (read-only files, spooling) Many resources are inherently exclusive (a mutex, a printer head)
Hold and wait Request everything at once, or release all held resources before asking for more Low utilization, possible starvation, hard to know needs in advance
No preemption If a request fails, release what you hold; or let the OS take resources from waiting processes Only works for resources whose state can be saved and restored (CPU registers, memory)
Circular wait Give every resource a number; always request in increasing order Needs a fixed global order; awkward if the order of use differs
flowchart TD
    D["Deadlock needs all four"] --> M["Mutual exclusion"]
    D --> H["Hold and wait"]
    D --> N["No preemption"]
    D --> C["Circular wait"]
    M --> M1["Spool or share"]
    H --> H1["All at once / release first"]
    N --> N1["Preempt or back off"]
    C --> C1["Global ordering"]

One broken branch is enough.

Mutual exclusion

You cannot make a lock non-exclusive, but you can avoid needing one. Spooling is the classic: instead of letting processes hold the printer, they write their output to a disk queue, and a single spooler daemon is the only process that uses the printer. Nobody waits for the printer while holding something else. Immutable or copy-on-write data and lock-free structures remove the exclusive resource altogether.

Hold and wait

Two variants:

  1. All at once: a process must request all its resources before it starts, and gets them atomically or not at all.
  2. Release first: a process that needs more must release everything it holds and request the whole set again.

The experiment below compares plain incremental locking with all-or-nothing acquisition. Four threads each need two of three locks (chosen at random) for three time units.

Python Hold and wait versus all-or-nothing

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.

Incremental locking can deadlock (two threads each grab one lock the other wants). All-at-once never deadlocks. (The finishing times are not a fair comparison: the incremental average counts only the lucky runs that did not deadlock.) The real price of all-at-once is hidden in this model: in a system where processes ask for resources they will not use until much later, those resources sit idle, and a thread that needs a popular set can be starved because others keep taking one of its locks first.

No preemption

If a process holding resources requests another that is not available, we may preempt: take its current resources away (it restarts later with everything it needs), or make it release them itself. Databases do the equivalent when they abort a transaction. This works well for resources whose state is easy to save and restore (registers, memory pages), and poorly for others (a half-written file, a printer in the middle of a page).

In application code, the same idea is the try-lock with back-off: take the first lock, try the second, and if that fails release the first and retry after a random pause. (Without the random pause you get a livelock.)

Circular wait: resource ordering

This is the most practical technique. Number all resources, and require that each process requests them in increasing order. Then a waiting chain always moves from lower to higher numbers and can never come back, so no cycle can close. The proof is short: a cycle would need some process holding a high-numbered resource to wait for a lower-numbered one, which the rule forbids.

Python Enforcing a global lock order

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.

Real tools work the same way. The Linux kernel's lockdep records the order in which locks are taken and warns when the same pair is ever taken in opposite orders, even if no deadlock actually happened in that run. In your own code, a simple rule such as "lock the account with the smaller id first" in a money-transfer function removes a whole class of deadlocks.

Ordering only helps if every code path follows it. A single function that locks in a different order, or a callback invoked while holding a lock, can re-introduce the cycle.

Which technique do real systems use?

Most systems prevent deadlock only where it is cheap: lock ordering in the kernel and in well-designed libraries, spooling for printers, and preemption for CPU and memory. For general resources, where none of the four conditions can be removed, systems rely on avoidance or on detection and recovery.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Which technique attacks the circular-wait condition?

    With a global order, a chain of waiting processes can only go upward, so it can never close into a cycle.
  2. 2. What is the main drawback of requesting all resources at the start (breaking hold and wait)?

    A process holds resources it will not use until later, which lowers utilization, and a process needing a popular set can be starved.
  3. 3. Why is breaking mutual exclusion usually impractical?

    A lock exists precisely to give exclusive access. Only read-only or spooled resources can be shared.
  4. 4. A try-lock failure makes a thread release its first lock and retry immediately, in lockstep with another thread. What can happen?

    Both threads keep backing off and retrying in sync. A random delay breaks the symmetry.

Summary

  • Prevention removes one of the four conditions by design, so deadlock cannot occur.
  • Spooling attacks mutual exclusion; all-at-once or release-first requests attack hold and wait; preemption or try-lock attacks no-preemption; a global resource order attacks circular wait.
  • Lock ordering is the most widely used technique; tools like lockdep check it.
  • Each technique costs utilization, flexibility or complexity.

Next: The Banker's Algorithm