Deadlock in DBMS
A
deadlock is a condition where two or more transactions are waiting indefinitely
for one another to give up locks. Deadlocks are not healthy for a system. In
case a system is stuck in a deadlock, the transactions involved in the deadlock
are either rolled back or restarted.
For
example, transaction T1 holds a lock on some rows in students table and
needs to update some rows in the grade table. Simultaneously, transaction T2
holds locks on some rows in the grade table and needs to update the rows in the
Student table held by Transaction T1. Now the problem is 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 no work is done.
It will remain in a standstill until the DBMS detects the deadlock and aborts
one of the transactions.
Deadlock Avoidance –
It is always better to avoid the deadlock rather
than restarting or aborting the database.
Deadlock avoidance method is suitable for
smaller database whereas deadlock prevention method is suitable for larger
database.
One method of avoiding deadlock is using application consistent logic.
One method of avoiding deadlock is using application consistent logic.
In the above given example, Transactions that
access Students and Grades should always access the tables in the same
order. In this way, Transaction T1 simply waits for transaction T2 to release
the lock on Grades before it begins. When transaction T2 releases the
lock, Transaction T1 can proceed freely.
Another method for avoiding deadlock is to apply both row level locking mechanism and READ COMMITTED isolation level. However, It does not guarantee to remove deadlocks completely.
Another method for avoiding deadlock is to apply both row level locking mechanism and READ COMMITTED isolation level. However, It does not guarantee to remove deadlocks completely.
Deadlock Detection
When a transaction waits
indefinitely to obtain a lock, the database managememt system should detect
whether the transaction is involved in a deadlock or not.
One of the methods to
detect deadlock situation is Wait-for-graph. This method is suitable for
smaller database. In this method a graph is drawn based on the transaction and
their lock on the resource. If the graph created has a closed loop or a cycle,
then there is a deadlock.
Example of the Wait-For graph is drawn below
When a deadlock has been detected the system
recover from the deadlock. The most common solution is to rollback one or more
transactions to break the deadlock (victim selection). The victim has to be
selected such that the rollback of those transaction incur minimum cost.
-
the transaction which has fewest locks
-
transaction tahat has done least work
-
transaction that is farthest from completion.
Deadlock prevention
Deadlock prevention method is suitable for large database. 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 create a deadlock situation, then that transaction is never allowed to be executed.
Deadlock
prevention mechanism proposes two schemes:
- Wait-Die Scheme
In this scheme, if a transaction request for a resource that is locked by other transaction, then the DBMS simply checks the timestamp of both transactions and allows the older transaction to wait until the resource is available for execution.
Suppose, there are two transactions T1 and T2 and let timestamp of any transaction T be TS (T). Now, if there is a lock on T2 by some other transaction and T1 is requesting for resources held by T2, then DBMS performs following actions:
Checks
if TS (T1) < TS (T2) – if T1 is the older transaction and T2 has held some resource, then it allows T1 to wait until
resource is available for execution. If T1
is older transaction and has held some
resource with it and if T2 is waiting for it, then T2 is killed and restarted latter with random delay but
with the same timestamp.
This scheme allows the older transaction to wait but kills the younger one.
This scheme allows the older transaction to wait but kills the younger one.
- Wound Wait Scheme
In this scheme, if an older transaction requests for a resource held by younger transaction, then older transaction forces younger transaction to kill the transaction and release the resource. The younger transaction is restarted with minute delay but with same timestamp. If the younger transaction is requesting a resource which is held by older one, then younger transaction is asked to wait till older releases it.
Deadlock is which unit sir
ReplyDelete