A deadlock happens in operating system when two or more processes need some resource to complete their execution that is held by the other process.

Coffman Conditions

A deadlock occurs if the four Coffman conditions hold true. But these conditions are not mutually exclusive.

The Coffman conditions are given as follows −

• Mutual ExclusionThere should be a resource that can only be held by one process at a time. In the diagram below, there is a single instance of Resource 1 and it is held by Process 1 only.

• Hold and WaitA process can hold multiple resources and still request more resources from other processes which are holding them. In the diagram given below, Process 2 holds Resource 2 and Resource 3 and is requesting the Resource 1 which is held by Process 1.
• No PreemptionA resource cannot be preempted from a process by force. A process can only release a resource voluntarily. In the diagram below, Process 2 cannot preempt Resource 1 from Process 1. It will only be released when Process 1 relinquishes it voluntarily after its execution is complete.

• Circular WaitA process is waiting for the resource held by the second process, which is waiting for the resource held by the third process and so on, till the last process is waiting for a resource held by the first process. This forms a circular chain. For example: Process 1 is allocated Resource2 and it is requesting Resource 1. Similarly, Process 2 is allocated Resource 1 and it is requesting Resource 2. This forms a circular wait loop.

Methods for Handling Deadlocks

• Generally speaking there are three ways of handling deadlocks:
  1. Deadlock prevention or avoidance – Do not allow the system to get into a deadlocked state.
  2. Deadlock detection and recovery – Abort a process or preempt some resources when deadlocks are detected.
  3. Ignore the problem all together – If deadlocks only occur once a year or so, it may be better to simply let them happen and reboot as necessary than to incur the constant overhead and system performance penalties associated with deadlock prevention or detection. This is the approach that both Windows and UNIX take.

Deadlock Detection

A deadlock can be detected by a resource scheduler as it keeps track of all the resources that are allocated to different processes. After a deadlock is detected, it can be resolved using the following methods:

• All the processes that are involved in the deadlock are terminated. This is not a good approach as all the progress made by the processes is destroyed.
• Resources can be preempted from some processes and given to others till the deadlock is resolved.

Deadlock Prevention

Deadlock prevention algorithms ensure that at least one of the necessary conditions (Mutual exclusion, hold and wait, no preemption, and circular wait) does not hold true. We do this by facing each of the four conditions on separate occasions. However, most prevention algorithms have poor resource utilization and hence result in reduced throughputs.

Facing the Mutual Exclusion condition

If no resource were ever assigned exclusively to a single process, then we would never have deadlocks. What this means is that all resources should be shared between all processes, and that will never lead to a deadlock. However, if two processes start printing on a shared printer together, then the output would be unreadable. In this model, the only process that actually requests the printer resource is the printer daemon. A daemon is a background process that handles all requests and provides services.

The daemon is strictly programmed to start printing when the complete output file is ready and not when it is being edited.

So how do we face the mutual exclusion condition? We avoid assigning a resource when that is not necessary. And we also try to make sure that as few processes as possible might claim the resource.

Facing the Hold and Wait condition

This condition is slightly more promising. Here, if the process is allocated all the resources it would require beforehand, then it won’t need to ask for more resources, and there would be no deadlock. If, for some reason, the resource can’t be allocated to the process due to unavailability, then the process just waits until it gets the resource, and then it is processed.

A slightly different variant to break the hold and wait condition is to make the process drop all of the resources it is currently holding, whenever requesting for a new resource. Then it can grab hold of all the required resources again. This is also not an optimal use of processing power.

Facing the No Preemption condition

Facing this condition is also a possibility to avoid deadlocks. Take, for example, the printer as the resource. If a process has been assigned the printer and is in the middle of printing its output, forcibly taking away the printer because a needed plotter isn’t readily available is tricky at best and impossible at worst. However, some resources can be virtualized to avoid this situation. Spooling printer output to the disk and allowing only the printer daemon access to the real printer eliminates deadlocks regarding the printer, but creating one for disk space.

Facing the Circular Wait condition

To avoid the circular wait, resources may be ordered, and we can ensure that each process can request resources only in increasing order of these numbers. The algorithm may itself increase complexity and may also lead to poor resource utilization.

Deadlock Avoidance

To avoid deadlocks, we can make use of prior knowledge about the usage of resources by processes, including resources available, resources allocated, future requests, and future releases by processes. Most deadlock avoidance algorithms need every process to tell in advance the maximum number of resources of each type that it may need. Based on all information, we may decide if a process should wait for a resource or not, and thus avoid chances for the circular wait.

If a system is already in a safe state, we can try to stay away from an unsafe state and avoid deadlock. Deadlocks cannot be avoided in an unsafe state. A system can be considered to be in a safe state if it is not in a state of deadlock and can allocate resources to the maximum available. A safe sequence of processes and allocation of resources ensures a safe state. Deadlock avoidance algorithms try not to allocate resources to a process if it makes the system go into an unsafe state.

Banker’s Algorithm to avoid Resource Deadlocks

Banker’s algorithm was written by Dijkstra. It is a scheduling algorithm and is an extension of the deadlock detection algorithm.

How does the banker’s algorithm work?

• Consider a banker going around town giving loans to customers.
• If granting a loan to a customer leads to an unsafe state, it is denied.
• If granting a loan to a customer leads to a safe state, it is carried out.

In this analogy, the loan is the number of resources, the customers are processes, and the banker is the operating system.

Now imagine a scenario where the banker has ten units of a loan (10 resources). There are four customers (processes), and they have all specified their maximum required units of the loan (resources).

Take a look at this initial table.

Before the Operating System has granted any resource. The maximum number of combined resources is 22, but the banker has only 10 to loan out. Luckily for us, these processes don’t need all the resources at once. So we can allocate some resources to them unless they get pushed to an unsafe state.

Now take a look at this table, here we have allocated some resources already. 8 resources, to be precise.

The banker still has two resources to give out. How is this still a safe state? Suppose process A has asked for the remaining five resources. But the banker has only two remaining. So process A gets delayed, and the banker waits for process C to finish running, keeping the two unallocated resources with itself. This is because the banker does not know whether process C is going to ask for more or free up the resources. And it has to be ready when and if process C asks for two resources to complete running.

Once process C is finished, the banker has four resources with it now, and it can use these resources to complete other processes.

Let’s take another look at an unsafe state when the banker takes some risk.