Deadlock
Subject: Computer and Technology noun /ˈdɛd.lɑːk/ 1 definition
- operating-systems
- concurrent-computing
- database-systems
- distributed-systems
-
Definition (noun)
Entry #39 · UpdatedA Deadlock is a permanent blocking state in concurrent computing where two or more processes, threads, or transactions halt indefinitely because each holds exclusive access to a resource while waiting for another resource held by a different participant in the cycle. For a resource deadlock to arise, four necessary conditions—known as the Coffman conditions—must hold simultaneously: mutual exclusion, hold and wait, no preemption, and circular wait. Unlike livelock, in which tasks continually change state without making progress, or starvation, in which a runnable task is repeatedly denied resources by a scheduler, deadlocked tasks remain permanently suspended until external intervention breaks the cycle through timeout, preemption, process termination, or transaction rollback.
Common Forms
Resource (Lock-Ordering) Deadlock: Occurs when competing threads or processes acquire exclusive locks—such as mutexes, semaphores, or I/O devices—in conflicting orders, forming a circular wait where none can release what it already holds.
Communication Deadlock: Arises in message-passing systems, pipelines, or bounded channels when processes block indefinitely waiting to send or receive messages or acknowledgments from peers that are likewise blocked.
Database Transaction Deadlock: Happens when concurrent transactions acquire incompatible row, index, or table locks and request access to records locked by one another, prompting the lock manager to detect the cycle and roll back a victim transaction.
Distributed Deadlock: Spans multiple machines or networked services when remote procedure calls or distributed locks form a global wait-for cycle across separate lock managers with no single node holding complete local visibility.
Example
During a concurrent bank transfer workload, Transaction A updates row
account_101and holds its row-level exclusive lock before requesting an update onaccount_202, while Transaction B concurrently updatesaccount_202and requests an update onaccount_101. Because neither transaction can proceed or release its lock, PostgreSQL's lock manager detects the cycle in its wait-for graph and aborts one victim transaction with a deadlock error so the other can commit.