Deadlock
There are many types of situations which a process has to go through before being executed and finally processed. There are basically two types of systems – single process systems and multi process systems. In multiple process systems, an unwanted condition especially in case of shared resources when a resource needed by process A is being used by process B. Lets take an example to understand this better, we have set of transactions {A0, A1…...AN}. A0 will use a resource which is being held by A1, A1 will use a resource which is being held by A2 and so on. So, this condition when all the processes are infinitely waiting for another resource so that when it releases the resource, they can complete their work is known as deadlock.
Such a condition is not very much appreciated by the system because when the system enters deadlock, there is infinite wait and the processes have to be either rolled back or restarted before they can continue their transaction. It is always better to prevent something before its even started so the philosophy of ‘prevention is better than cure is also tried to be followed in case of deadlock. Deadlock prevention and deadlock avoidance schemes help in making sure that we don’t have to get stuck in such a system.
DEADLOCK PREVENTION
To prevent the occurrence of deadlock, we have to make sure that DBMS runs a thorough check of all the systems where the transactions are going to be executed. After going through all the transactions, the one’s which are likely to cause deadlock are halted or sometimes removed from the execution queue.
There are following types of deadlock preventive processes which use timestamp mechanism: -
-
WOUND-WAIT SCHEME
In this type, the young and new transactions are supposed to wait and if an old transaction is supposed to use a resource occupied by the new transactions, it aborts the new transaction.
a
In this type of condition, when a transaction is willing to ‘lock’ a resource which is already being held by some other transaction, either of the two things happens: -
- If TS(Ta) < TS(Tb), then Ta makes sure that Tb rolls backs and Tb restarts later with a little bit of delay.
- If TS(Ta) > TS(Tb), then Ta should wait till the resource is freed and made available.
-
WAIT-DIE SCHEME
In this type, the older transaction is allowed to wait but the new transaction is killed.
In this when a lock is requested upon a data item which is in possession of another transaction, one of the two conditions will happen: -
- If TS(Ta) < TS(Tb), then Ta is allowed to wait for the data item till it’s available.
- If TS(Ta) > TS(Tb), then Ta is aborted (dies) and is restarted again.
DEADLOCK AVOIDANCE
It is not always possible and advised to abort transactions, therefore a more practical approach like deadlock avoidance should be followed. Although, this is a better suited technique for small systems. For huge systems, deadlock prevention is the type of method that’s preferred. A type of deadlock avoidance scheme called ‘wait-for graph’ is explained below.
WAIT FOR GRAPH
In this method, when transaction Ta enters a system, a node is dedicated to it and same happens for transaction Tb. Now when Ta wants to put a lock on data item X and the data item is held by Tb, an edge is created from transaction Ta to transaction Tb. And if a transaction is released between the 2 nodes, then the edge is dropped. This graph is made for all the transactions which are waiting for some data items being held because they are waiting for some data item.