What is a deadlock in DBMS, and how can the database detect it?
Interview preparation resource from Gate Smashers.
A deadlock occurs when two or more transactions wait for resources held by one another in a cycle so none can continue. A DBMS can detect deadlocks by building a wait-for graph (transactions as nodes; an edge T1 -> T2 means T1 is waiting for a resource held by T2) and checking the graph for cycles. If a cycle is found, the transactions in that cycle are deadlocked. Typical resolution is: detect the cycle, choose a victim transaction, abort or roll it back, release its locks, and allow the remaining transaction(s) to continue; the victim may be retried later. Some systems also use timeouts or prevention strategies.
Definition
A deadlock occurs when two or more transactions each wait for resources held by the other(s) in a cycle, so none of the transactions can make progress.
Deadlock detection — wait-for graph
The DBMS can detect deadlocks by constructing a wait-for graph and checking it for cycles. In this graph, each active transaction is represented as a node, and directed edges show waiting relationships.
- Edge meaning: An edge T1 -> T2 means T1 is waiting for a resource currently held by T2. A cycle in the graph indicates a deadlock.
Example
For example, T1 holds a lock on resource A and requests B, while T2 holds B and requests A. T1 waits for T2 and T2 waits for T1, producing a cycle in the wait-for graph and thus a deadlock.
Resolution steps
Once a cycle is detected, the DBMS resolves the deadlock by selecting one or more transactions as victims and rolling them back so other transactions can proceed.
- Detect cycle: Identify the cycle in the wait-for graph.
- Choose victim: Select one transaction in the cycle to abort (victim selection policy may vary).
- Abort/rollback: Abort or roll back the chosen victim transaction.
- Release locks: Release the victim's locks so other transactions can acquire the needed resources.
- Continue: Allow the remaining transaction(s) involved in the cycle to continue; the victim may be retried later.
Other approaches
In addition to cycle detection, some systems employ timeouts or prevention strategies to avoid or reduce deadlocks, but cycle detection via a wait-for graph is the standard detection technique described above.