In Deadlock Prevention & Avoidance (Banker's Algorithm) we tried to stop deadlocks before they happen. Both methods have a price: prevention restricts how programs may use resources, and avoidance needs each process's maximum need in advance and runs a safety check on every request.
There is a third, more relaxed approach: let deadlocks happen, notice them, and then clean up. This is exactly what databases like MySQL and PostgreSQL do every day.
This approach has two parts:
Detection: an algorithm that examines the current state and tells us whether a deadlock exists, and which processes are involved.
Recovery: a way to break the deadlock, either by terminating processes or by taking resources away from them.
Why Allow Deadlocks at All?
It sounds risky, but it is often the most efficient choice:
Deadlocks are rare in most systems. Paying the cost of avoidance on every single request, just to stop an event that seldom happens, is wasteful.
Detection does not need advance knowledge of maximum needs. It only looks at what processes hold and what they are waiting for right now.
Resources are never left idle "just to be safe", so utilisation is higher.
The trade-off is that when a deadlock does happen, some work is lost during recovery.
Avoidance | Detection and recovery | |
|---|---|---|
Attitude | Pessimistic: never enter an unsafe state | Optimistic: grant requests freely, fix problems later |
Needs Max in advance? | Yes | No |
Cost | Check on every request | Periodic check plus recovery cost when a deadlock is found |
Can deadlocks occur? | No | Yes, temporarily, until detected |
Detection with Single-Instance Resources: The Wait-for Graph
If every resource type has exactly one instance, detection is just cycle finding. We first simplify the Resource Allocation Graph from Deadlocks into a wait-for graph.
A wait-for graph contains only process nodes. There is an edge Pi → Pj if Pi is waiting for a resource that is currently held by Pj.
To build it, remove every resource node and join the edges through it: if the RAG has Pi → R and R → Pj, the wait-for graph gets Pi → Pj.
Example
Five processes and five single-instance resources:
Resource | Held by | Requested by (waiting) |
|---|---|---|
R1 | P2 | P1 |
R2 | P1 | P4 |
R3 | P3 | P2, P5 |
R4 | P4 | P3 |
R5 | P5 | nobody |
Converting each "waiting for R, R held by Q" pair into an edge:
Resource Allocation Graph Wait-for Graph
P1 → R1 → P2 P1 → P2
P2 → R3 → P3 P2 → P3
P3 → R4 → P4 P3 → P4
P4 → R2 → P1 P4 → P1
P5 → R3 → P3 P5 → P3
P1 ──► P2
▲ │
│ ▼
P4 ◄── P3 ◄── P5
The cycle P1 → P2 → P3 → P4 → P1 means these four processes are deadlocked. Since each resource has a single instance, a cycle in the wait-for graph is both necessary and sufficient for deadlock.
What about P5? It is not in the cycle, but it is waiting for R3, which P3 will never release. So P5 is also stuck forever, as a "victim" of the deadlock. If we break the cycle (for example by aborting P4), P3 can eventually finish and release R3, and P5 will get unstuck too.
Finding the cycle
Cycle detection in a directed graph is a standard depth-first search, the same technique from Cycle Detection in the DSA tutorial. A node that is reached again while it is still on the current DFS path closes a cycle.
# Wait-for graph: an edge P -> Q means "P is waiting for a resource held by Q"
wait_for = {
"P1": ["P2"],
"P2": ["P3"],
"P3": ["P4"],
"P4": ["P1"],
"P5": ["P3"],
}
def find_cycle(graph):
WHITE, GREY, BLACK = 0, 1, 2 # unvisited, on current path, done
color = {p: WHITE for p in graph}
path = []
def dfs(p):
color[p] = GREY
path.append(p)
for q in graph.get(p, []):
if color[q] == GREY: # back edge: cycle found
return path[path.index(q):] + [q]
if color[q] == WHITE:
cycle = dfs(q)
if cycle:
return cycle
path.pop()
color[p] = BLACK
return None
for p in graph:
if color[p] == WHITE:
cycle = dfs(p)
if cycle:
return cycle
return None
cycle = find_cycle(wait_for)
if cycle:
print("Deadlock! Cycle:", " -> ".join(cycle))
else:
print("No deadlock")
wait_for["P4"] = [] # suppose P4 stops waiting for P1
print("After P4's request is satisfied:", find_cycle(wait_for) or "No deadlock")
Deadlock! Cycle: P1 -> P2 -> P3 -> P4 -> P1
After P4's request is satisfied: No deadlock
With n processes, the wait-for graph has at most n² edges, so detection takes O(n²) time in the worst case (DFS is O(V + E)).
Detection with Multiple-Instance Resources
When resource types have several instances, a cycle no longer guarantees a deadlock (remember Example 3 in Deadlocks). We need an algorithm that actually tries to "play out" the future, just like the Banker's safety algorithm.
Data structures
Name | Size | Meaning |
|---|---|---|
| m | Free instances of each resource type |
| n × m | Instances of each type currently held by each process |
| n × m | The current, pending request of each process (what it is blocked waiting for right now) |
Notice there is no Max and no Need. Detection does not care what a process might want in the future, only what it is waiting for now.
The detection algorithm
1. Work = Available
For each i:
Finish[i] = true if Allocation[i] == 0 (holds nothing, can't be
part of a deadlock)
Finish[i] = false otherwise
2. Find an i such that
Finish[i] == false AND Request[i] ≤ Work
If none exists, go to step 4.
3. Assume P[i] gets what it asked for, finishes and releases everything:
Work = Work + Allocation[i]
Finish[i] = true
Go to step 2.
4. If some Finish[i] == false → the system is DEADLOCKED,
and every P[i] with Finish[i] == false
is one of the deadlocked processes.
Otherwise → no deadlock.
It looks almost identical to the Banker's safety algorithm. The differences are what make it a detection algorithm:
Banker's safety algorithm | Detection algorithm | |
|---|---|---|
Compares with | Need = Max − Allocation (future worst case) | Request (current pending request) |
Initial Finish | All false | True for processes holding nothing |
Answer | Safe or unsafe (could deadlock in the future) | Deadlocked right now or not, and who |
Used for | Deciding whether to grant a request | Deciding whether recovery is needed |
Why is it OK to optimistically assume Pi will finish once its request is met? If Pi actually asks for more later and gets stuck, that will be a new situation, and the next run of the detection algorithm will catch it. Detection only answers "is anyone stuck right now with no way out?"
Time complexity is the same as the safety algorithm: O(m × n²).
Worked example 1: No deadlock
Five processes, three resource types A, B, C with 6, 4 and 4 instances in total.
Process | Allocation (A B C) | Request (A B C) |
|---|---|---|
P0 | 1 0 1 | 2 0 0 |
P1 | 2 1 0 | 0 1 1 |
P2 | 0 1 1 | 1 0 1 |
P3 | 1 1 0 | 0 0 1 |
P4 | 1 0 1 | 1 1 2 |
Allocated = (1+2+0+1+1, 0+1+1+1+0, 1+0+1+0+1) = (5, 3, 3)
Available = (6, 4, 4) − (5, 3, 3) = (1, 1, 1)
Work = (1,1,1). Nobody holds zero resources, so all Finish = false.
(Each time, scan from P0 and take the first process that fits.)
P0 Request (2,0,0) ≤ (1,1,1)? No
P1 Request (0,1,1) ≤ (1,1,1)? Yes → Work = (1,1,1) + (2,1,0) = (3,2,1)
P0 Request (2,0,0) ≤ (3,2,1)? Yes → Work = (3,2,1) + (1,0,1) = (4,2,2)
P2 Request (1,0,1) ≤ (4,2,2)? Yes → Work = (4,2,2) + (0,1,1) = (4,3,3)
P3 Request (0,0,1) ≤ (4,3,3)? Yes → Work = (4,3,3) + (1,1,0) = (5,4,3)
P4 Request (1,1,2) ≤ (5,4,3)? Yes → Work = (5,4,3) + (1,0,1) = (6,4,4)
All Finish = true → NO DEADLOCK (one possible order: P1, P0, P2, P3, P4)
As a check, the final Work equals the total (6, 4, 4).
Worked example 2: Deadlock
Some time later the allocation is unchanged, but P0, P1 and P2 are now each waiting for two instances of C:
Process | Allocation (A B C) | Request (A B C) |
|---|---|---|
P0 | 1 0 1 | 2 0 2 |
P1 | 2 1 0 | 0 1 2 |
P2 | 0 1 1 | 1 0 2 |
P3 | 1 1 0 | 0 0 1 |
P4 | 1 0 1 | 1 1 2 |
Work = (1,1,1)
P0 Request (2,0,2) ≤ (1,1,1)? No
P1 Request (0,1,2) ≤ (1,1,1)? No
P2 Request (1,0,2) ≤ (1,1,1)? No
P3 Request (0,0,1) ≤ (1,1,1)? Yes → Work = (1,1,1) + (1,1,0) = (2,2,1)
P0 Request (2,0,2) ≤ (2,2,1)? No (C: 2 > 1)
P1 Request (0,1,2) ≤ (2,2,1)? No (C: 2 > 1)
P2 Request (1,0,2) ≤ (2,2,1)? No (C: 2 > 1)
P4 Request (1,1,2) ≤ (2,2,1)? No (C: 2 > 1)
Finish[0], Finish[1], Finish[2], Finish[4] are false
→ DEADLOCK. Deadlocked processes: {P0, P1, P2, P4}
P3 can finish, but even after it returns its resources only 1 instance of C is free, and every other process is waiting for 2. The three remaining instances of C are held by P0, P2 and P4, and they are all among the stuck processes. Nobody can ever release them.
When Should the Detection Algorithm Run?
This depends on two questions: how often do deadlocks happen, and how many processes will be affected when one does?
Option | Advantage | Disadvantage |
|---|---|---|
Every time a request cannot be granted immediately | Deadlock is found the moment it forms, and we know which request "completed" the cycle | High overhead, the algorithm runs very often |
At fixed intervals (for example, every few minutes) | Low overhead | Deadlocked processes stay stuck until the next check; more processes may pile up behind them; hard to tell who caused it |
When a symptom appears (for example, CPU utilisation drops sharply, or a lock wait lasts too long) | Runs only when something looks wrong | Needs a good symptom; may react late |
Why would CPU utilisation drop? Because deadlocked processes are blocked and do not use the CPU, as we saw with ps and top in Deadlocks. If enough processes are stuck, the CPU starts sitting idle.
Recovery from Deadlock
Once a deadlock is detected, it must be broken. The options are: tell the operator and let a human decide, or let the system recover automatically. Automatic recovery has two methods.
Method 1: Process Termination
(a) Abort all deadlocked processes. This definitely breaks the deadlock, quickly. But it is expensive: all of their work is thrown away, and they may have been running for hours.
(b) Abort one process at a time until the deadlock disappears. After each abort, run the detection algorithm again. Less work is lost, but detection may run several times.
Choosing the victim matters. Let us go back to worked example 2, where {P0, P1, P2, P4} were deadlocked. We tried aborting each one in turn (and re-ran detection after each):
Abort | Released (A B C) | New Available | Result |
|---|---|---|---|
P0 | 1 0 1 | (2, 1, 2) | Deadlock broken: P1, P2, P3, P4 can all finish |
P1 | 2 1 0 | (3, 2, 1) | Still deadlocked: {P0, P2, P4} remain stuck |
P2 | 0 1 1 | (1, 2, 2) | Deadlock broken: P1, P0, P3, P4 can all finish |
P4 | 1 0 1 | (2, 1, 2) | Deadlock broken: P0, P1, P2, P3 can all finish |
Aborting P1 is a waste: P1 holds no C at all, and C is exactly what everyone is waiting for. Killing it destroys P1's work without solving the problem, and we would have to kill a second process too. A good victim is one whose resources actually unblock the others.
In general, the OS picks the victim with the minimum cost, considering factors such as:
The priority of the process
How long it has run, and how much longer it needs (less work lost is better)
How many and what kind of resources it holds (does freeing them help?)
How many more resources it needs to finish
How many processes would have to be terminated in total
Whether it is interactive or batch
Danger: terminating a process in the middle of updating a file or shared data can leave that data inconsistent. This is why databases, which care deeply about consistency, roll back transactions using their logs rather than simply killing them.
Method 2: Resource Preemption
Instead of killing whole processes, take some resources away from one process and give them to others until the cycle breaks. Three issues have to be handled:
Selecting a victim: which resources from which process? Again, choose to minimise cost (number of resources held, time already used, and so on).
Rollback: a process that loses a resource cannot simply continue as if nothing happened. It must be rolled back to some safe earlier state and restarted from there.
Total rollback: abort and restart from the beginning. Simple.
Partial rollback: go back only as far as needed, to a checkpoint. Cheaper, but the system must save checkpoints of process state regularly.
Starvation: if the cost function always picks the same process (say, the youngest), it may be rolled back again and again and never finish. The fix is to include the number of times a process has already been rolled back in the cost, so a process can be picked as victim only a limited number of times.
Termination vs preemption
Process termination | Resource preemption | |
|---|---|---|
What is lost | All work of the aborted process(es) | Work since the last checkpoint (with partial rollback) |
Complexity | Simple | Needs checkpoints and rollback support |
Risk | Inconsistent data if killed mid-update | Starvation if the same victim is chosen repeatedly |
Typical user | Operating systems, a human with | Databases (transaction rollback) |
Detection and Recovery in the Real World: MySQL
General-purpose operating systems such as Linux do not run a deadlock detector on application locks. If your threads deadlock, the "recovery" is a human noticing that the program has hung and killing it. Database engines, on the other hand, detect deadlocks automatically, and you can watch it happen.
InnoDB, MySQL's storage engine, keeps a wait-for graph of transactions waiting for row locks. When a lock request would close a cycle, it picks a victim transaction, rolls it back (recovery by preemption with total rollback of that transaction) and lets the other one continue.
We opened two sessions on a copy of the sample company_db database used in the SQL tutorial. Each transaction updates two employee rows, but in opposite order, with a 2-second pause in between, exactly like our two-mutex C program:
-- Session 1
START TRANSACTION;
UPDATE employees SET salary = salary + 1000 WHERE emp_id = 2; -- locks row 2
SELECT SLEEP(2);
UPDATE employees SET salary = salary + 1000 WHERE emp_id = 3; -- wants row 3
COMMIT;
-- Session 2 (started half a second later)
START TRANSACTION;
UPDATE employees SET salary = salary - 500 WHERE emp_id = 3; -- locks row 3
SELECT SLEEP(2);
UPDATE employees SET salary = salary - 500 WHERE emp_id = 2; -- wants row 2
COMMIT;
Session 1 holds row 2 and waits for row 3. Session 2 holds row 3 and asks for row 2, which closes the cycle. MySQL reacted immediately, and Session 2 received:
ERROR 1213 (40001) at line 4: Deadlock found when trying to get lock; try restarting transaction
(The "at line 4" part appears because we ran the session from a script file.) Session 2's transaction was rolled back, its first update was undone and its row lock released, so Session 1's waiting update went through and it committed. The final data shows only Session 1's changes (both employees started at 95000.00):
+--------+-------------+----------+
| emp_id | name | salary |
+--------+-------------+----------+
| 2 | Priya Iyer | 96000.00 |
| 3 | Rohan Mehta | 96000.00 |
+--------+-------------+----------+
SHOW ENGINE INNODB STATUS keeps a report of the latest deadlock. Trimmed down, it shows both transactions, the lock each one holds, the lock each one is waiting for, and the decision:
LATEST DETECTED DEADLOCK
------------------------
*** (1) TRANSACTION:
UPDATE employees SET salary = salary + 1000 WHERE emp_id = 3
*** (1) HOLDS THE LOCK(S):
... index PRIMARY of table `os22_db`.`employees` ... lock_mode X locks rec but not gap
*** (1) WAITING FOR THIS LOCK TO BE GRANTED:
... index PRIMARY of table `os22_db`.`employees` ... lock_mode X locks rec but not gap waiting
*** (2) TRANSACTION:
UPDATE employees SET salary = salary - 500 WHERE emp_id = 2
*** (2) HOLDS THE LOCK(S):
...
*** WE ROLL BACK TRANSACTION (2)
This is the whole chapter in action: a wait-for graph, cycle detection, victim selection and rollback. InnoDB tries to choose a "small" transaction as the victim, measured by how many rows it has inserted, updated or deleted, so that the least work is lost. The error message's advice, "try restarting transaction", tells the application to simply run the victim transaction again.
Two related MySQL settings are worth knowing:
innodb_deadlock_detect(ON by default) turns this detection on or off. On very busy systems, some administrators turn it off and rely on the next setting instead.innodb_lock_wait_timeout(50 seconds by default) makes a transaction give up if it waits for a row lock too long. A timeout is a crude but cheap form of detection: "if you have waited this long, assume something is wrong".
Other systems use similar ideas. PostgreSQL runs its deadlock check only after a lock wait exceeds deadlock_timeout (1 second by default), which is the "run detection when a symptom appears" policy from the table above. The Java runtime can report deadlocked threads through ThreadMXBean.findDeadlockedThreads(), and a thread dump from jstack prints "Found one Java-level deadlock" when it sees one.
Comparing All Deadlock-Handling Strategies
Strategy | Deadlock possible? | Needs advance info? | Run-time cost | Used in practice by |
|---|---|---|---|---|
Prevention | No | No (just rules) | Low, but may reduce concurrency | Programmers using lock ordering; OS kernels |
Avoidance | No | Yes, maximum needs | Safety check on every request | Some specialised and real-time systems |
Detection and recovery | Yes, then fixed | No | Periodic detection plus lost work on recovery | Database systems |
Ignore (ostrich) | Yes, and not fixed automatically | No | None | Linux, Windows, macOS for application locks |
Common Mistakes
Using Need instead of Request in the detection algorithm. Detection uses the current pending Request; Banker's safety uses Need.
Starting all Finish values as false. In the detection algorithm, a process with zero allocation starts with Finish = true, because it holds nothing and cannot be part of a deadlock.
Using a wait-for graph for multi-instance resources. A cycle proves deadlock only when every resource has a single instance. Otherwise use the matrix-based detection algorithm.
Assuming any victim will do. As our example showed, aborting a process that holds none of the scarce resource does not break the deadlock.
Forgetting starvation in recovery. Always picking the same "cheapest" victim can roll back one process forever. Count rollbacks in the cost.
Thinking a process outside the cycle is safe. A process waiting for a resource held by a deadlocked process is stuck too, even though it is not part of the cycle.
Not retrying in the application. When a database reports a deadlock (MySQL error 1213), your code should retry the whole transaction, not just the last statement.
Interview Questions
What is a wait-for graph and how is it obtained?
A graph with only process nodes, where an edge Pi → Pj means Pi is waiting for a resource held by Pj. It is obtained from a resource allocation graph by removing resource nodes and joining Pi → R → Pj into Pi → Pj. With single-instance resources, a cycle in it means deadlock.
How does the deadlock detection algorithm differ from the Banker's safety algorithm?
Detection compares the current Request with Work instead of Need, and it starts with Finish[i] = true for processes holding no resources. It tells you whether processes are deadlocked now, while the safety algorithm tells you whether a state could lead to deadlock.
What is the time complexity of deadlock detection?
O(n²) with a wait-for graph for single-instance resources, and O(m × n²) for the multiple-instance algorithm with n processes and m resource types.
How often should the detection algorithm be run?
It depends on how often deadlocks occur and how costly they are. Running it on every blocked request finds deadlocks immediately but is expensive; running it periodically or when CPU utilisation drops is cheaper but lets deadlocks persist longer.
What are the ways to recover from a deadlock?
Process termination (abort all deadlocked processes, or abort one at a time until the cycle breaks) and resource preemption (take resources from a victim, roll it back to a checkpoint or restart it, and guard against starvation).
What factors decide which process to choose as a victim?
Priority, how long it has run and how long it still needs, the resources it holds and needs, how many processes must be terminated, whether it is interactive or batch, and how many times it has already been rolled back.
How can starvation occur during deadlock recovery?
If the victim is always chosen by the same cost rule, the same process may be preempted and rolled back again and again. Including the number of past rollbacks in the cost fixes this.
How does MySQL handle deadlocks?
InnoDB detects cycles in its transaction wait-for graph, rolls back one victim transaction (preferring the one that changed fewer rows) and returns error 1213 to it, so the application can retry. A lock wait timeout (innodb_lock_wait_timeout) acts as a backstop.
Summary
Detection and recovery lets deadlocks happen, finds them, and breaks them. It needs no advance knowledge and keeps utilisation high.
For single-instance resources, build a wait-for graph (Pi → Pj if Pi waits for Pj) and look for a cycle with DFS: O(n²).
For multiple instances, use the detection algorithm with Available, Allocation and Request: O(m × n²). Processes with Finish = false at the end are deadlocked.
Run detection on every blocked request, periodically, or when symptoms such as low CPU utilisation or long lock waits appear.
Recover by terminating processes (all, or one at a time) or by preempting resources (victim selection, rollback to a checkpoint, avoiding starvation).
Choose victims carefully: killing a process that does not hold the scarce resource does not help.
Databases such as MySQL InnoDB do exactly this: detect a cycle, roll back the smaller transaction, and return error 1213 so the application can retry.
This completes our study of deadlocks. Next we move to the second big resource the OS manages, main memory, starting with Memory Management Basics.