Deadlock

A Deadlock is a situation where a set of processes are blocked because each process is holding a resource and waiting for another resource acquired by some other process. 
Consider an example when two trains are coming toward each other on the same track and there is only one track, none of the trains can move once they are in front of each other. A similar situation occurs in operating systems when there are two or more processes that hold some resources and wait for resources held by other(s). For example, in the below diagram, Process 1 is holding Resource 1 and waiting for resource 2 which is acquired by process 2, and process 2 is waiting for resource 1. 

Deadlock Examples:

• P_i requests one I/O controller and the system allocates one.
• P_j requests one I/O controller and again the system allocates one.
• P_i wants another I/O controller but has to wait since the system ran out of I/O controllers.
• P_j wants another I/O controller and waits.

• Traffic is only in one direction.
• Each section of a bridge can be viewed as a resource.
• If a deadlock occurs, it can be resolved if one car backs up (preempt resources and rollback).
• Several cars may have to be backed up if a deadlock occurs.
• Starvation is possible.

Conditions for deadlocks

1. Mutual exclusion: No resource can be shared by more than one process at a time.
2. Hold and wait: There must exist a process that is holding at least one resource and is waiting to acquire additional resources that are currently being held by other processes.
3. No preemption: A resource cannot be preempted. Circular wait. There is a cycle in the wait-for graph.
4. Circular Wait: Process A waits for Process B waits for Process C …. waits for Process A

Deadlock Prevention

1. Mutual exclusion:

a) Automatically holds for printers and other non-sharable.
b) Shared entities (read-only files) don’t need mutual exclusion (and aren’t susceptible to deadlock.)
c) Prevention is not possible, since some devices are intrinsically non-sharable.

2. Hold and wait:

a) Collect all resources before execution.
b) A particular resource can only be requested when no others are being held. A sequence of resources is always collected beginning with the same one.
c) Utilization is low, and starvation is possible.

3. No preemption:

a) Release any resource already being held if the process can’t get an additional resource.
b) Allow preemption – if a needed resource is held by another process, which is also waiting on some resource, steal it. Otherwise, wait.

4. Circular wait:

a) Number resources and only requests in ascending order.
b) EACH of these prevention techniques may cause a decrease in utilization and/or resources. For this reason, prevention isn’t necessarily the best technique.
c) Prevention is generally the easiest to implement.

Deadlock Avoidance

If we have prior knowledge of how resources will be requested, it’s possible to determine if we are entering an “unsafe” state. Possible states are:

• Deadlock No forward progress can be made.
• Unsafe state A state that may allow deadlock.
• Safe state A state is safe if a sequence of processes exists such that there are enough resources for the first to finish, and as each finishes and releases its resources there are enough for the next to finish.

NOTE: All deadlocks are unsafe, but all unsafes are NOT deadlocks.

Deadlock Detection Algorithm

If a system does not employ either a deadlock prevention or deadlock avoidance algorithm then a deadlock situation may occur. In this case- 

• Apply an algorithm to examine the state of the system to determine whether deadlock has occurred or not.
• Apply an algorithm to recover from the deadlock.

Deadlock Avoidance Algorithm/ Bankers Algorithm: 

• Available – 
  A vector of length m indicates the number of available resources of each type.
• Allocation – 
  An n*m matrix defines the number of resources of each type currently allocated to a process. The column represents resources and the rows represent a process.
• Request – 
  An n*m matrix indicates the current request of each process. If request[i][j] equals k then process P_i is requesting k more instances of resource type R_j.

Now, the Bankers algorithm includes a Safety Algorithm / Deadlock Detection Algorithm 
The algorithm for finding out whether a system is in a safe state can be described as follows:

Steps of Algorithm: 

1. Let Work and Finish be vectors of length m and n respectively. Initialize Work= Available. For i=0, 1, …., n-1, if Request_i = 0, then Finish[i] = true; otherwise, Finish[i]= false.
2. Find an index i such that both 
   a) Finish[i] == false 
   b) Request_i <= Work 
   If no such i exists go to step 4.
3. Work= Work+ Allocation_i 
   Finish[i]= true 
   Go to Step 2.
4. If Finish[i]== false for some i, 0<=i<n, then the system is in a deadlocked state. Moreover, if Finish[i]==false the process P_i is deadlocked.

Deadlock Recovery :

A traditional operating system such as Windows doesn’t deal with deadlock recovery as it is a time and space-consuming process. Real-time operating systems use Deadlock recovery. 

1. Killing the process –
   Killing all the processes involved in the deadlock. Killing process one by one. After killing each process check for deadlock again and keep repeating the process till the system recovers from deadlock. Killing all the processes one by one helps a system to break circular wait conditions.
2. Resource Preemption –
   Resources are preempted from the processes involved in the deadlock, preempted resources are allocated to other processes so that there is a possibility of recovering the system from the deadlock. In this case, the system goes into starvation.