Operating System-Introduction to Deadlock and prevention

Every process needs some resources to complete its execution. However, the resource is granted in a sequential order.

  1. The process requests for some resource.
  2. OS grant the resource if it is available otherwise let the process waits.
  3. The process uses it and release on the completion.

A Deadlock is a situation where each of the computer process waits for a resource which is being assigned to some another process. In this situation, none of the process gets executed since the resource it needs, is held by some other process which is also waiting for some other resource to be released.

Let us assume that there are three processes P1, P2 and P3. There are three different resources R1, R2 and R3. R1 is assigned to P1, R2 is assigned to P2 and R3 is assigned to P3.

After some time, P1 demands for R1 which is being used by P2. P1 halts its execution since it can’t complete without R2. P2 also demands for R3 which is being used by P3. P2 also stops its execution because it can’t continue without R3. P3 also demands for R1 which is being used by P1 therefore P3 also stops its execution.

In this scenario, a cycle is being formed among the three processes. None of the process is progressing and they are all waiting. The computer becomes unresponsive since all the processes got blocked.

os Deadlock

Difference between Starvation and Deadlock

Sr. Deadlock Starvation
1 Deadlock is a situation where no process got blocked and no process proceeds Starvation is a situation where the low priority process got blocked and the high priority processes proceed.
2 Deadlock is an infinite waiting. Starvation is a long waiting but not infinite.
3 Every Deadlock is always a starvation. Every starvation need not be deadlock.
4 The requested resource is blocked by the other process. The requested resource is continuously be used by the higher priority processes.
5 Deadlock happens when Mutual exclusion, hold and wait, No preemption and circular wait occurs simultaneously. It occurs due to the uncontrolled priority and resource management.

Necessary conditions for Deadlocks

Mutual Exclusion

A resource can only be shared in mutually exclusive manner. It implies, if two process cannot use the same resource at the same time.

Hold and Wait

A process waits for some resources while holding another resource at the same time.

No preemption

The process which once scheduled will be executed till the completion. No other process can be scheduled by the scheduler meanwhile.

Circular Wait

All the processes must be waiting for the resources in a cyclic manner so that the last process is waiting for the resource which is being held by the first process.

Deadlock Prevention

If we simulate deadlock with a table which is standing on its four legs then we can also simulate four legs with the four conditions which when occurs simultaneously, cause the deadlock.

However, if we break one of the legs of the table then the table will fall definitely. The same happens with deadlock, if we can be able to violate one of the four necessary conditions and don’t let them occur together then we can prevent the deadlock.

Let’s see how we can prevent each of the conditions.

1. Mutual Exclusion

Mutual section from the resource point of view is the fact that a resource can never be used by more than one process simultaneously which is fair enough but that is the main reason behind the deadlock. If a resource could have been used by more than one process at the same time then the process would have never been waiting for any resource.

However, if we can be able to violate resources behaving in the mutually exclusive manner then the deadlock can be prevented.

Spooling

For a device like printer, spooling can work. There is a memory associated with the printer which stores jobs from each of the process into it. Later, Printer collects all the jobs and print each one of them according to FCFS. By using this mechanism, the process doesn’t have to wait for the printer and it can continue whatever it was doing. Later, it collects the output when it is produced.

2. Hold and Wait

Hold and wait condition lies when a process holds a resource and waiting for some other resource to complete its task. Deadlock occurs because there can be more than one process which are holding one resource and waiting for other in the cyclic order.

However, we have to find out some mechanism by which a process either doesn’t hold any resource or doesn’t wait. That means, a process must be assigned all the necessary resources before the execution starts. A process must not wait for any resource once the execution has been started.

3. No Preemption

Deadlock arises due to the fact that a process can’t be stopped once it starts. However, if we take the resource away from the process which is causing deadlock then we can prevent deadlock.

This is not a good approach at all since if we take a resource away which is being used by the process then all the work which it has done till now can become inconsistent.

4. Circular Wait

To violate circular wait, we can assign a priority number to each of the resource. A process can’t request for a lesser priority resource. This ensures that not a single process can request a resource which is being utilized by some other process and no cycle will be formed.