Deadlock Prevention

Introduction

Deadlock prevention: eliminate one of four necessary conditions. Goal: make deadlock impossible (not just unlikely). Approaches: lock ordering, resource allocation, avoidance protocols. Cost: reduced parallelism (conservative). Trade-off: simplicity vs performance.

"Prevention is better than cure, but it often means doing more work upfront. Deadlock prevention trades some concurrency for absolute guarantee of deadlock freedom." -- Concurrency theory

Deadlock Conditions

Four Necessary Conditions

Mutual exclusion: resource held exclusively. Hold and wait: transaction holds resource while waiting for another. No preemption: cannot forcibly take resources. Circular wait: cycle of waiting transactions.

All Four Required

Remove any one: deadlock impossible. Must have all four: deadlock possible. Strategy: break one condition. Effect: simple guarantee, no deadlock detection needed.

Condition Summary

Lock Ordering

Concept

Define global order: on all resources (tables, rows). All transactions: acquire locks in same order. Cycle impossible: total ordering prevents cycles. Guarantee: prevents circular wait.

Example: Three Locks

Global order: Table A < Table B < Table CGood (follows order):T1: Lock A, then B, then CT2: Lock A, then CProblem scenario prevented:T1: Lock A, then BT2: Lock B, then A (would violate order)-- T2 must lock A before B (following order)

Implementation

-- Assign numeric IDs to resourcesTable employees: ID = 1Table departments: ID = 2Table projects: ID = 3Lock order: always lock lower ID firstT1: Lock dept (2), then emp (1) -- WRONG, violate orderT1: Lock emp (1), then dept (2) -- Correct

Advantages

Simple: just order matters. Guaranteed: circular wait impossible. No overhead: no detection needed. Proven: mathematically sound.

Disadvantages

Rigid: fixed order required. Knowledge: must know all resources upfront. Inefficiency: may acquire unnecessary locks. Code discipline: developers must follow.

Enforcement

-- Procedure to acquire locks in orderLOCK_IN_ORDER(lock_list): Sort lock_list by ID For each lock in sorted list: Acquire lock-- Usagelocks_needed = [emp_table, dept_table, proj_table]LOCK_IN_ORDER(locks_needed)

No-Hold-Wait Protocol

Concept

Never hold resources while waiting: acquire all locks upfront or none. Two approaches: hold all from start, or release and retry. Effect: breaks hold-and-wait condition.

Conservative Locking (All Upfront)

Transaction start:1. Determine all resources needed2. Acquire all locks (BEFORE any operations)3. If any lock unavailable, release all and retry4. Perform all operations5. Release all locks (at commit/abort)

Example

-- Conservative lockingBEGIN TRANSACTION LOCK TABLE employees EXCLUSIVE LOCK TABLE departments EXCLUSIVE -- Now safe to do operations (have all locks) UPDATE employees SET dept_id = 2 WHERE emp_id = 1 SELECT * FROM departments WHERE dept_id = 2COMMIT -- Release all locks

Wait-Die Scheme

When T1 wants lock held by T2: If T1.timestamp < T2.timestamp (T1 older): T1 WAITS (older waits for younger) Else (T1 younger): T1 DIES (younger dies and retries)Property: older transactions never die younger transactions never wait (deterministic)

Wound-Wait Scheme

When T1 wants lock held by T2: If T1.timestamp < T2.timestamp (T1 older): T1 WOUNDS T2 (older forces younger to release) T2 rolls back Else (T1 younger): T1 WAITS (younger waits for older)Property: no older transaction ever waits older transactions always win

Advantages

Deadlock-free: guaranteed. Deterministic: priority clear (age). Predictable: behavior known upfront.

Disadvantages

Aborts: frequent (especially younger transactions). Wasted work: computations lost. Cascading: younger aborts trigger retries. Lock holding: all locks upfront (less parallelism).

No-Preemption Strategy

Concept

Allow forced resource release (preemption). Transaction waiting: can preempt other transactions. Release: forcibly take their locks. Effect: breaks no-preemption condition.

Implementation

Transaction T1 waiting for resource R held by T2: Check: T2.priority vs T1.priority If T1.priority > T2.priority: Preempt T2 (force release) T1 proceeds T2 rolls back (or waits) Else: T1 waits

Priority System

Timestamp: older = higher priority. System: critical transactions prioritized. Cost: expensive transactions prioritized. Fair: round-robin with aging.

Challenges

Implementation: complex (rollback logic). Fairness: starvation possible (high-priority always wins). Overhead: priority checking cost. Recovery: cascading rollbacks.

Practical Use

Rare in databases: more in OS (memory preemption). Alternative: better to detect and resolve than force preemption. Databases: prefer locking strategies instead.

Conservative Locking

Static Locks (All Upfront)

Transaction: Declare all needed locks Acquire all at once (atomic operation) If success: proceed If fail: release all and retryDeadlock prevention: all locks held immediatelyWait condition: no partial holds (can't wait while holding)

Dynamic with Release

Transaction: Acquire initial locks If need more locks: Release all locks (restart) Acquire all locks (new attempt)Cost: repeated restartsBenefit: prevents holding while waiting

Advantages

Simple: clear semantics. Deadlock-free: guaranteed. Works well: predictable locks needed.

Disadvantages

Locks many resources: even if not all used. Parallelism: reduced (many locks held). Prediction: difficult (dynamic queries). Overhead: acquire/release cost.

Transaction Design

Minimize Lock Scope

Hold locks: only when necessary. Release early: as soon as done. Short transactions: reduced lock duration. Fine-grained: lock specific rows (not whole table).

Access Pattern Consistency

Consistent order (good):T1: UPDATE employees (1), then departments (2)T2: UPDATE departments (2), then employees (1) -- WRONGT2 should be:T2: UPDATE employees (1), then departments (2) -- CorrectEnforcing: code review, linting, documentation

Read vs Write Locks

Shared locks: multiple readers (lower contention). Exclusive locks: single writer (necessary for writes). Deadlock: more common with many exclusive locks. Reduce: more shared locks when possible.

Avoid Nested Transactions

Problematic: BEGIN T1 Lock A BEGIN T2 (nested) Lock B Lock A (nested, already held!) COMMIT T2 COMMIT T1Better: Flat transactions (easier to reason about)

Timeouts

-- Set timeout for locksSET LOCK_TIMEOUT 5000; -- 5 seconds-- If lock not acquired in 5 seconds-- Auto-rollback (prevents indefinite waits)

Resource Allocation Graph

Graph Construction

Nodes: transactions, resources. Edges: T -> R (waiting), R -> T (holding). Cycle: deadlock. Acyclic: no deadlock.

Example

Resources: R1, R2Transactions: T1, T2Cycle scenario:T1 -> R1 (T1 waiting for R1)R1 -> T2 (R1 held by T2)T2 -> R2 (T2 waiting for R2)R2 -> T1 (R2 held by T1)Cycle: T1 -> R1 -> T2 -> R2 -> T1 (DEADLOCK)

Detection Algorithm

For each edge T1 -> R -> T2: Check if cycle exists Use DFS or topological sort Cycle = deadlock found

Prevention via Graph

Before granting lock: check if would create cycle. If yes: deny (wait/deny policy). Effect: no cycles possible.

Cost

Graph maintenance: O(n) per lock request. Cycle detection: expensive (DFS). Practical: use simpler methods (ordering, wait-die).

Deadlock Avoidance

Banker's Algorithm (Resource Allocation)

Idea: before granting lock, check if safe state maintainedSafe state: can find ordering where all transactions completeUnsafe state: granting would make future deadlock possibleProcess:1. Receive lock request from T2. Simulate: grant lock to T3. Check: safe state reachable?4. If yes: grant, If no: deny (wait)

Example

Resources: A=5 total T1 needs: 2 (currently has 1) T2 needs: 3 (currently has 2) Available: 2Request: T1 asks for 1 more lock If grant: T1 has 2 (satisfied), T2 still waiting Safe order: T1 finishes (releases 2), then T2 can proceed Decision: GRANT (safe)Request: T2 asks for 1 more lock If grant: T2 has 3 (satisfied), T1 satisfied too But remaining available: 1 (not enough for either if both restart) Safe order: exists? Check... if yes: GRANT, if no: DENY

Complexity

Computational: O(n^2 m) per request (expensive). Practical: rare (overhead outweighs benefit). Better: simpler prevention strategies (ordering, conservative).

When Used

Real-time systems: deadlock must not occur. Critical infrastructure: failure unacceptable. Research: theoretical interest. Databases: usually detection instead.

Practical Prevention Strategies

Combined Approach

Lock ordering: primary (simple, effective). Timeouts: safety net (fallback). Conservative: when needed. Detection: as last resort.

Implementation Steps

1. Design: identify lock order2. Document: clearly (comments, design docs)3. Enforce: code review, testing4. Monitor: watch for deadlocks5. Tune: adjust if needed

Code Example

-- Lock ordering constantLOCK_ORDER = { 'employees': 1, 'departments': 2, 'projects': 3, 'assignments': 4}-- Function to acquire in orderfunction acquireLocks(transaction, tables): sorted = sort(tables, by=LOCK_ORDER) for table in sorted: acquire_lock(transaction, table)-- UsageacquireLocks(T1, ['projects', 'employees', 'departments'])

Testing for Deadlocks

-- Stress testing: many concurrent transactions-- Reproduce patterns: specific access sequences-- Verify: no deadlocks under load-- Monitor: production systems (metrics, alerting)

Detection vs Prevention Trade-off

Prevention Costs

Conservative: many locks held (reduced parallelism). Ordering: design constraint (inflexible). Avoidance: expensive checks (overhead). Effect: throughput reduction.

Detection Costs

Overhead: deadlock detection algorithm. Aborts: transactions rolled back. Restarts: computations redone. Fairness: victim selection policy.

Decision Factors

Deadlock frequency: rare = detection better. Throughput critical: detection (less overhead). Predictability needed: prevention (guaranteed). Complexity: detection simpler (in practice).

Hybrid Approach

Prevention first: enforce ordering. Detection second: catch unusual patterns. Resolution: abort if deadlock detected. Monitoring: track both rates.

Industry Practice

Most databases: use detection (simpler, better throughput). MVCC systems: reduce deadlock likelihood (different mechanism). Specialized: prevention in hard real-time systems.

Real-World Examples

Banking System

Lock order: Account ID (ascending)T1: Transfer from account 100 to 200 Lock 100, then 200 (ascending)T2: Transfer from account 200 to 100 Must lock 100 first (ascending), then 200 Circular wait impossible (same order)

E-commerce Order Processing

Lock order: Customer -> Inventory -> OrderT1: Create order (lock customer, inventory, order)T2: Update inventory (lock inventory first? NO) Must respect order: customer, then inventory, then orderConsistent: all transactions acquire in same orderDeadlock-free: circular wait impossible

Message Queue

Lock order: Queue -> Message -> ConsumerT1: Enqueue message (lock queue first, then message)T2: Dequeue message (same order: queue, message, consumer)T3: Acknowledge (same order enforced)Scaling: multiple queues ordered by IDParallel: different queues (no interference)

References

• Silberschatz, A., Korth, H. F., and Sudarshan, S. "Database System Concepts." McGraw-Hill, 6th edition, 2010.
• Ramakrishnan, R., and Gehrke, J. "Database Management Systems." McGraw-Hill, 3rd edition, 2003.
• Bernstein, P. A., Hadzilacos, V., and Goodman, N. "Concurrency Control and Recovery in Database Systems." Addison-Wesley, 1987.
• Date, C. J. "An Introduction to Database Systems." Pearson, 8th edition, 2003.
• Garcia-Molina, H., Ullman, J. D., and Widom, J. "Database Systems: The Complete Book." Pearson, 2nd edition, 2008.