This content originally appeared on Level Up Coding - Medium and was authored by AlishaAS
A deadlock occurs when two or more transactions in a database system are waiting for a data item that is locked by another transaction. A cycle in the wait-for-graph can indicate a deadlock. This is a directed graph with vertices representing transactions and edges representing waits for the data item.
For example, in the wait-for-graph below, transaction P1 is waiting for data item X, which is locked by P3. P3 is waiting for Z, which is locked by P2, and P2 is waiting for Y, which is locked by P1. As a result, a waiting loop is generated, and none of the transactions can execute.
What is Deadlock in DBMS?
A deadlock in DBMS is an undesired state that occurs when a process waits indefinitely for a resource that is being held by another process.
To better understand the concept of deadlock, take a transaction T1 that has a lock on a few rows in the table Employee and has to change certain rows in another table Salary.
There is also another transaction T2 that has a lock on the Salary table and needs to update a few rows in the Employee table, which is already held by transaction T1.
In this case, both transactions and processes are waiting for each other to release the lock, and the processes are waiting for each other to release the resources. As a result of the preceding scenario, none of the jobs are accomplished, which is referred to as deadlock.
Why does Deadlock occur in DBMS?
A deadlock arises when two transactions wait endlessly for each other to unlock data.
A deadlock arises when two transactions, P1 and P2, exist in the following mode:
P1 = access data items X and Y
P2 = access data items Y and X
P2 cannot begin if P1 has not unlocked data item Y, and P1 cannot continue if P2 has not unlocked data item X.
As a result, P1 and P2 each wait for the other to unlock the desired data item. This type of deadlock is also described as a deadly embrace. The table below shows how a deadlock condition occurs in DBMS.
Deadlock Handling in Centralized Systems
There are three traditional ways to handle deadlock in DBMS:
- Deadlock prevention.
- Deadlock avoidance.
- Deadlock detection and removal.
All three ways can be used in both centralized and distributed database systems to handle the deadlock condition.
Deadlock Prevention
The deadlock prevention strategy prohibits any transaction from acquiring locks that will result in deadlocks. According to the convention, when multiple transactions request to lock the same data item, only one of them is granted the lock.
Pre-acquisition of all locks is one of the most popular deadlock prevention strategies. In this approach, a transaction gets all locks before beginning to execute and keeps them for the duration of the transaction.
If another transaction requires any of the previously acquired locks, it must wait until all of the locks required are accessible. This strategy prevents the system from becoming jammed because none of the waiting transactions are holding any locks.
There are two algorithms for avoiding deadlocks in DBMS.
- Wait/Die: When a transaction demands a resource that is already locked by another transaction, the DBMS compares the timestamps of the two transactions and forces the older transaction to wait until the resource is free for execution.
- Wound/Wait: When an older transaction requires a resource that has already been locked by a younger transaction (a later-initiated transaction), the younger transaction is obliged to kill/stop its processing and relinquish the locked resource for the older transaction’s own execution. The younger transaction has been restarted with a one-minute delay, but the timestamp remains unchanged. If a younger transaction wants a resource that an older transaction is holding, the younger transaction is forced to wait until the older transaction releases the resource.
For example, assume there are two transactions, T1 and T2, in which T1 attempts to lock a data item that is already locked by T2. Here are the algorithms:
- Wait-Die − T1 is allowed to wait if he is older than T2. If T1 is younger than T2, the process is aborted and then restarted.
- Wound-Wait − T2 is canceled and restarted if T1 is older than T2. T1 is allowed to wait if it is younger than T2.
Deadlock Avoidance
When a database is locked in a deadlock, avoiding the deadlock is always preferable to restarting or aborting the database. This is a complete waste of time and resources. The avoidance strategy is appropriate for smaller datasets, but the prevention method is more appropriate for larger databases.
The deadlock avoidance can be summarised as follows.
Transactions begin to execute and require data items that must be locked. The lock manager determines whether or not the lock is available. If it is available, the lock management assigns the data item to the transaction, and the transaction acquires the lock.
If the item is locked by another transaction in an incompatible mode, the lock management executes an algorithm to determine if maintaining the transaction in the waiting state would result in a deadlock or not. As a result, the algorithm determines whether the transaction can wait or whether one of the transactions should be canceled.
Deadlock Detection and Removal
The deadlock detection and removal strategy runs a deadlock detection algorithm on a regular basis and removes deadlock if one exists. When a transaction requests a lock, it does not check for deadlock while, the lock manager determines whether or not the lock is available. If it is available, the transaction may lock the data item; otherwise, the transaction may wait.
As no measures are taken while granting lock requests, some transactions may become deadlocked. The lock management checks the wait-for-graph for cycles on a regular basis to detect deadlocks. If the system is stuck, the lock management selects a victim transaction from each cycle. The victim is aborted, rolled back, and later restarted.
When a deadlock is found, it is resolved using the following methods:
- Terminating processes involved in a deadlock: Terminating all processes involved in a deadlock or terminating processes one by one until the deadlock is resolved are possible methods, but neither of them is good. The cost of terminating all processes is considerable, and partial work done by processes is lost. It takes a long time to terminate each process because each time a process is killed, it must verify whether the deadlock has been resolved or not. The optimal strategy is to terminate processes in a deadlock situation while taking into account their age and importance.
- Preemption of resources: Another strategy is to preempt resources and allocate them to other processes until the deadlock is resolved.
- Wait-for-graph: One way for detecting deadlock is to use a wait-for-graph. This approach is appropriate for smaller databases. In this strategy, a graph is constructed based on the transaction and their lock on the resource. There is a deadlock if the constructed graph contains a closed loop or a cycle.
Conclusion
- Deadlock is an undesirable state that brings the entire system to a halt since no task is ever completed and remains in a waiting state indefinitely. If any of the transactions have the potential to cause a deadlock, it is never completed.
- Deadlock handling and avoidance are approaches for dealing with the problem, whereas the Wait-die and Wait-wound schemes are two popular methods for avoiding a deadlock.
How to Handle Deadlock in DBMS was originally published in Level Up Coding on Medium, where people are continuing the conversation by highlighting and responding to this story.
This content originally appeared on Level Up Coding - Medium and was authored by AlishaAS
AlishaAS | Sciencx (2022-12-02T17:50:34+00:00) How to Handle Deadlock in DBMS. Retrieved from https://www.scien.cx/2022/12/02/how-to-handle-deadlock-in-dbms/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.