Difficulty: Intermediate
What is a deadlock? State the four necessary conditions and explain how deadlocks can be prevented, avoided, detected or ignored.
A deadlock is a situation where a set of processes are each waiting for a resource held by another in the set, so none can ever proceed. The everyday picture is four cars arriving at a four-way intersection at the same time, each waiting for the car on its right to move first. Everyone has a legitimate reason to wait, and the traffic is stuck forever. In software, the standard example is two threads and two locks: thread 1 holds lock A and wants B, thread 2 holds B and wants A.
A deadlock can occur only if four Coffman conditions hold simultaneously. Mutual exclusion: at least one resource is non-shareable, so only one process can use it at a time. Hold and wait: a process holds at least one resource while waiting to acquire more. No preemption: resources cannot be forcibly taken away; they are released only voluntarily. Circular wait: there is a cycle of processes where each waits for a resource held by the next. All four must be true; break any one and deadlock is impossible. Note that they are necessary but, with single-instance resources, the presence of a cycle is also sufficient.
We can model this with a resource allocation graph: processes as circles, resources as rectangles with dots for instances, a request edge from process to resource and an assignment edge from resource to process. If every resource has a single instance, a cycle means deadlock. With multiple instances, a cycle means only a possible deadlock.
There are four strategies for handling deadlock. Prevention attacks one of the four conditions structurally. You can't eliminate mutual exclusion for inherently exclusive resources like printers, although spooling helps. To break hold and wait, require processes to request all resources at once before starting, or release everything before requesting more; this hurts utilization and risks starvation. To break no preemption, allow the system to take resources away from a waiting process, which works for registers and memory but not for a half-printed page. To break circular wait, impose a total order on resources and require every process to request them in increasing order; this is the most practical technique and is exactly what well-designed multithreaded code does with lock ordering.
Avoidance is less strict: the system examines each request dynamically and grants it only if the resulting state is safe, meaning that some order exists in which all processes can complete. The Banker's algorithm is the standard avoidance method, and it needs to know each process's maximum needs in advance. Detection and recovery allows deadlocks to happen, periodically runs an algorithm to find cycles, and then recovers by killing processes or preempting resources. Ignoring the problem, the ostrich algorithm, is what Unix and Windows effectively do for most resources, because deadlocks are rare and prevention is expensive. It is a legitimate engineering trade-off, and many candidates are surprised that it counts as an answer.
Also distinguish between deadlock, livelock, and starvation. In livelock, threads keep changing state in response to each other but make no progress, like two people in a corridor repeatedly sidestepping the same way. Starvation is unfair denial, while deadlock is complete blockage.
To sum up in an interview: name the four conditions, say that breaking any one prevents deadlock, and offer lock ordering as your practical go-to.
import threading, time
A, B = threading.Lock(), threading.Lock()
def t1_bad():
with A:
time.sleep(0.1)
with B: # waits for B held by t2
print("t1 done")
def t2_bad():
with B:
time.sleep(0.1)
with A: # waits for A held by t1
print("t2 done")
# Deadlock: t1 holds A wants B, t2 holds B wants A.
# Fix: both threads acquire in the same global order (A then B).
def t2_good():
with A:
time.sleep(0.1)
with B:
print("t2 done")Ordering the locks removes the circular wait condition, so the threads can no longer deadlock.
deadlock, Coffman conditions, prevention, avoidance, resource allocation graph