In this post, we will see what is deadlock in os? necessary condition for deadlock to occur, different ways to detect deadlock in os, different ways to prevent deadlock in os etc.

Deadlock is defined as a situation where set of processes are blocked because each process holding a resource and waiting to acquire a resource held by another process.

Example: when two trains approach each other at a crossing, both shall come to a full stop and neither shall start up again until the other has gone.

In simple words, we can say that if two or more processes are waiting for some events to happen, which never happens, then, that is called deadlock and those processes are in deadlock state.

Tutorialwing Deadlock Example

Here, P1 and P2 are two processes. R1 and R2 are two resources.

Note: R –> P means process (P) has taken the resource (R). For example, R2 –> P2 means resource R2 has been allocated to process P2.

P –> R means process (P) is requesting for resource (R). For example, P1 –> R2 means Process P1 is requesting for resource R2.

Explanation:
In this figure, there are two resources R1 and R2 and two processes P1 and P2.
Let us say R1 is allocated to P1 or P1 has taken R1. P1 is requesting for R2 but R2 is held by P2. Now, P2 is requesting for R1. So, we can say that it is kind of deadlock or it is a deadlock situation.

Note – There are 4 necessary conditions for deadlock.

Necessary Conditions for Deadlock

Till now, we have seen what is deadlock in os with an example. Now, we will see what is necessary conditions for deadlock to occur.

A deadlock situation can arise if the following 4 conditions hold simultaneously in a system –

1. Mutual Exclusion: A process should work in mutual exclusive way. It means a resource is non-sharable. At a time only one process can use the resource. If another process requests to use resource, the requesting process must be delayed until the resource has been released.
2. Hold and Wait: A process must be holding at least one resource and waiting to acquire additional resources that are currently being held by other processes.
3. No Preemption: Once a process is holding a resource, then that resource cannot be taken away from the process until the process voluntarily releases it.
4. Circular Wait: A set of processes (P1, P2…..Pn) of waiting processes must exist such that P1 is waiting for resource that is held by P2, P2 is waiting for resource that is held by P3…Pn is waiting for a resource that is held by P1.

Methods for Handling Deadlock

As we have seen what is deadlock in os, now we need to see different methods to handle deadlock whenever it occurs.
There are three ways of handling deadlocks:

1. Deadlock prevention or avoidance: Don’t allow the system to get into a deadlock state.
2. Deadlock Detection and recovery: Let deadlock occur, then do preemption to handle it.
3. Ignore the problem all together: if deadlock occur once in a year or so, it may be better to let it
   happen and reboot the system. This is the approach that windows and Unix take.

1. Deadlock Prevention:

We have gone through what is deadlock in os, necessary conditions for deadlock to occur. Now, we will see how to handle deadlock if occurred. At first, we will see how to handle deadlock by deadlock prevention technique.

Deadlock can be prevented by preventing at least one of the four required conditions. Either try to remove all four conditions or one of the four conditions. So, we can easily prevent deadlock from the system.

Let’s see how we can avoid either one or all conditions from the system –

No Mutual Exclusion: Make the resources are shareable. It will be helpful to eliminate mutual exclusion. Unfortunately, some resources can be never be shareable such as printers and tape drives. It needs exclusive access by a single process.

No Hold and wait: When process starts up the execution, allocate all the required resources. Then, hold and wait condition won’t be existing. But, practically it is less possible. For example, if a process requires a printer at a later time and we have allocated printer before the start of the its execution. So, it can be wasteful for system resources.

It must be mandatory for the processes holding resources to release them before requesting new resources. Then, re-acquire the released resources along with a new one. It can lead to starvation if process requires one or more resources.

No Preemption: If a process holding some resources and requests another resource that can’t be immediately allocated to it (that is, the process must wait), then, all resources currently being held are preempted.

Circular Wait: A total ordering of all resource types should be imposed. Each process requests any resource in an increasing order of enumeration.

Let R = {R1, R2……Rn} be the set of resource types. Assign to each resource type a unique integer number.
For example, R = {tape drives, printers, disk drives}, then the function F might be as follows:

F(tape drives) = 2
F(printers) = 5
F(disk drives) = 18

If the below protocols are used, then the circular wait condition cannot hold.

• Each process can request only in an increasing order of enumeration i.e. A process, holding
  resource type Ri, can request instance of resource type Rj if and only if F(Rj) > F(Ri).
• A process requests resource type Rj if it has released any resource Ri.

That’s end of tutorial on What is Deadlock in OS.