Deadlock (Conditions, Prevention)

Deadlock (Conditions, Prevention)

Why This Matters

Think of deadlock like a traffic jam where cars are blocking each other in a circle. Car A is waiting for Car B to move, Car B is waiting for Car C to move, and Car C is waiting for Car A to move. None can move, so they're all stuck forever. Deadlock in systems works the same way—processes are waiting for resources held by each other, and none can proceed.

This matters because deadlocks can freeze your system. When processes deadlock, they stop making progress. Users experience hangs. The system becomes unresponsive. Understanding deadlock conditions helps you design systems that avoid deadlocks, or detect and recover from them.

In interviews, when someone asks "How would you design a concurrent system?", they're testing whether you understand deadlocks. Do you know the conditions that cause deadlocks? Can you prevent them? Most engineers don't. They write concurrent code and wonder why the system hangs.

What Engineers Usually Get Wrong

Most engineers think "deadlocks are rare, so I don't need to worry about them." But deadlocks become more likely as concurrency increases. A system that works fine with 10 concurrent requests might deadlock with 1000. Also, deadlocks can be hard to reproduce—they might only happen under specific timing conditions.

Engineers also don't understand that deadlocks require all four conditions (mutual exclusion, hold and wait, no preemption, circular wait). If you can break any one condition, you can prevent deadlocks. For example, if you always acquire locks in the same order, you can't have circular wait, so you can't have deadlocks.

How This Breaks Systems in the Real World

A service was processing orders. Two transactions were trying to update the same rows in different orders. Transaction A locked row 1, then tried to lock row 2. Transaction B locked row 2, then tried to lock row 1. Deadlock. The database detected it and killed one transaction. But if many transactions were doing this, deadlocks became frequent. The service became slow and unreliable. The fix? Always acquire locks in the same order. This prevents circular wait, which prevents deadlocks.

Another story: A service was using locks to protect shared resources. Processes acquired locks in different orders depending on the code path. Under normal load, this worked. But during high traffic, processes started deadlocking. The system became unresponsive. The fix? Always acquire locks in a consistent order (e.g., always lock by resource ID in ascending order). This prevents circular wait.

---

What is Deadlock?

Deadlock is a situation where processes are blocked, each waiting for a resource held by another.

Example:

Process A holds Resource 1, needs Resource 2
Process B holds Resource 2, needs Resource 1

Result: Both processes blocked forever (deadlock)

---

Deadlock Conditions (Coffman Conditions)

Four conditions must all be true for deadlock to occur:

1. Mutual Exclusion

At least one resource must be non-shareable (only one process can use it at a time).

Resource 1: Mutex (only Process A or Process B, not both)

2. Hold and Wait

Process holds at least one resource and waits for another.

Process A: Holds Resource 1, waits for Resource 2

3. No Preemption

Resources cannot be preempted (taken away from process).

Process A holds Resource 1
Cannot be taken away (must be released voluntarily)

4. Circular Wait

Circular chain of processes, each waiting for resource held by next.

Process A → waits for Resource 2 (held by Process B)
Process B → waits for Resource 1 (held by Process A)

---

Deadlock Example

import threading

# Two resources
resource1 = threading.Lock()
resource2 = threading.Lock()

def process_a():
    resource1.acquire()  # Hold Resource 1
    print("Process A: Got Resource 1")
    time.sleep(1)  # Simulate work
    
    resource2.acquire()  # Wait for Resource 2
    print("Process A: Got Resource 2")
    
    # Do work
    resource2.release()
    resource1.release()

def process_b():
    resource2.acquire()  # Hold Resource 2
    print("Process B: Got Resource 2")
    time.sleep(1)  # Simulate work
    
    resource1.acquire()  # Wait for Resource 1
    print("Process B: Got Resource 1")
    
    # Do work
    resource1.release()
    resource2.release()

# Both processes run simultaneously
thread1 = threading.Thread(target=process_a)
thread2 = threading.Thread(target=process_b)

thread1.start()
thread2.start()

# Deadlock: Both processes blocked forever

What happens:

Time 0: Process A acquires Resource 1
Time 0: Process B acquires Resource 2
Time 1: Process A tries to acquire Resource 2 (blocked, B holds it)
Time 1: Process B tries to acquire Resource 1 (blocked, A holds it)
Result: Deadlock (both blocked forever)

---

Deadlock Prevention

Prevent deadlock by breaking one of the four conditions.

1. Break Mutual Exclusion

Make resources shareable (not always possible).

Example: Read-only resources can be shared
But: Write operations need mutual exclusion

2. Break Hold and Wait

Process must acquire all resources at once (or none).

def process_a():
    # Acquire all resources at once
    resource1.acquire()
    resource2.acquire()
    
    try:
        # Do work
        pass
    finally:
        resource2.release()
        resource1.release()

Problem: Resource starvation (process waits for all resources)

3. Break No Preemption

Allow preemption (take resources away).

def process_a():
    while True:
        if resource1.acquire(timeout=1):
            if resource2.acquire(timeout=1):
                # Got both resources
                break
            else:
                resource1.release()  # Release and retry
        time.sleep(0.1)

Problem: Complex, may cause work loss

4. Break Circular Wait

Impose ordering on resources (acquire in same order).

# Always acquire in same order
def process_a():
    resource1.acquire()  # Lower ID first
    resource2.acquire()  # Higher ID second
    # Do work
    resource2.release()
    resource1.release()

def process_b():
    resource1.acquire()  # Same order!
    resource2.acquire()
    # Do work
    resource2.release()
    resource1.release()

Most practical: Easy to implement, prevents deadlock

---

Deadlock Avoidance

Avoid deadlock by not granting resources if it might lead to deadlock.

Banker's Algorithm

Concept: Only grant resource if system remains in safe state.

Safe state: System can allocate resources without deadlock.

Algorithm:

1. Check if request can be granted
2. Check if resulting state is safe
3. If safe: Grant request
4. If unsafe: Deny request (wait)

Example

Available: [3, 3, 2]
Processes:
  P0: Allocation [0, 1, 0], Need [7, 4, 3]
  P1: Allocation [2, 0, 0], Need [1, 2, 2]
  P2: Allocation [3, 0, 2], Need [6, 0, 0]
  P3: Allocation [2, 1, 1], Need [0, 1, 1]
  P4: Allocation [0, 0, 2], Need [4, 3, 1]

Safe sequence: P1 → P3 → P4 → P0 → P2

---

Deadlock Detection

Detect deadlock and recover from it.

Detection Algorithm

1. Build resource allocation graph
2. Detect cycles in graph
3. If cycle exists: Deadlock detected
4. Recover: Kill processes or preempt resources

Resource Allocation Graph

Processes: Circles
Resources: Squares
Edges:
  Process → Resource: Process requests resource
  Resource → Process: Resource allocated to process

Deadlock exists if: Cycle in graph

---

Examples

Deadlock Prevention (Lock Ordering)

import threading

class DeadlockFreeSystem:
    def __init__(self):
        self.locks = {
            'A': threading.Lock(),
            'B': threading.Lock(),
            'C': threading.Lock()
        }
        self.lock_order = ['A', 'B', 'C']  # Ordered
    
    def acquire_locks(self, lock_names):
        # Sort by order
        sorted_locks = sorted(lock_names, key=lambda x: self.lock_order.index(x))
        
        acquired = []
        try:
            for lock_name in sorted_locks:
                self.locks[lock_name].acquire()
                acquired.append(lock_name)
        except:
            # Release acquired locks
            for lock_name in reversed(acquired):
                self.locks[lock_name].release()
            raise
    
    def release_locks(self, lock_names):
        for lock_name in reversed(lock_names):
            self.locks[lock_name].release()

Deadlock Detection

class DeadlockDetector:
    def __init__(self):
        self.wait_for = {}  # process → resource it waits for
        self.holds = {}     # process → resources it holds
    
    def detect_deadlock(self):
        # Build wait-for graph
        graph = {}
        for process, resource in self.wait_for.items():
            # Find process holding this resource
            holder = self.find_holder(resource)
            if holder:
                graph[process] = holder
        
        # Detect cycle (DFS)
        visited = set()
        rec_stack = set()
        
        def has_cycle(node):
            visited.add(node)
            rec_stack.add(node)
            
            if node in graph:
                neighbor = graph[node]
                if neighbor not in visited:
                    if has_cycle(neighbor):
                        return True
                elif neighbor in rec_stack:
                    return True  # Cycle found
            
            rec_stack.remove(node)
            return False
        
        for process in graph:
            if process not in visited:
                if has_cycle(process):
                    return True  # Deadlock detected
        
        return False

---

Common Pitfalls

• Not using lock ordering: Different order causes deadlock. Fix: Always acquire locks in same order
• Nested locks: Acquiring locks in nested functions. Fix: Document lock order, use lock manager
• Timeout not set: Locks wait forever. Fix: Use timeout, detect potential deadlocks
• Not detecting deadlocks: System hangs without detection. Fix: Implement deadlock detection
• Inefficient recovery: Killing all processes. Fix: Kill minimum processes, use preemption

---

Interview Questions

Beginner

Q: What is deadlock and what are the four conditions for deadlock?

A:

Deadlock occurs when processes are blocked forever, each waiting for a resource held by another.

Four Conditions (Coffman Conditions):

1. Mutual Exclusion

   • At least one resource must be non-shareable
   • Only one process can use it at a time

2. Hold and Wait

   • Process holds at least one resource
   • And waits for another resource

3. No Preemption

   • Resources cannot be taken away
   • Must be released voluntarily

4. Circular Wait

   • Circular chain of processes
   • Each waits for resource held by next

All four must be true for deadlock to occur.

Example:

Process A: Holds Resource 1, waits for Resource 2
Process B: Holds Resource 2, waits for Resource 1

Circular wait: A → B → A (deadlock!)

Prevention: Break any one condition to prevent deadlock.

---

Intermediate

Q: Explain how to prevent deadlock by breaking each of the four conditions.

A:

1. Break Mutual Exclusion:

Make resources shareable (not always possible)
Example: Read-only resources can be shared
But: Write operations need mutual exclusion

2. Break Hold and Wait:

Acquire all resources at once (or none)

def process():
    # Acquire all at once
    resource1.acquire()
    resource2.acquire()
    try:
        # Do work
    finally:
        resource2.release()
        resource1.release()

Problem: Resource starvation

3. Break No Preemption:

Allow preemption (take resources away)

def process():
    while True:
        if resource1.acquire(timeout=1):
            if resource2.acquire(timeout=1):
                break
            else:
                resource1.release()  # Release and retry

Problem: Complex, may cause work loss

4. Break Circular Wait:

Impose ordering on resources (acquire in same order)

# Always acquire in same order
def process_a():
    resource1.acquire()  # Lower ID first
    resource2.acquire()  # Higher ID second

def process_b():
    resource1.acquire()  # Same order!
    resource2.acquire()

Most practical: Easy to implement, prevents deadlock

Best practice: Use lock ordering (break circular wait)

---

Senior

Q: Design a deadlock prevention system for a multi-threaded application that handles multiple resources and processes. How do you detect, prevent, and recover from deadlocks?

A:

class DeadlockPreventionSystem {
  private lockManager: LockManager;
  private deadlockDetector: DeadlockDetector;
  private resourceOrder: Map<string, number>;
  
  constructor() {
    this.lockManager = new LockManager();
    this.deadlockDetector = new DeadlockDetector();
    this.resourceOrder = new Map();
  }
  
  // 1. Lock Ordering (Prevention)
  class LockManager {
    async acquireLocks(processId: string, resourceIds: string[]): Promise<void> {
      // Sort by resource order
      const sorted = resourceIds.sort((a, b) => 
        this.getResourceOrder(a) - this.getResourceOrder(b)
      );
      
      const acquired = [];
      try {
        for (const resourceId of sorted) {
          await this.acquireLock(processId, resourceId, { timeout: 5000 });
          acquired.push(resourceId);
        }
      } catch (error) {
        // Release acquired locks
        for (const resourceId of acquired.reverse()) {
          await this.releaseLock(processId, resourceId);
        }
        throw error;
      }
    }
  }
  
  // 2. Deadlock Detection
  class DeadlockDetector {
    private waitFor: Map<string, string>; // process → resource
    private holds: Map<string, string[]>; // process → resources
    
    detectDeadlock(): string[] | null {
      // Build wait-for graph
      const graph = this.buildWaitForGraph();
      
      // Detect cycle (DFS)
      const cycle = this.findCycle(graph);
      
      if (cycle) {
        return cycle; // Deadlock detected
      }
      
      return null;
    }
    
    buildWaitForGraph(): Map<string, string> {
      const graph = new Map();
      
      for (const [process, waitingFor] of this.waitFor.entries()) {
        // Find process holding this resource
        const holder = this.findHolder(waitingFor);
        if (holder) {
          graph.set(process, holder);
        }
      }
      
      return graph;
    }
    
    findCycle(graph: Map<string, string>): string[] | null {
      const visited = new Set();
      const recStack = new Set();
      const path: string[] = [];
      
      const dfs = (node: string): boolean => {
        visited.add(node);
        recStack.add(node);
        path.push(node);
        
        if (graph.has(node)) {
          const neighbor = graph.get(node);
          if (!visited.has(neighbor)) {
            if (dfs(neighbor)) {
              return true;
            }
          } else if (recStack.has(neighbor)) {
            // Cycle found
            return true;
          }
        }
        
        recStack.delete(node);
        path.pop();
        return false;
      };
      
      for (const node of graph.keys()) {
        if (!visited.has(node)) {
          if (dfs(node)) {
            return path; // Cycle path
          }
        }
      }
      
      return null;
    }
  }
  
  // 3. Deadlock Recovery
  class DeadlockRecovery {
    async recover(deadlockedProcesses: string[]): Promise<void> {
      // Strategy 1: Kill processes (one at a time)
      for (const processId of deadlockedProcesses) {
        await this.killProcess(processId);
        if (!this.deadlockDetector.detectDeadlock()) {
          break; // Deadlock resolved
        }
      }
      
      // Strategy 2: Preempt resources
      // Rollback transactions, release resources
    }
    
    async killProcess(processId: string): Promise<void> {
      // Release all resources held by process
      const resources = this.lockManager.getHeldResources(processId);
      for (const resourceId of resources) {
        await this.lockManager.releaseLock(processId, resourceId);
      }
      
      // Kill process
      await this.processManager.kill(processId);
    }
  }
  
  // 4. Timeout-Based Prevention
  class TimeoutPrevention {
    async acquireWithTimeout(resourceId: string, timeout: number): Promise<boolean> {
      const startTime = Date.now();
      
      while (Date.now() - startTime < timeout) {
        if (await this.tryAcquire(resourceId)) {
          return true;
        }
        
        // Check for potential deadlock
        if (this.deadlockDetector.detectDeadlock()) {
          throw new PotentialDeadlockError();
        }
        
        await this.sleep(100);
      }
      
      return false; // Timeout
    }
  }
  
  // 5. Banker's Algorithm (Avoidance)
  class BankersAlgorithm {
    async requestResource(processId: string, resourceId: string): Promise<boolean> {
      // Check if request can be granted
      if (!this.canGrant(processId, resourceId)) {
        return false;
      }
      
      // Simulate allocation
      this.simulateAllocation(processId, resourceId);
      
      // Check if resulting state is safe
      if (this.isSafeState()) {
        // Grant request
        this.allocate(processId, resourceId);
        return true;
      } else {
        // Unsafe: Deny request
        this.undoSimulation(processId, resourceId);
        return false;
      }
    }
    
    isSafeState(): boolean {
      // Check if safe sequence exists
      // (All processes can complete)
      return this.findSafeSequence() !== null;
    }
  }
}

Features:

1. Lock ordering: Prevent circular wait
2. Deadlock detection: Detect cycles in wait-for graph
3. Recovery: Kill processes or preempt resources
4. Timeout: Prevent indefinite waiting
5. Banker's algorithm: Avoid unsafe states

---

Failure Stories You'll Recognize

The Lock Order Deadlock: A service was processing orders. Two transactions were trying to update the same rows in different orders. Transaction A locked row 1, then tried to lock row 2. Transaction B locked row 2, then tried to lock row 1. Deadlock. The database detected it and killed one transaction. But if many transactions were doing this, deadlocks became frequent. The service became slow and unreliable. The fix? Always acquire locks in the same order. This prevents circular wait, which prevents deadlocks.

The Inconsistent Lock Order: A service was using locks to protect shared resources. Processes acquired locks in different orders depending on the code path. Under normal load, this worked. But during high traffic, processes started deadlocking. The system became unresponsive. The fix? Always acquire locks in a consistent order (e.g., always lock by resource ID in ascending order). This prevents circular wait.

The Timeout That Never Happened: A service was waiting for locks without timeouts. When deadlocks occurred, processes waited forever. The system became unresponsive. Users experienced hangs. The fix? Always use timeouts when acquiring locks. If a lock can't be acquired within the timeout, fail fast and retry or return an error. This prevents indefinite waiting.

What Interviewers Are Really Testing

They want to hear you talk about deadlock prevention as breaking conditions, not just avoiding locks. Junior engineers say "avoid locks to prevent deadlocks." Senior engineers say "deadlocks require all four conditions. Break any one to prevent deadlocks. Most practical: always acquire locks in the same order (breaks circular wait). Use timeouts to prevent indefinite waiting. Implement deadlock detection for recovery."

When they ask "How would you design a concurrent system?", they're testing:

• Do you understand the four deadlock conditions?

• Do you know how to prevent deadlocks?

• Can you design systems that avoid or recover from deadlocks?

• Deadlock: Processes blocked forever, each waiting for resource held by another

• Four conditions: Mutual exclusion, hold and wait, no preemption, circular wait (all must be true)

• Prevention: Break any one condition (most practical: break circular wait with lock ordering)

• Avoidance: Banker's algorithm - only grant if safe state

• Detection: Build wait-for graph, detect cycles

• Recovery: Kill processes, preempt resources, rollback transactions

• Best practices: Always acquire locks in same order, use timeouts, implement detection

How InterviewCrafted Will Teach This

We'll teach this through production failures, not definitions. Instead of memorizing "deadlock requires four conditions," you'll learn through scenarios like "why did our system hang when we had high concurrency?"

You'll see how deadlocks affect system reliability and performance. When an interviewer asks "how would you design a concurrent system?", you'll think about deadlock prevention, lock ordering, and recovery strategies—not just "avoid locks."

• Synchronization (Mutex, Semaphore) - How improper use of synchronization primitives can lead to deadlocks
• Process vs Thread - Understanding processes and threads that can deadlock when sharing resources
• Context Switching - How deadlocks affect process scheduling and context switching
• Shared Memory vs Message Passing - Alternative communication mechanisms that can avoid deadlocks
• Scheduling Algorithms - How scheduling relates to deadlock prevention and resource allocation