Skip to content

Deadlock

Prime #
167
Origin domain
Computer Science & Software Engineering
Also from
Operations Research, Organizational & Management Science, Information Theory
Aliases
Circular Waiting, Mutual Blocking, Stalemate
Related primes
Concurrency, Synchronization, Interference and Contention

Core Idea

Deadlock occurs when two or more processes or agents are blocked, each waiting for resources locked by another, preventing all from proceeding.

How would you explain it like I'm…

Everyone Stuck Waiting

Imagine two kids in a doorway, each waiting for the other to step aside first. Neither moves, and nobody gets through. That's a deadlock. It happens any time people or machines all stop and wait for each other in a circle, and no one can go until someone else goes first.

Stuck-In-A-Circle Wait

Imagine you need the scissors and the glue to finish a project, but your friend has the scissors and is waiting for your glue. You won't give up the glue until you get the scissors. Your friend won't give up the scissors until they get the glue. Now you're both stuck forever. That's a deadlock: a circle of waiting where nobody can move because everyone needs something the next person is holding.

Circular Resource Wait

Deadlock happens when two or more processes or agents are all blocked, each waiting for resources or conditions controlled by the others, so none of them can make progress. The defining feature is a circular dependency: process A is waiting on something held by B, B is waiting on something held by C, and C is waiting on something held by A. Breaking the cycle requires at least one party to release what it's holding, but every party is blocked waiting for someone else to release first. Coffman and colleagues identified the four conditions that all must hold for deadlock to be possible, which means preventing any one of them prevents deadlock entirely.

 

Deadlock occurs when two or more processes or agents are blocked simultaneously, each waiting for resources or conditions controlled by another member of the set, such that none can proceed. The essential commitment is circular dependency: a cycle of wait-for relationships in which breaking the cycle requires at least one waiting party to act, but every party is itself blocked awaiting action from another. Coffman, Elphick, and Shoshani (1971) identified the four conditions whose joint satisfaction is necessary for deadlock: mutual exclusion of resources, hold-and-wait (a process holds resources while requesting more), no preemption (resources cannot be forcibly taken), and circular wait. Because all four must hold, deadlock prevention strategies typically negate at least one - for example, requiring processes to acquire all resources atomically eliminates hold-and-wait; imposing a total order on resource acquisition eliminates circular wait. The concept generalizes across operating systems, distributed databases, transaction processing, multi-agent coordination, and human organizational standoffs.

Broad Use

  • Computing: Threads each holding a lock and waiting for another lock the other thread holds.

  • Economics: Two negotiating parties each refusing to move first, stalling progress.

  • International Relations: Diplomatic standoffs where neither side concedes, halting negotiations.

  • Organizational Bottlenecks: Departments waiting on each other for sign-offs.

Clarity

Demonstrates how circular dependencies lead to systemic paralysis if not resolved.

Manages Complexity

Forces recognition of shared resources and potential standstills, prompting designs for prevention or resolution (e.g., lock hierarchies, protocols).

Abstract Reasoning

Highlights circular dependencies and the need for "break-the-cycle" strategies.

Knowledge Transfer

Deadlock resolution patterns (e.g., "avoid hold-and-wait") can inform conflict resolution, supply chain blockages, or interpersonal stalemates.

Example

Two interviewers each hold a timeslot for one candidate while waiting for the other to free up their schedule—neither can proceed until one person changes the plan, causing a scheduling deadlock.

Relationships to Other Abstractions

Local relationship map for DeadlockParents appear above the current abstraction, mutual partners to the right, and children below. Node labels state whether each abstraction is prime or domain-specific; colors identify relation types.DeadlockPRIMEPrime abstraction: Cycle — is a kind ofCyclePRIME

Current abstraction Deadlock Prime

Parents (1) — more general patterns this builds on

  • Deadlock is a kind of Cycle Prime

    Deadlock's essential commitment is a circular waiting dependency, which is precisely a closed loop returning to origin in the dependency graph, the structure cycle names.

Hierarchy path (1) — routes to 1 parentless root

Not to Be Confused With

  • Deadlock is not Concurrency because Deadlock is a specific failure state in concurrent systems where processes block each other indefinitely, while Concurrency is the general phenomenon of multiple processes executing in overlapping time—deadlock is a pathological condition, concurrency is a normal operational mode.
  • Deadlock is not Circular Causality because Deadlock involves mutual blocking where resources or locks are held and requested in a cycle, while Circular Causality involves mutual influence where events cause each other—deadlock concerns resource contention, circular causality concerns mutual influence or feedback.
  • Deadlock is not Synchronization because Deadlock is the failure of coordinated execution where processes halt indefinitely, while Synchronization is the successful coordination of processes reaching common states or moments—deadlock is failed synchronization, synchronization is successful coordination.