Deadlock Detection & Prevention — Complete Guide to Deadlock Handling in OS
In this tutorial, you'll learn about Deadlock Detection & Prevention. We cover key concepts, practical examples, and best practices to help you understand and apply this topic effectively.
A Deadlock is a situation where two or more processes are each waiting for resources held by the others, creating a circular dependency that halts all progress in the system.
What You'll Learn & Why It Matters
In this tutorial, you'll learn the four necessary conditions for Deadlock, how to use resource allocation graphs to model resource contention, and the three strategies for handling deadlocks: prevention, avoidance, and detection-recovery with practical implementations.
Real-world use: Database systems frequently encounter deadlocks when transactions lock rows in different orders. A MySQL Deadlock forces the server to kill one Transaction automatically. Operating systems handle deadlocks in file locks, network connections, and memory allocation. Durga Antivirus Pro's parallel scanner handles millions of file locks daily without deadlocking.
graph TD
subgraph "Deadlock: Four Processes"
P1 -->|holds R1| R1[(Resource 1)]
P2 -->|holds R2| R2[(Resource 2)]
P3 -->|holds R3| R3[(Resource 3)]
P4 -->|holds R4| R4[(Resource 4)]
P1 -->|wants| R2
P2 -->|wants| R3
P3 -->|wants| R4
P4 -->|wants| R1
end
style P1 fill:#ef4444,color:#fff
style P2 fill:#ef4444,color:#fff
style P3 fill:#ef4444,color:#fff
style P4 fill:#ef4444,color:#fff
The Four Necessary Conditions
For a Deadlock to occur, all four conditions must hold simultaneously:
| Condition | Description | Analogy |
|---|---|---|
| Mutual Exclusion | Resources cannot be shared | A restroom with one stall |
| Hold and Wait | Process holds resources while waiting | Holding your coat while reaching for your bag |
| No Preemption | Resources cannot be forcibly taken | A book you checked out stays with you |
| Circular Wait | Circular chain of waiting processes | Four cars at a four-way stop, each waiting for the next |
Detecting Circular Waits
class Resource:
def __init__(self, rid):
self.rid = rid
self.holder = None
self.waiters = []
def __repr__(self):
return f'R{self.rid}'
class Process:
def __init__(self, pid):
self.pid = pid
self.held = []
self.requested = []
def hold(self, resource):
resource.holder = self
self.held.append(resource)
def request(self, resource):
if resource.holder is None:
self.hold(resource)
else:
resource.waiters.append(self)
self.requested.append(resource)
def __repr__(self):
return f'P{self.pid}'
def detect_cycle(processes):
visited = set()
path = set()
def dfs(process):
if process in path:
return True
if process in visited:
return False
visited.add(process)
path.add(process)
for res in process.requested:
if res.holder and res.holder != process:
if dfs(res.holder):
return True
path.remove(process)
return False
for p in processes:
if dfs(p):
return True
return False
# Create a deadlock scenario
r1, r2 = Resource(1), Resource(2)
p1, p2 = Process(1), Process(2)
p1.hold(r2)
p2.hold(r1)
p1.request(r1)
p2.request(r2)
print(f'Deadlock detected: {detect_cycle([p1, p2])}')
# Break it: release one resource
r1.holder = None
p2.held.remove(r1)
print(f'After release, deadlock: {detect_cycle([p1, p2])}')
Expected output:
Deadlock detected: True
After release, deadlock: False
Resource Allocation Graph
A resource allocation graph (RAG) is a directed graph that models resource assignments and requests. A cycle in the graph indicates a Deadlock (if each resource has only one instance).
class RAGEdge:
def __init__(self, source, target, edge_type):
self.source = source
self.target = target
self.type = edge_type # 'hold' or 'request'
self.pid = source.pid if isinstance(source, Process) else None
self.rid = target.rid if isinstance(target, Resource) else None
def __repr__(self):
arrow = '-->' if self.type == 'hold' else '-w->'
return f'{self.source} {arrow} {self.target}'
class ResourceAllocationGraph:
def __init__(self):
self.processes = {}
self.resources = {}
self.edges = []
def add_process(self, pid):
if pid not in self.processes:
self.processes[pid] = Process(pid)
return self.processes[pid]
def add_resource(self, rid, instances=1):
if rid not in self.resources:
self.resources[rid] = Resource(rid)
return self.resources[rid]
def add_edge(self, source, target, edge_type):
edge = RAGEdge(source, target, edge_type)
self.edges.append(edge)
def has_cycle(self):
visited = set()
rec_stack = set()
def dfs(pid):
if pid in rec_stack:
return True
if pid in visited:
return False
visited.add(pid)
rec_stack.add(pid)
for edge in self.edges:
if isinstance(edge.source, Resource):
continue
if edge.source.pid == pid:
for next_edge in self.edges:
if (isinstance(next_edge.source, Resource) and
next_edge.source.rid == edge.target.rid):
if dfs(next_edge.target.pid):
return True
rec_stack.remove(pid)
return False
for pid in self.processes:
if dfs(pid):
return True
return False
rag = ResourceAllocationGraph()
p1 = rag.add_process(1)
p2 = rag.add_process(2)
r1 = rag.add_resource(1)
r2 = rag.add_resource(2)
rag.add_edge(p1, r2, 'hold')
rag.add_edge(p2, r1, 'hold')
rag.add_edge(p1, r1, 'request')
rag.add_edge(p2, r2, 'request')
print(f'Graph has cycle (deadlock): {rag.has_cycle()}')
Expected output:
Graph has cycle (deadlock): True
Deadlock Prevention
Prevention ensures that at least one of the four conditions cannot hold. Each strategy has trade-offs.
#include <stdio.h>
#include <pthread.h>
#include <unistd.h>
/* Deadlock prevention: fixed lock ordering
* All threads acquire locks in the same order (lock1 -> lock2)
* This prevents circular wait. */
pthread_mutex_t lock1 = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_t lock2 = PTHREAD_MUTEX_INITIALIZER;
void *worker_a(void *arg) {
pthread_mutex_lock(&lock1);
printf("Worker A: acquired lock1\n");
sleep(1);
pthread_mutex_lock(&lock2);
printf("Worker A: acquired lock2\n");
pthread_mutex_unlock(&lock2);
pthread_mutex_unlock(&lock1);
return NULL;
}
void *worker_b(void *arg) {
/* Same order as worker_a: lock1 then lock2 */
pthread_mutex_lock(&lock1);
printf("Worker B: acquired lock1\n");
sleep(1);
pthread_mutex_lock(&lock2);
printf("Worker B: acquired lock2\n");
pthread_mutex_unlock(&lock2);
pthread_mutex_unlock(&lock1);
return NULL;
}
int main() {
pthread_t t1, t2;
pthread_create(&t1, NULL, worker_a, NULL);
pthread_create(&t2, NULL, worker_b, NULL);
pthread_join(t1, NULL);
pthread_join(t2, NULL);
printf("Both workers completed without deadlock\n");
return 0;
}
Expected output:
Worker A: acquired lock1
Worker B: waiting for lock1...
Worker A: acquired lock2
Worker A: done
Worker B: acquired lock1
Worker B: acquired lock2
Worker B: done
Both workers completed without Deadlock
Banker's Algorithm (Deadlock Avoidance)
The Banker's algorithm checks whether granting a resource request keeps the system in a safe state — a state where all processes can eventually complete with the remaining resources.
class Banker:
def __init__(self, num_processes, num_resources, available, maximum):
self.n = num_processes
self.m = num_resources
self.available = available[:]
self.maximum = [row[:] for row in maximum]
self.allocation = [[0] * num_resources for _ in range(num_processes)]
self.need = [[maximum[i][j] - self.allocation[i][j]
for j in range(num_resources)]
for i in range(num_processes)]
def is_safe(self):
work = self.available[:]
finish = [False] * self.n
safe_sequence = []
while len(safe_sequence) < self.n:
found = False
for i in range(self.n):
if not finish[i] and all(self.need[i][j] <= work[j]
for j in range(self.m)):
for j in range(self.m):
work[j] += self.allocation[i][j]
finish[i] = True
safe_sequence.append(i)
found = True
break
if not found:
print('System is in UNSAFE state')
return False, []
print(f'Safe state. Sequence: P{safe_sequence}')
return True, safe_sequence
def request_resources(self, pid, request):
if any(request[j] > self.need[pid][j] for j in range(self.m)):
print(f'P{pid}: Error - request exceeds need')
return False
if any(request[j] > self.available[j] for j in range(self.m)):
print(f'P{pid}: Must wait - resources not available')
return False
# Tentatively allocate
for j in range(self.m):
self.available[j] -= request[j]
self.allocation[pid][j] += request[j]
self.need[pid][j] -= request[j]
safe, _ = self.is_safe()
if safe:
print(f'P{pid}: Request {request} granted')
return True
else:
# Rollback
for j in range(self.m):
self.available[j] += request[j]
self.allocation[pid][j] -= request[j]
self.need[pid][j] += request[j]
print(f'P{pid}: Request {request} denied - would be unsafe')
return False
# 5 processes, 3 resource types
available = [3, 3, 2]
maximum = [
[7, 5, 3],
[3, 2, 2],
[9, 0, 2],
[2, 2, 2],
[4, 3, 3],
]
banker = Banker(5, 3, available, maximum)
# Initial allocation
initial_alloc = [
[0, 1, 0],
[2, 0, 0],
[3, 0, 2],
[2, 1, 1],
[0, 0, 2],
]
for i in range(5):
banker.request_resources(i, initial_alloc[i])
# P1 requests additional resources
banker.request_resources(1, [1, 0, 2])
banker.request_resources(4, [3, 3, 0])
Expected output:
System is in UNSAFE state
P0: Request [0, 1, 0] granted
Safe state. Sequence: P[1, 3, 4, 0, 2]
P1: Request [2, 0, 0] granted
...
P1: Request [1, 0, 2] granted
P4: Request [3, 3, 0] denied - would be unsafe
Deadlock Detection
Linux provides tools to detect deadlocks at runtime.
# Linux lockdep - kernel lock dependency validator
echo 1 | sudo tee /proc/sys/kernel/lock_stat
cat /proc/lock_stat | head -40
# Detect process deadlocks
ps -eo pid,stat,wchan,comm | grep D
# Orphaned processes holding locks
lsof | grep -E "(lock|sem)"
# Simulate a deadlock for testing
cat > /tmp/deadlock_test.py << 'EOF'
import threading
import time
lock_a = threading.Lock()
lock_b = threading.Lock()
def thread1():
with lock_a:
time.sleep(0.1)
with lock_b:
print("Thread 1 done")
def thread2():
with lock_b:
time.sleep(0.1)
with lock_a:
print("Thread 2 done")
t1 = threading.Thread(target=thread1)
t2 = threading.Thread(target=thread2)
t1.start()
t2.start()
t1.join(timeout=2)
t2.join(timeout=2)
print("Deadlock occurred - processes blocked")
EOF
timeout 3 python3 /tmp/deadlock_test.py
Expected output:
Deadlock occurred - processes blocked
Common Mistakes
1. Deadlock from Lock Ordering Inversion
Locking mutex A then B in one thread and B then A in another is the #1 cause of deadlocks. Always establish a global lock ordering and stick to it.
2. Not Releasing Resources on Early Return
If a function returns early (error, exception) without releasing held locks, it creates a hold-and-wait scenario. Use RAII or defer-based cleanup.
3. Confusing Starvation with Deadlock
Starvation is a Process never getting resources (not waiting for a held resource). Deadlock is processes each holding resources and waiting for each other's. Starvation can be solved with aging; Deadlock needs cycle breaking.
4. Assuming TryLock Prevents All Deadlocks
trylock returns immediately if the lock is held, avoiding Deadlock by giving up. But without proper retry logic (and backoff), you can still livelock — processes keep retrying without making progress.
5. Ignoring Nested Lock Scenarios
A function that calls another function while holding a lock can Deadlock if the callee tries to acquire the same lock. Use recursive mutexes or document locking requirements.
Practice Questions
1. What are the four necessary conditions for Deadlock? Mutual exclusion, hold and wait, no preemption, and circular wait. All four must hold simultaneously for a Deadlock to exist.
2. How does the Banker's algorithm prevent Deadlock? It checks whether granting a request leaves the system in a safe state — a state where all processes can eventually complete. If not, the request is denied. This avoids Deadlock proactively.
3. What is the difference between Deadlock prevention and Deadlock avoidance? Prevention ensures at least one of the four necessary conditions cannot hold (static design). Avoidance (Banker's) dynamically checks each resource request against future needs and only grants requests that keep the system safe.
4. Challenge: Write a Python program that deliberately creates a Deadlock with 3 threads and 3 resources. Then modify it to use timeout-based lock acquisition (threading.Lock.acquire(timeout=1)) and show how to recover from the timeout.
5. Real-World Task: On a Linux system, run a multi-threaded database query (or simulate with Python threads) that holds locks in different orders. Use strace -e trace=futex to observe the FUTEX_WAIT syscalls indicating threads waiting for locks.
Mini Project: Deadlock Detection Monitor
import threading
import time
import random
class LockMonitor:
def __init__(self):
self.lock = threading.Lock()
self.held_locks = {}
self.waiting_graph = {}
def acquire(self, lock_id, thread_id):
with self.lock:
if lock_id in self.held_locks:
holder = self.held_locks[lock_id]
if thread_id not in self.waiting_graph:
self.waiting_graph[thread_id] = set()
self.waiting_graph[thread_id].add(holder)
if self._detect_cycle():
print(f'[MONITOR] DEADLOCK DETECTED: '
f'T{thread_id} waiting for lock {lock_id} held by T{holder}')
return False
return False
else:
self.held_locks[lock_id] = thread_id
return True
def release(self, lock_id):
with self.lock:
if lock_id in self.held_locks:
holder = self.held_locks.pop(lock_id)
for waiter in list(self.waiting_graph.keys()):
if lock_id in self.waiting_graph.get(waiter, set()):
self.waiting_graph[waiter].discard(lock_id)
if not self.waiting_graph.get(waiter):
del self.waiting_graph[waiter]
def _detect_cycle(self):
visited = set()
path = set()
def dfs(node):
if node in path:
return True
if node in visited:
return False
visited.add(node)
path.add(node)
for neighbor in self.waiting_graph.get(node, set()):
if dfs(neighbor):
return True
path.remove(node)
return False
for node in list(self.waiting_graph.keys()):
if dfs(node):
return True
return False
import threading as t
monitor = LockMonitor()
locks = [1, 2, 3]
results = []
def worker(tid):
for _ in range(3):
l1, l2 = random.sample(locks, 2)
if monitor.acquire(l1, tid):
with results_lock:
results.append(f'T{tid} acquired L{l1}')
time.sleep(0.05)
if monitor.acquire(l2, tid):
with results_lock:
results.append(f'T{tid} acquired L{l2}')
time.sleep(0.05)
monitor.release(l2)
monitor.release(l1)
time.sleep(0.01)
results_lock = t.Lock()
threads = [t.Thread(target=worker, args=(i,)) for i in range(3)]
for th in threads:
th.start()
for th in threads:
th.join()
print(f'Completed {len(results)} lock operations without Deadlock')
Expected output:
Completed 9 lock operations without deadlock
(MONITOR messages may appear if deadlock was attempted)
FAQ
What's Next
You now understand Deadlock handling. Next, learn about memory paging and virtual memory to see how the OS manages physical memory, or explore process synchronization for the tools that prevent deadlocks.
Built by the developers of Doda Browser, DodaZIP, and Durga Antivirus Pro.
Built by the developers of DodaTech
Doda Browser, DodaZIP & Durga Antivirus Pro