Deadlocks: Conditions, Prevention, Avoidance, Detection & Recovery

TAKEAWAYS:

• Deadlocks are circular wait scenarios where processes block each other indefinitely, requiring all four conditions (mutual exclusion, hold-and-wait, no preemption, circular wait) to occur simultaneously.
• Prevention (breaking one condition) is strict but simple; avoidance (e.g., Banker’s algorithm) is dynamic but computationally expensive; detection (e.g., Wait-For Graph) is reactive but risky.
• The Banker’s algorithm ensures safety by checking if resource allocation leaves the system in a deadlock-free state before granting requests.
• Recovery involves aborting processes, preempting resources, or rolling back transactions—each with trade-offs between cost and system stability.
• Real-world impact: Deadlocks cripple systems like Nepal’s NTC traffic control (mutual exclusion on road segments), Khalti payment queues (hold-and-wait on transaction locks), and Daraz order fulfillment (circular wait in inventory allocation).
• Exam focus: Expect scenario-based questions (e.g., "Why does a bank’s loan approval system deadlock?") and algorithm traces (e.g., "Apply Banker’s to a given resource allocation").

1. What is a Deadlock?

A deadlock is a state in which two or more processes are blocked forever, each waiting for a resource held by another. It arises when processes compete for limited resources in a way that creates a circular dependency.

Visual: Deadlock Scenario

graph LR
    A["Process P1"] -->|"Holds R1"| B["Resource R1"]
    B -->|"Requested by"| C["Process P2"]
    C -->|"Holds R2"| D["Resource R2"]
    D -->|"Requested by"| A

Key Idea: The cycle P1 → R1 → P2 → R2 → P1 traps both processes.

2. Four Necessary Conditions for Deadlock

For a deadlock to occur, all four conditions must hold simultaneously. Breaking any one prevents deadlocks.

Real-World Tie-In:

• Nepal’s Traffic Jams (Circular Wait): Imagine two roads intersecting without roundabouts. Car A takes the north-south road, Car B takes the east-west road, and both now block each other from proceeding. This is a deadlock where mutual exclusion (road space) + circular wait (no forward progress) freeze the system.

3. Deadlock Prevention: Breaking the Conditions

Prevention eliminates one of the four conditions at the system design level. It is simple but restrictive.

Strategies

1. Eliminate Mutual Exclusion

   • Allow sharing of resources where possible (e.g., read-only files).
   • Downside: Not all resources can be shared (e.g., printers).

2. Eliminate Hold-and-Wait

   • Require processes to request all resources at once (e.g., bank loans).
   • Example: A customer must declare all assets before a loan is approved (no partial holds).

3. Allow Preemption

   • Forcefully take resources from processes and restart them later.
   • Example: If a process holds a printer but is stuck, the OS can kill it and reassign the printer.

4. Eliminate Circular Wait

   • Impose a total ordering on resource types (e.g., always request resources in order: R1 → R2 → R3).
   • Example: In a library system, books must be checked out in alphabetical order (no circular waits).

Comparison Table: Prevention vs. Avoidance

4. Deadlock Avoidance: The Banker’s Algorithm

Avoidance dynamically checks if allocating a resource would lead to a deadlock. The Banker’s algorithm (Dijkstra, 1965) is the gold standard.

How It Works

1. Define:

   • Available: Free resources.
   • Maximum: Max resources a process can request.
   • Allocation: Currently held by processes.
   • Need: Maximum - Allocation (remaining requests).

2. Safety Check:

   • Simulate granting a request and check if the system can complete all processes without deadlock.
   • If safe, grant the request; else, deny.

Example: Bank Loan Approval (Avoidance)

Scenario:

• Resources: 3 types (R1: Land, R2: Capital, R3: Labor).

• Processes: P0 (Farmer), P1 (Shopkeeper), P2 (Factory).

• Current State: | Process | Allocation (R1,R2,R3) | Max Need (R1,R2,R3) | Available (R1,R2,R3) = (1,2,2) |

  | P0 | (0,1,0) | (0,2,2) | | P1 | (2,0,0) | (3,3,3) | | P2 | (3,2,1) | (3,3,2) |

Request: P1 asks for (1,0,2). Steps:

1. Tentative Allocation:
   • New Allocation: P1 = (3,0,2).
   • New Available: (0,2,0).
2. Check Safety:
   • Can P0 finish? Needs (0,1,2) → Available (0,2,0) cannot satisfy (needs 2 labor but only 0 available). Unsafe.
   • Reject P1’s request.

Visual: Banker’s Algorithm Workflow

sequenceDiagram
    participant Process as Process
    participant OS as OS (Banker's Algorithm)
    Process->>OS: Request Resources
    OS->>OS: Check Safety (Simulate Completion)
    alt Safe?
        OS->>Process: Grant Request
    else Unsafe
        OS->>Process: Deny Request
    end

Real-World Example: Khalti Payment System

• Problem: Two users (A and B) try to transfer money simultaneously, each holding a partial lock.
• Solution: Khalti uses avoidance by:
  1. Locking all accounts involved in a transaction at once (no hold-and-wait).
  2. Rolling back if any step fails (e.g., insufficient balance).

5. Deadlock Detection

If prevention/avoidance is too costly, detect deadlocks after they occur using:

1. Wait-For Graph (WFG)

   • Nodes = Processes/Resources.
   • Edges = P1 → R1 (P1 waits for R1), R1 → P2 (R2 holds R1).
   • Cycle = Deadlock.

2. Banker’s Algorithm (Detection Mode)

   • Periodically check if the system is in a safe state.

Example: Daraz Order Fulfillment Deadlock

Scenario:

• Processes: P1 (Order #101), P2 (Order #102).
• Resources: R1 (Inventory A), R2 (Inventory B).
• Allocation:
  • P1 holds R1, waits for R2.
  • P2 holds R2, waits for R1.

Wait-For Graph:

graph TD
    P1["Process P1"] -->|"Waits for"| R2["Resource R2"]
    R2 -->|"Held by"| P2["Process P2"]
    P2 -->|"Waits for"| R1["Resource R1"]
    R1 -->|"Held by"| P1

Detection: The cycle P1 → R2 → P2 → R1 → P1 indicates a deadlock.

A labelled WFG showing processes and resources in a cycle. (Image: Kkaaii, CC BY-SA 4.0, via Wikimedia Commons)

6. Deadlock Recovery

Once detected, break the deadlock by:

1. Process Termination
   • Abort all deadlocked processes (brute force).
   • Cost: High if processes are long-running.
2. Resource Preemption
   • Take resources from one process and give to another.
   • Example: Kill P1 to free R1 for P2.
3. Rollback
   • Undo actions of deadlocked processes (e.g., revert database transactions).

Trade-off:

Real-World Example: NTC Traffic Control

• Deadlock: Two cars block each other at an intersection.
• Recovery:
  • Preemption: Force one car to backtrack (like a traffic cop redirecting flow).
  • Abort: Clear the intersection by stopping all traffic (rare, but used in emergencies).

7. Deadlock vs. Starvation vs. Livelock

Example of Livelock: Two processes keep releasing and re-requesting the same resource in a loop:

stateDiagram-v2
    [*] --> P1: Request R1
    P1 --> P1a: Allocated R1
    P1a --> P1b: Release R1 (due to error)
    P1b --> P1: Request R1
    P1 --> P2: P2 holds R1
    P2 --> P2a: P2 releases R1
    P2a --> P2: P2 requests R1

In the Real World

1. Khalti Payment System (Hold-and-Wait + Circular Wait)

   • Problem: Two users (A and B) initiate transfers simultaneously. A locks B’s account while waiting for its own balance update, and B does the same.
   • Solution: Khalti uses atomic transactions (all locks acquired at once) to prevent deadlocks.

2. Daraz Order Fulfillment (Resource Preemption)

   • Problem: Inventory for two orders (P1 and P2) is split across warehouses. P1 holds warehouse X’s stock while waiting for Y, and P2 holds Y while waiting for X.
   • Solution: Daraz’s system preempts by canceling the less urgent order (P2) to free resources for P1.

3. Nepal’s NTC Traffic Lights (Mutual Exclusion + Circular Wait)

   • Problem: At a 4-way intersection without roundabouts, cars from perpendicular roads block each other indefinitely.
   • Solution: NTC’s smart traffic systems now use priority-based preemption (e.g., ambulances get green light by aborting other cars’ "hold").

4. Nepal Rastra Bank’s Loan System (Banker’s Algorithm)

   • Problem: Banks must approve loans without causing deadlocks (e.g., two borrowers waiting for collateral from each other).
   • Solution: The bank uses avoidance by checking if granting a loan leaves the system in a safe state (e.g., "Can all pending loans be fulfilled without deadlock?").

5. Pathao Driver Dispatch (Starvation vs. Deadlock)

   • Problem: Drivers near the same pickup location may starve if the algorithm always picks the closest driver, or deadlock if two drivers wait for each other’s confirmation.
   • Solution: Pathao uses timeouts (preemption) to abort stale requests and fair scheduling to prevent starvation.

Exam Tip

1. Scenario Questions (30% Weight)

   • Format: "Process A holds R1 and waits for R2. Process B holds R2 and waits for R1. Draw the WFG and explain the deadlock."
   • Key: Always label edges clearly (e.g., "P1 → R2" means P1 waits for R2).
   • Common Pitfall: Forgetting to include resources as nodes in the WFG.

2. Banker’s Algorithm (25% Weight)

   • Format: "Given a resource allocation table, check if a request is safe."
   • Steps to Show:
     1. Calculate Need = Max - Allocation.
     2. Simulate completion for each process in order.
     3. If all can finish, it’s safe; else, unsafe.
   • Example Trace:

     Request: P1 asks for (1,0,2).
     New Allocation: P1 = (3,0,2).
     Available becomes (0,2,0).
     Check P0: Needs (0,1,2) → Available (0,2,0) **cannot satisfy** (needs 2 labor, only 0 available).
     → **Unsafe**.
     

3. Prevention vs. Avoidance (20% Weight)

   • Format: "How would you prevent deadlocks in a hospital’s blood bank system?"
   • Answer Structure:
     • Prevention: "Eliminate hold-and-wait by requiring doctors to request all blood types at once."
     • Avoidance: "Use Banker’s algorithm to track blood inventory and patient needs."

4. Real-World Applications (15% Weight)

   • Format: "Explain how deadlocks occur in Nepal’s NTC traffic system and suggest a solution."
   • Must Mention:
     • Conditions: Mutual exclusion (road space), circular wait (perpendicular roads).
     • Solution: Roundabouts (break circular wait) or smart traffic lights (preemption).

5. Recovery Methods (10% Weight)

   • Format: "If a deadlock is detected in a database transaction, what are three recovery options?"
   • Answer:
     1. Abort all transactions involved.
     2. Preempt resources from the youngest transaction.
     3. Rollback to the last safe checkpoint.

Pro Tip for Diagrams:

• For WFG, always use two types of nodes: circles for processes, rectangles for resources.
• For Banker’s algorithm, show tables with columns: Process, Allocation, Max, Need, Available.
• For real-world examples, relate to Nepal: traffic, banking, e-commerce. Examiners love local context!