Deadlocks
In a database system with two or more transactions, deadlock occurs when each transaction waits for a piece of data that another transaction has locked. A cycle in the wait-for graph can be a sign of a deadlock. The edges of this directed network represent waits for data items, whereas the vertices represent transactions.
Real life example
When there is only one track and two trains are approaching one another on it, once they are in front of one another, none of the trains can move.
When two or more processes keep resources and wait for resources held by another process, a similar scenario occurs in operating systems.
Deadlock Handling in Centralized Systems
There are three classical approaches for Deadlock Handling, namely :
- Deadlock prevention
- Deadlock avoidance
- Deadlock detection and removal
1. Deadlock Prevention
According to the deadlock prevention technique, no transaction is allowed to obtain locks that will result in deadlocks. According to convention, only one transaction is provided the lock when multiple transactions request to lock the same data item.
Pre-acquisition of every lock is one of the most often used strategies for preventing deadlocks. Using this approach, a transaction obtains all of the locks before to execution and keeps them for the life of the transaction. Another transaction must wait until all the locks it requires are available if it requires any of the locks that have previously been acquired. This method keeps the system from being jammed because there are no locks on any of the pending transactions.
2. Deadlock Avoidance
By using the deadlock avoidance technique, deadlocks are avoided before they happen. Whether waiting results in a deadlock can be determined by examining the locks and transactions.
The following is a basic summary of the approach. As transactions begin to run, they ask for data elements that must be locked. The availability of the lock is verified by the lock manager. The transaction obtains the lock and the lock management assigns the data item, if it is accessible. The lock manager, however, uses an algorithm to determine whether or not maintaining the transaction in the waiting state will result in a deadlock if the item is locked by another transaction in incompatible mode. As a result, the algorithm determines if a transaction should be aborted or if it may wait.
Types of Deadlock Avoidance
Wait-die and wound-wait are the two algorithms used for this. Assume that T1 and T2 are two transactions in which T1 requests to lock a data item that T2 has already locked.
The following are the algorithms:
Wait-Die : One can wait if T1 is older than T2, or it can be stopped and restarted if T1 is younger than T2.
Wound-Wait : T2 is terminated and then restarted if T1 is older than T2. Otherwise, T1 is permitted to wait if T1 is younger than T2.
3. Deadlock Detection and Removal
The deadlock detection and removal method periodically executes a deadlock detection algorithm and, if a deadlock is present, eliminates it. No deadlock check is performed when a transaction requests a lock. After receiving a lock request from a transaction, the lock manager verifies its availability. In the event that it is available, the transaction can lock the data item; if not, it can wait.
Because lock requests are granted without any safeguards, some transactions might end up remained. Periodically, the lock management looks for cycles in the wait-for graph to identify deadlocks. A victim transaction is selected by the lock management from each cycle if the system is stuck. After the victim is aborted and rolled back, the process is then resumed.
A few of the techniques employed to choose victims are :
- Select the transaction that is the youngest.
- Select the transaction with the fewest pieces of information.
- Select the transaction that has made the fewest modifications.
- Select the transaction with the lowest overhead of restarts.
- Select a transaction that occurs in two or more cycles.
This method works best for systems that have few transactions and require quick responses to lock requests.
