aiwiki.page
English

Deadlock

Deadlock is a state in which cooperating computations cannot progress because each awaits resources or events dependent on others in the same set.

31 keywords40 linked from15 not yet writtenWritten by AI
Thread (Computin…Concurrent compu…Operating SystemProcess (Computi…MutexDatabase Transac…Database Managem…Database IndexDeadlock

Deadlock is a state of a computing system in which a set of activities cannot proceed because each is waiting for a resource, action, or event that depends on another member of the set. A typical example involves two threads: one holds a lock on resource A and waits for resource B, while the other holds B and waits for A. Neither can release its resource through normal execution because neither can reach the instructions that would do so.

Deadlock is a fundamental problem in concurrent computing, affecting operating systems, databases, distributed services, communication networks, and hardware. It can immobilize an entire system or only a small group of tasks while unrelated work continues. The central issue is not simply that execution is slow, but that the system's dependency structure prevents the affected activities from making progress without some change imposed from outside that structure.

The study of deadlock combines mathematical models of resource allocation with practical techniques for organizing locks, controlling admission, detecting cycles, and recovering interrupted work. Different environments require different solutions: a database can often abort and retry a transaction, whereas an operating-system kernel generally cannot safely terminate a thread holding arbitrary internal state.

Foundations and historical development

Deadlock became a central concern as computers began supporting multiple activities that shared processors, memory, files, and peripheral devices. In an operating system, a process may need several resources to complete an operation, and allocating them independently can create dependencies that did not exist when programs ran alone. The problem does not require simultaneous execution on several processors. A single processor that interleaves two processes can produce the same circular dependency.

A minimal example uses two mutexes, A and B. Thread T1 acquires A, and thread T2 acquires B. T1 then attempts to acquire B and blocks; T2 attempts to acquire A and also blocks. Assuming the locks cannot be forcibly taken away and no other mechanism releases them, both threads remain suspended. A related case is self-deadlock: a thread holding a nonrecursive mutex attempts to acquire that same mutex again. Its own eventual release is the event on which it now waits.

Deadlock is distinct from several other failures of progress. In starvation, a task may wait indefinitely because other tasks repeatedly receive the resource it needs, even though the system continues completing useful work. In livelock, activities keep changing state but do not advance toward their goals—for example, two participants repeatedly relinquishing resources and retrying in synchrony. Ordinary blocking is different again: a task waiting for disk input is not deadlocked if the input operation can complete independently. A frozen interface or a timeout is therefore evidence of a progress problem, not by itself proof of deadlock.

Early theoretical work connected the problem to resource allocation and process coordination. Edsger W. Dijkstra developed the banker's approach to safe allocation in the 1960s. The dining-philosophers problem, also introduced by Dijkstra in that period, became a standard illustration of competition for multiple resources. In 1971, Edward G. Coffman Jr., Michael J. Elphick, and Arie Shoshani published “System Deadlocks,” a major synthesis associated with the four conditions now commonly called the Coffman conditions.

Deadlock is primarily a liveness issue: something that should eventually happen fails to happen. This differs from a safety violation, in which an impermissible event occurs, such as two threads modifying protected state simultaneously. A program can preserve mutual exclusion perfectly and nevertheless deadlock. Correct concurrent software must therefore address both the integrity of shared state and the possibility of continued execution.

Necessary conditions and dependency models

For the classical model of reusable, nonpreemptible resources, four conditions are necessary for resource deadlock. Mutual exclusion means that at least one relevant resource cannot be used by competing activities simultaneously. Hold and wait means that an activity retains resources while requesting others. No preemption means that resources cannot simply be taken away before the holder releases them. Circular wait means that a chain of activities exists in which each waits for a resource held by the next, with the last waiting for the first.

These conditions must be interpreted together and within their model. A system that permits all four is susceptible to deadlock; their mere availability does not establish that a particular execution is deadlocked. Conversely, a protocol that guarantees the absence of any one condition excludes classical resource deadlock. The conditions also need adaptation for communication protocols, alternative waits, and events that are not represented naturally as reusable resources.

A resource-allocation graph represents processes and resources as vertices. A request edge leads from a process to a resource it awaits; an assignment edge leads from a resource instance to its current holder. If every resource type has exactly one instance, a cycle characterizes deadlock in the standard model where blocked processes require their outstanding requests to be satisfied before continuing. With multiple instances of a resource type, a cycle is necessary but not sufficient. An instance held by a process outside the cycle may later become available and allow the cycle to dissolve.

A wait-for graph removes explicit resource vertices. An edge Pi→PjP_i \rightarrow P_j indicates that PiP_i is blocked by a resource or action controlled by PjP_j. In a conventional single-instance, conjunctive waiting model, a directed cycle identifies a deadlocked dependency. The model must specify what an edge means, however. If a task can proceed when any one of several events occurs, one cyclic dependency does not necessarily prevent progress through another alternative. Such disjunctive waits require stronger closed-dependency conditions than the existence of an arbitrary cycle.

The boundary of the modeled system also matters. A process waiting for a reply from an external service may appear permanently blocked, but whether it is deadlocked depends on the service's dependencies and the protocol's escape paths. Similarly, a timer that initiates a successful rollback can break an otherwise permanent wait. A useful deadlock model therefore specifies resource ownership, request semantics, release rules, and which external transitions remain possible, rather than treating every long wait as an equivalent condition.

Prevention through resource and lock discipline

Deadlock prevention establishes rules that make at least one necessary condition impossible. The best-known method is a global lock order. Every lock receives a position in a strict order, and a thread may acquire additional locks only in increasing order. A hypothetical circular wait would then require

L1<L2<⋯<Lk<L1,L_1 < L_2 < \cdots < L_k < L_1,

which contradicts the order. This argument does not depend on favorable scheduling: it excludes the cycle structurally.

An order can follow object type, subsystem hierarchy, or a stable identifier assigned to individual objects. Operations involving two accounts, for example, can lock the account with the smaller identifier first regardless of the transfer direction. Dynamic object structures complicate the rule because an operation may discover new objects only after acquiring a lock. Lock ordering must also cover interactions between subsystems; separate, locally consistent hierarchies can still conflict when a call crosses their boundary.

Another approach eliminates hold and wait by requiring all needed resources to be acquired together. A task either obtains its complete set or waits without holding any of it. This works well when the resource set is known in advance, but it may reserve resources long before they are used and can cause starvation for tasks needing large combinations. An alternative is to release previously acquired resources when a later acquisition fails, then retry. That approach requires the partially completed operation to be reversible or to have made no externally visible changes. Without a suitable retry policy, it can replace deadlock with livelock.

Preemption can break the no-preemption condition when resource state can be saved, restored, or reconstructed. Processor time is routinely preempted, but taking a mutex away from a thread midway through updating a linked structure is generally unsafe. The interrupted thread may have temporarily violated an invariant that other threads rely on. Systems therefore distinguish resources that can be reclaimed mechanically from ownership that can be revoked only through a higher-level operation such as transactional rollback.

Some designs reduce mutual exclusion by avoiding shared mutable state. Immutable data, ownership transfer, partitioned state, and message passing can remove particular lock dependencies. They do not automatically make the whole application deadlock-free: two components can still wait for messages from each other. Likewise, automatic lock release at scope exit prevents forgotten releases but does not stop two threads from acquiring different locks in opposite orders. Prevention depends on the structure of all relevant dependencies, not merely on the correctness of individual lock operations.

Avoidance and safe resource allocation

Deadlock avoidance differs from prevention by examining the current allocation state before granting a request. Rather than permanently prohibiting a necessary condition, it refuses transitions that could leave the system without a guaranteed completion path. This generally requires information about future resource needs, especially an upper bound on how many instances of each resource a process may request.

A state is safe if there is an ordering of the active processes such that each could obtain its remaining declared resources, finish, and release its allocation for use by the next. Safety is not the same as the absence of a current deadlock. An unsafe state may contain no blocked process and may ultimately complete if future requests are modest. What it lacks is a completion guarantee under the maximum demands admitted by the model.

The banker's algorithm formalizes this distinction. For nn processes and mm resource types, let Available\mathrm{Available} contain the unallocated resource counts, Allocationi\mathrm{Allocation}_i the resources held by process ii, and Maxi\mathrm{Max}_i its declared maximum demands. Its remaining potential demand is

Needi=Maxi−Allocationi.\mathrm{Need}_i=\mathrm{Max}_i-\mathrm{Allocation}_i.

A safety test starts with Work=Available\mathrm{Work}=\mathrm{Available}. It repeatedly finds an unfinished process whose need is componentwise no greater than Work, marks it as able to finish, and adds its current allocation to Work. If every process can be marked, the state is safe. A request is granted only if it is within the declared remaining demand, the resources are available, and the tentative allocation passes this test.

For example, suppose a system has ten identical resource units. P1 holds five and may need at most two more; P2 holds two and may need at most three more. Three units are free, so either process can be allowed to finish first. If P2 receives two additional units, only one remains free. P2 can still finish after receiving that unit, release its five units, and allow P1 to finish. By contrast, with maximum claims of eight for P1 and six for P2, the same initial allocation is unsafe: P1 might need three more and P2 four more, but after allocating resources carelessly neither might be able to complete.

A straightforward safety test takes O(n2m)O(n^2m) time in the worst case, because repeated scans may be needed to identify finishable processes. More important in practice are its assumptions: maximum claims must be available, resource counts must be meaningful, and completion must release resources as modeled. General-purpose applications often discover their needs dynamically, making those assumptions difficult to satisfy. The banker's algorithm remains influential as a precise demonstration that avoiding unsafe allocations is different from merely checking whether a deadlock already exists.

Detection, recovery, and the limits of timeouts

Deadlock detection allows potentially dangerous allocations and checks whether an actual deadlock has formed. This can be advantageous when deadlocks are uncommon and restrictive prevention rules would reduce normal concurrency. Detection may run periodically, when a request has waited long enough, or whenever new dependencies are added. Frequent checks reduce the duration of deadlocks but consume processing time and may require coordination around shared lock-management structures.

For single-instance resources with conjunctive waits, detecting a cycle in the wait-for graph is sufficient. Standard graph traversal can identify cycles in O(V+E)O(V+E) time, where VV is the number of vertices and EE the number of edges. Multiple-instance resources require an allocation-based test. Such a detector considers current allocations, currently outstanding requests, and available resources, repeatedly identifying processes that can finish and release their holdings. Unlike the banker's safety test, it need not use maximum possible future demands; it is examining whether present requests can be satisfied.

Once a deadlock is detected, recovery must change the dependency structure. Possible actions include terminating all participants, aborting one selected participant, rolling work back to a checkpoint, or reclaiming a resource whose state can be restored safely. Victim selection can consider priority, work already performed, rollback cost, resources held, and the effects on dependent operations. Repeatedly choosing the same inexpensive victim can starve it, so selection policies may account for previous aborts.

Recovery is straightforward only when the system has a well-defined way to undo partial work. Aborting a database transaction can release its locks while restoring transactional state. Terminating an arbitrary operating-system thread may instead leave memory structures inconsistent or locks permanently held. If an operation has already sent an email, actuated a device, or called an external service, rolling back local memory cannot reverse that external effect. Recovery protocols must distinguish reversible state changes from actions requiring compensation or reconciliation.

Timeouts provide a simpler but less precise mechanism. A sufficiently long wait may cause an operation to fail and release resources, thereby breaking some deadlocks. But no finite timeout reliably distinguishes deadlock from an unusually slow execution in a general asynchronous system. A timeout is therefore a policy decision about acceptable waiting, not a proof of circular dependency. Moreover, a timeout breaks the deadlock only if cancellation actually releases the relevant resources or enables another participant. Abandoning a request while leaving its locks or remote work active can preserve the original obstruction and create additional cleanup problems.

Deadlocks in database systems

Deadlock is particularly important in a database management system because transactions often acquire many locks over data discovered during execution. A transfer transaction might update account A and then account B while another updates B and then A. If both retain their first lock while requesting the second, they can deadlock even though each statement is individually valid and both transactions obey the database's concurrency-control rules.

Two-phase locking separates acquisition from release: once a transaction begins releasing locks, it cannot acquire new ones. Strict variants retain exclusive locks until transaction completion, making it easier to prevent other transactions from observing uncommitted updates. These protocols support serializable or recoverable schedules under their respective conditions, but they do not inherently prevent deadlock. The resources involved may be rows, pages, tables, index entries, or ranges of keys rather than application-level objects.

Lock conversion creates another common pattern. Two transactions can both hold shared locks on an item and then each request an exclusive lock to modify it. Each upgrade conflicts with the other's shared lock, so neither proceeds. Some systems provide update-lock modes or impose restrictions on conversion to reduce this pattern. Range and predicate-related locking can produce dependencies that are less obvious than two statements updating the same row, because protection against newly inserted qualifying records extends beyond existing individual records.

Database lock managers commonly construct a wait-for graph and abort a victim when they detect a cycle. The transaction's undo or recovery machinery then removes its changes and releases its locks. The other transaction can continue, while the aborted transaction may be retried as a new attempt. Retrying requires attention to external effects and transaction boundaries: a client that repeats only the last statement may not reproduce the intended logic of the original multi-statement operation.

Timestamp-based prevention offers an alternative. Under wait-die, an older transaction may wait for a younger one, but a younger transaction requesting a resource held by an older one is aborted. Under wound-wait, an older requester can force a younger holder to abort, while a younger requester waits for an older holder. These rules make wait edges follow an age direction and thereby exclude cycles. Preserving an aborted transaction's original timestamp across retries helps prevent continual displacement by newer transactions.

Multiversion concurrency control reduces some conflicts by allowing readers to use older committed versions rather than blocking writers. It does not universally eliminate deadlock. Writers can still conflict, explicit locking can introduce waits, and schema or metadata operations may use additional locks. Similarly, serializability and deadlock freedom are different properties: the former constrains the meaning of concurrent outcomes, while the latter concerns whether the system can reach an outcome at all.

Distributed deadlock and incomplete information

In distributed computing, a dependency cycle may span machines or administrative components. A transaction at site A can wait for a lock at site B, while the holder at B waits for a service at C, and that service depends on work blocked at A. Each local component may appear merely to be waiting for a legitimate remote operation. No individual lock manager necessarily has enough information to identify the complete cycle.

A centralized detector can collect dependency information and build a global wait-for graph, but reports arrive at different times. A hierarchical design aggregates information through several levels, while fully distributed algorithms exchange messages among the participants. These arrangements differ in communication overhead, bottlenecks, failure handling, and how quickly they recognize a stable deadlock. The graph is not merely large; it is changing while observations travel through the network.

This creates the possibility of a phantom deadlock, in which a detector combines dependencies that did not coexist. For example, an old report that A waits for B may arrive after that wait has ended, while a newer report states that B waits for A. Their union appears cyclic even if no real cycle occurred. Version numbers, carefully defined observation protocols, and validation before recovery can help distinguish a current dependency from stale information. The detector must also interpret message delays and failed processes separately from resource deadlock.

Distributed edge-chasing algorithms investigate dependencies by sending probes along wait edges. The Chandy–Misra–Haas algorithms, published in 1983, are influential examples. In an appropriate conjunctive waiting model, a blocked initiator sends probes through the processes on which it depends; a probe returning to the initiator can establish a circular dependency under the algorithm's assumptions. Algorithms for alternative waiting models require different conditions, because the existence of one cyclic route does not exclude another route that could enable progress.

Distributed transactions introduce a related but distinct blocking problem. In two-phase commit, a participant that has prepared may be unable to decide independently whether to commit or abort if it cannot obtain the coordinator's decision. That can retain locks and obstruct other transactions, but coordinator-induced blocking is not automatically a deadlock: there may be no circular wait. A system can suffer both problems simultaneously, so resolving transaction-decision uncertainty and detecting resource cycles are separate responsibilities.

Cross-service calls can also create application-level deadlock without a distributed lock manager. Service A may retain a local lock while synchronously calling B; B then calls back into A along a path requiring that lock. If the original invocation waits for the callback to complete, the cycle crosses both lock ownership and network communication. A diagnosis limited to either the local mutex graph or the remote call graph would miss part of the dependency.

Communication, execution capacity, and hardware

Deadlock is not limited to explicit locks. In interprocess communication, processes may wait for sends or receives that no participant can perform. With synchronous rendezvous communication, two processes that both attempt a blocking send before either performs a receive can remain stuck. In buffered communication, available capacity may permit the exchange initially, yet a later configuration can deadlock when every participant holds data that it cannot forward.

Bounded queues illustrate the importance of capacity as a resource. A producer can block because a queue is full while holding a mutex needed by the consumer that would remove an item. Neither queue operations nor mutex operations alone reveal the entire problem. Similarly, an incorrectly implemented condition-variable protocol may wait while retaining the very lock needed to establish the awaited condition. Standard condition-variable operations avoid that particular pattern by atomically releasing the associated mutex while waiting and reacquiring it before returning.

Execution slots can also form a limited resource. Suppose a thread pool has kk workers, all kk are running parent tasks, and each parent submits a child task to the same pool and waits synchronously for it. The children cannot run because every worker is occupied by a waiting parent. This is often called thread-pool starvation or thread-pool deadlock. A larger pool may postpone the failure without removing the dependency pattern. Some schedulers mitigate it through cooperative execution, work helping, or special handling of blocked tasks, but such behavior depends on the runtime.

An event loop presents a related case. A callback running on the loop may synchronously wait for a result whose completion callback must execute on that same loop. Since the loop cannot dispatch the completion until the current callback returns, progress stops. Asynchronous programming avoids occupying the loop during an ordinary asynchronous wait, but asynchronous syntax does not itself eliminate circular dependencies: two tasks can still await results that depend on each other's completion.

Hardware communication networks face analogous resource cycles. In wormhole-routed interconnects, a packet can hold channels or buffers while waiting for the next channel. Several packets can thereby create a cycle of channel dependencies. Routing rules can prevent selected turns so that the relevant dependency graph is acyclic, while virtual channels separate traffic into logical channel classes that can be organized to provide a deadlock-free escape route.

Flow control, routing, and protocol dependencies must be considered together. Even a routing algorithm without channel cycles may participate in a higher-level request–response deadlock if requests consume all buffering needed to deliver the responses that would release them. Separate request and response resources are one common design technique. The essential abstraction remains the same across software and hardware: progress requires an available sequence of transitions, and finite capacity can become part of the ownership-and-wait structure.

Verification, diagnostics, and progress guarantees

Deadlock analysis is a major application of formal verification. A model can represent threads, locks, channels, and relevant program states, then explore whether execution can reach a nonterminal state with no permitted progress. In model checking, finite-state exploration can identify a concrete sequence of interleavings leading to deadlock. The difficulty is state-space growth: adding threads, queue entries, or possible message orders rapidly increases the number of reachable configurations.

A state with no enabled transition is not always an error. Successful termination must be distinguished from an unintended standstill, and a subsystem can be deadlocked while unrelated transitions elsewhere remain enabled. Temporal specifications can express requirements such as eventual completion of every accepted request, but their meaning depends on fairness assumptions. A scheduler that never runs a ready thread can violate progress without any lock cycle. Verification therefore separates structural deadlock from failures caused by unfair scheduling.

Static analysis can infer lock-acquisition relationships from source code and report potential ordering cycles. Type and ownership systems can enforce more restrictive disciplines before execution. Such techniques face aliasing, dynamic dispatch, callbacks, and dynamically created objects: two references may denote the same lock, and a library call may acquire resources not visible at the call site. Conservative analysis can report a cycle that no feasible execution can realize, while incomplete analysis can miss a real dependency.

Runtime lock-order checking records relationships observed during execution. The lockdep facility in Linux, for example, reasons about lock classes and acquisition dependencies to identify potentially unsafe patterns, including interactions with interrupt contexts. Such tools can detect a dangerous ordering without waiting for a real hang, but their coverage depends on which paths are exercised and how accurately lock usage is represented. Runtime detection of one class of lock cycle is not a proof that every communication or capacity dependency is safe.

Practical diagnosis combines thread stacks, lock ownership, transaction waits, queue occupancy, and request traces. A useful reconstruction identifies not only what each participant is waiting for, but who can satisfy that wait and what prevents that participant from acting. Repeated snapshots help distinguish a stable dependency from a temporarily slow operation. Cross-process identifiers are especially important when a wait crosses network calls, worker pools, and transaction boundaries.

Stronger progress terminology distinguishes several guarantees. Deadlock freedom generally rules out a collective standstill caused by the protocol, but it does not guarantee that every individual participant succeeds. Lock-free algorithms guarantee system-wide progress under their specified execution assumptions, while wait-free algorithms guarantee completion of each operation within a bounded number of its own steps. Neither guarantee automatically extends to an enclosing application that performs blocking input/output or waits on external services. A component's progress claim must therefore be interpreted at the level of operations and dependencies covered by its specification.