Deadlock Handling

Deadlock Handling              

AU: May-09, Dec.-14,15,16,19, Marks 16

Deadlock is a specific concurrency problem in which two transactions depend on each other for something.

For example- Consider that transaction T1 holds a lock on some rows of table A and needs to update some rows in the B table. Simultaneously, transaction T2 holds locks on some rows in the B table and needs to update the rows in the A table held by Transaction T1.

Now, the main problem arises. Now Transaction T1 is waiting for T2 to release its lock and similarly, transaction T2 is waiting for T1 to release its lock. All activities come to a halt state and remain at a standstill. This situation is called deadlock in DBMS.

Definition: Deadlock can be formally defined as - " A system is in deadlock state if there exists a set of transactions such that every transaction in the set is waiting for another transaction in the set. "

There are four conditions for a deadlock to occur

A deadlock may occur if all the following conditions holds true.

1. Mutual exclusion condition: There must be at least one resource that cannot be used by more than one process at a time.

2. Hold and wait condition: A process that is holding a resource can request for vd's additional resources that are being held by other processes in the system.

3. No preemption condition: A resource cannot be forcibly taken from a process. Only the process can release a resource that is being held by it.

4. Circular wait condition: A condition where one process is waiting for a resource that is being held by second process and second process is waiting for third process In the....so on and the last process is waiting for the first process. Thus making a circular chain of waiting.

Deadlock can be handled using two techniques -

1. Deadlock Prevention

2. Deadlock Detection and deadlock recovery

1. Deadlock prevention :

For large database, deadlock prevention method is suitable. A deadlock can be prevented if the resources are allocated in such a way that deadlock never occur. The DBMS analyzes the operations whether they can create deadlock situation or not, If they do, that transaction is never allowed to be executed.

There are two techniques used for deadlock prevention -

(i) Wait-Die:

• In this scheme, if a transaction requests for a resource which is already held with a conflicting lock by another transaction then the DBMS simply checks the timestamp of both transactions. It allows the older transaction to wait until the resource is available for execution.

• Suppose there are two transactions T; and T, and let TS(T) is a timestamp of any transaction T. If T2 holds a lock by some other transaction and T1 is requesting for resources held by T2 then the following actions are performed by DBMS:

     • Check if TS(T) < TS(T) - If T, is the older transaction and T, has held some resource, then T, is allowed to wait until the data-item is available for execution. That means if the older transaction is waiting for a resource which is locked by the younger transaction, then the older transaction is allowed to wait for estb n resource until it is available.

    • Check if TS(T;) < TS(T;) - If T; is older transaction and has held some resource and if T, is waiting for it, then T, is killed and restarted later with the random delay but with the same timestamp.

Timestamp is a way of assigning priorities to each transaction when it starts. If timestamp is lower then that transaction has higher priority. That means oldest transaction has highest priority.

For example-

Let T1 is a transaction which requests the data item acquired by Transaction T2. Similarly T3 is a transaction which requests the data item acquired by transaction T2.

Here TS(T1) i.e. Time stamp of T1 is less than TS(T3). In other words T1 is older than T3. Hence T1 is made to wait while T3 is rolledback.

(ii) Wound - wait:

    • In wound wait scheme, if the older transaction requests for a resource which is held by the younger transaction, then older transaction forces younger one to not kill the transaction and release the resource. After some delay, the younger bevomer transaction is restarted but with the same timestamp.

    • If the older transaction has held a resource which is requested by the Younger transaction, then the younger transaction is asked to wait until older releases it.

Suppose T1 needs a resource held by T2 and T3 also needs the resource held by T2, with TS(T1)=5, TS(T2)=8 and TS(T3)=10, then T1 being older waits and T3 being younger dies. After the some delay, the younger transaction is restarted but with the same timestamp.

This ultimately prevents a deadlock to occur.

To summarize

2. Deadlock detection:

• In deadlock detection mechanism, an algorithm that examines the state of the system is invoked periodically to determine whether a deadlock has occurred or not. If deadlock is occurrence is detected, then the system must try to recover from it.

• Deadlock detection is done using wait for graph method.

Wait for graph

• In this method, a graph is created based on the transaction and their lock. If the created graph has a cycle or closed loop, then there is a deadlock.

• The wait for the graph is maintained by the system for every transaction which is waiting for some data held by the others. The system keeps checking the graph if there is any cycle in the graph.

• This graph consists of a pair G = (V, E), where V is a set of vertices and E is a set of edges.

• The set of vertices consists of all the transactions in the system.

• When transaction T_i requests a data item currently being held by transaction T_i, then the edge T_i → T_j is inserted in the wait-for graph. This edge is removed only when transaction T_j  is no longer holding a data item needed by transaction T_i.

• For example - Consider following transactions, We will draw a wait for graph for this scenario and check for deadlock.

We will use three rules for designing the wait-for graph -

Rule 1: If T1 has Read operation and then T2 has Write operation then draw an edge T1->T2.

Rule 2: If T1 has Write operation and then T2 has Read operation then draw an edge T1->T2

Rule 3: If T1 has Write operation and then T2 has Write operation then draw an edge T1->T2

Let us draw wait-for graph

Step 1: Draw vertices for all the transactions

Step 2: We find the Read-Write pair from two different transactions reading from top to bottom. If such as pair is found then we will add the edges between corresponding directions. For instance –

Step 3:

As cycle is detected in the wait-for graph there is no need to further process. The deadlock is present in this transaction scenario.

Example 3.16.1 Give an example of a scenario where two phase locking leads to deadlock. AU: May-09, Marks 4

Solution: Following scenario of execution of transactions can result in deadlock.

In above scenario, transaction T₁, makes an exclusive lock on data item B and then transaction T₂ makes an exclusive lock on data item A. Here unless and until T₁, does not give up the lock (i.e. unlock) on B; T₂ cannot read/write it. Similarly unless and until T₂ does not give up the lock on A; T₁, cannot read or write on A.

This is a purely deadlock situation in two phase locking.

Review Questions

1. Outline deadlock handling mechanisms.    AU: Dec-16, Marks 7

2. What is deadlock? How does it occur? How transactions can be written to

(i) Avoid deadlock. (ii) Guarantee correct execution.

Illustrate with suitable example.      AU: Dec.-15, Marks 16

3. Write short note on- Deadlock       AU: Dec.-14, Marks 4