AKU UNIVERSITY EXAM QUESTION  2019

Discuss the various approaches for handling the deadlocks in DBMS.

Sol:

Deadlock occur in concurrent execution of transactions. Below fig shows there are transaction T1 and T2 executing concurrently. So, there is a chance to occur deadlock.

Transaction T1 apply exclusive lock on data item B  because T1 performing read and write operation on data item B. After that transaction T2 starts and apply shared lock on data item A because transaction T2 performing read operation on data item A. Now same transaction ask for exclusive lock on data item B but it won't be granted because this item is already locked by transaction T1 but it request and its request is waiting. Here transaction T2 is waiting so transaction T1 will proceed now. Here transaction T1 request  for exclusive lock on data item A which will not be granted because A is already  locked by transaction T1 . Although it is shared locked so we can only grant shared lock but we can grant exclusive lock if it is already applied shared lock. So this is waiting. Here all scenario is shown by below diagram 

This diagram shows that there is waiting cycle, T2 is waiting for applying lock on  B on which T1 is already applied lock so it is in wait state and T1 is waiting to apply lock on data item A on which transaction T2 is already applied on lock so it is also on wait state and this is the situation for deadlock. There is only growing phase of Two Phase Locking . Therefore we can say Two Locking Protocol suffers from Deadlock situation.

There are following approach to handle deadlock situation in DBMS system:

1) Conservative 2- Phase Locking Protocol :

It requires lock on the all data item  before transaction starts means that here is  early prediction that how many data items transaction is going to use. Lets say ,

T1 : A,B,C 

So transaction T1 will request lock on all the data items A, B, C . If it is granted then only transaction will start if lock on all data item A,B,C not  granted  then it will  not start to execute. Transaction T1 will simply wait until all lock granted. So, in this situation we do not have any growing phase because transaction starts when all the lock granted  then transaction will start its shrinking phase. In shrinking phase transaction will keep an unlocking the data item  and then transaction end which is shown in below fig

As all locks are already acquired by this transaction before transaction starts. So, this kind of protocol will not have Deadlock situation. Thus, Two Phase Conservative protocol is Deadlock free protocol but practical implementation is difficult because of early prediction.

2) Time Stamp Protocol :

It is Deadlock free protocol because there is no lock.

What is timestamp?

Timestamp is used to associate time with some transaction. For Example, Lets start counting from 1 Jan 2020 after each sec this give us unique value. Timestamp can be represented by TS(T).  Time stamp can be system clock also. If transaction T1 has come first, then T1 then T3  so this can be represented as below

TS(T1)< TS(T2) < TS( T3)  which is equivalent to serial schedule 

T1 -> T2  -> T3

We have two timestamp associated with data item one is read timestamp another one is write timestamp. Read Timestamp(A) means youngest transaction perform read operation over data A. To understand this let there are multiple transaction T1, T2, T3 performing read operation on data item A and youngest time stamp is T3 so it is read timestamp on data item A

Write Timestamp(B) will be largest timestamp value among the transaction applied on data item B . Youngest transaction will have largest timestamp value.

Basic Time Stamp Ordering Protocol

 if(write TS(x) > TS(T))

 abort T and Rollback;

else 

    {

read(x);

read TS(x)=TS(T);

    }