Deadlock
A deadlock is a situation where two or more processes are unable to proceed because each is waiting for a resource held by another, creating a circular dependency.
A deadlock is a critical condition in operating systems and concurrent programming where a set of processes become permanently blocked because each process holds a resource while waiting for another resource held by a different process in the set.
For a deadlock to occur, four conditions (known as the Coffman conditions) must simultaneously exist:
1. Mutual Exclusion: Resources cannot be shared
2. Hold and Wait: Processes hold resources while waiting for others
3. No Preemption: Resources cannot be forcibly taken
4. Circular Wait: A circular chain of processes exists
Operating systems handle deadlocks through: Prevention (eliminating one condition), Avoidance (Banker's Algorithm), Detection and Recovery, or Ignorance (the 'Ostrich Algorithm' used by Windows and UNIX).
graph LR
Center["Deadlock"]:::main
Pre_process["process"]:::pre --> Center
click Pre_process "/terms/process"
Pre_mutex["mutex"]:::pre --> Center
click Pre_mutex "/terms/mutex"
classDef main fill:#7c3aed,stroke:#8b5cf6,stroke-width:2px,color:white,font-weight:bold,rx:5,ry:5;
classDef pre fill:#0f172a,stroke:#3b82f6,color:#94a3b8,rx:5,ry:5;
classDef child fill:#0f172a,stroke:#10b981,color:#94a3b8,rx:5,ry:5;
classDef related fill:#0f172a,stroke:#8b5cf6,stroke-dasharray: 5 5,color:#94a3b8,rx:5,ry:5;
linkStyle default stroke:#4b5563,stroke-width:2px;
🧠 Knowledge Check
🧒 Explain Like I'm 5
Imagine two people on a narrow [bridge](/en/terms/bridge) from opposite sides. Each refuses to back up, so neither can cross. They're stuck forever! That's what happens to computer programs in a deadlock.
🤓 Expert Deep Dive
Deadlock detection uses wait-for graphs (cycle = deadlock). Recovery options: process termination (abort all/one), resource preemption (rollback with checkpoints). Distributed deadlocks require edge-chasing algorithms. Livelock is a variation where processes continually change state without progress. Modern databases use timeout-based deadlock detection with transaction rollback. The Dining Philosophers problem (Dijkstra, 1965) is a canonical illustration.