Showing posts with label Deadlock. Show all posts

Saturday, April 26, 2014

Deadlock Prevention algorithms in Database

What are the deadlock prevention algorithms in database?

Notes and Tutorials on How to prevent deadlock? / How to prevent deadlock in DBMS? / Deadlock prevention techniques in DBMS / Wait-die and Wound-wait in DBMS / Database deadlock avoidance / Wait-die and Wound-wait example

The Deadlock prevention protocol prevents the system from deadlock through transaction rollbacks. It chooses rollback over waiting for the lock whenever the wait could cause a deadlock. In this approach we have the following two deadlock prevention algorithms;

1. Wait-die scheme

2. Wound-wait scheme

Assume that a transaction T1 requests for a lock on a data item X. And, the data item X is already locked by another transaction T2 in an incompatible mode. Now the question is “Can we allow transaction T1 to wait or to roll-back?” The Deadlock Prevention algorithm works by allowing a transaction to wait or force it to roll-back to prevent the occurrence of deadlock.

Points to note:

1. Deadlock prevention technique is used for a system for which the possibilities for entering a deadlock state are high.

2. Using 2 Phase Locking protocol to lock all the required data items at once may help in preventing deadlock at the cost of lower data-item utilization.

3. Every time Wait-die or Wound-wait roll-back a transaction, it is very important to ensure that the system does not choose the same transaction repeatedly. The repeated rollback of same transaction will lead to the state called Starvation. Both Wait-die and Wound-wait avoids starvation. This is handled by issuing the same timestamp for the transaction which is rolled back.

4. In Wait-die scheme, older transaction waits. In Wound-wait scheme, older transaction never waits.

5. The major drawback: both schemes lead to unnecessary rollbacks.

Deadlock prevention in dbms

How to prevent deadlock in database management systems

Wait die and wound wait algorithm in deadlock prevention

Deadlock Handling Techniques in Database

What are the Deadlock handling techniques in database?

A set of transactions are considered to be in a deadlock state, if the transactions are waiting for one another to release the data items needed for them that are held by others. In a deadlock state no transaction will proceed.

The deadlock can be handled by rolling back a transaction which would be chosen as the victim.

Deadlock can be handled in the following ways;

Deadlock Prevention – this concept ensures that the system never enters a deadlock state. It chooses the transaction which would probably cause the deadlock and rolls-back the transaction.

Deadlock Detection – this identifies the deadlock if any happened and recovers the system from deadlock.

Deadlock Recovery - recovers the system from deadlock state. It chooses the identified transaction which caused the deadlock, and rolls-back it.

How to handle deadlock in database management systems

Monday, April 14, 2014

What is deadlock in database?

What is Deadlock? / Deadlock - Explained with examples / How to handle deadlocks?

What is Deadlock?

In Database Management System, Deadlock is part of discussion in Transaction Processing Component. Deadlock is a situation where two or more transactions waiting for locks on some data items which are locked by other transactions in an incompatible mode.

Here, incompatible mode would mean one of the following;

A read lock request for a data item which is locked in write mode

A write lock request for a data item which is locked in read mode

A write lock request for a data item which is locked in write mode.

Example:

Assume that two transactions T1 and T2 are needed data items A and B to be locked. In the lock acquiring process, let us suppose T1 locked A successfully and T2 locked B successfully. For successfully completing the transactions, T1 needs B also to be locked and T2 needs A. The problem is T1 cannot release lock on A and T2 cannot release lock on B. This situation is called deadlock. If you carefully observe this you would understand that we have formed a cycle which leads to deadlock.

1 (a)

1 (b)

Figure 1 - (a) Deadlock occurrence with two transactions, (b) deadlock occurrence with three transactions

Real time example of Deadlock situation:

Let us assume two bank transactions, namely T1 and T2 as follows;

T1 – Transaction which transfers money, say Rs. 5000 from account A to account B. T1 needs to lock both A and B in Write mode (Exclusive Lock). T1 is said to be completed if and only if it successfully updates the old balance of A and B with a new balance and commits the transaction.

T1 would involve two update queries;

UPDATE ACCOUNT SET balance = balance -5000 WHERE account = ‘A’;

UPDATE ACCOUNT SET balance = balance +5000 WHERE account = ‘B’;

T2 – Transaction which updates all the accounts with yearly interest, say 5%. T2 need to lock all the accounts in Write mode (Exclusive lock). T2 is said to be completed if and only if it successfully updates the old balances of all the accounts with the new balances and commits the transaction.

T2 would involve one update query;

UPDATE ACCOUNT SET balance = balance + (balance*0.05);

Assume that the transactions are executed as follows;

T1 has started and acquired Write lock on account A. T1 can now debit the amount to be transferred from account A and save the new value of A. (cannot commit the transaction T1 at this stage)

T2 also has started at the same time and acquired Write lock on B along with other accounts. T2 can now update all the accounts with their interest amounts except account A. (because account A is held by T1. Hence, T2 cannot commit as well at this stage).

At this stage, both T1 and T2 are waiting for each other which leads to deadlock. This is shown in Figure 2.

Figure 2 - Deadlock situation example

What is the solution to handle deadlocks if occured?

The only solution is to pick up one of the Transactions and roll back the same.