Deadlock Prevention & Avoidance

The Story That Explains Prevention & Avoidance

Quick Recap — The Four Coffman Conditions

Before we can break any condition, remember all four must simultaneously hold for a deadlock to occur. Prevention strategies attack these one by one.

Prevention Strategy 1 — Break Mutual Exclusion

If a resource can be shared by multiple processes, no process ever needs to wait, and therefore no deadlock. Sadly, most interesting resources are intrinsically non-sharable: a printer cannot print two documents mid-page, a mutex cannot be locked twice.

Prevention Strategy 2 — Break Hold and Wait

A process may not hold any resource while requesting others. Two protocols implement this.

Example Comparison

A copy program copies data from tape (T) to disk (D), then prints results (P). Under Protocol A, it grabs T + D + P at the start — even though P isn't used for hours of copying. Under Protocol B, it grabs T + D, does the copy, releases both, then grabs D + P and prints. The middle release point creates a race: another process might snatch D and the copy program blocks.

Prevention Strategy 3 — Break No Preemption

Allow the OS to forcibly take resources back from a waiting process. Two rules apply.

Prevention Strategy 4 — Break Circular Wait (Most Practical)

Impose a total ordering on all resource types. Assign each type a unique integer F(R_i). Every process must request resources in strictly increasing order of F. To request a resource lower in the order, first release all resources of equal or higher order.

🎮 Interactive — Watch Ordered Locking Prevent Deadlock

Two processes both need R1 (order=1) and R2 (order=2). With the ordering rule enforced, both must acquire R1 first, then R2. Click Next to trace the execution.

Deadlock Avoidance — Concept

Prevention is pessimistic — it disallows patterns that could deadlock even when they wouldn't. Avoidance is optimistic — it grants requests whenever safe and postpones only truly risky ones. The trade-off is that avoidance requires a priori information: each process must declare its maximum future resource need.

Safe State — Formal Definition

A state is safe if there exists a safe sequence ⟨P₁, P₂, …, P_n⟩ of all processes such that, for each P_i, the resources P_i may still request can be satisfied by:

Banker's Algorithm — Overview

Dijkstra's Banker's Algorithm is the classic implementation of avoidance for systems with multiple instances of each resource type. Named for a bank that only lends when it can still guarantee all customers can be fully repaid.

The Safety Algorithm

Given the current state (Available, Allocation, Need), the safety algorithm asks: "Does a safe sequence exist?" It simulates completion of processes in a hypothetical order.

# Determine whether the system is in a safe state
Work    = Available                     # snapshot of free resources
Finish  = [false] * n                 # has each process finished?

while exists i such that Finish[i] == false and Need[i] <= Work:
    Work      = Work + Allocation[i]    # pretend Pi finishes, returns its resources
    Finish[i] = true

if all(Finish):
    return "SAFE — a safe sequence exists"
else:
    return "UNSAFE — deadlock is possible"

🎮 Interactive — Walk Through Banker's Safety Check (Galvin's Classic)

Setup: 5 processes (P0–P4), 3 resource types (A, B, C). Total instances: A=10, B=5, C=7. Currently allocated: A=7, B=2, C=5, so Available = [3, 3, 2]. Click Next to test one process at a time.

Resource-Request Algorithm

When process P_i makes a request Request_i, the Banker doesn't grant it blindly. It pretends to grant, runs the safety algorithm, and only truly commits if the result is safe. Otherwise, roll back and make P_i wait.

def resource_request(i, Request):
    # Step 1 — sanity check: can't ask for more than declared max
    if Request > Need[i]:
        raise Error("Process exceeded its Max declaration")

    # Step 2 — physical check: is there enough right now?
    if Request > Available:
        return "WAIT — not enough resources yet"

    # Step 3 — pretend to grant
    Available     -= Request
    Allocation[i] += Request
    Need[i]       -= Request

    # Step 4 — safety check on the pretended state
    if is_safe():
        return "GRANTED"                # commit the change
    else:
        # Roll back — request would lead to unsafe state
        Available     += Request
        Allocation[i] -= Request
        Need[i]       += Request
        return "DENIED — unsafe, must wait"

🎮 Interactive — Two Requests Handled by the Banker

Same initial state as before. Watch the Banker evaluate two requests: one is granted, the next is refused because it would drive the system into an unsafe state.

Numerical Problem 1 — Fully Worked Static Example

Given the following system state, determine whether it is safe. If safe, find a safe sequence.

Problem Statement

Step 1 — Compute Available

# Total allocated per column
Sum_A = 1 + 3 + 2 + 1 = 7
Sum_B = 0 + 1 + 1 + 0 = 2
Sum_C = 2 + 1 + 0 + 1 = 4

# Available = Total − Sum
Available_A = 8 − 7 = 1
Available_B = 5 − 2 = 3
Available_C = 6 − 4 = 2

Available = [1, 3, 2]

Step 2 — Run Safety Algorithm

Numerical Problem 2 — Interactive Walkthrough

Consider a different system. Click Next to run the safety algorithm one step at a time.

Setup

Advantages & Disadvantages

Comparison — Prevention vs Avoidance

Real-World Applications

Golden Rules — Prevention & Avoidance