DDBMS - Deadlock Handling

DDBMS - Deadlock Handling

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.

What are Deadlocks?

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.

Deadlock Handling in Centralized Systems

There are three classical approaches for deadlock handling, namely −

• Deadlock prevention.
• Deadlock avoidance.
• Deadlock detection and removal.

Both a centralized and a distributed database system will incorporate any of the three approaches.

Deadlock Prevention

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.

Deadlock Avoidance

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-

• Wait-Die − If T1 is older than T2, T1 is allowed to wait. Otherwise, if T1 is younger than T2, T1 is aborted and later restarted.
• Wound-Wait − If T1 is older than T2, T2 is aborted and later restarted. Otherwise, if T1 is younger than T2, T1 is allowed to wait.

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-

• Choose which transaction is youngest.
• Select the transaction with the fewest data items.
• Choose the transaction with the least number of updates performed.
• Pick the transaction that has the least overhead restart.
• Select a transaction that has two or more cycles in common.

This approach is mainly suited to systems with low transaction levels and where rapid response to lock requests is needed.

Deadlock Handling in Distributed Systems

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.

Transaction Location

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

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

• As the centre of control, one server can be selected.
• From one server to another, the control centre can travel.
• A number of servers can share the controlling responsibility.

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-

• Pre-acquisition of locks for communication delays takes a long time. This increases the transaction time required.
• A transaction has to wait for a long time in case of site or link failure in order for the sites to recover. Meanwhile, the things are locked at the running sites. This can prevent the execution of other transactions.
• It will not interact with the other sites if the controlling site fails. The locked data items continue to be kept in their locked state by these sites, leading to blocking.

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,

• Conflict between two site-specific transactions.
• Conflict between two different site transactions.

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 Wound-Die
  • T1 is allowed to wait if T1 is older than T2. After Site P receives a message that T2 has either committed or aborted successfully at all sites, T1 will resume execution.
  • T1 is aborted if T1 is younger than T2. Site P's competition control sends a request to all the sites that T1 has visited to abort T1. When T1 is successfully aborted on all sites, the controlling site notifies the user.
• Distributed Wait-Wait
  • T2 has to be aborted if T1 is older than T2. Site P aborts and rolls back T2 if T2 is active on Site P, and then transmits this message to other relevant sites. Site P broadcasts that T2 has been aborted if T2 has left Site P but is active at Site Q; Site L then aborts and rolls back T2 and sends this message to all sites.
  • T1 is allowed to wait if T1 is younger than T1. After Site P gets a message that T2 has finished processing, T1 will resume execution.

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.

• Centralized Deadlock Detector-The central deadlock detector is designated as one site.
• Hierarchical Deadlock Detector- A number of hierarchical deadlock detectors are grouped.
• Distributed Deadlock Detector-Both sites are involved in the detection and removal of deadlocks.