Deadlock handling and Prevention

Deadlock Handling

Consider the following two transactions:

T₁: Write (X)
Write (Y)

T₂: Write (Y)
Write (X)

Schedule with deadlock:

System is said to be deadlocked if there is a set of transactions in such a way that every transaction in the set is waiting for another transaction in the same set. Deadlock prevention protocols ensures that the systems will never enter into a deadlock state. Some prevention strategies which:

• Require that each transaction locks all its data items before it begins execution that is predeclaration
• Impose partial ordering of all data items and require that a transaction can lock data items only in the order which is specified by the partial order that is graph-based protocol.

Deadlock Prevention

Two approaches to deadlock prevention:

• One approach ensures that no cycle waits can occur by ordering the requests for locks, requiring all locks to be acquired together.
• Another approach performs the roll back of a transaction instead of waiting for a lock while the wait could potentially result in a deadlock anytime.

The first approach requires that each transaction locks all its data items before execution. Moreover either all are locked in one step or none are locked. There are two main disadvantages:

• It is often hard to predict what data items need to be locked before the transaction begins.
• Data item utilization may be very low since many of the data items may be locked but is unused for a long time.

The second approach for preventing deadlocks is to use preemption and transaction rollback. These schemes use timestamps for just deadlock prevention.

A Wait-die scheme is non-preemptive. When transaction T_i requests a data item currently held by T_j, T_i is allowed to wait only if it has a timestamp smaller than that of T_j. Otherwise T_i rolled back (dies). For example, suppose that transactions T1, T2 and T3 have timestamps 20, 30 and 40 respectively. If T1 request a data item held by T2 then T2 will wait. If T3 requests a data item held by T2 then T3 will be rolled back.

Wound-wait scheme is preemptive.When transaction T_i requests a data item currently held by T_j T_i is allowed to wait only if it has a timestamp which is larger than that of T_j. Otherwise T_i rolled back. For example,suppose that transactions T1, T2 and T3 have timestamps 20, 30 and 40 respectively. If T1 request a data item held by T2 then the data item will be preempted from T2 and will be rolled back. If T3 requests a data item held by T2 then T3 will wait.

Both in wait-die and wound-wait schemes a roll back transaction is restarted with its original timestamp. Thus the older transactions have precedence over newer ones and hence the starvation is avoided.

Timeout-Based Schemes: A transaction waits for a block only for a specified amount of time. After that, the wait times out and the transaction is rolled back. Thus deadlocks are not possible. These schemes are simple to implement but starvation is possible. It is also difficult to determine the good value of timeout interval.

Deadlock Detection

Deadlocks can be described as a wait-for graph which consists of a pair G = (V,E) where,

• V is a set of vertices (all the transactions in the system)
• E is a set of edges and each element is an ordered pair T_i→ T_j.

If T_i→ T_j is in E then there is a direct edge from T_i to T_j which implies that T_i is waiting for T_j to release a data item. When T_i requests a data item which is currently being held by T_j then the edge T_i- T_j is inserted in the wait-for graph. This edge is removed only when T_j is no longer holding a data item which is needed by T_i. The system is in a deadlock state if and only if the wait-for graph has a cycle. It must invoke a deadlock-detection algorithm to look for the cycles periodically.

Deadlock Recovery

When deadlock is detected:

• Some transaction will have to roll back (made a victim) to break deadlock. Select the transaction as victim that will incur minimum cost.
• Rollback determines how far the transaction should be rolled back. Total rollback aborts the transaction and then restart it. It is more effective to roll back transaction only as far as necessary to break the deadlock.

Starvation occurs if the same transaction is always chosen as a victim. It includes the number of roll backs in the cost factor to avoid starvation.

References:

1. H.F.Korth and A. Silberschatz,"Database system concepts",McGraw Hill,2010
2. A.K.Majumdar and p, Bhatt acharya,"Database Management Systems",Tata McGraw Hill,India,2004
3. F.Korth, Henry. Database System Concepts. 6th edition.