Heading

Deadlock is a condition in which a group of processes are waiting for the resources held by some other process, while holding a resource which is required by the other process. Under such condition, none of the processes can proceed further in execution. Hence, these processes are blocked.

Once the deadlock is detected, the system must be recovered from deadlock.
The following are the three methods of data recovery after deadlock:
1. Preemption:
By preemption, the resources held by a process are taken back to avoid deadlock. The resources taken are given to another process that is waiting for that resource. By doing so, the ‘Hold and Wait’ condition is eliminated and the system can recover from deadlock.
2. Kill the Process:
Another method of removing deadlock is by killing the processes one by one. After killing each process, the existence of deadlock is checked. If the deadlock still exists, this process is continued. The processes are killed until the system is free from deadlock.
3. Rollback
The different states of the process are recorded by the Operating System. When a deadlock occurs, the processes are rolled back to their previous states. If the system is free from the deadlock in any of the previous states of a process, then, the process is rolled back to that particular state. In this way, the system can be freed from deadlock.

Consider a bridge which can allow only one vehicle to pass across it at a time (The width of the bridge is narrow). When two vehicles try to cross the bridge from opposite directions, a deadlock occurs. Neither of the two vehicles can move further. Here, we consider the bridge as the resource and the vehicles as processes.

For a deadlock to occur in a system when all the following conditions hold:
1. Mutual exclusion
Mutual exclusion is a condition in which only one process can hold a resource at a time.
2. Hold and Wait
A process holds a resource until it gets another resource.
3. No pre-emption
A process does not give-up a resource before it has completed execution.
4. Circular wait
Circular wait condition occurs when a group of processes are waiting for the resources held by each other in a circular fashion.

Deadlock can be prevented by making one of the below four conditions False.
i. Mutual Exclusion
ii. Hold and Wait
iii. No pre-emption
iv. Circular Wait
a. Mutual Exclusion
The mutual exclusion condition can be violated if a resource is used by more than one process at a time. But, removing the mutual exclusion condition is impossible as it might lead to un-sharable resources.
b. Hold and Wait
Hold and wait condition can be prevented by preventing a process from holding a resource or by preventing the process from waiting for a resource. Such a condition can be achieved by the allocation of necessary resources before the execution of a process.
c. No pre-emption
Pre-emption can be achieved by stopping a process while execution and taking away the resource held by that process. But, this is not an advisable approach.
d. Circular Wait
Circular wait can be avoided by assigning a number to each resource and each process. A process should not be able to request a resource with a number less than itself. This ensures the prevention of the circular wait condition.

Deadlock avoidance is different from deadlock prevention. In deadlock avoidance, our aim is to avoid unsafe states. Deadlock avoidance methods allocate resources to the processes only if the system remains in the safe state. Safe state refers to the condition in which deadlock cannot occur. The most commonly used deadlock avoidance algorithm is the ‘Banker’s Algorithm’

Wait-for-graph method is used for deadlock detection. This method involves the transaction graph. A transaction graph is drawn by considering the transactions and their lock on the resource. If a cycle is detected in the graph, then deadlock is said to exist in the system. Else, there is no deadlock.
Example:In the above transaction graph, a cycle exists. Hence, the system is in deadlock.

The following are the disadvantages of deadlock avoidance algorithm:
a. The deadlock avoidance algorithms are not efficient because they cause unwanted delays while trying to avoid the unsafe states.
b. It is applicable to only limited number of resources and processes.
c. It does not completely prevent deadlock. So, deadlock might occur.

The Banker’s algorithm is a deadlock avoidance algorithm which checks for safe state. It simulates the resource allocation before actually allocating the resources to the processes. Hence, it detects the possible un-safe states and avoids deadlock.
Need matrix:
The need matrix shows the resources which are needed by the processes, but still are not allocated.
Safety Algorithm:
The safety algorithm is used to find whether the given system is safe or not.
Let Work and Finish be vectors of length ‘m’ and ‘n’ respectively.
Initialize: Work = Available
Finish[i] = false; for i=1, 2, 3, 4….n

2) Find an i such that both
a) Finish[i] = false
b) Need i<= Work
if no such i exists goto step (4)
3) Work = Work + Allocation[i]
Finish[i] = true
goto step (2)
4) if Finish [i] = true for all i then the system is in a safe state
Resource Request Algorithm
1) If Request i &lt;= Need,
iGoto step (2); otherwise, raise an error
2) If Request i &lt;= Available Goto step (3);
otherwise, P i must wait
3) Have the system pretend to have allocated the requested resources to process
P,by modifying the state as follows:
Available = Available – Request i
Allocation i = Allocation i + Request i
Need i = Need i – Request i

Need Matrix:
Need [i, j] = Max [i, j] – Allocation [i, j]
By applying the safety algorithm, we find that the system is safe