Skip to main content

Handling Deadlocks: Prevention, Avoidance, Detection & Recovery

Medium

Interview Question: "What is the difference between deadlock prevention, deadlock avoidance, and deadlock detection & recovery? What is the Banker's Algorithm, what are Safe vs. Unsafe states, and why do modern OSs use the Ostrich Algorithm?"

There are four ways an OS can deal with the risk of deadlock: stop it from ever being possible (prevention), check every request before granting it (avoidance), let it happen and clean up after (detection & recovery), or just ignore it (the Ostrich Algorithm — what Linux, Windows, and macOS actually do).

The analogy: a one-lane bridge​

Cars want to cross a narrow bridge from both directions at once.

  • Prevention (the architect): redesign the bridge — add a divider, or make it strictly one-way. Head-on collisions become structurally impossible.
  • Avoidance (the traffic cop): keep it one lane, but post a cop at the entrance who checks each car's declared route before letting it on. If letting this car on risks a jam further down, it waits.
  • Detection & recovery (the tow truck): let cars drive on freely. If two crash head-on, send a crane to drag one into the river so traffic can move again.
  • The Ostrich Algorithm (the careless mayor): pretend the problem doesn't exist. If cars get stuck, wait for the drivers to give up and walk away (a reboot).

Strategy 1: Prevention — break one of the four conditions​

A deadlock can only happen if four conditions are all true at the same time (the Coffman conditions). Break any single one of them structurally, and deadlock becomes impossible:

  1. Kill mutual exclusion — make the resource shareable. Read-only files, or a print queue where jobs write to a disk buffer instead of fighting over the printer directly.
  2. Kill hold-and-wait — force processes to request everything they'll need upfront, or give up everything they're holding before asking for more. Simple, but wastes resources since things get grabbed "just in case."
  3. Kill no-preemption — if a process asks for something and gets denied, the OS just takes back everything it's currently holding.
  4. Kill circular wait (the one everyone actually uses): force a global order on resources — every process must request them in ascending order. If the smaller-numbered resource always gets locked first, a cycle can never form.

Strategy 2: Avoidance — the Banker's Algorithm​

Instead of permanently banning a condition, avoidance checks every single request as it arrives, and only grants it if doing so leaves the system in a state where everyone can still, eventually, finish.

Safe State
a finishing order exists
may become
Unsafe State
no order guaranteed
might become
Deadlock
actual freeze
  • Safe state: there's at least one order in which every process could run to completion and hand back its resources, one at a time.
  • Unsafe state: no such order exists anymore. This is not a deadlock — it just means the OS can no longer guarantee one won't happen if everyone asks for their declared maximum at once.
  • Deadlock: an actual freeze. It's a subset of unsafe states, not the same thing.

How the Banker's Algorithm (Dijkstra) works, like a bank managing cash reserves:

  • Every process declares its maximum possible need upfront.
  • The OS tracks what's allocated and what's still available.
  • A process's remaining need is just Max − Allocated.
  • When a process asks for more resources, the OS simulates granting it and checks: is there still some order in which everyone can finish? If yes, grant it. If no, make the process wait.

Strategy 3: Detection & recovery — let it happen, clean up after​

No restrictions upfront. Instead:

  • Detection: a background thread periodically builds a Wait-For Graph — an edge from T1 to T2 means "T1 is waiting on something T2 holds" — and checks it for cycles.
  • Recovery, once a cycle is found:
    • Kill processes — abort all of them, or abort one at a time until the cycle breaks.
    • Preempt resources — pick a victim, roll it back to a safe checkpoint, and hand its resources to someone else.

Why real operating systems just ignore the problem​

Linux, Windows, and macOS don't run the Banker's Algorithm. Three reasons:

  1. You can't know the max in advance. A real application can't declare upfront how much memory, how many sockets, or how many file handles it'll eventually need.
  2. The check itself is expensive. Running a full safety-matrix calculation on every malloc() or file open would add real latency to the most common operations in the system.
  3. Deadlocks are rare. Compared to the millions of normal system calls happening every second, actual deadlocks barely happen.

So general-purpose OSes use the Ostrich Algorithm: ignore the theoretical risk, optimize for speed, and give the user kill -9 for when something does get stuck.

Say this in the interview​

"Prevention structurally removes one of the four Coffman conditions — usually circular wait, by enforcing a lock order. Avoidance checks every allocation at runtime with the Banker's Algorithm to keep the system in a Safe State. Detection lets deadlocks happen and recovers by killing a victim. Real operating systems use the Ostrich Algorithm — they just ignore the risk, because declaring resource maximums upfront isn't realistic and the safety check is too expensive to run on every allocation."

Code: Banker's Algorithm safety check​

def is_safe_state(available, max_matrix, allocation):
    num_processes = len(allocation)
    num_resources = len(available)

    # Calculate Need matrix: Need[i][j] = Max[i][j] - Allocation[i][j]
    need = [[max_matrix[i][j] - allocation[i][j] for j in range(num_resources)] for i in range(num_processes)]

    work = list(available)
    finish = [False] * num_processes
    safe_sequence = []

    while len(safe_sequence) < num_processes:
        found_process = False
        for p in range(num_processes):
            if not finish[p]:
                # Check if Need <= Work for all resource types
                if all(need[p][r] <= work[r] for r in range(num_resources)):
                    # Simulate process finishing and releasing resources
                    for r in range(num_resources):
                        work[r] += allocation[p][r]
                    finish[p] = True
                    safe_sequence.append(f"P{p}")
                    found_process = True
                    break

        # If no process could be satisfied, system is in an UNSAFE state
        if not found_process:
            return False, []

    return True, safe_sequence

if __name__ == "__main__":
    # 3 Resource types: R0, R1, R2
    available_resources = [3, 3, 2]

    allocation_matrix = [
        [0, 1, 0],  # P0
        [2, 0, 0],  # P1
        [3, 0, 2],  # P2
        [2, 1, 1],  # P3
        [0, 0, 2]   # P4
    ]

    max_demand = [
        [7, 5, 3],  # P0
        [3, 2, 2],  # P1
        [9, 0, 2],  # P2
        [2, 2, 2],  # P3
        [4, 3, 3]   # P4
    ]

    safe, seq = is_safe_state(available_resources, max_demand, allocation_matrix)
    if safe:
        print(f"System is in a SAFE STATE!")
        print(f"Safe Execution Sequence: {' -> '.join(seq)}")
    else:
        print("System is in an UNSAFE STATE! (Risk of Deadlock)")