A procedure or mechanism that identifies the presence of deadlocks—situations in which one or more processes or threads are permanently blocked because each is waiting for resources held by others so that no further progress is possible without intervention.

Principle

Detection models resource contention with graphs (wait‑for graphs or resource‑allocation graphs) and uses cycle detection or state‑space analysis to identify circular waits. Detection is one of three families of approaches (prevention, avoidance, detection+recovery); practical detectors trade completeness for cost, may run periodically or on demand, and must map abstract cycles to concrete recovery actions.

Demonstration

Concrete examples: operating system deadlock detectors that build wait‑for graphs and detect cycles to choose a victim to kill or preempt; database systems that detect waits on locks and abort one transaction to break a cycle; static analysis tools that approximate possible deadlocks in multithreaded code by modeling lock acquisition orders.

Misapplication

Assuming detection equals resolution—detection only reports (or signals) that a deadlock exists and must be followed by recovery (killing, rollback, preemption). Overinterpreting false positives from conservative static analyses or ignoring livelock and starvation, which are distinct problems with different remedies, are common misuses.

Consequence

Effective deadlock detection enables targeted recovery actions (rollback, resource preemption, thread termination) and informs system design and tuning, but introduces monitoring overhead and requires careful policy for victim selection and minimal disruption.

Reversal

Deadlock prevention or avoidance (imposing global ordering on resources, using Banker's algorithm, or allocating resources only if safe) eliminates the need to detect and recover but can reduce concurrency or require conservative overprovisioning.

Boundary

Applies to systems with mutually exclusive resources and blocking acquisition semantics (locks, semaphores, I/O channels); excludes progress anomalies that are not circular waits (starvation, livelock) and models where resources are not held while waiting (pure message passing without blocking holds), unless a wait‑for relation can be derived.

Semantic Tension

Tension between runtime detection (reactive, may be cheaper in the common case) and prevention/avoidance (proactive, may impede concurrency). Also tension between precise dynamic detection and conservative static analyses that trade false positives for safety.

Synthesis

Deadlock detection is the runtime or analysis‑time identification of cyclic resource‑waiting conditions via wait‑for or resource‑allocation graphs; it sits within the broader design space of prevention, avoidance, and recovery, providing a pragmatic means to discover blocking cycles so that controlled recovery policies can restore progress.