Deadlock: conditions, prevention and avoidance
50 min · Intermediate
Need help? Ask a tutor on WhatsApp (opens in a new tab)Deadlock is an interviewer favourite because it mixes a definition, a real example, four conditions and a small calculation. They check that you can list all four conditions and say which one each fix breaks.
The four Coffman conditions with a real-life example
Deadlock is a state where every process in a set is waiting for a resource held by another process in the same set, so none of them can ever continue.
The program below plays out two roommates with two locks: Asha holds the extension board and wants the charger, Bhavna holds the charger and wants the board.
Example 1 · Two threads in a circular wait
import threading
board = threading.Lock() # extension boardcharger = threading.Lock() # laptop chargerboth_holding = threading.Barrier(2)both_tried = threading.Barrier(2)report = []
def roommate(name, first, second, wanted): with first: # hold one resource both_holding.wait() # wait until both roommates hold one got = second.acquire(timeout=0.2) if got: second.release() both_tried.wait() # nobody lets go before both have tried report.append(f"{name} got the {wanted}" if got else f"{name} gave up waiting for the {wanted}")
asha = threading.Thread(target=roommate, args=("Asha", board, charger, "charger"))bhavna = threading.Thread(target=roommate, args=("Bhavna", charger, board, "board"))asha.start()bhavna.start()asha.join()bhavna.join()print(*sorted(report), sep="\n")Asha gave up waiting for the charger Bhavna gave up waiting for the board
What this code does
- All four conditions hold: locks are exclusive, each thread holds one while waiting for the other, nobody takes a lock away, and the waits form a circle.
- With a plain
acquire()both threads would wait forever.acquire(timeout=0.2)lets them give up, which breaks the no-preemption condition (each releases what it holds).
A deadlock can happen only if all four Coffman conditions hold at the same time. Remove any one and deadlock becomes impossible, which is the basis of prevention.
- Mutual exclusion: a resource can be used by only one process at a time (one charger).
- Hold and wait: a process holds one resource while waiting for another.
- No preemption: a resource cannot be taken away; it is released only voluntarily.
- Circular wait: P1 waits for P2, P2 waits for P3, ..., Pn waits for P1.
Order of execution
How the deadlock forms
Put the roommates' story in the order it happens.
Resource allocation graphs
RAG (resource allocation graph) draws processes and resources as nodes, with a request edge from a process to a resource and an assignment edge from a resource to its holder.
The program below stores a wait-for graph, where an edge P1 to P2 means P1 waits for something P2 holds, and uses a depth-first search to find a cycle in two small graphs.
Example 2 · Finding a cycle in a wait-for graph
def has_cycle(wait_for, node, state): state[node] = 1 # 1 = on the current path for nxt in wait_for.get(node, []): s = state.get(nxt, 0) if s == 1: return True # back on the path: cycle if s == 0 and has_cycle(wait_for, nxt, state): return True state[node] = 2 # 2 = fully explored return False
def deadlocked(wait_for): state = {} return any(state.get(p, 0) == 0 and has_cycle(wait_for, p, state) for p in wait_for)
g1 = {"P1": ["P2"], "P2": ["P3"], "P3": []}g2 = {"P1": ["P2"], "P2": ["P3"], "P3": ["P1"]}print("P1->P2->P3: deadlock =", deadlocked(g1))print("P1->P2->P3->P1: deadlock =", deadlocked(g2))P1->P2->P3: deadlock = False P1->P2->P3->P1: deadlock = True
What this code does
- Each edge means "waits for a resource held by". A depth-first search that returns to a node still on its current path has found a cycle.
- With single-instance resources, the cycle in the second graph is a deadlock. This is how detection algorithms work, run periodically or when CPU use drops.
A request edge P → R means P is waiting for R; an assignment edge R → P means R is held by P. With single-instance resources the graph can shrink into a wait-for graph with only processes.
If the graph has no cycle, there is no deadlock. With single-instance resources, a cycle means deadlock. With several instances per resource, a cycle means deadlock is possible but not certain, because another holder may release an instance.
Find the bug
Read the graph
Each reading of a graph has one wrong line. Click it.
Single-instance resources. R1 is held by P1, P2 holds R2.
Round 1 of 2Prevention vs avoidance vs detection and recovery
Deadlock prevention breaks one of the four Coffman conditions by design, so a deadlock can never happen; avoidance instead checks every request at run time.
The program below makes two threads take two locks in one fixed order, so the cycle of waits from the first example can never form.
Example 3 · Prevention: always lock in the same order
import threading
board = threading.Lock() # resource #1charger = threading.Lock() # resource #2
def use_both(name): with board: # everyone takes #1 first... with charger: # ...then #2 print(name, "charged the laptop")
asha = threading.Thread(target=use_both, args=("Asha",))asha.start()asha.join()bhavna = threading.Thread(target=use_both, args=("Bhavna",))bhavna.start()bhavna.join()print("No deadlock: both finished")Asha charged the laptop Bhavna charged the laptop No deadlock: both finished
What this code does
- Numbering resources and always requesting them in increasing order breaks circular wait: nobody can hold #2 while waiting for #1.
- The joins only make the print order fixed for this page; the ordering rule is what prevents deadlock even when both threads run at the same time.
Prevention breaks one condition by design, avoidance grants a request only if the system stays in a safe state, and detection and recovery lets deadlocks happen, finds them and then kills processes or preempts resources. Many general-purpose OSs mostly ignore deadlock in user programs (the "ostrich" approach) because it is rare and prevention is costly.
- Break hold and wait: request all resources at once (poor utilisation).
- Break no preemption: if a request fails, release what you hold and retry.
- Break circular wait: number all resources and always request in increasing order (the most practical).
- Mutual exclusion usually cannot be broken: a printer cannot print two jobs at once.
Predict the output
Lock ordering
Two transfers use the rule "lock the lower account number first".
A transfer from account 7 to account 3. Which locks does it take, and in what order?
Banker's algorithm worked example (safe sequence)
Safe state is a state in which some order of the processes, a safe sequence, lets every process get its remaining need, finish and release its resources.
The program below runs Banker's algorithm on the classic data: three resource types, five processes. It checks for a safe sequence, then tests two new requests.
Example 4 · Banker's algorithm: safety check and requests
def safe_sequence(available, alloc, need): work = available[:] done, order = set(), [] progress = True while progress: progress = False for i in range(len(alloc)): if i not in done and all(n <= w for n, w in zip(need[i], work)): work = [w + a for w, a in zip(work, alloc[i])] # P_i finishes done.add(i) order.append(f"P{i}") progress = True return order if len(order) == len(alloc) else None # None = unsafe
def request(p, req, available, alloc, need): for j, amount in enumerate(req): if amount > need[p][j]: return "error: more than declared max" if amount > available[j]: return "wait: not enough available" av = [a - x for a, x in zip(available, req)] # pretend to grant al = [row[:] for row in alloc] nd = [row[:] for row in need] al[p] = [a + x for a, x in zip(al[p], req)] nd[p] = [n - x for n, x in zip(nd[p], req)] seq = safe_sequence(av, al, nd) return "deny: state would be unsafe" if seq is None else f"grant, safe sequence {seq}"
alloc = [[0, 1, 0], [2, 0, 0], [3, 0, 2], [2, 1, 1], [0, 0, 2]]maximum = [[7, 5, 3], [3, 2, 2], [9, 0, 2], [2, 2, 2], [4, 3, 3]]available = [3, 3, 2]need = [[m - a for m, a in zip(mrow, arow)] for mrow, arow in zip(maximum, alloc)]
for i, row in enumerate(need): print(f"Need P{i} = {row}")print("Safe sequence:", safe_sequence(available, alloc, need))print("P1 requests [1, 0, 2]:", request(1, [1, 0, 2], available, alloc, need))print("P2 requests [4, 0, 0]:", request(2, [4, 0, 0], available, alloc, need))print("P4 requests [3, 3, 0]:", request(4, [3, 3, 0], available, alloc, need))Need P0 = [7, 4, 3] Need P1 = [1, 2, 2] Need P2 = [6, 0, 0] Need P3 = [0, 1, 1] Need P4 = [4, 3, 1] Safe sequence: ['P1', 'P3', 'P4', 'P0', 'P2'] P1 requests [1, 0, 2]: grant, safe sequence ['P1', 'P3', 'P4', 'P0', 'P2'] P2 requests [4, 0, 0]: wait: not enough available P4 requests [3, 3, 0]: deny: state would be unsafe
What this code does
- The safety check finds P1 first (Need (1,2,2) ≤ (3,3,2)); after P1 returns its (2,0,0), Available is (5,3,2), which lets P3 and then P4 finish, and so on.
- Each request is checked against the starting state: P2's request is within its Need but asks for 4 of A when only 3 are free, so it must wait. P4's request fits, but granting it would leave (0,0,2) free, where no process can finish, so it is denied.
Banker's algorithm is the classic avoidance method. Each process declares its Max need in advance. The OS keeps Allocation (what each holds), Available (free instances) and Need = Max − Allocation. The safe sequence for the data above is P1, P3, P4, P0, P2.
- Compute Need = Max − Allocation for every process.
- Find a process whose Need ≤ Available (every resource).
- Pretend it finishes: Available += its Allocation; mark it done.
- Repeat; if all finish, the state is safe and the order is a safe sequence.
- For a new request: check Request ≤ Need and ≤ Available, pretend to grant, run the safety check, and grant only if safe.
Predict the output
The safety check, one resource
Ten units in total, three free. Pick what the safety check prints.
P0 needs 6 more, P1 needs 2, P2 needs 5. The check scans P0, P1, P2 and restarts after each finish.
Deadlock vs starvation
Starvation is when a ready process keeps being passed over and never gets what it needs, although the rest of the system keeps working.
In a deadlock, the processes in the cycle can never proceed without outside help. In starvation a process could proceed but is passed over. The comparison below also shows a third case.
Deadlock: A waits for B, B waits for A -> nobody moves, foreverStarvation: C is ready but always passed over -> others move, C does notLivelock: A and B keep yielding to each other -> both busy, no progressA typical starvation case is a low-priority job in priority scheduling. A livelock is the third case: processes keep changing state in response to each other but make no progress, like two people in a corridor who keep stepping aside the same way.
Deadlock implies the involved processes starve, but starvation does not imply deadlock.
Find the bug
Weak spoken answers
Each spoken answer has one wrong sentence. Click it.
Answer to "Deadlock vs starvation?"
Round 1 of 2Next step
Check your understanding
12 quick questions