The chapter on concurrency control ended with an honest caveat: two-phase locking guarantees serializability, but it does not, by itself, prevent every possible problem that can arise when multiple transactions compete for locks on shared data. One of the most frustrating problems that can still occur is deadlock, a situation where two or more transactions become permanently stuck, each waiting for a lock held by another transaction in the group, with none of them able to proceed and none of them willing to give up what they already hold.
Deadlock is not a rare, exotic edge case; it is a natural consequence of any system that allows transactions to hold some locks while waiting for others. Left unaddressed, a deadlocked group of transactions would simply sit frozen forever, silently consuming resources without making any progress, eventually bringing an application to its knees as more and more transactions pile up waiting behind the stuck ones. Database systems must therefore include explicit strategies for dealing with deadlock, whether by preventing it from ever occurring, avoiding it dynamically, or detecting and recovering from it after the fact.
In this tutorial, you will learn what deadlock is and the conditions required for it to occur, how a wait-for graph is used to represent and detect deadlock visually, the wait-die and wound-wait schemes used to prevent deadlock before it happens, and the standard techniques used to recover once a deadlock has actually been detected.
Deadlock occurs when a set of two or more transactions are each waiting for a lock currently held by another transaction within that same set, forming a closed cycle of waiting from which none of the involved transactions can ever escape without outside intervention.
T1: Lock-X(A) T2: Lock-X(B) T1: Lock-X(B) (must wait, since T2 currently holds a lock on B) T2: Lock-X(A) (must wait, since T1 currently holds a lock on A) T1 is waiting for T2 to release B. T2 is waiting for T1 to release A. Neither transaction can proceed, and neither will voluntarily release the lock it holds, since doing so would violate two-phase locking's growing phase rules discussed in the previous chapters. Both transactions are now permanently stuck.
This small example captures the essential shape of every deadlock: a circular chain of "waiting for," where following the chain of dependencies eventually leads back to where it started, with every transaction along that chain unable to make progress.
Deadlock can only occur when four specific conditions are all simultaneously true. Removing even one of these conditions is enough to make deadlock impossible, which is exactly the strategy behind several prevention techniques discussed later in this chapter.
| Condition | Description |
|---|---|
| Mutual Exclusion | At least one resource must be held in a non-shareable mode, meaning only one transaction can use it at a time, such as an exclusive lock. |
| Hold and Wait | A transaction holding at least one resource is simultaneously waiting to acquire additional resources currently held by other transactions. |
| No Preemption | Resources cannot be forcibly taken away from a transaction; they can only be released voluntarily by the transaction holding them. |
| Circular Wait | A closed chain of transactions exists, where each transaction is waiting for a resource held by the next transaction in the chain. |
A wait-for graph is a simple, powerful tool used to represent which transactions are currently waiting for which other transactions, making it easy to visually spot, and formally detect, the presence of deadlock within a system.
1. Create one node for every active transaction in the system. 2. Draw a directed edge from Ti to Tj whenever Ti is waiting for a lock currently held by Tj. Rule: A deadlock exists in the system if and only if the wait-for graph contains a cycle.
Using the earlier example: T1 is waiting for T2 (since T1 wants lock on B, held by T2) T2 is waiting for T1 (since T2 wants lock on A, held by T1) Wait-For Graph: T1 → T2 T2 → T1
T1 ⇄ T2
This graph contains a direct two-node cycle between T1 and T2, confirming that these two transactions are indeed deadlocked. A larger system might involve longer cycles spanning several transactions, but the detection rule remains exactly the same: search the wait-for graph for any cycle at all.
T1 waits for T2 T2 waits for T3 T3 waits for T1 Wait-For Graph: T1 → T2 → T3 → T1
Even though no two transactions here are waiting directly on each other, the three-way cycle T1 → T2 → T3 → T1 still represents a genuine deadlock, since following the chain of dependencies eventually loops back to T1, meaning none of the three transactions can ever be the first to proceed.
Database systems generally adopt one of three broad strategies for dealing with the possibility of deadlock, each with its own tradeoffs between overhead, complexity, and how aggressively transactions are restarted.
| Strategy | Approach |
|---|---|
| Deadlock Prevention | Design the locking protocol so that deadlock can never occur in the first place, typically by imposing an ordering on transactions and forcing certain transactions to abort rather than wait indefinitely. |
| Deadlock Avoidance | Allow transactions to wait, but carefully check before granting each lock request whether granting it could potentially lead to deadlock, denying requests that would create risk. |
| Deadlock Detection and Recovery | Allow deadlock to occur, periodically check the system for cycles using a wait-for graph, and recover by aborting one or more of the deadlocked transactions once a cycle is found. |
Two widely taught deadlock prevention schemes use transaction timestamps, similar to the timestamp-based concurrency control protocol from the previous chapter, to decide what should happen whenever a transaction requests a lock currently held by another transaction. Both schemes guarantee that no circular wait can ever form, directly removing one of the four necessary conditions for deadlock.
In the wait-die scheme, when transaction Ti requests a lock held by Tj, the decision depends on which transaction is older, meaning which one has the earlier timestamp. If Ti is older than Tj, Ti is allowed to wait. If Ti is younger than Tj, Ti is immediately aborted, or "dies," and must restart later with its original timestamp preserved.
Rule: Older transaction waits for younger transaction.
Younger transaction dies (aborts) if it requests a lock held by an older transaction.
Example:
T1 has timestamp 10 (older), T2 has timestamp 20 (younger)
T2 requests a lock held by T1:
T2 is younger than T1, so T2 dies and is rolled back, restarting later with timestamp 10 preserved.
T1 requests a lock held by T2:
T1 is older than T2, so T1 is allowed to wait.
The wound-wait scheme reverses the roles compared to wait-die. If Ti is older than Tj and requests a lock held by Tj, Ti forcibly aborts Tj, said to "wound" it, taking the lock for itself. If Ti is younger than Tj, Ti is allowed to wait normally.
Rule: Older transaction wounds (forcibly aborts) younger transaction holding the lock.
Younger transaction waits if it requests a lock held by an older transaction.
Example:
T1 has timestamp 10 (older), T2 has timestamp 20 (younger)
T1 requests a lock held by T2:
T1 is older than T2, so T1 wounds T2, forcing T2 to abort and release the lock.
T2 requests a lock held by T1:
T2 is younger than T1, so T2 is allowed to wait.
Both schemes guarantee that only one direction of waiting is ever permitted, based on transaction age, which makes it mathematically impossible for a circular wait to ever form, since a cycle would require waiting to occur in both directions simultaneously somewhere along the chain.
| Scheme | Older Transaction's Behavior | Younger Transaction's Behavior |
|---|---|---|
| Wait-Die | Waits for the younger transaction. | Dies (aborts) if it requests a lock held by an older transaction. |
| Wound-Wait | Wounds (forcibly aborts) the younger transaction holding the needed lock. | Waits for the older transaction. |
Rather than preventing deadlock proactively, many systems instead allow it to occur, periodically constructing a wait-for graph and checking it for cycles. This approach trades some risk of temporary deadlock for lower overhead during normal operation, since prevention schemes like wait-die and wound-wait require extra bookkeeping and can cause unnecessary aborts even when no actual deadlock would have occurred.
Once a cycle is found in the wait-for graph, the system must choose at least one transaction within that cycle to abort, breaking the cycle and allowing the remaining transactions to proceed. Several factors are typically considered when selecting which transaction, sometimes called the victim, to abort.
Wait-For Graph: T1 → T2 → T3 → T1 Suppose T3 has completed the least work so far among the three transactions. Recovery action: Abort T3, releasing all locks it currently holds. Updated Wait-For Graph: T1 → T2 The cycle is broken, and T2 can now acquire the lock previously held by T3, allowing both T1 and T2 to eventually proceed normally.
Without any deadlock handling strategy at all, a busy database system would eventually accumulate deadlocked transactions that silently consume locks and system resources forever, gradually strangling the system's ability to make progress on new work. Whether a system chooses prevention, avoidance, or detection and recovery depends heavily on its specific workload characteristics, since prevention schemes trade some unnecessary aborts for guaranteed safety, while detection-based approaches trade a small risk of temporary deadlock for lower everyday overhead.
| Mistake | Correct Understanding |
|---|---|
| Confusing deadlock with starvation. | Deadlock is a permanent circular wait with no progress possible at all, while starvation involves a transaction being repeatedly delayed or aborted, but eventually could still complete. |
| Believing all four deadlock conditions must be actively removed at once. | Removing even a single one of the four necessary conditions, such as circular wait, is sufficient to prevent deadlock entirely. |
| Mixing up the wait-die and wound-wait rules. | In wait-die, the older transaction waits and the younger one dies; in wound-wait, the older transaction wounds the younger one, and the younger transaction waits instead. |
| Assuming a wait-for graph cycle must involve exactly two transactions. | A cycle can involve any number of transactions chained together, as demonstrated by the three-transaction cycle example in this chapter. |
Deadlock represents a permanent standstill among a group of transactions, each waiting on the others in a closed circular chain, and every strategy for handling it revolves around either preventing that circular chain from ever forming, avoiding it dynamically, or detecting and breaking it once it appears. Through the four necessary conditions, the wait-for graph detection method with worked cycle examples, and the wait-die and wound-wait prevention schemes, this chapter demonstrated the complete toolkit database systems use to keep concurrent transactions moving forward reliably.
In this tutorial, you learned what deadlock is and the four conditions required for it to occur, how to construct and interpret a wait-for graph using two worked examples, how the wait-die and wound-wait schemes prevent deadlock using transaction timestamps, and how systems recover once a deadlock has actually been detected. With this foundation, you are ready to move on to the recovery system, which covers how a database restores itself to a consistent state after a crash, building on many of the same logging and rollback ideas introduced throughout this chapter.