What is Deadlock ? – Definition

Data base management system (DBMS) represent the management of data which includes various processes like collection of related data , storing and retrieving them, using set of programs for easy and effective manner.   While it may sound quit simple and easy but in reality it is not. As the bulk of data increases with the complexity of systems and multiple process running head to head it leads to most feared complication called Deadlock. It is nightmare for the developers and programmers. We will be discussing in detail everything about this evil Deadlock in our following article below. Starting with the definition first.

Definition

Deadlock is a situation which occurs in a multi-process system where there is a resource sharing environment and when one process keep on holding the resource for an indefinite period of time, which is been required by another process then this situation lead to a deadlock or halt in the system working. To understand this phenomena more clearly we will take up the following example.
Suppose we have two process P1 and P2 and two resources R1 and R2 and R1 is allocated to P1 and R2 is allocated to P2.
P1  →  R1
P2  →  R2
Now P1 wants R2 resource to complete its process but P2 keep holding it whereas P2 wants R1 resource to complete itself thus both P1 and P2 keep waiting and all this will lead to a standstill situation in which no process will be able to complete itself and will be in wait state forever. Thus ultimately leading to deadlock.

Deadlock Detection and Avoidance:

Now here arises a question how to detect whether a deadlock occurred or not. For that we have resource scheduler and if any deadlock situation arises it would be known to resource scheduler. Always terminating a transaction is not considered best approach to solve the problem of deadlock instead a deadlock avoidance mechanism can be employed to detect the deadlock situation before hand. One such mechanism is called Wait – for graph. This is easy and good to use but won’t work with bulky system rather are made for system with lighter and transactions and resource movements.
Wait-for graph:
It is an easy and simple way to find if any deadlock situation occurs. Here a node is created for every transaction entering the system. For example T1 requesting for the resource R which is held by another transaction T2 then a directed edge is created from T1 and T2. When T2 release the resource R then this edge will be dropped or cancelled and T1 will have the resource R. the system maintain this wait-for graph for every transaction waiting for the resource.

Deadlock Occurrence Conditions:

Coffman Condition:Deadlock can arise if following four conditions occurs together or simultaneously. These conditions are also considered while working on deadlock related to OS also.
1 Mutual Exclusion: at least one resource must be there that cannot be allocated to one process more than one time.
2.Hold and Wait: a process at any time can request for another resource been hold by another process while already holding one resource with itself.  
3.No Preemption: a process cannot be forced to release the resource at any particular point of time. Its upto the process to release it accordingly.
4.Circular Wait: here exist a wait condition in which process P1 is waiting for resource held by process P2 and Process P2 is waiting for resource held by Process P3 and so on, thus making a circular chain of waiting.

Deadlock Prevention:

We have learnt above that deadlock situation occurs when the above 4 conditions occurs simultaneously so if we are able to prevent one or more of them to occur, it will definitely prevent the deadlock situation to happen. Lets learn more about this context below:
• Mutual Exclusion Avoidance: resources are sharable so at a particular time more than one process can get hold of it thus this way is practically not viable.
• Hold and Wait Condition Avoidance: this can be achieved when the process is allocated all the resources well before the process starts.
• Preemption of Resources: a process can be forced to quit the resources leading to rollback and thus able to maintain stability of system.
• Avoiding Circular Wait Condition: this could be achieved if rules are made that one process can get another resource only when it will release the already allocated resource or other way is to maintain a hierarchy of process while allocating resources.

Deadlock Prevention Scheme:

If we want to prevent a deadlock to occur then we need get active transactions of the system monitored by the DBMS. If DBMS detects a possibility of deadlock situation because of certain transactions then that transaction would be terminated and thus maintaining the overall stability of system. There are certain schemes that could be applied by DBMS system which are discussed below.

1. Wait and Die Scheme :
This scheme make use of Time Stamp. Here the core theme is to reject the transaction requesting for a resource based on its Time Stamp. For example:

• If transaction T1 is requesting for resource R1 and is having a Time stamp older than that of the transaction T2 which is holding Resource R1 then transaction T1 will wait and would not be terminated.
T1 > T2     T1 will wait for resource.
• If transaction T1 who is requesting for resource R1 has a Time stamp younger than the Time stamp of Transaction T2 which is holding the resource R1 then the transaction T1 will be automatically terminated.
T1<T2     T1 will be terminated.

2. Wound – Wait scheme :
Under this scheme Time Stamp is of uttermost importance as it was in Wait and Die scheme. Here also transaction with younger time Stamp will be terminated. Lets understand by an example.

• If transaction T1 request for resource R1which is been hold by transaction T2  and if its Time Stamp is older than that of T2 then immediately transaction T2 will be halted and resource will be allocated to T1 while Transaction T2 will restart later with random delay but same time stamp.

T1 > T2        T1 will get resource immediately.

• If transaction T1 request for resource R1 been held by transaction T2 but T1 time Stamp is younger than T2 then it would be aborted.

T1  <  T2     T1 will be terminated.
The only difference between both the schemes is that in Wait and Die scheme – transaction with older Time Stamp will wait for resource to set free. Where as in the Wound-Wait scheme – transaction with older Time Stamp will get the resource immediately from the transaction with younger time Stamp.

Recovery in DBMS from Deadlock:

By recovery we mean to get back the system to its normal operation state. If failure happens it is the basic requirement that the process where the failure happened need to be recover to its correct state. Below I have mentioned some of the points to be considered for process recovery.
• Get back the resource allocated to the process.
• Undo the change made to database.
• Recommence the process
• Recommence the process from the point of failure and restart the execution.

Why need for recovery:
• System failure: System requirement not meet
• Error: problem in system state in comparison to original state.
• Fault: unusual physical condition example: external disturbances, manufacturing problem.
• Invalid system state – state which cause system failure by sequence of transactions.

Different techniques for recovery:

Extra components and algorithms can be added to the system so that these components and algo’s will work on errors and invalid system states or system failure , to restore it to stable state for regular processing of system to continue. These extra components and algorithms are called the recovery techniques.
Some of the techniques are:
• Backward and forward error recovery
• Log based recovery
• Write ahead logging protocol
Some of the advanced recovery techniques are:
• ARIES
• Shadow paging
• RAID levels.