Deadlock Handling in Database Systems
Deadlock Prevention
Read aloud is unavailable in this browser.
Designing Deadlock Impossibility
What if we could design a system where deadlocks are mathematically impossible? Where no matter how transactions interleave or compete for resources, they could never form the circular dependencies that cause permanent blocking?
This is the promise of deadlock prevention—a proactive approach that constrains how transactions acquire locks to guarantee that at least one of the four Coffman conditions can never be satisfied. While detection accepts deadlocks and deals with them reactively, prevention eliminates the possibility at its root.
By the end of this page, you will master every major deadlock prevention strategy—from lock ordering to timestamp-based protocols. You'll understand which Coffman condition each technique targets, the performance tradeoffs involved, and when to choose prevention over detection.
Prevention vs. Detection: Deeper Analysis
Before examining specific prevention techniques, let's understand when prevention is preferable to detection:
When to Choose Prevention:
- Transactions are short-lived with predictable resource needs
- The cost of aborting and restarting is very high (long transactions, external effects)
- System has low tolerance for transaction rollbacks
- Resource access patterns are known in advance
- Deadlocks would be frequent without intervention
When Detection is Better:
- Dynamic, unpredictable resource access patterns
- High concurrency where prevention overhead is too costly
- Deadlocks are rare (< 0.1% of transactions)
- Quick rollback and retry is acceptable
- Maximum throughput is the priority
| Aspect | Prevention | Detection |
|---|---|---|
| Deadlock Possibility | Impossible by design | Can occur, resolved reactively |
| Normal Operation Overhead | Constant (every transaction) | Minimal (only check periodically) |
| When Deadlock Would Occur | May reject/wait preemptively | Actually deadlocks, then resolves |
| Transaction Aborts | Potentially many (preemptive) | Only when deadlock detected (actual) |
| Concurrency Level | Often restricted | Maximum possible |
| Implementation Complexity | Protocol design complexity | Algorithm complexity |
| Work Wasted | Aborts happen early (less wasted) | Aborts after deadlock (may waste more) |
| Determinism | More predictable behavior | Non-deterministic resolution |
Many production systems combine both approaches: use prevention techniques to minimize deadlock frequency, with detection as a safety net for cases that slip through. This defense-in-depth strategy provides robust deadlock management.
Breaking Mutual Exclusion
Coffman Condition #1: Mutual Exclusion
At least one resource must be held in non-sharable mode.
This condition is inherently difficult to eliminate because exclusive access is fundamental to maintaining data consistency during writes. However, certain techniques can reduce or work around it:
- •Multi-Version Concurrency Control (MVCC) — Readers can access older versions while writers create new versions. Readers never block writers and writers never block readers, eliminating read-write deadlocks entirely.
- •Optimistic Concurrency Control — Allow all operations to proceed without locks, validate at commit time. Conflicts detected (not prevented), but no blocking means no deadlock during execution.
- •Copy-on-Write (COW) — Create copies of resources instead of modifying in place. Multiple transactions work on independent copies, merging at commit. Reduces contention over shared resources.
- •Lock-Free Data Structures — Use atomic compare-and-swap operations instead of locks for certain structures. No blocking means no deadlock for those resources.
MVCC in Practice:
MVCC is the most impactful technique in this category. Here's how it eliminates read-write deadlocks:
Without MVCC (Traditional Locking):
T₁: Read X (acquires S-lock) → wants to Write Y (needs X-lock on Y)
T₂: Read Y (acquires S-lock) → wants to Write X (needs X-lock on X)
Deadlock possible: T₁ holds S(X), wants X(Y); T₂ holds S(Y), wants X(X)
With MVCC:
T₁: Read X (reads version 1, no lock) → Write Y (creates version 2)
T₂: Read Y (reads version 1, no lock) → Write X (creates version 2)
No deadlock: Reads don't block anything!
MVCC is used by PostgreSQL, MySQL InnoDB (with certain isolation levels), Oracle, and most modern databases.
For write-write conflicts, some form of mutual exclusion is unavoidable to maintain consistency. MVCC still requires exclusive access for concurrent writes to the same row. These techniques reduce but don't eliminate deadlock possibility entirely.
Breaking Hold and Wait
Coffman Condition #2: Hold and Wait
A transaction holds at least one resource while waiting for additional resources held by others.
This condition can be broken by ensuring transactions never hold resources while waiting for others. Two main approaches achieve this:
Approach 1: Pre-claim All Resources
Also known as Conservative 2PL or Static 2PL:
- Before execution begins, declare all resources needed
- Acquire ALL locks atomically before starting
- If any lock unavailable, wait without holding any
- Once all acquired, execute transaction
-- Conceptual implementation
BEGIN TRANSACTION;
ACQUIRE_ALL_LOCKS(Account_A, Account_B, Journal);
-- If successful, proceed
-- If any unavailable, release all and retry
EXECUTE transaction_logic;
COMMIT;
RELEASE_ALL_LOCKS();
Pros: Deadlock impossible Cons: Low concurrency, must know all resources upfront, resources held longer than necessary
Approach 2: Release Before Requesting
- When needing a new resource, first release all currently held resources
- Request the needed resource plus all previously held ones
- Re-acquire as atomic batch
-- Conceptual implementation
BEGIN TRANSACTION;
LOCK(Account_A);
work_on_A();
-- Need Account_B now
SAVE current_state;
UNLOCK(Account_A);
LOCK(Account_A, Account_B); -- Atomic batch
RESTORE saved_state;
work_on_A_and_B();
COMMIT;
Pros: Works with dynamic needs Cons: Complex state management, wasted work on re-acquisition, potential livelock
Implementation Considerations:
| Approach | Resource Prediction | Concurrency | Complexity | Best For |
|---|---|---|---|---|
| Pre-claim all | Required upfront | Low | Simple | Batch processing, static transactions |
| Release and re-acquire | Not required | Moderate | Complex | Dynamic transactions with state save/restore |
| Timeout with retry | Not required | High | Moderate | OLTP with short transactions |
Practical Challenges:
- Predicting Resources: Many transactions don't know what they'll access until they read data
- Lock Duration: Acquiring all locks upfront means holding them for the entire transaction
- Deadlock to Livelock: Release-and-retry can cause livelock if not carefully randomized
- Batch Lock Overhead: Atomic batch acquisition requires coordination, adding latency
Breaking No Preemption
Coffman Condition #3: No Preemption
Resources cannot be forcibly taken from a transaction; they must be released voluntarily.
Breaking this condition means the system can forcibly take locks from transactions. This is implemented through preemptive abort protocols:
- •Wait-Die Protocol — Older transactions wait for younger ones; younger transactions die (abort) if they need resources held by older ones. Non-preemptive for old transactions, preemptive for young.
- •Wound-Wait Protocol — Older transactions wound (preempt) younger ones by forcing them to abort; younger transactions wait for older ones. Preemptive for old transactions, non-preemptive for young.
- •Timeout-Based Preemption — Any transaction waiting beyond a threshold is aborted and restarted. Simple but may abort unnecessarily.
- •Priority-Based Preemption — Higher-priority transactions can preempt lower-priority ones. Priorities based on business importance, age, or resources held.
Wait-Die Protocol in Detail:
Each transaction is assigned a timestamp when it begins. When Tᵢ requests a lock held by Tⱼ:
WAIT-DIE(Tᵢ requests lock held by Tⱼ):
IF timestamp(Tᵢ) < timestamp(Tⱼ): // Tᵢ is older
Tᵢ waits for Tⱼ to release
ELSE: // Tᵢ is younger
ABORT Tᵢ (Tᵢ "dies")
Restart Tᵢ with SAME timestamp // Important: keep original timestamp
Why it prevents deadlock:
- Transactions only wait in one direction (old waits for young)
- No cycle possible: T₁ (older) waits for T₂ (younger), but T₂ cannot wait for T₁ (would die instead)
Important: Restarted transactions keep their original timestamp to eventually become the oldest and succeed.
Wound-Wait Protocol in Detail:
WOUND-WAIT(Tᵢ requests lock held by Tⱼ):
IF timestamp(Tᵢ) < timestamp(Tⱼ): // Tᵢ is older
ABORT Tⱼ (Tᵢ "wounds" Tⱼ)
GRANT lock to Tᵢ
ELSE: // Tᵢ is younger
Tᵢ waits for Tⱼ to release
Why it prevents deadlock:
- Transactions only wait in one direction (young waits for old)
- Older transactions immediately preempt younger ones
Comparison:
| Aspect | Wait-Die | Wound-Wait |
|---|---|---|
| Who waits | Older waits for younger | Younger waits for older |
| Who aborts | Younger dies when blocked | Younger wounded by older |
| Preemption | No preemption of running transactions | Active preemption |
| Abort frequency | Generally more aborts | Generally fewer aborts |
| Lock transfer | On natural release only | Immediate on wound |
When a transaction is aborted and restarted, it MUST keep its original timestamp. Otherwise, it would perpetually be the youngest and keep getting aborted—leading to starvation. With the original timestamp, an aborted transaction eventually becomes one of the oldest and is guaranteed to complete.
Breaking Circular Wait
Coffman Condition #4: Circular Wait
There must exist a circular chain of transactions, each waiting for a resource held by the next.
This is the most commonly targeted condition because it can be broken without significant impact on transaction logic. The key technique is Lock Ordering.
Global Lock Ordering:
Impose a total ordering on all lockable resources. Transactions must acquire locks in ascending order according to this ordering.
Theorem: If all transactions acquire locks in a consistent global order, circular wait is impossible.
Proof by Contradiction:
Suppose a cycle exists: T₁ → T₂ → T₃ → ... → Tₙ → T₁
This means:
- T₁ holds resource R₁ and waits for resource Rₓ held by T₂
- By lock ordering: order(Rₓ) > order(R₁) (T₁ acquired R₁ before requesting Rₓ)
- Similarly, T₂ holds Rₓ and waits for Rᵧ with order(Rᵧ) > order(Rₓ)
- Following the chain: order(R₁) < order(Rₓ) < order(Rᵧ) < ... < order(Rz)
- But Tₙ waits for R₁ (to complete the cycle)
- This requires order(R₁) > order(Rz), contradicting order(R₁) < ... < order(Rz)
Therefore, cycles cannot form. ∎
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556
class OrderedLockManager: """ Lock manager that enforces global lock ordering to prevent deadlock. """ def __init__(self): self.locks = {} self.transaction_locks = {} # txn_id -> list of held lock IDs in order def get_lock_order(self, resource): """ Compute global order for a resource. Options: hash, hierarchical path, explicit numbering. """ # Simple approach: use hash of resource identifier return hash(resource) % (10**9) def acquire_lock(self, txn_id, resource, lock_type='X'): """ Acquire lock with ordering enforcement. Raises exception if lock order is violated. """ resource_order = self.get_lock_order(resource) # Check lock ordering constraint if txn_id in self.transaction_locks: held_locks = self.transaction_locks[txn_id] for held_resource, held_order in held_locks: if held_order >= resource_order: raise LockOrderViolation( f"Transaction {txn_id} holds lock on {held_resource} " f"(order {held_order}) but requested {resource} " f"(order {resource_order}). Violates lock ordering." ) # Acquire the lock (simplified) self._grant_lock(txn_id, resource, lock_type) # Record lock acquisition if txn_id not in self.transaction_locks: self.transaction_locks[txn_id] = [] self.transaction_locks[txn_id].append((resource, resource_order)) def acquire_multiple_ordered(self, txn_id, resources, lock_types): """ Acquire multiple locks in correct order. Automatically sorts resources before acquisition. """ # Sort by global order ordered = sorted( zip(resources, lock_types), key=lambda x: self.get_lock_order(x[0]) ) for resource, lock_type in ordered: self.acquire_lock(txn_id, resource, lock_type)Defining Lock Order in Practice:
| Ordering Method | Description | Pros | Cons |
|---|---|---|---|
| Row ID / Primary Key | Order by table then primary key value | Natural, intuitive | Cross-table comparisons tricky |
| Resource Hash | Hash of fully-qualified resource name | Universal, simple | Hash collisions possible |
| Hierarchical Path | Database → Schema → Table → Row | Reflects lock granularity | Complex comparison logic |
| Explicit Numbering | DBA assigns explicit order to tables | Full control | Must maintain as schema changes |
Example: Primary Key Ordering
-- Transaction updating two accounts
-- Always lock in account_id order
BEGIN TRANSACTION;
-- Determine order
SET @acc1 = 1000, @acc2 = 2000; -- Account IDs
-- Lock lower ID first, then higher
SELECT * FROM accounts WHERE account_id = @acc1 FOR UPDATE;
SELECT * FROM accounts WHERE account_id = @acc2 FOR UPDATE;
-- Now safely update both
UPDATE accounts SET balance = balance - 100 WHERE account_id = @acc1;
UPDATE accounts SET balance = balance + 100 WHERE account_id = @acc2;
COMMIT;
Most databases don't enforce lock ordering automatically—it's the application's responsibility. Developers must standardize resource access order across all code paths. Database-level enforcement exists in some specialized systems but adds overhead.
Timeout-Based Prevention
While not a pure prevention technique (it doesn't guarantee deadlocks won't form), timeout-based approaches provide practical deadlock avoidance by aborting transactions before they can complete a deadlock cycle:
How It Works:
- Each lock request has a maximum wait time
- If lock not acquired within timeout, transaction aborts
- Aborted transaction releases all locks and retries
- Deadlocks are implicitly resolved by timeout, not explicit detection
| Database | Parameter | Default | Scope |
|---|---|---|---|
| MySQL InnoDB | innodb_lock_wait_timeout | 50 seconds | Session/Global |
| PostgreSQL | lock_timeout | 0 (disabled) | Session |
| Oracle | LOCK_TIMEOUT (DDL) | Platform-dependent | Session |
| SQL Server | SET LOCK_TIMEOUT | -1 (infinite) | Session |
Timeout Selection Strategy:
def calculate_timeout(transaction):
"""
Adaptive timeout calculation based on transaction characteristics.
"""
base_timeout = 5.0 # seconds
# Factor 1: Transaction complexity
complexity_factor = 1.0
if transaction.estimated_duration > 10:
complexity_factor = 1.5
elif transaction.estimated_duration > 60:
complexity_factor = 2.0
# Factor 2: Current system load
load_factor = 1.0 + (current_lock_contention() * 0.5)
# Factor 3: Transaction importance
priority_factor = 1.0
if transaction.priority == 'HIGH':
priority_factor = 2.0
elif transaction.priority == 'LOW':
priority_factor = 0.5
timeout = base_timeout * complexity_factor * load_factor * priority_factor
return min(timeout, MAX_TIMEOUT)
Tradeoffs:
- Too Short: May abort transactions that would have succeeded without deadlock
- Too Long: Deadlocks persist longer, blocking more resources
- Fixed vs Adaptive: Adaptive timeouts respond to load but add complexity
Timeouts cannot distinguish between a transaction blocked by deadlock and one legitimately waiting for a long transaction to complete. This leads to false positives—aborting transactions that would have succeeded. Combine with actual deadlock detection for best results.
Prevention Strategy Selection Guide
With multiple prevention strategies available, choosing the right one depends on your system's characteristics and requirements:
| Strategy | Condition Broken | Concurrency Impact | Implementation Effort | Best Suited For |
|---|---|---|---|---|
| MVCC | Mutual Exclusion (partial) | Minimal | High (system-level) | Read-heavy workloads |
| Pre-claim All | Hold and Wait | High (low concurrency) | Low | Batch processing, static transactions |
| Lock Ordering | Circular Wait | Low | Medium (discipline required) | OLTP with known access patterns |
| Wait-Die | No Preemption | Medium | Medium | Systems needing guaranteed progress |
| Wound-Wait | No Preemption | Medium (preemptive) | Medium | Priority to older transactions |
| Timeout | None (avoidance) | Low | Low | General purpose, supplements detection |
Decision Framework:
Choose your prevention strategy:
1. Can you predict all resources upfront?
YES → Consider Pre-claim All (Conservative 2PL)
NO → Continue to #2
2. Are transactions read-heavy with occasional writes?
YES → Implement MVCC if not already available
NO → Continue to #3
3. Can you establish and enforce a global lock order?
YES → Implement Lock Ordering (low overhead, effective)
NO → Continue to #4
4. Is transaction age a good priority indicator?
YES → Implement Wait-Die or Wound-Wait
NO → Continue to #5
5. Default path:
→ Use Detection with Timeout as backup
→ This is what most OLTP systems do
In practice, most systems use MVCC (eliminating many read-write conflicts), lock ordering where feasible (at the application level), and deadlock detection with timeouts as the safety net. Pure prevention is rare outside specialized systems.
KEEP LEARNING
There’s more to understand.
You’re reading the introduction. Create a free account to read the complete lesson, save notes and keep track of your progress.