Topic Overview
Deadlock (Conditions, Prevention)
Understand deadlock conditions (mutual exclusion, hold and wait, no preemption, circular wait) and prevention strategies.
Deadlock occurs when two or more processes are blocked forever, each waiting for a resource held by another. Understanding deadlock conditions is crucial for designing deadlock-free systems.
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):
-
Mutual Exclusion
- At least one resource must be non-shareable
- Only one process can use it at a time
-
Hold and Wait
- Process holds at least one resource
- And waits for another resource
-
No Preemption
- Resources cannot be taken away
- Must be released voluntarily
-
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:
- Lock ordering: Prevent circular wait
- Deadlock detection: Detect cycles in wait-for graph
- Recovery: Kill processes or preempt resources
- Timeout: Prevent indefinite waiting
- Banker's algorithm: Avoid unsafe states
Key Takeaways
- 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