System Deadlocks¶
Coffman, E. G., Elphick, M., & Shoshani, A. (1971). System Deadlocks. ACM Computing Surveys, 3(2), 67-78.
Cited by¶
12 citations across 12 artifacts.
Each citation links to the sentence it supports in the citing article.
Primes¶
- Deadlock
- The essential commitment is circular dependency: a cycle of waiting relationships such that breaking the cycle requires one of the waiting parties to act, but all are blocked awaiting action from others
Supported in partVerified against the work's full text
Describes deadlock as tasks each requesting a resource allocated to another, forming a circuit in the request graph; the fragmentary text only partly shows the wording.
“R, is requested by one task but allocated to another so that none of the R~ can be effec-”
- The essential commitment is circular dependency: a cycle of waiting relationships such that breaking the cycle requires one of the waiting parties to act, but all are blocked awaiting action from others
- Goal Shielding
- Concurrency theory's deadlock, starvation, and priority inversion port to individual attention management as diagnostic concepts: deadlock is two goals each waiting on the other's release, starvation is a chronically deprioritised goal that never gets shielded time.
This sourceDefines deadlock (the four Coffman conditions) and starvation in concurrent resource allocation, the diagnostic concepts ported to attention management (deadlock as mutual waiting, starvation as a chronically deprioritized goal).
Supported in partVerified against the work's full text
Coffman et al. supply the concurrency-theory concept of deadlock (tasks mutually waiting on resources); the attention-management transfer and the starvation concept are not in the text.
“A problem of increasing importance in the design of large multiprogramming systems is the, so-called, deadlock or deadly-embrace problem.”
- Concurrency theory's deadlock, starvation, and priority inversion port to individual attention management as diagnostic concepts: deadlock is two goals each waiting on the other's release, starvation is a chronically deprioritised goal that never gets shielded time.
- Mutual Exclusion
- The interventions are strikingly portable, and they transfer as a menu keyed to the structure. Shrink the critical region: take the lock later and release it earlier, narrow the exclusivity claim, reduce the airlock dwell, shorten the legal exclusivity window — the same move wherever serialization is paid. Add timeouts to bound the hold: recover liveness when a holder fails, via lease-based locks, expiry clauses in contracts, or dead-man switches in railway interlocks. Order resource acquisition: a single fixed-order rule prevents operating-system deadlock, dining-philosophers deadlock, and bargaining stalemate alike.
This sourceStates the four necessary conditions for deadlock and resource-ordering as a deadlock-prevention strategy.
- The interventions are strikingly portable, and they transfer as a menu keyed to the structure. Shrink the critical region: take the lock later and release it earlier, narrow the exclusivity claim, reduce the airlock dwell, shorten the legal exclusivity window — the same move wherever serialization is paid. Add timeouts to bound the hold: recover liveness when a holder fails, via lease-based locks, expiry clauses in contracts, or dead-man switches in railway interlocks. Order resource acquisition: a single fixed-order rule prevents operating-system deadlock, dining-philosophers deadlock, and bargaining stalemate alike.
Domain-specific¶
- Circular Reasoning
- That structure recurs as genuine co-instances in substrates that have nothing rhetorical about them — build-system cycle detection (Make, Bazel, Cargo flagging a circular import), legal-citation cycle detection over case-law DAGs, ontology and terminology design avoiding definitional loops via conceptual primitives, deadlock as a cyclic resource-wait
This sourceA survey of the deadlock ('deadly-embrace') problem in large multiprogramming systems, theoretical and practical.
Supported in partVerified against the publisher's abstract
“In this article we survey the work that has been done on the treatment of deadlocks from both the theoretical and practical points of view.”
- That structure recurs as genuine co-instances in substrates that have nothing rhetorical about them — build-system cycle detection (Make, Bazel, Cargo flagging a circular import), legal-citation cycle detection over case-law DAGs, ontology and terminology design avoiding definitional loops via conceptual primitives, deadlock as a cyclic resource-wait
Mechanisms¶
- All-or-Nothing Acquisition
- All-or-Nothing Acquisition attacks deadlock at exactly one of its four preconditions: hold-and-wait, the state in which a participant clutches something it already has while blocking on something it still needs.
This sourceIdentifies hold-and-wait as one of the jointly necessary conditions for deadlock and defines it as retaining allocated resources while waiting for additional ones.
- All-or-Nothing Acquisition attacks deadlock at exactly one of its four preconditions: hold-and-wait, the state in which a participant clutches something it already has while blocking on something it still needs.
- Blocked Dependency Trace
- … is to record the specific held condition at each hop (so a revisit is a true circular wait, not just a busy department) and to hand the loop to a mechanism that carries the authority to act, such as Mediation or Renegotiation or Escalation to Authority.
This sourceDefines circular wait as a closed chain in which each process holds a resource requested by the next.
- … is to record the specific held condition at each hop (so a revisit is a true circular wait, not just a busy department) and to hand the loop to a mechanism that carries the authority to act, such as Mediation or Renegotiation or Escalation to Authority.
- Booking Lock
- Its honest failure mode is that pessimistic locking trades the double-book risk for contention and deadlock — two requests each holding one lock and each waiting on the other stall until something is killed.
This sourceCharacterizes deadlock as processes holding resources while waiting in a cycle and describes termination of a process as a recovery method.
- Its honest failure mode is that pessimistic locking trades the double-book risk for contention and deadlock — two requests each holding one lock and each waiting on the other stall until something is killed.
- Deadlock Timeout and Detection
- The four Coffman conditions name the necessary ingredients of any deadlock — mutual exclusion, hold-and-wait, no preemption, and a circular wait — and prevention that removes one of them (most practically, imposing a global lock-ordering to kill the circular wait) is usually cheaper than detection.
This sourceIntroduces the four deadlock conditions and shows how denying one—such as circular wait through a linear resource ordering—prevents deadlock.
- The four Coffman conditions name the necessary ingredients of any deadlock — mutual exclusion, hold-and-wait, no preemption, and a circular wait — and prevention that removes one of them (most practically, imposing a global lock-ordering to kill the circular wait) is usually cheaper than detection.
- Lock or Hold Until Use
- Lock Preemption
- It directly negates the no-preemption condition that circular waits depend on.
This sourceCoffman, Elphick, and Shoshani define no-preemption as the condition that resources cannot be forcibly removed and describe deadlock prevention by removing a necessary condition.
- It directly negates the no-preemption condition that circular waits depend on.
- Process Kill or Restart
- This is the same victim-choice dial deadlock recovery always faces
This sourceFrames deadlock recovery as choosing which deadlocked tasks or resources to abort or preempt, with the choice governed by recovery cost.
- This is the same victim-choice dial deadlock recovery always faces
- Wait-For Graph Analysis
- On the classic circular-wait condition it is exact: a cycle in the wait-for graph is the deadlock,
This sourceIdentifies circular wait as a defining deadlock condition in which each task waits for a resource held by the next task in a cycle.
- On the classic circular-wait condition it is exact: a cycle in the wait-for graph is the deadlock,
Verification¶
Does it exist? Confirmed. This work's DOI resolves to a registered record, which fixes its identity. That is all it fixes.
Does it back the claim? Read against the text for 3 of 12 citations: 3 supported in part. Each verdict is shown under its citation below, with what in the work backs the sentence.
Was it audited? Yes. A second, independent pass read the citation against the article text and recorded a verdict.
Support is checked per citation rather than per work — the same source can be cited soundly in one article and wrongly in another. Per-citation recording began recently, so a citation with no recorded check is a gap in the record rather than evidence it went unchecked.
See how references were verified.
Registry ID ref:725612a94162 · see in the full table