Introduction
Database transactions often lock records before updating them. A transaction may need to wait when another transaction holds a conflicting lock. Usually, that wait ends when the lock holder finishes its work.
A deadlock is different: transactions form a circular dependency, so none can continue without intervention. Deadlock handling combines prevention techniques, detection, rollback, and retries to keep database work moving.
What Is a Deadlock in DBMS?
A deadlock occurs when two or more transactions wait for resources held by one another in a cycle.
For example, T1 may hold a lock that T2 needs, while T2 holds a lock that T1 needs. Neither transaction can complete its next operation and release the lock blocking the other.
An ordinary lock wait is not necessarily a deadlock. If T2 waits for T1, but T1 can continue and commit, the wait can resolve normally.
Example Table and Deadlock Formation
The examples use an Account table containing each account’s identifier, holder name, and balance.
Account: initial data
AccountID | HolderName | Balance |
|---|---|---|
1 | Asha | 1000.00 |
2 | Ravi | 500.00 |
AccountID is the primary key. A refers to Asha’s account, and B refers to Ravi’s account.
An exclusive lock, written as X, protects an item against conflicting access by other transactions. Thus, X(A) means an exclusive lock on Asha’s account.
Consider this sequence:
Step | T1 | T2 |
|---|---|---|
1 | Locks A. | |
2 | Locks B. | |
3 | Requests B and waits for T2. | |
4 | Requests A and waits for T1. |
T1 cannot continue without B, and T2 cannot continue without A. This circular wait creates a deadlock.
Deadlocks can occur even when transactions follow two-phase locking correctly. Serializability guarantees and freedom from deadlock are separate concerns.
Conditions Required for Deadlock
The classical deadlock model has four necessary conditions:
Condition | Meaning in the account example |
|---|---|
Mutual exclusion | Conflicting exclusive locks cannot be held by different transactions on the same account. |
Hold and wait | Each transaction holds one lock while requesting another. |
No preemption | A transaction cannot simply take a conflicting lock away from its holder. |
Circular wait | T1 waits for T2, and T2 waits for T1. |
The database can break the situation by aborting a transaction and releasing its locks. This is controlled recovery, rather than another transaction forcibly taking a lock while the holder continues unchanged.
Deadlock Prevention and Avoidance
Prevention imposes rules that stop a necessary deadlock condition from arising.
Common approaches include:
Consistent lock ordering: Every transaction locks shared resources in the same order. For the example, both transactions lock A before B.
Conservative locking: Obtain the full required lock set before beginning data operations. If the set is unavailable, wait without holding a partial set.
No-wait policy: Abort and retry a transaction instead of allowing it to wait for an unavailable lock.
Timestamp-based rules: Use transaction age to decide which transaction may wait and which must abort.
Consistent ordering prevents the illustrated circular wait. If T1 locks A first, T2 waits for A before acquiring B, leaving T1 free to acquire B and finish.
Use one lock order
Avoidance makes a decision when a resource request arrives, granting it only if the system remains in a safe state. A safe state has an order in which all transactions could finish, given their declared resource needs. This approach requires information about future requests that database applications may not know in advance. An unsafe state means completion cannot be guaranteed, not that a deadlock already exists.
Wait-Die and Wound-Wait
These timestamp-based prevention schemes assign each transaction an age. An earlier timestamp means an older transaction.
Situation | Wait-die | Wound-wait |
|---|---|---|
Older transaction requests a lock held by a younger transaction | Older requester waits. | Younger holder is aborted. |
Younger transaction requests a lock held by an older transaction | Younger requester is aborted. | Younger requester waits. |
In wait-die, a transaction either waits or aborts itself. In wound-wait, an older requester can cause a younger holder to abort.
Restarted transactions normally retain their original timestamps under these schemes. This helps prevent repeated restarts from continually making the same transaction “youngest.”
These are theoretical protocol choices, not settings that MySQL and PostgreSQL universally use for every lock conflict.
Deadlock Detection with a Wait-For Graph
A wait-for graph represents current blocking relationships:
Each node represents a transaction.
An edge T1 → T2 means T1 is waiting for a lock held by T2.
For the account example:
Waiting transaction | Lock needed | Lock holder | Graph edge |
|---|---|---|---|
T1 | B | T2 | T1 → T2 |
T2 | A | T1 | T2 → T1 |
The graph contains a cycle. In this ordinary transaction-lock model, that cycle identifies a deadlock.
A wait-for graph differs from a serializability precedence graph. It records current waiting, not the order of conflicting operations that already executed.
A lock timeout is another way to stop prolonged waiting, but it does not prove that a deadlock exists. A slow transaction can cause a timeout without any circular dependency.
Detecting a deadlock
Recovery, Victim Selection, and Retries
After detecting a deadlock, the database selects a victim transaction to abort. Rolling back that transaction releases its locks, allowing other transactions to proceed.
Victim selection may consider factors such as rollback cost, transaction size, priority, and work already performed. The exact policy depends on the database. Applications must not assume that the transaction issuing the last statement will always be selected.
A suitable application retry process is:
Recognize the deadlock error.
Ensure the failed transaction has ended.
Wait briefly, often with a small randomized delay.
Start a new transaction.
Repeat the whole transaction, including its reads and condition checks.
Commit if successful, with a limit on retry attempts.
Retrying only the failed statement is unsafe when the database has rolled back the entire transaction.
Repeatedly aborting the same transaction can cause starvation. Fair victim selection and sensible retry policies help reduce that risk.
Recover and retry
A Compact SQL Example
Objective: Create a two-session deadlock using locking reads and observe how the database resolves it.
The example intentionally performs no updates. It demonstrates that a deadlock concerns locks and waiting, even when stored values have not changed.
Use two separate database connections:
Session A: Represents T1.
Session B: Represents T2.
Execute the numbered steps in order. When Session A waits in step 4, continue in Session B rather than waiting for Session A’s query to finish.
1. Create the Initial Table
Consider the following queries to create and populate the account table.
CREATE TABLE Account ( AccountID INT PRIMARY KEY, HolderName VARCHAR(50) NOT NULL, Balance DECIMAL(10, 2) NOT NULL);START TRANSACTION;INSERT INTO Account (AccountID, HolderName, Balance)VALUES (1, 'Asha', 1000.00), (2, 'Ravi', 500.00);COMMIT;Initial data:
AccountID | HolderName | Balance |
|---|---|---|
1 | Asha | 1000.00 |
2 | Ravi | 500.00 |
2. Session A: Lock Asha’s Account
Consider the following queries to start T1 and lock account 1.
START TRANSACTION;SELECT AccountID, BalanceFROM AccountWHERE AccountID = 1FOR UPDATE;FOR UPDATE requests a row lock suitable for a later update. The transaction keeps the lock while it remains open.
Expected result:
AccountID | Balance |
|---|---|
1 | 1000.00 |
3. Session B: Lock Ravi’s Account
Consider the following queries to start T2 and lock account 2.
START TRANSACTION;SELECT AccountID, BalanceFROM AccountWHERE AccountID = 2FOR UPDATE;Expected result:
AccountID | Balance |
|---|---|
2 | 500.00 |
4. Session A: Request Ravi’s Account
Consider the following query to request the row already locked by Session B.
SELECT AccountID, BalanceFROM AccountWHERE AccountID = 2FOR UPDATE;5. Session B: Request Asha’s Account
Consider the following query to request the row already locked by Session A.
SELECT AccountID, BalanceFROM AccountWHERE AccountID = 1FOR UPDATE;There is now a cycle: Session A waits for Session B, and Session B waits for Session A.
With normal deadlock detection enabled and no earlier timeout interrupting the example, the database selects one transaction as the victim.
Expected outcomes:
Database | Typical victim error | Recovery behavior |
|---|---|---|
MySQL | Error | Rolls back the victim transaction. |
PostgreSQL |
| Aborts the victim transaction; issue |
The surviving transaction’s waiting query can complete:
Survivor | Result of its waiting query |
|---|---|
Session A | AccountID 2, Balance 500.00 |
Session B | AccountID 1, Balance 1000.00 |
Only one of these survivor outcomes occurs in this two-transaction example. The victim is not fixed.
6. End Both Transactions and Check the Data
Consider the following command in each session to finish the demonstration and release any remaining transaction state.
ROLLBACK;If the database has already ended a transaction, this command may simply report that no transaction is active.
Consider the following query in either session to inspect the final table.
SELECT AccountID, HolderName, BalanceFROM AccountORDER BY AccountID;Expected result:
AccountID | HolderName | Balance |
|---|---|---|
1 | Asha | 1000.00 |
2 | Ravi | 500.00 |
The balances remain unchanged because the demonstration acquired locks but performed no updates.
To prevent this particular deadlock, both transactions should request account 1 before account 2. One transaction may wait, but it will not hold account 2 while waiting for account 1.
Summary
A deadlock forms when transactions wait for one another in a cycle. Prevention rules reduce the opportunity for circular waiting, while detection uses blocking relationships to identify a deadlock that has already formed. A timeout indicates excessive waiting, not necessarily a deadlock.
Recovery usually aborts a victim transaction and releases its locks. Applications should handle the resulting error, retry the whole transaction when appropriate, and use consistent lock ordering and short transactions to reduce repeated conflicts.
Be the first to add a comment.