Deadlocks: Conditions, Prevention, Avoidance & Recovery

TAKEAWAYS:

• Deadlocks occur only when all four conditions (mutual exclusion, hold-and-wait, no preemption, circular wait) are met simultaneously.
• Prevention (breaking one condition) is stricter than avoidance (using algorithms like Banker’s) or recovery (killing processes/resources).
• Resource allocation graphs visually detect deadlocks by identifying cycles.
• Starvation differs from deadlock: starvation is indefinite postponement, while deadlock is a circular wait.
• Preemptable resources (e.g., CPU) can be forcibly taken; non-preemptable (e.g., printers) cannot.
• Deadlock recovery prioritizes minimal process termination or resource preemption.

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. No process can proceed, and the system halts.

The Four Necessary Conditions

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

1. Mutual Exclusion: At least one resource must be non-sharable (only one process can use it at a time).
2. Hold-and-Wait: A process holds at least one resource while waiting for additional resources.
3. No Preemption: Resources cannot be forcibly taken from a process; they must be released voluntarily.
4. Circular Wait: A circular chain of processes exists, where each process waits for a resource held by the next.

Real-World Examples of Deadlocks

1. Banking Systems (Loan Processing)

• Scenario: Two customers, A and B, apply for loans. A’s loan requires collateral from B, and B’s loan requires collateral from A.
• Deadlock: Both banks hold partial approvals, waiting for the other’s collateral. No loan is processed.
• How it uses deadlock: Circular wait (A → B → A) + hold-and-wait (both hold partial approvals).

2. E-Commerce Order Fulfillment (Daraz/Khalti)

• Scenario: A user’s order requires both inventory update (Process 1) and payment processing (Process 2). Process 1 locks the inventory while waiting for payment confirmation, and Process 2 locks the payment system while waiting for inventory confirmation.
• Deadlock: Both processes are stuck, and the order is never fulfilled.
• How it uses deadlock: Mutual exclusion (inventory/payment locks) + circular wait (1 → 2 → 1).

3. Traffic Systems (Kathmandu Roads)

• Scenario: Two vehicles, X and Y, enter an intersection from perpendicular roads. X has the green light but waits for Y to move, while Y also waits for X.
• Deadlock: Neither vehicle proceeds, causing a gridlock.
• How it uses deadlock: Mutual exclusion (road space) + circular wait (X → Y → X).

Worked Example: Deadlock Trace

Given:

• Processes: A, B, C
• Resources: X, Y, Z
• Events:
  1. A requests X (granted).
  2. B requests Y (granted).
  3. C requests Z (granted).
  4. A requests Y (waiting, held by B).
  5. B requests Z (waiting, held by C).
  6. C requests X (waiting, held by A).

Resource Allocation Graph:

graph TD
    A["Process A"] -->|"holds"| X["Resource X"]
    B["Process B"] -->|"holds"| Y["Resource Y"]
    C["Process C"] -->|"holds"| Z["Resource Z"]
    A -->|"waits for"| Y
    B -->|"waits for"| Z
    C -->|"waits for"| X

Analysis:

• A circular wait exists: A → Y (held by B) → B → Z (held by C) → C → X (held by A).
• Deadlock detected because all four conditions are met.

Deadlock Handling Strategies

Prevention Techniques

Break one of the four conditions to prevent deadlocks:

1. Eliminate Mutual Exclusion:

   • Allow resources to be shared (e.g., read-only files).
   • Example: Multiple processes can read a file simultaneously, but only one can write.

2. Eliminate Hold-and-Wait:

   • Require processes to request all resources at once or release all held resources before requesting new ones.
   • Example: A bank loan system where a customer must provide all collateral upfront.

3. Allow Preemption:

   • Forcefully take resources from processes (e.g., rollback in databases).
   • Example: A printer can be preempted and reassigned to another process if the current job is stuck.

4. Eliminate Circular Wait:

   • Impose a total ordering of resources (e.g., processes request resources in increasing order of IDs).
   • Example: In a library, books are requested by Dewey Decimal number to avoid circular waits.

Avoidance Algorithms

Banker’s Algorithm

Ensures the system never enters an unsafe state (a state where deadlock is possible).

Steps:

1. Define a safe sequence where all processes can complete without deadlock.
2. Use the allocation matrix, request matrix, and available resources to check if granting a request keeps the system safe.

Example:

• Available: [1, 1, 1] (X, Y, Z)
• Max Needs: A=[2,1,2], B=[1,2,2], C=[1,1,2]
• Current Allocation: A=[1,0,1], B=[0,1,0], C=[0,0,1]
• Request: A requests [0,1,0]

Check:

1. Simulate granting A’s request: New allocation for A = [1,1,1].
2. Check if remaining resources can satisfy all processes’ max needs.
3. If yes, grant the request; else, deny it.

sequenceDiagram
    participant A as Process A
    participant Sys as System
    A->>Sys: Request [0,1,0]
    Sys->>Sys: Check safe state (simulate allocation)
    alt Safe
        Sys-->>A: Grant
    else Unsafe
        Sys-->>A: Deny
    end

Detection and Recovery

Detection

Use resource allocation graphs to detect cycles (deadlocks).

• Wait-for graph: Nodes = processes; edges = "waits for."
• If a cycle exists → deadlock.

Recovery

1. Process Termination:
   • Kill processes until the cycle is broken.
   • Priority: Kill the process with the least progress or highest cost to terminate.
2. Resource Preemption:
   • Take resources from processes and assign them to others.
   • Rollback: Save process state and restart later.
3. Resource Allocation:
   • Assign resources to the process that needs them most urgently.

Example:

• In a hospital system, if two doctors are stuck waiting for each other’s equipment, terminate the less critical procedure first.

Deadlock vs. Starvation

Exam Tip

1. Memorize the Four Conditions: Always check if all four are present in exam questions.
2. Draw Resource Allocation Graphs: Visuals (like the mermaid graph above) are worth marks. Label edges clearly (e.g., "holds," "waits for").
3. Compare Prevention/Avoidance/Recovery: Know when to use each (e.g., prevention is overkill for some systems; avoidance is used in banking).
4. Worked Examples: Practice traces like the one above. Examiners love step-by-step reasoning.
5. Real-World Links: Connect concepts to systems like eSewa (payment locks), Daraz (order deadlocks), or NTC (traffic signals). Even if not asked, this shows deep understanding.