Skip to content
Tutorials Center
My learning

Topics

Lesson 35 of 66 ยท Deadlocks

Deadlock Detection, Recovery and the Ostrich Algorithm

Detect deadlocks with wait-for graphs and the detection algorithm, recover by killing a victim or preempting resources, and learn why many systems simply ignore deadlock.

Prevention and avoidance are conservative: they restrict resource use so deadlocks never happen. The third strategy is optimistic. Let processes request resources freely, check now and then whether a deadlock has occurred, and recover if it has. This is cheap when deadlocks are rare, and it is what database systems do.

Detection

Single instance per resource type

If each resource type has only one instance, keep a wait-for graph (a resource allocation graph with the resource nodes collapsed). A deadlock exists if and only if this graph has a cycle. Finding a cycle in a graph with n nodes costs O(n^2) with a simple search, so it can be done often.

Several instances per resource type

Use the detection algorithm, a close relative of the safety algorithm in the banker's algorithm, but it uses what processes currently request rather than their maximum:

  1. Work = Available. A process with Allocation = 0 is marked finished (it cannot be part of a deadlock). Everything else is unfinished.
  2. Find an unfinished process whose current Request <= Work. If none exists, go to step 4.
  3. Assume it finishes and returns its resources: Work += Allocation[i]; mark it finished; go to step 2.
  4. Every process still unfinished is deadlocked.

The algorithm is optimistic: it assumes that a process that can proceed now will finish and release, which is the best case for everyone else. If even this optimistic assumption leaves processes stuck, they are really stuck.

When to run the detector

  • On every request that cannot be granted immediately: finds deadlocks right away, but is expensive.
  • At fixed intervals (every few minutes).
  • When CPU utilization drops below a threshold (processes are all blocked).

Running it rarely means that, once a cycle forms, more and more processes may pile up behind it before it is found, and you cannot tell which request closed the cycle.

Recovery

Once a deadlock is found, the system must break it. Two main strategies:

flowchart TD
    D["Deadlock detected"] --> A["Process termination"]
    D --> B["Resource preemption"]
    A --> A1["Abort all deadlocked processes"]
    A --> A2["Abort one at a time until the cycle is gone"]
    B --> B1["Select a victim"]
    B --> B2["Roll back to a safe state"]
    B --> B3["Prevent starvation of the victim"]

Process termination

  • Abort all deadlocked processes. Certain to work, but wasteful: all their computation is lost.
  • Abort one process at a time and rerun detection after each. Less waste, more detector runs.

Which process is the victim? Choose the one that is cheapest to lose: lowest priority, least CPU time spent so far, fewest resources held, nearest to the beginning of its work, or "interactive over batch". A process that has modified files or half-finished a database update needs those changes undone, so termination is not always free.

Resource preemption

Instead of killing a process, take a resource away from one of the deadlocked processes and give it to another until the cycle is broken. Three issues must be handled:

  1. Victim selection: minimize cost, as above.
  2. Rollback: the process that lost a resource cannot continue normally. Return it to some earlier safe state (a checkpoint) and restart from there, or abort it entirely.
  3. Starvation: if the same process is always the cheapest victim it will never finish. Count rollbacks as part of the cost so that a process cannot be chosen forever.

Here is a small recovery loop built on the detection algorithm: repeatedly detect, choose the cheapest deadlocked victim, abort it (releasing its resources), and stop when no deadlock remains.

Python Detect, pick a victim, recover

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 first pass finds a deadlocked group. Aborting its cheapest member returns resources that let the others finish, and the second pass confirms that no deadlock remains. P4 is waiting too, but it holds nothing, so it was never a member of the deadlocked set: it was only blocked by it.

The ostrich algorithm

The fourth strategy is to do nothing: pretend deadlocks never happen, like an ostrich with its head in the sand. This sounds irresponsible but is the choice of most general-purpose operating systems, including Linux, Windows and macOS, for resources such as application locks and process-table slots.

The reasoning is an engineering trade-off:

  • Deadlocks are rare in practice (once a month? once a year?).
  • Prevention would restrict programmers and slow every request; detection and avoidance cost CPU on every system.
  • When a deadlock does occur, the user can kill the stuck program or reboot, and the system is back.
Python Is doing nothing cheaper?

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 numbers are invented, but the lesson is real: ignoring is best when deadlocks are rare and cheap to fix; detection and recovery pays off when they are frequent or expensive. A database is a typical example of the second case: it detects deadlocked transactions within a fraction of a second, rolls one back, and the application simply retries it.

Deadlock or starvation?

A final reminder, because the two are often confused: in a deadlock a set of processes waits forever for each other and nothing outside can change that; in starvation the system keeps working but one process is repeatedly passed over (see the previous chapter). Deadlocks need all four Coffman conditions; starvation needs only an unfair policy, and aging cures it.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. With single-instance resources, how can a deadlock be detected?

    A cycle in the wait-for graph is both necessary and sufficient for deadlock when each resource has one instance.
  2. 2. In the detection algorithm, which processes start out marked as finished?

    A process holding nothing cannot be part of a deadlock, because it blocks no one.
  3. 3. Why must the cost of a victim include how often it has been chosen before?

    If the same cheap process is the victim each time it never finishes, so repeated selection raises its cost.
  4. 4. Why do general-purpose systems often use the ostrich algorithm?

    It is an engineering trade-off: ignoring is cheaper when deadlocks are rare and easy to clear.
  5. 5. Which recovery method restarts a process from an earlier saved state after it loses a resource?

    Rollback returns the victim to a safe state or checkpoint so it can be restarted consistently.

Summary

  • Detection checks for deadlock after the fact: a cycle search for single instances, or the optimistic detection algorithm for several.
  • Run the detector on blocked requests, at intervals or when CPU use drops.
  • Recovery means terminating processes (all, or one at a time) or preempting resources with rollback; pick victims by cost and guard against starvation.
  • The ostrich algorithm ignores the problem and is common where deadlocks are rare.
  • Deadlock and starvation are different problems with different cures.

Next: Memory Management: The Basics