Deadlocks in OS

Deadlocks are a set of blocked processes each holding a resource and waiting to acquire a resource held by another process.

In the above figure, process T0 has resource1, it requires resource2 in order to finish its execution. Similarly, process T1 has resource2 and it also needs to acquire resource1 to finish its execution. In this way, T0 and T1 are in a deadlock because each of them needs the resource of others to complete their execution but neither of them is willing to give up their resources.

In General, a process must request a resource before using it and it must release the resource after using it. And any process can request as many resources as it requires in order to complete its designated task. And there is a condition that the number of resources requested may not exceed the total number of resources available in the system.

Basically in the Normal mode of Operation utilization of resources by a process is in the following sequence:

1. Request:
   Firstly, the process requests the resource. In a case, if the request cannot be granted immediately(e.g: resource is being used by any other process), then the requesting process must wait until it can acquire the resource.

2. Use:
   The Process can operate on the resource ( e.g: if the resource is a printer then in that case process can print on the printer).

3. Release:
   The Process releases the resource.

Let us take a look at the differences between starvation and deadlock.

Starvation vs Deadlock

Let's understand the difference between starvation and deadlock.

The occurrence of deadlock can be detected by the resource scheduler.

Now in the next section, we will cover the conditions that are required to cause deadlock.

Conditions causing Deadlock

The deadlock situation can only arise if all the following four conditions hold simultaneously:

1. Mutual Exclusion

According to this condition, atleast one resource should be non-shareable (non-shareable resources are those that can be used by one process at a time.)

2. Hold and wait

According to this condition, A process is holding atleast one resource and is waiting for additional resources.

3. NO preemption

Resources cannot be taken from the process because resources can be released only voluntarily by the process holding them.

4. Circular wait

In this condition, the set of processes are waiting for each other in the circular form.

The above four conditions are not completely independent as the circular wait condition implies the hold and wait condition. We emphasize on the fact that all four conditions must hold for a deadlock.

Deadlock conditions can be avoided with the help of a number of methods. Let us take a look at some of the methods.

Methods For Handling Deadlocks

Methods that are used in order to handle the problem of deadlocks are as follows:

1. Ignoring the Deadlock

According to this method, it is assumed that deadlock would never occur.This approach is used by many operating systems where they assume that deadlock will never occur which means operating systems simply ignores the deadlock. This approach can be beneficial for those systems that are only used for browsing and for normal tasks. Thus ignoring the deadlock method can be useful in many cases but it is not perfect in order to remove the deadlock from the operating system.

2. Deadlock Prevention

As we have discussed in the above section, that all four conditions: Mutual Exclusion, Hold and Wait, No preemption, and circular wait if held by a system then causes deadlock to occur. The main aim of the deadlock prevention method is to violate any one condition among the four; because if any of one condition is violated then the problem of deadlock will never occur. As the idea behind this method is simple but the difficulty can occur during the physical implementation of this method in the system.

3. Avoiding the Deadlock

This method is used by the operating system in order to check whether the system is in a safe state or in an unsafe state. This method checks every step performed by the operating system. Any process continues its execution until the system is in a safe state. Once the system enters into an unsafe state, the operating system has to take a step back.

Basically, with the help of this method, the operating system keeps an eye on each allocation, and make sure that allocation does not cause any deadlock in the system.

4. Deadlock detection and recovery

With this method, the deadlock is detected first by using some algorithms of the resource-allocation graph. This graph is mainly used to represent the allocations of various resources to different processes. After the detection of deadlock, a number of methods can be used in order to recover from that deadlock.

One way is preemption by the help of which a resource held by one process is provided to another process.

The second way is to roll back, as the operating system keeps a record of the process state and it can easily make a process roll back to its previous state due to which deadlock situation can be easily eliminate.

The third way to overcome the deadlock situation is by killing one or more processes.

In our upcoming tutorial, we will cover each method in detail one by one.