Deadlock in DBMS: Explained in Detail

Deadlock in a Database Management System (DBMS) occurs when transactions become stuck waiting for resources held by one another. The affected transactions cannot continue unless the circular dependency is broken, making deadlock an important issue in database concurrency management.

Understanding deadlock is crucial for Database Administrators and Developers alike to ensure smooth, efficient operations. This blog breaks down the concept of deadlock in DBMS, explores its causes, and explains methods to prevent and resolve deadlocks, helping you keep your database running seamlessly.

What is Deadlock in DBMS?

A Deadlock in DBMS refers to the situation in which two or more transactions are in a state such that none of them can proceed because each of them is waiting for the other to release some resources.

Imagine a scenario where Transaction A is holding Resource 1 and waiting for Resource 2, while Transaction B is holding Resource 2 and waiting for Resource 1. Neither can proceed until the other releases a resource, leading to a system standstill: this is a deadlock.

Deadlock primarily arises in multi-transactional systems where multiple processes are running concurrently. It's not necessarily common but can be devastating when it happens, freezing the entire system and requiring significant effort to resolve the situation.

Pro Tip

When learning deadlocks, write each transaction as Holds → Waits For. For example, T1: Holds R1 → Waits for R2. This makes circular dependencies much easier to spot.

Conditions for Deadlock

To have effective deadlock detection and management, there is a need to identify the major characteristics of deadlocks. In the DBMS world, deadlock occurs only when four conditions are met simultaneously:

1) Mutual Exclusion: There must be at least one resource that is in a non-shareable mode. Thus, only one transaction can access the resource at one time.

2) Hold and Wait: A transaction is holding one resource and waiting for other resources held by other transactions.

3) No Preemption: A resource cannot be forcibly taken from the transaction holding it. The system must wait until the transaction releases it voluntarily.

4) Circular Wait: Circular wait for transactions always exists. Here, each transaction holds a resource on which the next one needs to hold. A waits for B, B waits for C, and so on, until a transaction waits on A.

Trainer Insight

Memorise the four deadlock conditions as a set. A deadlock requires all four conditions to exist simultaneously. If the system can prevent even one of them, the deadlock can be prevented.

Deadlock Avoidance

Stopping deadlocks before they occur is often better than recovering from them. Deadlock avoidance is an example of careful resource allocation. Deadlock avoidance evaluates whether granting a resource request would leave the system in a safe state. If an allocation could move the system into an unsafe state, the request can be delayed or denied.

Banker's Algorithm is a classic deadlock avoidance algorithm that grants resource requests only when the resulting allocation remains in a safe state. It requires advanced knowledge of resource requirements, which can limit its practical use in general database transaction workloads.

However, deadlock avoidance may degrade system performance because algorithms that continuously monitor and predict possible deadlocks incur computational overhead.

Deadlock Detection

If deadlocks are not avoided, they must be detected; hence, deadlock detection techniques periodically check for deadlock conditions and resolve these by aborting one or more transactions involved.

The DBMS may employ deadlock detection algorithms to look for cycles in the resource allocation graph. If any cycle is detected, it implies a deadlock, and the system might abort one of the transactions to break the cycle.

Wait-for Graph

The Wait-for Graph is a technique used for deadlock detection. In the graph, every node represents a transaction. Now, an edge from Transaction A to Transaction B means that A is waiting for a resource being held by B. If a cycle is in the graph, then there is deadlock. To break this, one or more transactions in the cycle must be aborted so the deadlock is broken and the others can proceed.

Expand your knowledge and expertise on database approaches and DBMS with our Relational Databases & Data Modelling Training - Register now!

Trainer Insight

When reading a Wait-for Graph, follow the direction of each edge. If the waiting relationships eventually lead back to the starting transaction, you have identified a cycle and therefore a Deadlock in the model described here.

Deadlock Prevention

Deadlock prevention techniques change the way resources are allocated such that at least one of the necessary conditions for deadlock cannot occur. Prevention, unlike avoidance, does not rely on predicting a deadlock but rather prevents deadlock from happening in the first place by managing resource requests. Two prominent deadlock prevention schemes are:

Wait-Die Scheme

In the Wait-Die Scheme, when a transaction requests a resource that is currently held by another transaction, the system checks the timestamp of both transactions. If the requesting transaction is older (has a smaller timestamp), it can wait.

If the requesting transaction is younger, it is aborted and later restarted, typically using its original timestamp. Because transactions are permitted to wait only according to the timestamp ordering rule, circular waiting is prevented.

Wound-Wait Scheme

When a transaction requests a resource held by a younger transaction, an older requesting transaction causes the younger holder to be rolled back or aborted, allowing the older transaction to proceed. If the requesting transaction is younger than the holder, it waits.

This approach also eliminates the possibility of a circular wait by ensuring that older transactions are prioritised and younger transactions either wait or are aborted.

Deadlock Disadvantages

There are several issues that concern the efficiency of a DBMS in handling deadlocks. Some of the major disadvantages of deadlock are:

1) Blocked Transactions: Transactions involved in a deadlock cannot make progress until the deadlock is resolved. Other independent database transactions may continue operating normally.

2) Resource Waste: In case of a deadlock, resources held by a transaction are not available to other processes; this is an inefficient way of utilising resources.

3) Transaction Rollback: The resolution of a deadlock usually involves the abortion of one or more transactions, which wastes some computation and restarting processes.

4) Performance Overhead: Deadlock prevention, detection and recovery mechanisms can introduce additional processing or transaction-retry overhead, depending on the DBMS and workload.

Quick Deadlock Checklist

When analysing a potential deadlock, check:

☐ Is a resource exclusively held by one transaction?

☐ Is a transaction holding one resource while waiting for another?

☐ Can the held resource be taken away before it is released?

☐ Is there a circular chain of waiting transactions?

☐ Does the Wait-for Graph contain a cycle?

☐ Is the DBMS using avoidance, prevention or detection?

☐ If timestamps are involved, which transaction is older?

☐ Which transaction should wait, restart or be aborted under the chosen scheme?

Unlock the power of GraphQL and master database queries like never before. Join our GraphQL Database Training and advance your skills today!