This chapter overviews the mechanisms of deadlock handling in database systems. We will review the mechanisms of deadlock handling in both centralized and distributed database systems.
When each transaction is waiting for a data item that is locked by some other transaction, Deadlock is a state of a database system having two or more transactions. In the wait-for-graph, a deadlock can be indicated by a cycle. This is a directed graph in which transactions are denoted by the vertices and the edges denote waits for data items.
For example, transaction T1 waits for data item X, which is locked by T3, in the following wait-for-graph. T3 is waiting for the T2-locked Y, and T2 is waiting for the T1-locked Z. A waiting cycle is then established and none of the transactions will continue to be executed.
There are three classical approaches for deadlock handling, namely −
Both a centralized and a distributed database system will incorporate any of the three approaches.
The approach of deadlock prevention does not allow any transaction to acquire locks that lead to deadlocks. The convention is that if more than one transaction requests the same data item to be locked, the lock is given only to one of them.
Pre-acquisition of all the locks is one of the most common deadlock prevention methods. In this method, before starting to run, a transaction acquires all the locks and maintains the locks for the entire duration of the transaction. If any of the already acquired locks are needed by another transaction, it has to wait until all the locks it needs are available. Using this method, because none of the waiting transactions carry any lock, the system is prevented from being deadlocked.
Before they arise, the deadlock avoidance strategy treats deadlocks. To determine whether or not waiting leads to a deadlock, it analyses the transactions and the locks.
It is possible to briefly state the process as follows. Transactions begin to execute and request data items that must be locked. The manager of the lock checks if the lock is open. The lock manager allocates the data item if it is available, and the transaction acquires the lock. However, if the item is locked in incompatible mode by any other transaction, the lock manager runs an algorithm to test whether or not holding the transaction in the waiting state would cause a deadlock. The algorithm then decides whether the transaction should wait or whether one of the transactions should be aborted.
For this function, there are two algorithms, which are wait-die and wound-wait. Let 's say there are two transactions, T1 and T2, where T1 attempts to lock an item of data that is already locked by T2. As follows, the algorithms are-
Deadlock Detection and Removal
The deadlock detection and removal method regularly runs a deadlock detection algorithm and, if there is one, removes the deadlock. When a transaction places a request for a lock, it does not search for deadlock. The lock manager checks whether it is available when a transaction requests a lock. The transaction is allowed to lock the data item if it is available; otherwise, the transaction is allowed to wait.
Any of the transactions could be deadlocked, as there are no precautions when granting lock requests. The lock manager periodically checks if the wait-for graph has cycles in order to detect deadlocks. The lock manager selects a victim transaction from each loop if the system is deadlocked. The victim is aborted and rolled back; later the victim is restarted. Some of the methods used to select victims are-
This approach is mainly suited to systems with low transaction levels and where rapid response to lock requests is needed.
Transaction processing is often distributed in a distributed database system, which means that more than one site will process the same transaction. Transaction location and transaction control are the two primary deadlock handling concerns in a distributed database system that are not present in a centralized system. Once these concerns are addressed, deadlocks are handled by detecting and removing any deadlock prevention, deadlock avoidance or deadlock.
In a distributed database system, transactions are processed on multiple sites and data items are used on multiple sites. The amount of processing of data between these sites is not universally distributed. The processing time period varies, too. The same transaction may therefore be active at certain sites and inactive at others. If two conflicting transactions are located on a site, one of them may be in an inactive state. In a centralized structure, this situation does not occur. This concern is called the problem of transaction location.
The Daisy Chain model could address this concern. A transaction carries some information in this model as it travels from one location to another. Some of the specifics are the list of required tables, the list of required sites, the list of tables and sites visited, the list of tables and sites yet to be visited, and the list of types of locks obtained. After either having committed or aborting a transaction ends, the data should be sent to all the concerned sites
Transaction control is concerned with designating and managing the sites needed in a distributed database system to process a transaction. There are several choices for deciding where to process the transaction and how to designate the control center, such as
Distributed Deadlock Prevention
Just as in centralized deadlock prevention, before beginning to execute, a transaction should obtain all the locks in the distributed deadlock prevention approach. It avoids deadlocks.
The site of entry of the transaction is designated as the site of control. In order to lock the items, the controlling site sends messages to sites where the data items are located. It waits for confirmation then. If all the sites have confirmed that the data items have been locked, the transaction begins. The transaction has to wait until it has been fixed if any site or communication link fails.
Although the implementation is quick, there are some drawbacks to this approach-
Distributed Deadlock Avoidance
Distributed deadlock avoidance manages deadlock prior to occurrence, as in a centralized system. In addition, transaction location and transaction control problems need to be discussed in distributed systems. The following conflicts can occur because of the distributed nature of the transaction,
Let's assume that two transactions are taking place, T1 and T2. T1 arrives at Site P and tries to lock a data item that at that site is already locked by T2. There is a conflict at Site P, therefore. The algorithms are as follows-
Distributed Deadlock Detection
Deadlocks are allowed to occur and are removed if detected, just like the centralized deadlock detection approach. When a transaction issues a lock request, the system does not perform any checks. Global wait-for-graphs are generated for implementation. The presence of a cycle implies deadlocks in the global wait-for-graph. However, since the transaction waits for resources across the network, it is hard to spot deadlocks.
Instead, algorithms for deadlock detection may use timers. A timer that is set to a time span in which a transaction is supposed to end is associated with each transaction. The timer goes off, indicating a possible deadlock if a transaction does not finish within this time period.
A deadlock detector is another tool used for deadlock handling. There is one deadlock detector in a centralized system. There can be more than one deadlock detector in a distributed system. For the sites under its control, a deadlock detector can locate deadlocks. In a distributed scheme, there are three alternatives for deadlock identification, namely.