Deadlocks: Conditions, Prevention, Avoidance, Detection & Recovery

TAKEAWAYS:

• Deadlocks occur when four conditions (mutual exclusion, hold-and-wait, no preemption, circular wait) coincide, causing processes to wait indefinitely.
• Prevention eliminates one or more conditions at design time, while avoidance dynamically ensures the system never enters an unsafe state.
• Detection algorithms like the Wait-For Graph identify deadlocks at runtime, and recovery involves terminating processes or preempting resources.
• Banker’s algorithm is a classic avoidance strategy that checks resource allocation safety before granting requests.
• Real-world deadlocks appear in eSewa payment queues, Ncell network routing, and Kathmandu traffic jams due to resource contention.

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. Deadlocks are common in systems with shared resources (CPU, memory, I/O devices, files).

Four Necessary Conditions for Deadlock

For a deadlock to occur, all four conditions 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 held by others.
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 process in the chain.

stateDiagram-v2
    [*] --> Idle
    Idle --> Allocating
    Allocating --> Requesting
    Requesting --> Blocked: If deadlock occurs
    Blocked --> [*]
    Allocating --> Release: Resources freed
    Requesting --> Granted: Resources allocated

Real-World Examples of Deadlocks

1. eSewa Payment System

• Scenario: Two users try to transfer money simultaneously. User A locks User B’s account while waiting for User A’s balance update, and User B locks User A’s account while waiting for User B’s balance update.
• Result: Both transactions hang, and neither user can complete the payment.
• Solution: eSewa uses timeouts and retry mechanisms to break deadlocks.

2. Ncell Network Routing

• Scenario: Two routers hold partial routes to each other’s packets, waiting indefinitely for the other to release the next hop.
• Result: Data packets get stuck in a loop, causing network congestion.
• Solution: Ncell implements deadlock detection in routing protocols to reroute traffic.

3. Kathmandu Traffic Jam

• Scenario: Four roads intersect, and each driver holds the right-of-way for the next road while waiting for the previous one.
• Result: Vehicles form a circular wait, causing gridlock.
• Solution: Traffic lights use priority scheduling to break the circular wait.

Deadlock Prevention

Prevention ensures that at least one of the four conditions cannot occur. This is done at design time and may reduce system efficiency.

Strategies

Example: Bank Loan System

• A customer requests a loan of ₹50,000.
• The bank reserves all required funds before processing.
• If funds are insufficient, the request is rejected immediately, preventing deadlock.

Deadlock Avoidance

Avoidance dynamically ensures the system never enters an unsafe state (a state where a deadlock is possible). The Banker’s Algorithm is the most famous avoidance technique.

Banker’s Algorithm

1. Define:

   • Available: Resources currently free.
   • Max: Maximum demand a process can make.
   • Allocation: Resources currently allocated.
   • Need: Remaining resources a process may request (Need = Max - Allocation).

2. Safety Check:

   • Before granting a request, the algorithm checks if the system can still reach a safe state.
   • A safe state is one where all processes can complete without deadlock.

sequenceDiagram
    Process->>OS: Request Resources
    OS->>OS: Check Safety (Banker's Algorithm)
    alt Safe State
        OS->>Process: Grant Resources
    else Unsafe State
        OS->>Process: Deny Request
    end

Worked Example: Banker’s Algorithm

Resources: 3 units of R1, 2 units of R2. Processes:

Available: (1, 1)

Request from P0: (1, 1)

• New Allocation: (2, 1)
• New Need: (1, 1)
• Available: (0, 0)

Check Safety:

1. P2 can run (Need ≤ Available: (1,1) ≤ (0,0)? No → Try another order).
2. P1 can run (Need (2,1) ≤ Available (0,0)? No).
3. P0 can run (Need (1,1) ≤ Available (0,0)? No).

Result: Unsafe state → Deny request.

Deadlock Detection and Recovery

If prevention/avoidance is too restrictive, detection identifies deadlocks at runtime, and recovery resolves them.

Detection: Wait-For Graph

A directed graph where:

• Nodes = Processes.
• Edge P→Q = P is waiting for Q.

Deadlock exists if the graph has a cycle.

graph TD
    P0["Process 0"] --> P1["Process 1"]
    P1 --> P2["Process 2"]
    P2 --> P0

Example: Ncell Network Deadlock

• Router A waits for Router B’s route.
• Router B waits for Router C’s route.
• Router C waits for Router A’s route.
• Cycle detected → Deadlock.

Recovery Techniques

Example: Daraz Order Deadlock

• Scenario: Two users request the same out-of-stock item. Both lock the inventory while waiting for payment confirmation.
• Recovery: Daraz rolls back one order and notifies the user.

Comparison: Prevention vs. Avoidance vs. Detection

Exam Tip

1. Memorize the Four Conditions: Always check if all four are present in exam questions.
2. Banker’s Algorithm: Know how to compute Need, Available, and Safety Sequence.
3. Wait-For Graph: Draw it correctly to identify cycles (deadlocks).
4. Real-World Links: Relate deadlocks to banks (loans), e-commerce (inventory), and traffic systems.
5. Recovery Methods: Be ready to explain process termination, preemption, and rollback with examples.