Deadlock in DBMS
A deadlock is an unwanted condition in which two or more transaction are waiting indefinitely for one another to give up locks. It is said to be one of the most feared complications in database management system as no operation ever gets completed and is in waiting state forever.
To understand the concept of deadlock, take an example:In the account table, transaction T1 holds a lock on some rows and needs to update some rows in the order table. Simultaneously, transaction T2 holds a lock on some rows in the order table but needs to update the rows in the account table held by Transaction T1.
Now, the main problem arises. Transaction T1 cannot complete its execution because it is waiting for transaction T2 to release its lock. And similarly, transaction T2 is waiting for transaction T1 to release its lock. Due to this, all activities come to a halt state and remains at a standstill forever until the database management system (DBMS) detects the deadlock and aborts one of the transactions.
When a database is stuck in the deadlock condition, then it is always better to avoid the database rather than restarting or aborting the database.
The deadlock avoidance method is used to detect and deadlock situation in advance, and this mechanism is suitable for smaller databases. For the larger databases, deadlock prevention mechanism can be used.
When a transaction waits indefinitely to obtain a lock in the database, then the database management system (DBMS) should detect whether the transaction is involved in a deadlock condition or not. To detect the deadlock cycle in the database lock manager maintains the wait-for-graph.
- Wait-for graph is one of the suitable methods for deadlock detection, and it is suitable for smaller databases. In this method,
- graph can be created on the basis of a transaction and their locks on the resources. If the created graph contains a loop or a cycle, then there exists a deadlock situation.
- For the above scenario, the wait-For graph is shown below:
- Deadlock prevention is method which is suitable for large databases. If the resources are allocated in such a way that the deadlock situation never occurs, then a deadlock can be prevented.
- The database management system (DBMS) analyses the operation of a transaction, whether they can create a deadlock condition or not. If they create a situation, then DBMS never allowed that transactions to execution.
Deadlock prevention mechanism proposes the following two different schemes:
2. Wound-Wait Scheme
The wait–die scheme is a nonpreemptive technique. When transaction Ti requests a data item which is currently held by Tj. T
hen Ti transaction is allowed to wait only if the timestamp of Ti transaction is smaller than that of transaction Tj ( i.e., Ti is older than Tj). Otherwise, Ti is rolled back (dies).
For example, suppose that transactions T14, T15, and T16 have timestamps 5, 10, and 15, respectively. If transaction T14 requests a data item held by T15, then T14 will wait for execution. If T24 transaction requests a data item held by T15, then T16 will be rolled back.
The wound–wait scheme is a preemptive technique. When Ti transaction requests a data item which is currently held by Tj, Ti is allowed to wait only if it has a timestamp larger than that of Tj (that is, Ti is younger than Tj). Otherwise, Tj transaction is rolled back(Tj is wounded by Ti).