Deadlock in DBMS

 Deadlock in DBMS 

A deadlock is a condition where two or more transactions are waiting indefinitely for one another to give up locks. Deadlock is said to be one of the most feared complications in DBMS as no task ever gets finished and is in waiting for state forever.

Deadlock conditions (Coffman conditions)

Coffman specified four conditions for a deadlock occurrence. A deadlock may occur if all the following conditions hold true.

·        Mutual exclusion condition: two processes cannot use the same resource at the same time.

·        Hold and wait condition: A process that is holding a resource can request for additional resources that are being held by other processes in the system.

·        No pre-emption(book) condition: The process which once scheduled will be executed till the completion. No other process can be scheduled by the scheduler meanwhile.

·        Circular wait condition: All the processes must be waiting for the resources in a cyclic manner so that the last process is waiting for the resource which is being held by the first process.

 

Deadlock Handling

There are three classical approaches for deadlock handling:−

• Deadlock prevention.
• Deadlock avoidance.
• Deadlock detection and removal.

 

Deadlock Prevention

(Ostrich algorithm)

Just like Ostrich behavior “to stick one’s head in the sand and pretend there is no problem.”

Deadlock Prevention ensures that the system never enters a deadlock state.

Following are the requirements to free the deadlock:

1. No Mutual Exclusion: No Mutual Exclusion means removing all the resources that are sharable.

2. No Hold and Wait: Removing hold and wait condition can be done if a process acquires all the resources that are needed before starting out.

3. Allow Pre-emption: Allowing pre-emption is as good as removing mutual exclusion. The only need is to restore the state of the resource for the pre-empted process rather than letting it in at the same time as the pre-emptor.

4. Removing Circular Wait: The circular wait can be removed only if the resources are maintained in a hierarchy and process can hold the resources in increasing the order of precedence.

 

Deadlock Avoidance

 

·        Deadlock Avoidance helps in avoiding the rolling back conflicting transactions.

·        Deadlock avoidance method is suitable for smaller database whereas deadlock prevention method is suitable for larger database.

·        It is not good approach to abort a transaction when a deadlock occurs.

·        Rather deadlock avoidance should be used to detect any deadlock situation in advance.

There are two algorithms for deadlock avoidance.

·        Wait/Die

·        Wound/Wait

Wait / Die

·       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 the resource is available for execution. That means if a younger transaction has locked some resource and older the transaction is waiting for it, then the older transaction is allowed to wait for it till it is available.

•  If T1 is an older transaction and has held some resource with it and if T2 is waiting for it, then T2 is killed and restarted later with random delay but with the same timestamp. i.e. if the older transaction has held some resource and younger transaction waits for the resource, then the younger transaction is killed and restarted with very minute delay with the same timestamp. 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 a younger transaction, then an older transaction forces a younger transaction to kill the transaction and release the resource.

·       The younger transaction is restarted with a minute delay but with the same timestamp.

·       If the younger transaction is requesting a resource which is held by an older one, then the younger transaction is asked to wait till the older one releases it.

Summary

	Wait/Die	Wound/Wait
The older process needs a resource held by the younger process	Older process waits	Younger process dies
The younger process needs a resource held by older process	Younger process dies	Younger process waits

 

Deadlock detection

In a database, when a transaction waits indefinitely to obtain a lock, then the DBMS should detect whether the transaction is involved in a deadlock or not.

The lock manager maintains a Wait for the graph to detect the deadlock cycle in the database.

Wait for Graph

• This is the suitable method for deadlock detection. In this method, a graph is created based on the transaction and its lock. If the created graph has a cycle or closed-loop, then there is a deadlock.
• The wait for the graph is maintained by the system for every transaction which is waiting for some data held by the others. The system keeps checking the graph if there is any cycle in the graph.

The wait for a graph for the above scenario is shown below:

Here, we can use any of the two following approaches −

·      First, do not allow any request for an item, which is already locked by another transaction. This is not always feasible and may cause starvation, where a transaction indefinitely waits for a data item and can never acquire it.

·      The second option is to roll back one of the transactions. It is not always feasible to roll back the younger transaction, as it may be important than the older one. With the help of some relative algorithm, a transaction is chosen, which is to be aborted. This transaction is known as the victim and the process is known as victim selection.

 

Some of the methods used for victim selection are −

• Choose the youngest transaction.
• Choose the transaction with the fewest data items.
• Choose the transaction that has performed the least number of updates.
• Choose the transaction having the least restart overhead.
• Choose the transaction which is common to two or more cycles.

This approach is primarily suited for systems having transactions low and where fast response to lock requests is needed.

=============================================