Deadlocks in DBMS

Deadlock is a critical concept in Database Management Systems. It has to be resolved in the DBMS to prevent transactions from getting stuck indefinitely, disrupting database operations. It typically occurs in multi-user environments, where multiple transactions compete for limited resources, such as locks on rows or tables. If not handled properly, deadlocks can lead to performance decrease, transaction rollbacks, and inconsistent data states. In this blog, let us explore the deadlock concepts in detail.

Table of Contents: 

• What is a Deadlock in DBMS?
• Types of Deadlocks in DBMS
• Conditions of Deadlocks in DBMS
• Deadlock Handling in DBMS
• Deadlock Avoidance
  • Deadlock Detection
  • Deadlock Prevention
  • Deadlock Recovery
• Difference Between various Deadlock handling types in DBMS
• Real-World Example
• Drawbacks of Deadlocks in DBMS
• Conclusion
• Deadlocks in DBMS – FAQs

What is a Deadlock in DBMS?

A deadlock occurs in a DBMS when two or more transactions are waiting for each other to release resources, creating a cycle where none of the transactions can proceed. This creates an indefinite wait, which blocks further execution. These deadlocks have to be handled properly to ensure efficient database operations.

For Example, consider two transactions, T1 and T2, that are accessing two resources, R1 and R2. Imagine that 

• T1 locks R1 and requests R2, which is already locked by T2. 
• T2 locks R2 and requests R1, which is already locked by T1.

Now both transactions are waiting to release the locked resource, causing a circular wait state. Since none of the transactions proceed further, a deadlock occurs, leading to an indefinite wait state.

Types of Deadlocks in DBMS

Based on their nature and occurrence, deadlocks can be classified into:

1. Resource Deadlock:

• A resource deadlock occurs when multiple transactions hold resources and wait indefinitely for each other to release the required resources.
• Example: Consider a situation where transaction T1 holds resource R1 and requests resource R2, while T2 holds R2 and requests R1; this leads to a circular wait.

2. Communication Deadlock:

• This communication deadlock occurs when two or more processes wait for responses from each other, creating an indefinite waiting state.
• Example: Consider a situation where Server S1 sends a request to S2 and waits for a response, while S2 also sends a request to S1 and waits for a response, causing a communication deadlock. 

Conditions of Deadlocks in DBMS

• Mutual Exclusion: One transaction can only use a resource at a time if it is held in a non-shareable mode.
• Hold and Wait: When a transaction has at least one resource, it can ask for more while keeping the resources it has already obtained.
• No Preemption: A resource assigned to a transaction must be released freely by the transaction holding it; it cannot be taken away by force.
• Circular Wait: This occurs when two or more transactions are waiting for a resource that is held by another transaction in the cycle, which results in an endless waiting state.

Deadlock Handling in DBMS

DBMS deadlock handling ensures that transactions do not remain indefinitely blocked in case of a circular wait condition. Deadlock handling is done by prevention, detection, and recovery mechanisms to keep the system efficient and data consistent.

Deadlock Avoidance

It is a technique that ensures that the system never gets into a deadlock state by carefully allocating resources only if it guarantees a safe execution path. Algorithms, like Banker’s Algorithm, can be used to prevent deadlocks before they occur.

Banker’s Algorithm

The Banker’s Algorithm is a deadlock avoidance technique that can be used in DBMS and Operating Systems. Before granting a resource to a process or transaction, it ensures that resources are allocated in such a way that prevents deadlock by checking whether the system remains in a safe state.

Why is it called the Banker’s Algorithm?

This algorithm is named after a banker who gives loans (resources) to customers (transactions) only if the bank has enough funds to satisfy all the demands. Similarly, the resources are allocated only if the system ensures safe execution without leading to a deadlock.

Key Terminologies used in Banker’s Algorithm 

To understand how the Banker’s Algorithm works, it is necessary to know the following terminology.

• Available: Number of free resources available in the system
• Maximum Need: The Maximum number of resources that a transaction needs
• Allocated: Number of resources currently allocated to a transaction
• Remaining Need: Additional resources that a transaction still needs, i.e, Maximum-Allocated
• Safe State: A State where all transactions are completed without causing a deadlock
• Unsafe State: A state where granting requests may lead to a deadlock

How Banker’s Algorithm Works?

Step 1: Check if it is a valid request

• A transaction T requests a certain amount of resources.
• If the requests exceed the maximum need, then they are considered invalid and are denied.

Step 2: Check if resources are available

• If the requested resources are available or free, then it is moved to the next step
• If not, the transaction has to wait for the requested resource until it is available or free

Step 3: Pretend to allocate and check for a safe state

• Temporarily allocate the requested resource and check the system if it is in a safe state
• If granting the resource keeps the system safe, then it is allocated permanently
• If granting the resource leads to an unsafe state, then the request is denied.

Example of Banker’s Algorithm

Let’s consider a scenario where there are three transactions (T1, T2, T3) and ten available resources (R1, R2, R3, R4, R5, and so on)

Step 1: Understanding the Problem

Each transaction declares the maximum number of resources it will need in advance. The system will allocate only the resources if it ensures that it will not lead to a deadlock.

Step 2: Data Setup

Let’s represent the state of the transaction using a table

This system has 10 resources in total

Now, let’s calculate the available resources:

                Available = (Total resources – Allocated resources)

                               = 10 – (3+2+4) = 10 – 9 

                               = 1

So, the available resources = 1

Step 3: Transaction Requests

Now, let’s consider the situation where T2 requests 2 more resources

First Check:

• This requested resource is first compared with the maximum need of the transaction.
• T2’s maximum need is 5, and it has already been allocated with 2.
• It requests 2 more resources, i.e, 2(already allocated) + 2 = 4, which is within its maximum need (5), so it is considered valid.

Second Check:

• Checks if there are enough resources available.
• Here, only 1 resource is available, and T2 is requesting 2.
• Since 1 < 2, the request cannot be granted immediately.

Step 4: Resolving the issue

Suppose T3 finishes the execution, and if it releases all 4 resources that it was holding, then the total available resources will be, 

                            Total available Resources = 1(already available) + 4 = 5 

Now, if the T2 again requests 2 more resources:

Available = 5 

Requested = 2

Since the requested resources are smaller than the available resources, the system grants the request.

Advantages of Banker’s Algorithm

• It avoids the deadlocks before they occur.
• Safe Execution of the transaction is ensured.
• Used efficiently in systems with predictable resource allocation.

Disadvantages of Banker’s Algorithm

• Due to the continuous monitoring of safe states, it increases the system overhead.
• If certain resources are repeatedly denied, then it leads to resource starvation.

Deadlock Detection

Deadlock detection is a procedure adopted in a DBMS to discover deadlocks and fix them after their occurrence. Deadlock detection differs from deadlock prevention and deadlock avoidance, which resolve the situation before it arises. Once a deadlock occurs, deadlock detection can be used to cycle detection algorithms on the Resource Allocation Graph (RAG) or wait-for graphs to determine whether or not a deadlock exists. Once a deadlock is detected, some corrective action is initiated by the DBMS, either by terminating the transactions and releasing the resources or, by some form of resource preemption to break the deadlock and restore normal operation of the DBMS.

Resource Allocation Graph (RAG) for Deadlock Detection

It is a graphical representation that is used to track resource allocation and process requests in a system. Analyzing the dependencies between processes and resources helps in deadlock detection and avoidance.

Why is RAG important?

• Helps in visualizing the potential deadlocks before they happen.
• It ensures smooth execution without deadlocks.
• The system can use this method to decide whether to grant the requested resource or not.

Components of Resource Allocation Graph

Example 1: Safe State (No Deadlock)

Let’s assume we have 

• Two Transactions: T1 and T2
• Two Resources: R1 and R2
• Each resource has only one instance, i.e, can be assigned to only one transaction at a time

Initial Allocation:

• T1 is assigned R1
• T2 is assigned R2

Graphical representation:

(T1) ○ ←— (R1) □     

(T2) ○ ←— (R2) □  

Here, T1 holds R1 and T2 holds R2

Since there is no cycle, it is a safe state. Transactions can complete execution and release their resources.

Example 2: Deadlock Scenario

Now, let’s say 

• T1 requests R2, which is already held by T2
• T2 requests R1, which is already held by T1

Graphical representation:

(T1) ○ → (R2) □  

        ↑     ↓  

        □ (R1) ← ○ (T2)  

Here, neither T1 nor T2 can proceed further, and they have to wait for each other.

This is a deadlock because there is a cycle in the graph, which means that transactions are waiting indefinitely.

How to avoid deadlock using RAG?

To avoid deadlock, we can use the following techniques

i) Cycle Detection:

• The system continuously monitors RAG to see if a cycle is developing.
• The system stops one transaction from waiting to end a cycle if one is identified.

ii) Ordering Resources:

• The system has to follow a strict order of resource allocation
• For instance, T1 must request R2 before any other transaction receives R2 if it is assigned R1.

iii) Preemptive Resource Allocation:

• The system may forcefully take (preempt) a resource and reassign it if a transaction waits too long. 

Advantages of RAG:

• Potential deadlocks can be quickly identified with the help of a visual representation.
• If a cycle exists in RAG, then it indicates a deadlock

Disadvantages of RAG: 

• Only works with single-instance resources; it is inefficient when used with multiple instances of a resource.
• System overhead is increased by continuous cycle detection.

Wait-For Graph

A Wait-For Graph is a simplified form of Resource Allocation Graph, which is used for deadlock detection in DBMS.

Components of Wait-For Graph

Example 1: Safe State (No Deadlock)

Let’s consider a scenario where we have three transactions

• T1 is waiting for T2
• T2 is waiting for T3
• T3 is not waiting for any other transaction

Graphical Representation:

T1 → T2 → T3  

Here, T3 is free and it releases its resources once the execution is finished, so that T2 will get the resource, then T1 will execute, ensuring no deadlock occurs.

Example 2: Deadlock Scenario

Now, let’s say 

• T1 is waiting for T2
• T2 is waiting for T3
• T3 is waiting for T1 (Forms a Cycle)

Graphical Representation:

T1 → T2 → T3  

↑                    ↓  

└───────┘  

Here, T1, T2, and T3 wait for each other, and no transaction can proceed further, which leads to a deadlock.

Advantages of Wait-For Graph

• WFG excludes resources from the graph and only contains transactions, which reduces complexity while improving efficiency. 
• If there are few transactions, WFG can detect the cycles and often recover from deadlock with little impact.

Disadvantages of Wait-For Graph

• WFG does not prevent deadlocks; it can only detect deadlocks after they occur, and users must take further action to get to a resolution.
• The WFG does not prevent deadlocks; it can only detect a deadlock after it occurs.

Deadlock Prevention     

By removing at least one of the four conditions of deadlock (Mutual Exclusion, Hold and Wait, No Preemption, and Circular Wait), it can be prevented. Deadlock prevention is a DBMS technique that guarantees deadlocks never happen. Prevention techniques like Wait-die and Wound-wait can be used.

Wait-Die Scheme

Wait-Die scheme is a deadlock prevention technique based on the timestamp of the transaction. While allowing only older transactions to wait and forcing younger transactions to abort(die) and restart ensures that deadlocks never happen.

How does the Wait-Die Scheme work?

Step 1: Assign a timestamp to each transaction

• Based on what time the transaction began, the system assigns it a timestamp (TS).
• Older transactions have smaller timestamps (lower values).
• Younger transactions have larger timestamps (higher values).

Step 2: Transaction requests

When a transaction requests a resource that is already locked by another transaction, then these rules can be followed:

• If the requesting transaction has a lower timestamp, i.e older transaction, then it waits.
• If the requesting transaction has a higher timestamp, i.e younger transaction, it aborts(dies) and restarts later.

Example 1: Safe State(No Deadlock)

Consider a scenario where T1(older, TS = 5) needs R1, which is already held by T2(younger, TS = 10).

Since T1 is older, it is allowed to wait until T2 releases R1. This prevents circular waiting and avoids deadlock.

Example 2: Deadlock Prevention 

Now let’s assume T2(younger, TS = 10) needs R1, which is held by T1 (older, TS = 5)

Since T2 is younger, it is not allowed to wait and must abort. T2 is terminated and restarted with a new timestamp, preventing a deadlock.

Wound-Wait Scheme

The Wound-Wait scheme is a deadlock prevention method that uses timestamps to determine which transaction waits and which aborts. In contrast to Wait-Die, the Wound-Wait scheme allows younger transactions to wait, while older transactions are allowed to wound (abort), if necessary.

How does the Wound-wait scheme work?

Step 1: Assigning a timestamp to each transaction

• Based on what time the transaction began, the system assigns it a timestamp (TS).
• Older transactions have smaller timestamps (lower values).
• Younger transactions have larger timestamps (higher values).

Step 2: Transaction Request

When a transaction requests a resource that is already locked by another transaction, then these rules can be followed:

• If the requesting transaction has a lower timestamp, i.e older transaction, then it is wounded (aborted), and the older one gets the resource.
• If the requesting transaction has a higher timestamp, i.e younger transaction, it waits until the resource is available.

Example 1: Safe State(No Deadlock)

Consider a scenario where T2(younger, TS = 10) needs R1, which is already held by T1 (older, TS = 5).

Since T2 is younger, it is allowed to wait until T1 releases R1. This prevents circular waiting and avoids deadlock.

Example 2: Deadlock Prevention

Now let’s assume T1 (older, TS = 5) needs R1, which is held by T2(younger, TS = 10).

Since T1 is older, it wounds T2 by forcing it to abort. T2 is terminated and restarted with a new timestamp, preventing a deadlock.

Difference Between Wait-Die and Wound-Wait Scheme

Deadlock Recovery

Although deadlock prevention and avoidance techniques are in place, deadlocks can occur in some situations as well. Deadlock recovery involves determining which transactions form the deadlock, choosing one victim, and aborting it, so that its resources can be released to be used by other transactions. There are different strategies, like process termination, resource preemption for determining which transaction to abort, with the same focus of seeking to minimise the impact on system performance.

Process Termination 

In process termination, to break the deadlock, the system chooses one or more transactions to abort (terminate). Once the transaction is terminated, the resources held by that transaction are released, allowing other transactions to continue execution.

How does process termination work?

When a deadlock is detected, the system follows one of the following two approaches

Method 1: Abort all deadlocked transactions

• Whatever transaction is involved in the deadlock, the system terminates it.
• This ensures that the deadlock is completely removed

Method 2: Abort one transaction at a time

• The system selects a victim transaction and aborts it.
• Once that transaction is aborted, the system checks if the deadlock is resolved
• If not, this process is repeated until the deadlock is broken.  

Example:

Let’s consider that we have two transactions (T1 and T2) and two resources (R1 and R2).

Each resource can use only one transaction at a time, i.e, there is no sharing of resources

Initial Resource Allocation:

Let’s assume that the transaction holds resources as follows

Here, T1 already owns R1 and requests R2, which is currently held by T2. Similarly, T2 already owns R2 and requests R1, which is currently held by T1. None of the transactions can proceed further since each of the transactions is waiting for the other to release the resource. There is a cycle dependency between the transactions, so a deadlock occurs in this scenario.  

Now, let’s see how this deadlock can be resolved using the process termination method.

Step 1: Deadlock Detection

(T1) ○ → (R2) □  

        ↑     ↓  

        □ (R1) ← ○ (T2)  

The system detects a deadlock using techniques like the Wait-For graph. The graph shows that T1 → T2 → T1 forms a cycle. This cycle indicates that a deadlock is occurring, and the system has to break it.

Step 2: Choosing the victim transaction to terminate

To resolve the deadlock, the system chooses one transaction, and it must abort (terminate) that transaction.

There are a few factors that the system considers to select the victim transaction

• Transaction Priority: Older transaction is preferred to continue.
• Number of resources held: A transaction is chosen in such a way that it holds a minimum number of resources. 
• Progress of the transaction: If the transaction is in its near completion stage, instead of aborting, that transaction is allowed to finish.

The system picks T2 as a victim because,

• If T2 started after T1, then T2 is considered a younger transaction, so it is a better candidate for termination.
• If T2 has only R2, while T1 has both R1 and R2, then T2 has fewer resources. T2 satisfies this condition by holding fewer resources compared to T1.
• If T2 has just started and T1 is in the completion stage, then terminating T2 might be the best option.

Step 3: Terminating the victim transaction

• Since T2 is considered a victim transaction, it is terminated(rolled back).
• Now, T2 releases R2, which is available for other transactions.

Step 4: Resolving a deadlock

Now, T1 gets the requested resource R2 and T1 completes the execution and releases both R1 and R2. Now, the system is deadlock-free.

Step 5: Restart the terminated transaction

Now, the terminated transaction T2 is restarted from the beginning. T2 can now request R1 again, but this time, both resources are free, so it is allocated to T1.

Advantages of Process Termination:

• No Transaction Termination: A deadlock solution occurs without terminating transactions, therefore, there is no data loss.
• Effective Resource Utilisation: Resources are assigned with dynamic reallocation.
• Limits Work Loss: Transactions are not restarted; only delayed.

Disadvantages of Process Termination: 

• Waiting Time: Preempted transactions have to wait to regain the resources they lost, leading to higher waiting times.
• Implementation Complexity: More complex in the case of deadlock detection and selection of victim transactions.
• Possible Starvation: Some transactions can repeatedly lose resources and delay potentially forever.

Resource Preemption 

Resource Preemption is a technique used for deadlock recovery in which the system forcibly takes (preempts) a resource from a transaction and gives it to another transaction to break the deadlock. Instead of aborting a transaction, this will release some resources to allow some other transactions to progress further.

How does resource preemption work?

Detecting the deadlock: The system detects a deadlock using any of the deadlock detection techniques and selects a victim transaction to release its resources based on factors like the number of resources held and the impact on the system.

Resolve the deadlock: The system takes the resource forcefully and assigns it to another waiting transaction, allowing it to execute, which resolves the deadlock without terminating the transaction.

Example: Let’s consider a scenario where there are two transactions, T1 and T2, and two resources, R1 and R2. Each resource can be assigned to only one resource at a time.

Step 1: Initial Resource Allocation

Let’s assume that the transaction holds resources as follows

Here, T1 already owns R1 and requests R2, which is currently held by T2. Similarly, T2 already owns R2 and requests R1, which is currently held by T1. None of the transactions can proceed further since each of the transactions is waiting for the other to release the resource. There is a cycle dependency between the transactions, so a deadlock occurs in this scenario.

Step 2: Deadlock Detection

(T1) ○ → (R2) □  

        ↑     ↓  

        □ (R1) ← ○ (T2)  

The system detects a deadlock using techniques like the Wait-For graph. The graph shows that T1 → T2 → T1 forms a cycle. This cycle indicates that a deadlock is occurring, and the system has to break it.

Step 3: Selecting a transaction for preemption

The system chooses T2 based on factors like 

• T2 has done less work, which is easier to delay. 
• T2 holds fewer resources, then it minimises the system impact.
• By preempting (forcefully taking the resource), T2 will break the cycle.

So here, T2 is considered for preemption.

Step 4: Preempting the resource

The system preempts R2 from T2. R2 is free now, and it is assigned to T1. T2 is on hold until R2 is available again. 

Step 5: Resolving the deadlock

Now, T1 has both resources R1 and R2, hence it completes its execution. T1 releases the resources R1 and R2 after the completion, so that T2 can now request R1 and continue the execution. Thus, the deadlock is resolved using the resource preemption method, without terminating the process.

Advantages of Resource Preemption:

• Fast Deadlock Resolution: Forcefully terminating a transaction quickly breaks the deadlock cycle. 
• Easier to Implement: It involves slightly simpler logic to go through compared to preempting resources.
• Quickly Frees Up Resources: Once a transaction is terminated, its resources will be available and released, allowing its associated processes to continue.

Disadvantages of Resource Preemption: 

• Lost Work: Terminated transactions will be restarted from scratch, resulting in wasted CPU cycles. 
• Risk of Data Inconsistency: Abrupt termination can leave a transaction in an incomplete state, which leads to corruption of data.
• Rollback Overhead: If the terminated transaction was in the middle of a critical section to perform a rollback, they have a system performance cost during retries and errors implicated within these tasks.

Difference Between various Deadlock handling types in DBMS 

Real-World Example 

1. Online Ticket Booking System: Suppose that two users (User A and User B) are attempting to purchase tickets for the same event. Here, the transactions are referred to as two users, and the resources are seat selection and payment processing.

How does a deadlock happen?

• User A selects a seat by locking the seat and moves to payment processing.
• User B selects the payment processing and then tries to change the seat.
• Here, User A is waiting for the payment system, and User B is waiting for seat selection, but both are waiting for each other to release the lock. Thus, the deadlock happens.

How is deadlock removed?

Method 1: Resource Preemption (Forcing one user to retry payment or seat selection)

• The system will forcibly unlock the lock held by User B on the payment system, and will transfer the lock to User A. 
• User A will complete the payment of the transaction and then release the locks, and now User B can retry the booking. Thus, the Deadlock will be resolved without cancelling the transactions.

Method 2: Process Termination (Cancelling one user’s booking attempt)

• If the deadlock continues, the system will automatically abort one of the transactions (Ex, User B’s booking attempt).
• Now, User B needs to restart the booking, but User A can continue with the payment processing.
• This ensures that at least one booking succeeds rather than keeping User A and B in a deadlock.

2. Banking system: Suppose that two users (User A and User B) are exchanging money. The system needs to lock two accounts: UserA’s Account and UserB’s Account.

How does deadlock happen?

• User A initiates a money transfer to User B, where User A’s account is locked, and waits for User B’s account.
• User B initiates a transfer to User A, where User B’s account is locked, and waits for User A’s account.
• Here, both users are waiting for each other to release the lock. Thus, the deadlock occurs.

How is deadlock removed?

Method 1: Resource Preemption (Forcing one user to retry transfer)

• The system will forcefully release the lock on User B’s account, so that User A’s transfer will be completed first.
• User A’s transaction will proceed further, and the system will release both accounts to allow User B to attempt the transfer again. Deadlock will be avoided without cancelling the transactions.

Method 2: Process Termination (Cancelling one transfer request)

• If the deadlock continues, then the system will automatically cancel one of the transfer requests (e.g., User B’s request). 
• User B needs to restart their transfer, while User A’s transfer will be completed successfully. 
• At least one transaction will be completed instead of two transfers being blocked.

Drawbacks of Deadlocks in DBMS

Deadlock is a critical problem in database management systems (DBMS) because it affects transactions that can become indefinitely stuck in the deadlock state and ultimately impact system performance and eventual system failure. Below are the key disadvantages of deadlock:

• Transaction Stalling 

When two or more transactions are blocking each other for needed resources, they cannot proceed to completion. They will wait indefinitely unless the system intervenes.

• System resources are wasted 

The transactions involved in a deadlock will continue to consume CPU time, memory, and locks, but they will not make any progress. This can cause a resource starvation for other transactions.

• Inconsistency in data

Deadlocks may cause the system to forcefully abort transactions, which might lead to some process being incomplete, and possibly result in the data being inconsistent. 

• Transaction Rollback Increases

When an application encounters a deadlock situation, the system may choose to abort one or more of the transaction processes and then restart the aborted process. This will consume extra processing time, and the actions will have to be re-executed.

Conclusion

Deadlocks happen in a DBMS when two or more transactions compete for resources and end up in a condition called circular wait, and can no longer execute further. Modern DBMSs use built-in deadlock detection mechanisms, which automatically identify and terminate one of the conflicting transactions to break the cycle and restore normal operation. It is critical to avoid this condition, as deadlocks can prevent users and processes from accessing resources, using resources while frozen, and ultimately result in transactions being aborted. To manage the program efficiently, deadlocks need to be prevented, avoided, detected, and resolved. In this blog, you have gained knowledge on deadlocks in DBMS in detail. 

To learn more about SQL functions, check out this SQL course and also explore SQL Interview Questions prepared by industry experts.

Deadlocks in DBMS – FAQs