Coursify

Deadlock Handling in DBMS: Prevention, Avoidance, Detection, and Recovery

Deadlock Handling in DBMS: Prevention, Avoidance, Detection, and Recovery

Verified Sources
Sep 12, 2026

Deadlocks occur in a database when transactions form a cycle of wait-for dependencies such that none of the involved transactions can proceed. In DBMS research and practice, deadlock handling is commonly organized into four families: Prevention , Avoidance , Detection , and Recovery.2

A useful mental model is that DBMS implementations trade off: (i) runtime overhead (e.g., graph monitoring), (ii) concurrency (more restrictions can reduce throughput), and (iii) complexity of correctness arguments (e.g., safety proofs).

Key concepts (wait cycles and resource allocation)

  • Transaction issues Lock requests on Resources.
  • If granting locks leads to a cycle in the wait dependency, the system enters deadlock. One classic formalization uses a Wait-for graph cycle detection.

Footnotes

  1. Database Deadlocks—Prevention via resource ordering and related constraints (Coffman-style conditions). https://en.wikipedia.org/wiki/Deadlock#Prevention - Explains deadlock prevention strategies and conditions. ↩

  2. Deadlocks and deadlock handling overview (prevention/avoidance/detection/recovery). https://en.wikipedia.org/wiki/Deadlock#Handling_deadlocks - Survey of main approaches. ↩ ↩2

  3. Wait-for graph and deadlock detection (cycle corresponds to deadlock). https://en.wikipedia.org/wiki/Deadlock#Wait-for_graph - Describes wait-for graph model used for detection. ↩

Deadlocks in DBMS (wait-for graph, prevention, detection, recovery)

Core approaches for handling deadlocks

1) Deadlock prevention

Deadlock prevention ensures that deadlocks cannot occur by eliminating (or controlling) at least one necessary condition for deadlock. The classic Coffman conditions can be targeted via database-specific constraints, such as ordering resources or restricting lock acquisition patterns.2

Approach patterns

  • Strict resource ordering / lock ordering: transactions must acquire locks in a global order (e.g., by page ID). This prevents cycles in the wait-for graph, since edges can only go “forward.”
  • Hold-and-wait prevention: require transactions to either (a) request all needed locks upfront or (b) release held locks before requesting additional ones. This reduces/avoids the “wait while holding” behavior that enables cycles.
  • Preemption (less common in classic DBMS texts): if a transaction cannot safely proceed, the system aborts or forces it to release resources to break potential cycles.

Pros/cons

  • Pros: deadlocks never occur → simpler runtime behavior once enforced.
  • Cons: may reduce concurrency and increase waiting/lock hold times depending on the chosen policy.2

Tip: If you implement lock ordering, document the global ordering rule and ensure all code paths (including indexes and metadata locks) follow it—otherwise “hidden” resources can reintroduce cycles.

Footnotes

  1. Database Deadlocks—Prevention via resource ordering and related constraints (Coffman-style conditions). https://en.wikipedia.org/wiki/Deadlock#Prevention - Explains deadlock prevention strategies and conditions. ↩ ↩2 ↩3

  2. Deadlocks and deadlock handling overview (prevention/avoidance/detection/recovery). https://en.wikipedia.org/wiki/Deadlock#Handling_deadlocks - Survey of main approaches. ↩ ↩2 ↩3 ↩4 ↩5

2) Deadlock avoidance (safety-based granting)

Deadlock avoidance does not forbid deadlocks syntactically; instead, it decides whether to grant a lock request based on future feasibility. Many avoidance algorithms maintain whether the system remains in a Safe state. If granting would move the system into an unsafe state, the DBMS delays the request instead.2

A widely discussed conceptual method is to test whether the request preserves safety using system-wide information (e.g., current allocations and remaining needs).

Common requirements

  • The DBMS needs information about each transaction’s potential future lock needs (or an approximation).
  • Decision-making can become expensive if it requires frequent safety checks under high contention.

Pros/cons

  • Pros: deadlocks are avoided without overly rigid ordering constraints in all cases.
  • Cons: generally higher overhead and often impractical without knowing future lock needs precisely.2

Warning: True “optimal” avoidance may require knowledge of future resource requirements; many real workloads only approximate or reveal those needs late via query execution, which makes strict avoidance costly or unrealistic.

Footnotes

  1. Wait-for graph and deadlock detection (cycle corresponds to deadlock). https://en.wikipedia.org/wiki/Deadlock#Wait-for_graph - Describes wait-for graph model used for detection. ↩

  2. Banker's algorithm / avoidance using safety condition. https://en.wikipedia.org/wiki/Deadlock#Avoidance - Connects avoidance to safety checks (e.g., Banker's algorithm concepts). ↩ ↩2 ↩3 ↩4 ↩5

  3. Deadlocks and deadlock handling overview (prevention/avoidance/detection/recovery). https://en.wikipedia.org/wiki/Deadlock#Handling_deadlocks - Survey of main approaches. ↩

3) Deadlock detection (wait-for graph monitoring)

Deadlock detection allows deadlocks to occur temporarily, then periodically detects cycles and resolves them by aborting one or more transactions. In the wait-for-graph model, deadlocks correspond to cycles: if the wait-for graph contains a cycle, transactions in that cycle are deadlocked.

Detection strategy

  • Maintain the wait-for graph as lock requests are blocked/unblocked.
  • Run cycle detection either:
    • Periodically (every kk seconds or after nn events), or
    • On demand (e.g., when contention crosses a threshold).

Pros/cons

  • Pros: no need for overly restrictive lock policies; can preserve concurrency.
  • Cons: adds runtime overhead (graph maintenance + cycle detection), and deadlocks may cause “stuck” transactions until detection runs.

Footnotes

  1. Wait-for graph and deadlock detection (cycle corresponds to deadlock). https://en.wikipedia.org/wiki/Deadlock#Wait-for_graph - Describes wait-for graph model used for detection. ↩ ↩2 ↩3

4) Deadlock recovery (after detection)

Once deadlock is detected, the DBMS must break the deadlock by taking corrective action. Typical recovery chooses a Victim transaction to abort and roll back, thereby removing its edges in the wait-for graph and letting others proceed.2

Recovery choices

  • Rollback/abort the victim: the system undoes its changes using Logging and then releases its locks.
  • Cascading rollback (in some designs): aborting one transaction may force others to abort if their dependencies cannot be resolved cleanly.
  • Selection policies for victims: common heuristics include:
    • abort the transaction with the least cost / smallest amount of work done,
    • abort the youngest (or oldest) transaction,
    • abort to minimize expected wasted work.

Pro Tip: “Least wasted work” victim selection can reduce recovery cost, but the DBMS must estimate or track metrics (e.g., log size, time in system). Use metrics already collected by the scheduler/lock manager when possible.

Footnotes

  1. Deadlocks and deadlock handling overview (prevention/avoidance/detection/recovery). https://en.wikipedia.org/wiki/Deadlock#Handling_deadlocks - Survey of main approaches. ↩

  2. Transaction recovery and abort/rollback concept in DBMS. https://en.wikipedia.org/wiki/Transaction_processing#Recovery - Discusses undo/rollback and recovery concepts used when aborting transactions. ↩ ↩2 ↩3 ↩4

How a DBMS typically handles deadlocks over time

Transactions begin

1. Lock requests

Transactions request locks and may block when locks are incompatible."

Waits build dependencies

2. Potential deadlock formation

If cycles in dependencies arise, a deadlock can form."

Prevention/Avoidance OR Detection

3. Handling policy triggers

Prevention/avoidance restricts or delays requests; detection monitors for cycles."

Abort/rollback and release locks

4. Recovery

A victim is selected, rolled back, and locks are released to unblock others."

Deadlock detection + recovery workflow (cycle-based)

  1. 1
    Step 1

    Whenever a lock request is blocked, add/update edges in a Wait-for graph reflecting “waiting-for” dependencies.

  2. 2
    Step 2

    Periodically (or on-demand), detect whether the wait-for graph contains a directed cycle. A cycle implies deadlocked transactions for that subset.

    Footnotes

    1. Wait-for graph and deadlock detection (cycle corresponds to deadlock). https://en.wikipedia.org/wiki/Deadlock#Wait-for_graph - Describes wait-for graph model used for detection. ↩

  3. 3
    Step 3

    Select a Victim transaction using a heuristic (e.g., minimal rollback cost/time).

  4. 4
    Step 4

    Abort the victim and undo its effects using recovery facilities based on Logging.

  5. 5
    Step 5

    Release locks held by the aborted transaction so waiting transactions can reattempt their lock requests.

  6. 6
    Step 6

    If multiple independent deadlocks exist, the process may need to be repeated until the wait-for graph becomes cycle-free.

Comparative summary of the approaches

ApproachCore ideaDBMS overheadConcurrency impactWhen deadlocks occur?
PreventionDisallow patterns that enable deadlock (e.g., lock ordering)Low–MediumMedium (often reduced)Never (by design)
AvoidanceGrant only if the state remains Safe stateHighSometimes better than preventionNot allowed (at decisions)
DetectionMonitor for cyclesMedium–HighHighYes, temporarily
RecoveryAbort/rollback victims to break cyclesVariable (depends on victim choice)Improves after resolutionAfter detection

Common exam-style nuances

Concept map (approach families)

Knowledge Check

Question 1 of 4
Q1Single choice

Which approach for deadlock handling uses a system-wide safety notion (e.g., a safe state) to decide whether to grant a lock request?

Explore Related Topics

1

Deadlock Avoidance and Resource-Allocation Graphs with Cycles but No Deadlock

Deadlock avoidance grants resources only when the resulting state is safe, using safety tests (e.g., the Banker’s algorithm) and graph analysis to prevent unsafe allocations.

  • A request is granted iff the post‑allocation state satisfies a safe sequence: Grant request  ⟺  state is safe\text{Grant request} \iff \text{state is safe}.
  • In a single‑instance resource graph, any cycle means deadlock; with multiple instances, a cycle only indicates a possible deadlock.
  • The safety test checks for a process PiP_i with Needi≤AvailableNeed_i \le Available; such a process can finish, release resources, and repeat the check.
  • Example: R1R_1 (1 instance) and R2R_2 (2 instances) form a cycle, but P3P_3 can complete and break it, so no deadlock occurs.
  • The OS may defer a request even when resources are free if granting it would move the system to an unsafe state.
2

The Banker's Algorithm: Deadlock Avoidance in Operating Systems

The Banker's Algorithm is a deadlock‑avoidance method that keeps a system in a safe state by checking each resource request against the maximum declared needs of processes.

  • Maintains Available, Max, Allocation, and Need matrices, where Need[i][j]=Max[i][j]−Allocation[i][j]\text{Need}[i][j]=\text{Max}[i][j]-\text{Allocation}[i][j].
  • The Safety Algorithm uses vectors Work and Finish to find an execution order; if all processes finish, the state is safe.
  • The Resource‑Request Algorithm simulates allocation, runs the safety check, and commits only if the resulting state remains safe.
  • Time complexity of the safety check is O(m×n2)O(m \times n^{2}).
  • In practice the algorithm is rarely used because processes must predeclare maximum needs and the algorithm’s overhead is high.
3

Database Triggers: What They Are, When to Use Them, and Why They Matter

Browse all research articles