Deadlocks: Conditions, Detection, Prevention & Recovery

TAKEAWAYS:

• A deadlock is a state where processes are blocked forever, each waiting for a resource held by another.
• Four conditions (mutual exclusion, hold-and-wait, no preemption, circular wait) must coexist for a deadlock to occur.
• Resource Allocation Graphs (RAG) visually model deadlocks, while the Banker’s Algorithm ensures safe resource allocation.
• Prevention (e.g., breaking hold-and-wait) and recovery (e.g., process termination) are trade-offs between efficiency and safety.
• Starvation differs from deadlock: processes may never get resources but can still progress over time.
• Real-world examples include banking systems (loan deadlocks) and e-commerce (order processing queues).

1. Introduction to Deadlocks

A deadlock is a situation where two or more processes are blocked indefinitely, each waiting for a resource held by another. Unlike starvation (where a process may never get resources but can still proceed), deadlocks create a circular wait, trapping all involved processes.

Why does this matter? In real-world systems like Nepal’s NEPSE stock exchange or Daraz’s order processing, deadlocks can freeze transactions, causing financial losses or customer dissatisfaction. Even eSewa’s payment systems rely on deadlock-free resource allocation to prevent failed transactions.

2. Necessary Conditions for Deadlock

For a deadlock to occur, all four of these conditions must hold simultaneously:

stateDiagram-v2
    [*] --> Deadlock
    Deadlock --> MutualExclusion: Mutual Exclusion
    Deadlock --> HoldAndWait: Hold-and-Wait
    Deadlock --> NoPreemption: No Preemption
    Deadlock --> CircularWait: Circular Wait

• Mutual Exclusion: At least one resource must be non-sharable (e.g., a printer, a database lock).
• Hold-and-Wait: A process holds at least one resource while waiting for another.
• No Preemption: Resources cannot be forcibly taken from a process (e.g., a file lock).
• Circular Wait: A circular chain of processes exists where each waits for a resource held by the next.

Breaking any one condition prevents deadlock.

3. Resource Allocation Graph (RAG)

A Resource Allocation Graph (RAG) visually represents processes (circles) and resources (squares) to detect deadlocks.

Key Observations:

• If the graph contains a cycle, a deadlock exists.
• Example: In the above graph, P1 → R2 → P2 → R1 → P1 forms a cycle → deadlock.

Worked Example: Consider two processes (P1, P2) and two resources (R1, R2):

• P1 holds R1 and waits for R2.
• P2 holds R2 and waits for R1. Is there a deadlock? Yes, because the RAG forms a cycle (P1 → R2 → P2 → R1 → P1).

4. Banker’s Algorithm (Deadlock Avoidance)

The Banker’s Algorithm ensures that the system never enters an unsafe state by checking if allocating resources would leave the system in a safe sequence.

Key Terms:

• Allocation Matrix (A): Resources currently held by processes.
• Max Matrix (M): Maximum resources a process may request.
• Available Matrix (Av): Resources not held by any process.
• Need Matrix (N): N = M - A (remaining resources a process may need).

Example: Suppose:

• Processes: P1, P2
• Resources: R1, R2 (each has 3 units)
• Allocation:

  A = [1 0; 0 1]  (P1 holds 1 R1, P2 holds 1 R2)
  M = [2 2; 2 2]  (Max requests)
  Av = [1 1]       (Available resources)
  

Is the system safe?

1. Check if any process can finish with Av:
   • P1 needs N1 = [1 2] → Cannot finish (needs 2 R2, only 1 available).
   • P2 needs N2 = [2 1] → Cannot finish.
2. Unsafe state → Deadlock possible.

Solution: Release some resources or deny requests to avoid deadlock.

5. Deadlock Prevention vs. Avoidance vs. Detection & Recovery

Example of Prevention:

• No Hold-and-Wait: Force processes to request all resources at once (inefficient).
• No Circular Wait: Order resources (e.g., always request R1 before R2).

6. Deadlock Recovery Strategies

If a deadlock is detected, recovery involves:

1. Process Termination: Kill one or more processes (risky if they hold critical data).
2. Resource Preemption: Forcefully take resources from processes (requires rollback).
3. Starvation-Free Termination: Prioritize processes to avoid bias.

Example: In Nepal’s banking system, if two branches deadlock over a shared ledger:

• Recovery: Terminate the less critical branch’s transaction or preempt the ledger temporarily.

7. Starvation vs. Deadlock

In the Real World

1. Nepal Rastra Bank (NRB) Loan Processing

   • Idea: Deadlock in resource allocation occurs when two departments (e.g., Loan and Audit) hold each other’s reports indefinitely.
   • Impact: Delays in loan approvals, affecting small businesses.
   • Solution: NRB uses Banker’s Algorithm to ensure safe resource allocation for reports.

2. Daraz Order Fulfillment

   • Idea: Circular wait between warehouse and delivery teams if both hold inventory but wait for each other’s confirmation.
   • Impact: Orders stuck in "processing" state, reducing customer trust.
   • Solution: Daraz enforces no hold-and-wait by requiring full order details upfront.

3. eSewa Payment Gateway

   • Idea: Mutual exclusion on transaction locks can cause deadlocks if two users try to update the same account simultaneously.
   • Impact: Failed payments, refund delays.
   • Solution: eSewa uses timeouts and preemption to break deadlocks automatically.

Exam Tip

• For definitions: Always state all four conditions for deadlock.
• For RAGs: Draw the graph and identify cycles to explain deadlocks.
• For Banker’s Algorithm: Show Need Matrix and safe sequence steps.
• For prevention vs. avoidance: Compare efficiency trade-offs (e.g., prevention wastes resources).
• For recovery: Mention process termination vs. preemption and their risks.
• Real-world link: Always tie examples to Nepal’s banking, e-commerce, or telecom (e.g., NTC’s network resource allocation).

Visual Summary:

flowchart TD
    DeadlockConditions["Four Conditions"] --> MutualExclusion["Mutual Exclusion"]
    DeadlockConditions --> HoldAndWait["Hold-and-Wait"]
    DeadlockConditions --> NoPreemption["No Preemption"]
    DeadlockConditions --> CircularWait["Circular Wait"]
    DeadlockConditions --> RAG["Resource Allocation Graph"]
    RAG --> BankersAlgorithm["Banker’s Algorithm"]
    BankersAlgorithm --> SafeSequence["Safe Sequence"]
    DeadlockRecovery["Recovery"] --> ProcessTermination["Process Termination"]
    DeadlockRecovery --> ResourcePreemption["Resource Preemption"]
    BankersAlgorithm --> DeadlockDetection["Deadlock Detection"]
    DeadlockDetection --> DeadlockRecovery

| Caption: A deadlock in Nepal Rastra Bank’s loan processing system where two departments hold each other’s reports indefinitely. |

| Caption: Circular wait between Daraz’s warehouse and delivery teams, causing order delays. |

| Caption: Mutual exclusion on transaction locks in eSewa, risking deadlocks during high traffic. |