DBMS Deadlock

DBMS Deadlock

In a multi-process system, deadlock is an unwanted situation that occurs in a shared resource setting where a process is waiting for a resource held by another process indefinitely.

For example , assume a {T0, T1, T2, ..., Tn} transaction set. In order to complete its task, T0 requires resource X. T1 is the holding of resource X, and T1 is waiting for resource Y to be held by T2. Resource Z, which is held by T0, is waiting for T2 All the processes are therefore waiting for each other to release resources. None of the processes can finish their task in this situation. This situation is regarded as a deadlock.

For a system, deadlocks are not healthy. The transactions involved in the deadlock are either rolled back or restarted in the event that a system is stuck in a deadlock.

Deadlock Prevention

The DBMS actively inspects all the operations where transactions are about to be performed in order to prevent any deadlock situation in the system. The DBMS inspects the activities and evaluates whether a deadlock situation can be established. If it finds that there may be a deadlock situation, then it is never allowed to execute that transaction.

To predetermine a deadlock situation, deadlock prevention schemes use the time stamp ordering process of transactions.

Wait-Die Scheme

In this scheme, if a transaction requests to lock a resource (data item) that is already held by another transaction with a conflicting lock, then one of the two options may occur,

• If TS(Ti) < TS(Tj) − that is Ti, which is requesting a conflicting lock, is older than Tj − then Ti is allowed to wait until the data-item is available.
• If TS(Ti) > TS(tj) − that is Ti is younger than Tj − then Tidies. Ti is restarted later with a random delay but with the same timestamp.

This scheme allows the older transaction to wait but kills the younger one.

Wound-Wait Scheme

In this scheme, if a transaction requests to lock a resource (data item) that is already held by some other transaction with a conflicting lock, one of the two options which occur.

• If TS(Ti) < TS(Tj), then Ti forces Tj to be rolled back − that is Ti wounds Tj. Tj is restarted later with a random delay but with the same timestamp.
• If TS(Ti) > TS(Tj), then Ti is forced to wait until the resource is available.

This scheme allows the younger transaction to wait, but the older transaction requires the younger one to abort and release the item when an older transaction demands an item kept by a younger one.

In both instances, at a later stage, the transaction that enters the system is aborted.

Deadlock Avoidance

Not always a practical approach is to abort a transaction. Instead, to detect any deadlock situation in advance, deadlock avoidance mechanisms can be used. Methods such as "wait-for graph" are available, but they are only appropriate for those systems where transactions are lightweight with fewer resource cases. In a bulky system, techniques of deadlock prevention may work well.

Wait-for Graph

This is a simple tool available for tracking if there could be a deadlock situation. A node is generated for each transaction that comes into the system. When a transaction Ti asks for a lock on an item, say X, which is kept by some other transaction Tj, a guided edge is created from Ti to Tj. The edge between them is dropped if Tj releases item X and Ti locks the data item.

For any transaction waiting for certain data items kept by others, the system retains this wait-for graph. If there is some cycle in the graph, the system keeps checking.

We can use any of the following two approaches here.

• First, do not allow any request for an item, which is already locked by another transaction. This is not always possible and can cause starvation, where a transaction waits for a data item forever and can never obtain it.
• The second option is to roll back one of the transactions. Rolling back the younger transaction is not always possible, as it may be necessary for the older one. A transaction is chosen with the assistance of some relative algorithm, which is to be aborted. This transaction is known as the victim, and the selection of victims is known as the process.