As shown in partial schedule transaction T1 is waiting for transaction T2 to release its lock on data item B and transaction T2 is waiting for transaction T I to release its lock on data item A. Such a cycle of transactions waiting for locks to be released is called a Deadlock.
Clearly, these two transactions will make no further progress. Now we can define the deadlock as
"A system is in a deadlock state if there exists a set of transactions such that every transaction in the set is waiting for another transaction in the set."
More precisely, there exists a set of waiting transactions (T0,TI, Tn) such that TO is waiting for a data item that is held by T I and T I is waiting for a data item that is held by T2 and
....... Tn-l is waiting for a data item that is held by Tn and Tn is waiting for a dCltaitem that is held by TO. None of the transactions can make progress in such a situation.
There are two principal methods for dealing with the deadlock problem.
- Deadlock prevention
- Deadlock detection
Deadlock prevention: We can use a deadlock-prevention protocol to ensure that the system will never enter a deadlock state.
Deadlock detection: In this case, we can allow the system to enter a deadlock state, and then try to recover using a deadlock detection and deadlock recovery scheme.
Both the above methods may result in transaction rollback. Prevention is commonly used if the probability that the system would enter a deadlock state is relatively high; otherwise detection and recovery are more efficient.
Deadlock Prevention
We can prevent deadlocks by giving each transaction a priority and ensuring that lower priority transactions are not allowed to wait for higher priority transactions (or vice versa). One way to assign priorities is to give each transaction a timestamp when it starts up. The lower the timestamp, the higher the transaction priority that is, the oldest transaction has the highest priority.
If a transaction Ti requests a lock and transaction Tj holds a conflicting lock, the lock manager can use one of the following two policies:
Wait-die
If Ti has higher priority, it is allowed to wait; otherwise it is aborted. It means when transaction Ti requests a data item currently held by Tj, Ti is allowed to wait only if it has a timestamp smaller than that of T1 (that is Ti is older than Tj). Otherwise Ti is rolled back (dies).
Example
Suppose that transactions T22, T23 and T24 have timestamps 5, 10 and 15 respectively. If T22 requests a data item held by T23 then T22 will wait. If T24 requests a data item held by T23 then T24 will be rolled back.
T22 will Wait T24 will rollback
T22 ----------------------> T23 <---------------------- T24
(5) (10) (15)
The wait-die scheme is non-preemptive scheme because only a transaction requesting a lock can be aborted. As a transaction grows older (and its priority increases), it tends to wait for more and more younger transactions.
Wound-wait
If Ti has higher priority, abort Tj otherwise Ti waits. It means when transaction Ti requests a data item 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 is rolled back (Tj is wounded by Ti).
Example:
Returning to our previous example, with transactions T22,T23 and T24, ifT22 requests a data item held by T23 then the data item will be preempted from T23 and T23 will be rolled back. IfT24 requests a data item held by T23, and then T24 will wait.
T22 access T23 will be
Data item rollback
T22 --------------------> T23
(5) (10)
Data item with T23 wait for T23
T23 <------------------ T24
(10) (15)
This scheme is based on a preemptive technique and is a counterpart to the wait-die scheme. In the wait-die scheme, lower priority transactions can never wait for higher priority transactions. In the wound-wait scheme, higher priority transactions never wait for lower priority transactions. In either case no deadlock cycle can develop.
When a transaction is aborted and restarted, it should be given the same timestamp that it had originally. Reissuing timestamps in this way ensures that each transaction will eventually become the oldest transaction, and thus the one with the highest priority, and will get the locks that it requires.
Problem of starvation
Whenever transactions are rolled back, it is important to ensure that there is no starvation that is, no transaction gets rolled back repeatedly and is never allowed to make progress.
Both the wound-wait and the wait-die schemes avoid starvation. At any time, there is a transaction with the smallest timestamp. This transaction cannot be required to roll back in either scheme. Since timestamps always increase, and since transactions are not assigned new timestamps when they are rolled back, a transaction that is rolled back will eventually have the smallest timestamp. Thus it will not be rolled back again.
Differences between wait-die and wound-wait scheme
There are following differences between wait-die and wound-wait schemes:
- In the wait-die scheme an older transaction must wait for a younger one to release its data item. Thus, the older the transaction gets the more it tends to wait. By contrast, in the wound wait scheme, an older transaction never waits for a younger transaction.
- In the wait-die scheme, if a transaction T24 request a data item held a data item by T23 and T24 then die and roll back because Ti request a data held by Tj and TS(Ti» TS(Tj). Now T24 restarted and may reissue the same sequence of requests if data item is still held by T23 then T24 will die again. Thus T24 may die several times before acquiring the needed data item.
Now see what happen in case of wound-wait scheme transaction Ti is wound and rollback because Tj request a data item that it holds and TS(Ti>TS(Tj). Now suppose that data item is held by T23 and T22 request the data item held by T23. Then T23 is wound and rollback because TS (23>TS (T22). When T23 will again restarted and request the data item T22 then again, TS (23>TS (22) and T23 will wait for transaction T22 and T23 will not rollback again. Thus, there may be few rollbacks in the wound wait scheme.
Timeout-Based Schemes
Another simple approach to deadlock handling is based on lock timeouts. In this approach, a transaction that has requested a lock waits for at most a specified amount of time. If the lock has not been granted within that time, the transaction is said to time out, and it rolls itself back and restarts. If there was in fact a deadlock, one or more transactions involved in the deadlock will time out and roll back, allowing the others to proceed. This scheme falls somewhere between deadlock prevention, where a deadlock will never occur and deadlock detection and recovery.
Uses of Timeout-Based Schemes
The timeout scheme is particularly easy to implement, and works well if transactions· are short, and if long waits are likely to be due to deadlocks.
Limitations
• It is hard to decide how long a transaction must wait before timing out. Too long a wait results in unnecessary delays once a deadlock has occurred. Too short a wait results in transaction rollback even when there is no deadlock, leading to wasted resources.
• Starvation is also a possibility with this scheme.
Hence the timeout-based scheme has limited applicability.
No comments:
Post a Comment