A
AiTechWorlds
AiTechWorlds
Picture two trains approaching each other on a single-track railway that has one short passing siding. Train A enters from the west, occupies the siding. Train B arrives from the east, but it needs the siding to get by. Train A cannot move forward because Train B is blocking the main track. Train B cannot move backward because more trains are behind it. Neither moves. Forever.
This is deadlock. Not a bug, not a crash — just an eternal freeze where every party is waiting for a resource held by the other.
In operating systems, processes take the role of trains. Resources (memory, files, locks, database records) take the role of track sections. Deadlock occurs when a group of processes are each waiting for a resource held by another member of the group. No process can ever proceed.
Deadlock requires four conditions to hold simultaneously. Remove any one condition, and deadlock becomes impossible. These are the Coffman Conditions, identified by Edward Coffman in 1971.
At least one resource must be held in a non-shareable mode — only one process can use it at a time. If Process A holds the resource, Process B must wait.
Example: A printer can only print one job at a time. A database row lock is exclusive.
Note: Read-only resources are shareable and cannot cause deadlock through this condition.
A process is holding at least one resource while waiting to acquire additional resources held by other processes.
Example: Process A holds lock_a and waits for lock_b. Process B holds lock_b and waits for lock_a.
This is the "greedy holding" condition — processes do not release what they have while requesting more.
Resources cannot be forcibly taken from a process holding them. A process only releases a resource voluntarily (when it has finished using it).
Example: If Process A holds a file lock, the OS cannot simply take it away. The lock is released only when Process A calls unlock().
Some resources (CPU time, memory pages) can be preempted. Others (a printer mid-job, a database transaction) fundamentally cannot be interrupted.
A circular chain of processes exists, each waiting for a resource held by the next process in the chain.
P1 waits for resource held by P2
P2 waits for resource held by P3
P3 waits for resource held by P1
The chain loops back. Everyone waits. No one proceeds.
A Resource Allocation Graph is the visual tool for reasoning about deadlock. It has two types of nodes and two types of edges:
Nodes:
Edges:
P1 requests R1 (held by no one — no assignment edge from R1). P2 requests R2 (also free). No cycle. No deadlock.
P1 holds R2, requests R1
P2 holds R1, requests R3
P3 holds R3, requests R2
Cycle: P1 → R1 → P2 → R3 → P3 → R2 → P1
Rule: If each resource type has exactly one instance, a cycle in the RAG means deadlock is certain. If resources have multiple instances, a cycle indicates deadlock is possible but not guaranteed.
Database deadlocks are the most common real-world manifestation:
-- Transaction A:
BEGIN;
UPDATE accounts SET balance = balance - 100 WHERE id = 1; -- locks row 1
UPDATE accounts SET balance = balance + 100 WHERE id = 2; -- waits for row 2 lock
-- Transaction B (running simultaneously):
BEGIN;
UPDATE accounts SET balance = balance - 50 WHERE id = 2; -- locks row 2
UPDATE accounts SET balance = balance + 50 WHERE id = 1; -- waits for row 1 lock
Transaction A holds row 1, waits for row 2. Transaction B holds row 2, waits for row 1. Circular wait. Deadlock.
Modern database engines (PostgreSQL, MySQL InnoDB, Oracle) detect this automatically using a wait-for graph and abort one transaction, allowing the other to complete. The aborted transaction returns an error to the application, which must retry.
| Condition | Definition | Progress? |
|---|---|---|
| Deadlock | Circular waiting; no process makes progress | None |
| Starvation | A process waits indefinitely due to unfair scheduling | Others progress |
| Livelock | Processes keep changing state in response to each other but no work is done | State changes but no useful progress |
Livelock analogy: Two people in a hallway both step the same direction to let the other pass, simultaneously, forever. They are active but accomplish nothing.
Most modern general-purpose operating systems (Linux, Windows, macOS) use a pragmatic approach: ignore deadlock in user processes. The assumption is that application-level deadlocks are rare and the recovery cost (kernel complexity) outweighs the benefit.
However:
The four Coffman conditions are the necessary and sufficient conditions for deadlock:
| Condition | What It Means |
|---|---|
| Mutual Exclusion | Resources are non-shareable |
| Hold and Wait | Processes hold resources while waiting for more |
| No Preemption | Resources cannot be forcibly taken |
| Circular Wait | Processes form a waiting cycle |
All four must hold simultaneously for deadlock to occur. This insight is the basis for all deadlock prevention, avoidance, and detection strategies.
Get this course's notes on Telegram!
Free cheat sheets, summaries & practice exercises