Deadlock and their prevention |Concurrency Control

DEADLOCK-

In order to understand deadlock, let us consider the following example:

           

 T1                T2                CONCURRENCY CONTROLLER

 lock-X(A)                         Lock granted

                     lock-X(B)     Lock granted

 lock-X(B)                        Request is queued i.e T1 wait for T2 to                              release the lock on data item B.

                  lock-X(A)        Request is again queued i.e T2 will                                                 wait for T1 to release the lock on data                                                                                               item A.

As shown in partial schedule transaction T1 is waiting for transactions T2 to release its lock on data item B and transaction T2 is waiting for transaction T1 to release its lock on data item A. Such a cycle of transactions waiting for locks to be released is called a Deadlock.

DEADLOCK CONDITIONS:

1. Circular wait

2. No preemption

3. Mutual exclusion

4. Hold & wait

HOW TO PREVENT FROM DEADLOCK?

IST APPROACH:- To allow every transaction lock all the data items, it needs before it starts execution and if any of the data items can't be obtained then none of the data items should be locked.

DRAWBACKS: It is very difficult to acquires locks on 3 data items simultaneously.

2ND APPROACH:- It involves assigning an arbitrary serial order on the data item and ensure that data items are locked by the transaction in the order.

DRAWBACKS: It reduces concurrency.

3RD APPROACH:- Based on the concept of Time Stamp Values.This approach is used to decide whether a transaction has to wait or abort & rollback.

TIME STAMP VALUES: 
A time stamp is a unique identifier assigned to each transaction. It usually based on the order in which the transactions are started.

Two methods under 3RD Approach:-

1.) Wait Die- If T1 is the requesting transaction and T2 is requested transaction then

CASE 1 - t(T1)<t(T2) then T1 is allow to wait.

CASE 2 - t(T1)>t(T2) then T1 is abort and rollback.

where t represents time stamp value.

2.) Wound Wait-If T1 is the requesting transaction and T2 is requested transaction then

CASE 1 - t(T1)<t(T2) then T1 is abort and rollback.

CASE 2 - t(T1)>t(T2) then T1 is allow to wait.

where t represents time stamp value.

DEADLOCK DETECTION:

For detecting a deadlock information requires are:

1.) The current set of transactions.

2.) Information about the current allocations of the data item to each of the transactions.

3.) Current set of data items for which each transaction is waiting.

Wait for graph method is used.In this we have to make graph for all transaction.Each node represent the active transaction and edges represents the waiting request.If the cycle is formed then it is in deadlock otherwise not.

DEADLOCK RECOVERY:
There are three methods in which deadlock will recover which are:-

1.) SELECTION OF VICTIM: We should rollback those transactions that will incur the minimum cost. When a deadlock is detected the choice of which transaction to abort can be made using following criteria:

1.) The transaction which have the fewest locks

2.) The transaction that done the least work

3.) The transaction that is farthest from competition.

2.) ROLLBACK: Once we have decided that a particular transaction must be rolled back, we must determine how far this transaction should be rolled back.The simplest solution is to total rollback;Abort the transaction and then restart it. However it is necessary to rollback the transaction only as far as necessary to break the deadlock. But this method requires the system to maintain additional information about the state of all the running system.

3.) PROBLEM OF STARVATION: In a system where the selection of victim is based primary on cost factors, it may happen that the same transaction is always picked as a victim. As a result this transaction never completes its designated task. This situation is called Starvation. The most common solution is to include the number of rollbacks in the cost factor.