Deadlock & Coffman's Conditions

Edgar Coffman identified four necessary conditions in 1971 — all four must hold simultaneously for a deadlock to occur. Mutual exclusion means a resource can only be used by one thread at a time. Hold-and-wait means a thread already holding a resource is waiting to acquire another. No preemption means the OS cannot forcibly reclaim a resource. Circular wait means there's a cycle in the resource-allocation graph.

Five philosophers sit at a round table with a fork between each pair. Each philosopher must pick up both adjacent forks to eat. If every philosopher picks up their left fork simultaneously, they all wait forever for the right fork — circular wait achieved. This thought experiment maps directly to real database lock scenarios where two transactions each hold one row lock and wait for the other.

-- Transaction A          -- Transaction B
LOCK row 1               LOCK row 2
WAIT for row 2...        WAIT for row 1...
-- Deadlock! Neither can proceed.

To prevent deadlocks you only need to break one of the four conditions. The most practical approach is to eliminate circular wait by imposing a global ordering on resources — threads must always acquire locks in the same fixed order. Another approach is to require threads to request all resources at once (breaks hold-and-wait), though this reduces concurrency. Allow preemption (forcibly roll back a thread) is used in database systems.

Some systems (like most database engines) allow deadlocks to happen and then detect them by running a cycle-detection algorithm on the wait-for graph. Once a deadlock is detected, the system picks a victim — typically the transaction that has done the least work — and rolls it back, releasing its locks. The other transaction can then proceed. The victim retries automatically.