Deadlocks in DBMS: Preventing and Handling Circular Dependencies

Learn about the concept of deadlocks in database management systems (DBMS) and understand how they can occur in multi-process environments. Explore the conditions that lead to deadlocks and the various strategies to prevent and handle them, such as deadlock detection, prevention, and avoidance.

DBMS - Deadlock

In a multi-process system, a deadlock is an undesirable condition that occurs in a shared resource environment when a process is indefinitely waiting for a resource held by another process.

Understanding Deadlock

Consider a set of transactions {T₀, T₁, T₂, ..., T_n}. For instance, let’s say T₀ requires resource X to complete its task. However, resource X is currently held by T₁, which in turn is waiting for resource Y held by T₂. Meanwhile, T₂ is waiting for resource Z, which is held by T₀. In this circular waiting scenario, none of the processes can complete their tasks, leading to a deadlock.

Deadlocks can be detrimental to a system. When the system is stuck in a deadlock, the transactions involved are typically either rolled back or restarted.

Deadlock Prevention

To avert any deadlock situations, the Database Management System (DBMS) rigorously inspects all operations about to be executed. It analyzes these operations to determine if they could potentially create a deadlock. If a potential deadlock is identified, the transaction is not permitted to execute.

Several deadlock prevention schemes utilize a timestamp ordering mechanism to preemptively identify deadlock scenarios:

• Wait-Die Scheme: In this scheme, if a transaction requests to lock a resource (data item) that is already held by another transaction with a conflicting lock, one of two scenarios may occur:
  • If TS(T_i) < TS(T_j), meaning T_i (the requesting transaction) is older than T_j, then T_i is allowed to wait until the resource becomes available.
  • If TS(T_i) > TS(T_j), meaning T_i is younger than T_j, then T_i is terminated (dies) and will be restarted later with a random delay but retain the same timestamp.
• Wound-Wait Scheme: Similar to the wait-die scheme, if T_i requests a lock on a resource held by another transaction T_j, one of the following may happen:
  • If TS(T_i) < TS(T_j), T_i forces T_j to roll back (wounds T_j), and T_j will be restarted later with a random delay while retaining its original timestamp.
  • If TS(T_i) > TS(T_j), T_i must wait until the resource is available.

Deadlock Avoidance

Aborting transactions is not always a practical solution. Instead, deadlock avoidance techniques can be employed to detect potential deadlocks in advance. Methods like the wait-for graph can be used, but these are generally suited for systems with lightweight transactions that have fewer resource instances. In larger systems, deadlock prevention techniques may prove more effective.

Wait-For Graph

The wait-for graph is a simple method to track potential deadlocks. A node is created for each transaction that enters the system. When a transaction T_i requests a lock on an item (e.g., X) held by another transaction T_j, a directed edge is drawn from T_i to T_j. If T_j releases item X, the edge is removed, allowing T_i to lock the data item.

The system continuously monitors this wait-for graph for cycles, which indicate a potential deadlock.

Deadlock Resolution Approaches

Two main approaches can be applied:

• First, disallow requests for items already locked by another transaction. However, this approach may lead to starvation, where a transaction waits indefinitely for a data item.
• Second, roll back one of the transactions. It is not always practical to abort the younger transaction, as it may hold more importance than the older one. By utilizing a relative algorithm, a transaction is selected for rollback, known as the victim, and the process of choosing the victim is referred to as victim selection.