Deadlock
Noun · Development
Definitions
A state where two or more processes are each waiting for the other to release a resource, so none of them can proceed. The computational equivalent of two people meeting in a narrow hallway and both stepping aside in the same direction forever.
In plain English: When two programs are each waiting for the other to finish first, so neither one can ever continue — a permanent standoff.
The four conditions required for deadlock (Coffman conditions, 1971): mutual exclusion, hold and wait, no preemption, and circular wait. Breaking any one condition prevents deadlock. Database systems detect deadlocks by tracking wait-for graphs and killing one transaction to break the cycle.
Example: 'PostgreSQL detected the deadlock and killed one of our transactions: ERROR: deadlock detected. The fix was acquiring locks in a consistent order.'
Source: Coffman conditions / prevention
Origin Story
Four hungry philosophers and one missing fork
A **deadlock** occurs when two or more processes are each waiting for the other to release a resource, creating a permanent standoff where nothing progresses. The concept was formalized by **E.W. Dijkstra** in 1965 through his famous **Dining Philosophers Problem**: five philosophers sit at a round table with five forks. Each needs two forks to eat. If every philosopher picks up the fork to their left simultaneously, they all wait forever for the right fork.
Dijkstra identified four conditions that must all hold for a deadlock to occur: mutual exclusion, hold and wait, no preemption, and circular wait. Break any one condition and deadlock becomes impossible. This framework remains the foundation of deadlock prevention in operating systems and concurrent programming.
The term "deadlock" predates computing — it was used in the 19th century for legislative impasses and even traffic jams (when four carriages arrived at an intersection simultaneously, each waiting for the one on its right to move). Dijkstra formalized what humans had observed for centuries.
Coined by: E.W. Dijkstra (formalized)
Context: 1965, Dining Philosophers Problem
Fun fact: Real-world deadlocks can have catastrophic consequences. In 2003, a threading deadlock in the Northeast U.S. power grid's monitoring software contributed to a cascading blackout that left 55 million people without power.