Topic: deadlocks

topics > computer science > Group: parallel processing

communication protocols
concurrency control by monitors
critical regions
database transactions
lock-free concurrency
non-preemptive task scheduling
plan-based task scheduling
proving concurrent programs
race conditions
safety, liveness, and system properties
task scheduling
updating information with locking


A deadlock occurs when A waits for B while B waits for A. A livelock occurs when event A never happens. The liveness property is a guarantee that a system is free of deadlocks.

Deadlocks may be prevented or detected. If transactions acquire and release locks in order, deadlock is not possible. Priority inheritance avoids priority inversion problems. (cbb 8/06)

Subtopic: deadlocks up

Quote: when writing mutex code must manage locks, decide on lock granularity, and handle deadlock; hides important safety and progress properties [»harrT10_2003]
Quote: if resources are consumable, then deadlock avoidance is intractable; algorithms exist for reusable resources [»dennPJ_1980]

Subtopic: deadlock detection up

Quote: deadlocks are easy to detect; use a debugger to look at relevant threads, especially those tied to a mutex or condition variable [»birrAD_1991]
Quote: improve static reachability analysis for deadlock detection with state space reduction, symbolic model checking, and inequality necessary conditions [»corbJC3_1996]
Quote: efficient search technique for detecting deadlocks and assertion violations in concurrent programs [»godeP1_1997]
Quote: efficient, one-phase algorithm to detect generalized distributed deadlocks; outward sweep constructs wait-for-graph; inward sweep detects deadlock [»ksheAD1_1994]

Subtopic: deadlock prevention up

Quote: each GFS namespace node has a read-write lock; consistent total order to prevent deadlock
Quote: can avoid deadlocks by eliminating circular waits with ordered resources [»dennPJ_1980]
Quote: avoid deadlocks by applying a partial order to the acquisition of mutexes; condition variables may still cause deadlocks [»birrAD_1991]
Quote: can avoid deadlocks with a data-driven network; every message includes work to be done, a process must reduce the work remaining [»dennPJ_1980]
Quote: algorithm for concurrent, tunable indexing of B*-trees; deadlock free [»bayeR_1977]
Quote: can avoid deadlocks with a hierarchical process organization; subordinates must reply and can't fill up queues [»dennPJ_1980]

Subtopic: binary operations up

Quote: binary operations on shared objects must synchronize both objects; all threads must use the same lock acquisition order [»hoveD7_2004]

Subtopic: no deadlock up

Quote: for meaningful, interprocess communication need: no livelock, no deadlock, all messages handled, concurrency is order independent, serialization [»chowTS_1978]
Quote: coordinated addressing requires waiting until relevant messages arrive; needs deadlock detection [»martP1_1986]
Quote: desired properties for state machines--absence of deadlock, completeness, and liveness; catch basic flaws and unwarranted assumptions [»holzGJ5_1999]

Subtopic: livelock up

Quote: Modula-2's scheduler can cause livelock when a consumer process is linked immediately before its producer process [»hemmD3_1988]
Quote: receive livelock--responding to interrupts all of the time; can happen with host-based routing, passive network monitoring, network file service [»moguJC8_1997]
Quote: avoid receive livelock by round-robin polling on interrupts and interrupt only when not polling; guarantees CPU for user tasks [»moguJC8_1997]

Subtopic: model testing up

Quote: 450 lines of test driver code caught 25 timing-dependent errors; difficult to detect with conventional testing [»holzGJ5_1999]

Subtopic: priority inheritance up

Quote: in PORTAL, a priority is assigned to both processes and monitors; if a process inside a monitor, it takes the monitor's priority

Related Topics up

Topic: communication protocols (62 items)
Topic: concurrency control by monitors (24 items)
Topic: critical regions (58 items)
Topic: database transactions (27 items)
Topic: lock-free concurrency (8 items)
Topic: non-preemptive task scheduling (16 items)
Topic: plan-based task scheduling (13 items)
Topic: proving concurrent programs (37 items)
Topic: race conditions (33 items)
Topic: safety, liveness, and system properties (22 items)
Topic: task scheduling (49 items)
Topic: updating information with locking
(20 items)

Updated barberCB 5/05
Copyright © 2002-2008 by C. Bradford Barber. All rights reserved.
Thesa is a trademark of C. Bradford Barber.