Deadlock in DBMS (Detection Techniques and How to Prevent Deadlock)
Deadlock in a DBMS (Database Management System) occurs when two or more transactions are blocked because each transaction is waiting for one of the others to release a lock. This results in a standstill situation where none of the transactions can proceed.
Deadlocks are usually resolved by a technique called “deadlock detection and resolution” which involves identifying and breaking the deadlock by releasing one of the locked resources. This can be done by rolling back one of the transactions, or by using a timeout mechanism to release a lock after a certain period of time.
What is deadlock?
In a database system, a transaction may need to wait for another transaction to release a resource before it can proceed. If two or more transactions are each waiting for a resource that the other has locked, a deadlock can occur. A deadlock is a situation in which two or more transactions are blocked and cannot proceed, and they are waiting for each other to release resources, resulting in a circular wait.
How to Detect Deadlock in DBMS?
These are deadlock detection techniques used to detect deadlocks in a DBMS.
Wait-for Graph
A Wait-for Graph represents dependencies between transactions. Each node in the graph represents a transaction, and each directed edge from one node to another represents a transaction waiting for a resource held by the other transaction. A cycle in the graph indicates a deadlock.
To detect and resolve deadlocks, the database management system periodically examines the Wait-for Graph to see if there are any cycles. If a cycle is found, the system can choose one of the transactions in the cycle to abort, releasing its resources and allowing the other transactions to proceed. The aborted transaction will then be rolled back, and any changes made by the transaction will be undone.
Wait-for Graphs are commonly used in database management systems to prevent and resolve deadlocks. By representing the dependencies between transactions, they allow the system to detect and resolve deadlocks in a timely and efficient manner.
Resource Allocation Graph
Resource Allocation Graph (RAG) is a graphical representation of the resource allocation state of a system. It is a useful tool for detecting and resolving deadlocks in a system. The following steps are used to identify deadlocks using the Resource Allocation Graph method:
- Construct the Resource Allocation Graph (RAG) for the system: The graph should show the resources in the system and the processes that are using those resources.
- Check for the presence of cycles in the graph: If a cycle is present in the graph, then it indicates that a deadlock may exist in the system.
- Identify the processes and resources involved in the cycle: This will help in determining which resources are being held by which processes and which resources are being requested by which processes.
- Determine the status of each process in the cycle: If a process is holding a resource and requesting another resource that is being held by another process in the cycle, then that process is in a deadlock state.
- Resolve the deadlock by breaking the cycle: This can be done by releasing one or more resources held by a process in the cycle, allowing other processes to acquire those resources and proceed with their execution.
- After breaking the cycle, go back to step 2 to check if any other cycles exist in the graph: If there are no cycles, then the system is deadlock-free.
The Resource Allocation Graph method is an effective way of identifying deadlocks in a system and resolving them by breaking the cycles in the graph. By following the steps outlined above, it is possible to identify the processes and resources involved in the deadlock and take appropriate action to resolve the deadlock and keep the system running smoothly.
Polling
Polling deadlock detection is a method for detecting deadlocks in a computer system by periodically checking the state of the system for signs of a deadlock. In this method, a special process called a deadlock detector is responsible for monitoring the state of the system and detecting deadlocks when they occur.
The polling deadlock detection method works by periodically examining the allocation and request status of all resources in the system to check for circular waits. If the detector detects that a circular wait has occurred, it can take steps to resolve the deadlock by releasing resources or killing processes.
One advantage of the polling deadlock detection method is that it can be implemented in a distributed system where resources and processes may be located on different nodes or machines. However, the method can be resource-intensive, especially in large systems with many processes and resources, as the detector must continually monitor the system state to detect deadlocks. The time required for the deadlock detector to detect and resolve a deadlock may be longer than the time required for other deadlock detection and prevention methods.
How to prevent Deadlock in DBMS?
There are several ways to prevent deadlocks in a DBMS:
Lock ordering
By acquiring locks on resources in a specific order, you can prevent the possibility of deadlocks. For example, always acquire locks on tables in alphabetical order.
Timeout
A timeout mechanism can be used to release a lock after a certain period of time. This can prevent a deadlock from occurring if one transaction is waiting for a lock that is held by another transaction that is not making progress.
Deadlock prevention by DBMS
Some DBMS have built-in deadlock prevention mechanisms that use techniques such as lock escalation, lock timeout, and lock conversion to prevent deadlocks.
Two-phase Locking
Two-phase locking is a concurrency control method that ensures that a transaction releases all its locks before it can request any new locks. This prevents the possibility of deadlocks.
Optimistic concurrency control
In optimistic concurrency control, each transaction is allowed to proceed, and any conflicts are detected and resolved at the time of commit. This prevents the possibility of deadlocks because conflicts are resolved before the transactions are committed.
Avoiding long-running transaction
Deadlock is more likely to happen in long-running transactions, so try to minimize the time a transaction holds a lock.
Use of Stored procedures and triggers
The use of stored procedures and triggers can help to minimize the amount of time a transaction holds a lock.
It’s worth noting that preventing deadlocks can impact performance and can increase the complexity of the system. So, it’s important to find the right balance between deadlock prevention and system performance.
Further Reading
- Types of Data Models in DBMS
- Hashing in DBMS
- Functional Dependency in DBMS
- Referential Integrity in DBMS
- Difference between DBMS and RDBMS
- ACID Properties DBMS (Atomicity, Consistency, Isolation, Durability)