Deadlock in Transaction
What is Deadlock and How the Deadlock is occurred?
Deadlock occurs when each transaction T in a set of 2 or more transactions is waiting for some item that is locked by some other transaction T’ in the set. Hence, each transaction in the set is on a waiting queue, waiting for one of the other transaction in the set to release the lock on an item.
Where the Deadlock Occurs ?
The concurrency control technique called locking may lead to deadlock.
- 2 Phase Locking (2PL)
- 2PL + Binary Locking
- 2PL + Shared and Exclusive Locking
However, 2 phase locking ensures serializability but it may lead to a deadlock state.
The combination of (binary lock + 2 PL) and the combination of (shared and exclusive lock + 2 PL) also may lead to a deadlock state.
What is Deadlock Detection and Deadlock Prevention ?
Deadlock Detection deals with deadlocks in which the system check if state of deadlock actually exists or not whereas Deadlock Prevention Protocols are used to prevent from deadlock.
When to Use Deadlock Detection and When to Use Deadlock Prevention?
- If the transaction load is light or if the transactions are short and each transaction lock only a few items, then we should use a deadlock detection scheme.
- However, if the transaction load is quite heavy or if the transaction are long and each transaction uses many data items, then we should use a deadlock prevention scheme.
Deadlock Detection Schemes
To detect the state of deadlock, directed graph is to be constructed which is called wait-for-graph(WFG). The nodes of WFG are labelled with active transaction names. and an edge exists from Ti → Tj from node Ti to node Tj iff transaction Ti is waiting for transaction Tj to release some lock.
For a deadlock to be occur, the WFG must have a cycle and the scheduler can detect deadlocks by checking for cycles in the WFG.
- After the detection of the deadlock, it can be prevent by aborting a transaction.
- The scheduler should select the transaction among the transactions involved in the cycle of WFG whose absorption involves minimum cost i.e. it tries to select younger transactions( which do not made many changes).
- The chosen transaction for abort is called victim transaction.
Point : The algorithm for victim selection generally avoid those transactions that have been for a long time and that have performed many updates.
Timeout Method is more practical scheme for deadlock. In timeout method if a transaction waits for a period longer than a system defined timeout period, the system assumes that the transaction may be in deadlock state and aborts it regardless of whether a deadlock actually exist or not.
Deadlock Prevention Protocols
Deadlock prevention protocols are used to prevent from deadlock. There are various deadlock prevention protocols which are :
Conservative Two Phase Locking (Conservative 2PL)
- Since each transaction lock all the items it needs in advance, therefore no deadlock occurs. If any of the items cannot be obtained then none of the items are locked.
- The conservative 2pl is not a practical method as it provides less concurrency and it can leads to starvation also.
Ordering All the Items Protocol
- This protocol also limits concurrency because it involves ordering all the items in the database and making sure that the transaction that need several items will look them according to that order.
- It is also not a practical method as the programmer order system is aware of the chosen order of the items.
No Waiting Algorithm
- In No Waiting Algorithm scheme if a transaction is unable to obtain a lock it is immediately abort it and then restarted after a certain time delay without seeing whether a deadlock will actually occur or not.
- This Algorithm can cause transactions to abort and restart needlessly.
Cautious Waiting Algorithm
To reduce the number of needless aborts and restarts, the cautious algorithm is used.
Suppose there are two transaction Ti and Tj. Ti is waiting for a data item X which is locked by Tj.
- If Tj : Blocked( waiting for some other locked data item) – Abort Ti.
- If Tj : Not Blocked( not waiting for some other locked data item) – Ti is blocked and allowed to wait.
The Cautious Waiting is Deadlock Free because no transaction will never wait for another blocked transaction.
Deadlock Prevention Using the Concept of Timestamp Ordering [TS(T)]
Transaction timestamp TS(T) is a unique identifier assigned to each transaction based on the order in which transaction are started.
Transaction timestamp TS(T) Timestamp TS(T) is a unique identifier but not any kind of time. TS(T) can be understand as a priority identifier in which the lesser number identifies the older transaction and the greater number identifies the younger transaction i.e. if T1 starts before transaction T2, then, TS(T1) < TS(T2). (Lesser priority) (Higher priority) (Older Transaction) (Younger Transaction)
There are two methods for preventing deadlock using the concept of timestamp ordering :
- Wait Die
- Wound Wait
Suppose there are two transaction Ti and Tj where Ti is older than Tj i.e. TS(Ti) < TS(Tj),
The following rules are followed by these schemes :
Wait die :
- If transaction Ti is waiting for a data item X which is locked by Tj, then Ti is allowed to wait.
- If transaction Tj is waiting for a data item X which is locked by Ti abort Tj or rollback Tj and restart it later with the same timestamp.
Wound Wait :
- If transaction Ti is waiting for a data item X which is locked by Tj then abort Tj or rollback Tj and restart it later with the same timestamp.
- If transaction Tj is waiting for a data item X which is locked by Ti, then Tj is allowed to wait.
|Thomas write rule||Starvation in Deadlock (Livelock)|