Once deadlocks are possible (due to resource contention, circular wait, etc.), the DBMS must detect them so it can break the standstill.

Deadlock detection is the technique where the system periodically checks whether any transactions are involved in a circular wait, and if so, chooses one to abort, allowing the others to proceed.

How Deadlock Detection Works

The core idea is to model dependencies between transactions as a wait‑for graph:

  • Each node = a transaction.

  • An edge Ti→TjT_i \to T_j = “TiT_i is waiting for a resource currently held by TjT_j.”

Whenever a transaction must wait for a lock, the DBMS adds the corresponding edge to the wait‑for graph.

The DBMS then runs a cycle‑detection algorithm on this graph:

  • If the graph has no cycle, no deadlock exists.

  • If the graph has a cycle, the transactions in that cycle form a deadlock.

At that point, the DBMS aborts one transaction (often the youngest, or the one with least work) to break the cycle.

Frequency of Detection

Detection can be triggered in different ways:

  • Periodic checks:

    • The DBMS checks the wait‑for graph every few seconds or after a fixed number of lock requests.

  • On timeout:

    • If a transaction has been waiting unusually long, the system checks for deadlocks.

  • On every wait:

    • More aggressive systems check the graph each time a transaction is blocked.

More frequent checks detect deadlocks faster but add overhead; less frequent checks may allow deadlocks to persist longer.

Choosing Which Transaction to Abort

When a cycle is found, the DBMS must pick a victim transaction to abort. Common heuristics include:

  • Lowest cost:

    • Abort the transaction that has done the least work (fewest writes, least time).

  • Youngest transaction:

    • Abort the transaction that started most recently.

  • Priority‑based:

    • Abort the lower‑priority transaction, if priorities are used.

After aborting the victim:

  • Its locks are released.

  • The wait‑for graph is updated (edges from the victim are removed).

  • Other transactions in the cycle can now proceed.

The victim transaction may be restarted later if the application logic allows.

Advantages of Deadlock Detection

  • Flexible:

    • The system can allow lock‑based concurrency freely and still be safe because deadlocks are caught later.

  • Practical:

    • Used in many real‑world DBMS products (for example, via timeout‑based or periodic checks).

Disadvantages of Deadlock Detection

  • Overhead:

    • Maintaining the wait‑for graph and running cycle‑detection algorithms takes time.

  • Aborts cause annoyance:

    • Applications must handle transaction aborts and possibly retry.

  • Not prevented:

    • Deadlocks still occur; the system only reacts after they form.

For beginners, deadlock detection is like drawing a diagram of who is waiting for whom and then, when a circle is found, canceling one person’s request so the rest can move on.

Summary

Deadlock detection in DBMS is the technique of using a wait‑for graph to periodically or on‑demand check for circular waits between transactions. If a cycle is found, the DBMS aborts one transaction to break the deadlock and release its resources. This method allows the system to use normal locking for concurrency while still ensuring that deadlocks do not last forever, though it adds overhead and requires applications to handle transaction aborts gracefully.