Last Updated on March 2, 2023 by Prepbytes
In this article, we will learn about what is Deadlock in DBMS with the help of examples. Then we will look at the necessary conditions for a Deadlock to occur. After that, we will learn the process of Deadlock Avoidance in DBMS and Deadlock Detection in DBMS. We will also learn the technique of Deadlock Prevention along with wait die and wound wait schemes in detail. Also, we will learn about the concept of Phantom Deadlock in DBMS.
What is Deadlock in DBMS
A deadlock in a database management system (DBMS) is a situation where two or more processes are blocked, waiting for each other to release a resource that they need to proceed with their execution. This creates a circular wait, where each process is waiting for a resource that is held by another process, leading to a complete blockage of the system. Deadlocks can occur in multi-user, multi-tasking environments, where multiple processes are accessing shared resources simultaneously and can cause decreased system performance or system failure if not resolved.
Example to understand Deadlock in DBMS
Let us use an example to better grasp the notion of Deadlock:
Assume T1 has a lock on some rows in the Employees database and needs to change some rows in the Salary table. Simultaneously, Transaction T2 has locks on the Salary table rows (which T1 needs to update) but needs to update the Employees table rows held by Transaction T1.
The main issue has now arise, Transaction T1 will wait for transaction T2 to release the lock, and transaction T2 will similarly wait for transaction T1. As a result, all activity comes to a halt and will remain so indefinitely unless the DBMS recognizes the deadlock and aborts one of the transactions.
To resolve this deadlock, either P1 or P2 must be killed or must release one of the resources to allow the other process to proceed. The DBMS must have mechanisms in place to detect and resolve deadlocks, such as timeout mechanisms or killing a process to release its resources.
This has been explained graphically by the given image:
Necessary Conditions for Deadlock to Occur
There are four necessary conditions that must be met for a deadlock to occur in a DBMS. These conditions were stated by Coffman. A Deadlock in DBMS will occur if all of the four condition holds true at any point in time. The conditions are:
- Mutual Exclusion: At least one resource must be held in a non-shareable mode, meaning only one process can access it at a time.
- Hold and Wait: A process is holding at least one resource and is waiting for additional resources that are currently held by other processes.
- No Preemption Condition: Resources cannot be taken away from a process and given to another process.
- Circular Wait: A set of processes are waiting for resources held by each other, forming a circular chain.
When all four conditions are met, a deadlock occurs, and the processes involved are unable to proceed or release their resources. This results in a situation where the system cannot continue processing transactions.
Deadlock Avoidance in DBMS
Deadlock avoidance in DBMS is a technique used to prevent deadlocks from occurring. This is achieved by introducing a policy for allocating resources that avoids the conditions for a deadlock.
There are two main methods for deadlock avoidance in DBMS are Resource Allocation Graph (RAG) Algorithm and Wait-For Graph Algorithms. Both of these approaches aim to ensure that there are no circular wait conditions in the system, which is the root cause of deadlocks.
Deadlock avoidance is an effective technique for preventing deadlocks in a DBMS. It allows for more efficient use of system resources and reduces the risk of system failure.
Deadlock Detection in DBMS
Deadlock detection is a technique used in DBMS to identify and resolve deadlocks. In this technique, the system continuously checks for deadlocks and, if found, takes appropriate action to resolve the deadlock.
We use Wait-For Graph for Deadlock Detection in DBMS :
Wait-for Graph: This method uses a graph-based model to represent the allocation of resources. The graph is used to detect the existence of cycles, which indicate a deadlock has occurred. The wait-for graph is updated whenever a resource is requested or released.
For the above example of the Employee and Salary table, the Wait-For Graph can be constructed as shown below:
Deadlock detection is an important technique for ensuring the correct functioning of a DBMS. It allows the system to identify and resolve deadlocks in a timely manner, reducing the risk of system failure. However, it can also lead to decreased system performance as a result of the additional overhead required for monitoring and controlling resource allocation.
Deadlock Prevention in DBMS
The deadlock prevention strategy is appropriate for huge databases. A stalemate can be avoided by allocating resources in such a way that a deadlock never arises. The DBMS examines the operations to see if they can cause a deadlock. If they do, the transaction is never permitted to be executed.
Deadlock prevention in DBMS is a technique used to eliminate the possibility of deadlocks occurring in a database management system. It involves making certain changes to the system to reduce the chances of resource contention, which is the main cause of deadlocks.
There are two main schemes followed for Deadlock Prevention in DBMS namely, Wait Die and Wound Wait Schemes. These are explained below in detail:
-
Wait-Die Scheme
The Wait-Die algorithm is a deadlock prevention scheme used in DBMS (Database Management Systems). The algorithm makes use of timestamps to prevent deadlocks from occurring in a multi-user database environment. The concept is that transactions with older timestamps are given priority to access a resource, and transactions with newer timestamps are forced to wait. The algorithm functions in two ways:- Wait: If a transaction T1 requests a lock on a resource that is currently locked by T2, and T2 has a smaller timestamp than T1, T1 waits until T2 releases the lock.
- Die: If a transaction T1 requests a lock on a resource that is currently locked by T2, and T2 has a larger timestamp than T1, T1 aborts (dies). The reasoning behind this is that T1 has a lower priority, and allowing it to proceed could lead to a deadlock.
The Wait-Die algorithm is simple and effective, but it may not be the best solution for all types of databases. Other algorithms, such as the Wound-Wait algorithm, may be more appropriate for certain types of databases or workloads.
-
Wound-Wait Scheme
The Wound-Wait Algorithm is a deadlock prevention strategy in database management systems (DBMS). It is based on the idea that the process requesting a resource with the lowest timestamp (i.e., the oldest process) will be granted access to the resource first.In the Wound-Wait Algorithm, each transaction has a timestamp that indicates its age. When a transaction requests a resource, it compares its timestamp with the timestamp of the transaction currently holding the resource. If the requesting transaction has a lower timestamp, it "wounds" the transaction holding the resource, which must then either release the resource or "wait" for the requesting transaction to release it first.
The Wound-Wait Algorithm helps to prevent deadlocks by ensuring that the transaction with the lowest priority does not have to wait for a resource. This helps to maintain the stability and consistency of the database and reduces the likelihood of deadlocks occurring. However, the algorithm does not guarantee deadlock freedom, and other deadlock prevention or detection methods may still be necessary.
Both algorithms work by avoiding deadlocks by rolling back transactions that are more likely to deadlock. The choice between Wait-Die and Wound-Wait depends on the particular requirements of the application.
In general, the Wait-Die algorithm is used when data consistency is a high priority, and the Wound-Wait algorithm is used when data availability is a high priority.
Phantom Deadlock
A phantom deadlock is a type of deadlock that occurs when multiple transactions in a database management system each have locks on different sets of resources, and there is no actual deadlock between any of these transactions. This can occur when there are a large number of transactions and resources, and the database management system’s deadlock detection algorithms are not able to accurately detect the relationships between these transactions and resources. As a result, the system may incorrectly identify a phantom deadlock and abort one or more transactions, even though there is no actual conflict between them. To mitigate the risk of phantom deadlocks, it is important to carefully design and implement the database management system’s deadlock detection and resolution algorithms and to thoroughly test these algorithms to ensure their accuracy and effectiveness.
Summary
Deadlock is a situation in database management systems (DBMS) where two or more transactions are waiting for each other to release resources, leading to a permanent blocking state. To prevent deadlocks, there are several methods such as Deadlock Avoidance, Deadlock Detection, and Deadlock Prevention. The Wait-Die and Wound-Wait algorithms are two common deadlock prevention methods used to resolve deadlocks. These algorithms determine the ordering of transactions that request resources and prevent deadlocks by making sure that conflicting transactions do not execute simultaneously. The goal of these algorithms is to minimize the number of transactions that have to be rolled back, while still ensuring the integrity and consistency of the data.