Deadlock in OS: Conditions and Preventions

What is Deadlock in OS? Deadlock Detection and Prevention, Resource Allocation Graph, Mutual Exclusion, Hold and Wait, No Pre-emption, Circular Wait.

Deadlock in operating system

Today we will discuss Deadlock in OS. Deadlock is the most important topic in the operating system. There are many reasons for deadlock and various techniques of deadlock prevention in the operating system.

What is Deadlock in OS?

If P1 and P2 are two processes, R1 and R2 are two resources. P1 requests the resource R1, R1 is held by process P2, P2 requests the resource R2, R2 is held by process P1, and both P1 and P2 are in the waiting state. There is no work progress for processes P1 and P2. It is a deadlock too. Resource Allocation Graph (RAG) can represent deadlock.

Resource allocation graph in OS

Resource Allocation Graph

A resource allocation graph is a directed graph; it is used to represent the deadlocks. There are two types of nodes in the graph. One for the process, it is represented by a circle, and the second, for the resource, is represented by a square. There are two types of edges in the graph. One is the requesting edge (Pi to Rj), and another is the assignment edge (Rj to Pi).

Conditions for Deadlock

  • Condition 1: If the resource allocation graph contains no cycle, then there is no deadlock.
  • Condition 2: If the resource allocation graph contains cycles, then the system may or may or may not be in deadlock. But, if the system is in a deadlock state, the resource allocation graph must consist of cycles.
Deadlock free

A deadlocked system must satisfy the following four conditions

  1. Mutual Exclusion
  2. Hold and Wait
  3. No Pre-emption
  4. Circular Wait

Mutual Exclusion

Mutual exclusion means resources are (at least one) in non-sharable mode only. It means only one process at a time can use a resource. For example, If process P1 requests the resource R1 then process P2 must wait til resource R1 has been released by process P1.

For example, line printers, the line printers are always in non-sharable mode only, only one process can use the resource at a time.

Hold and Wait

Each process in the deadlock state must hold at least one resource and wait for additional resources that are currently being held by another process.

No Pre-emption

No pre-emption means resources are not released in the middle of the work, they release only after the process has completed its task.

Circular Wait

Circular wait deadlock in OS

In the above figure,  P1 is waiting for the resource R1, R1 is held by process P2, P2 is waiting for the resource R2, R2 is held by process P3, P3 is waiting for the resource R4, R4 is held by process P2, P2 is waiting for resource R3, R3 is held by P1, it is said to be a circular wait.

Circular wait

Deadlock Prevention

Deadlock prevention refers to the methods used to prevent deadlocks before they occur. For a deadlock to occur, all four necessary conditions must hold.

By ensuring that at least one of these conditions cannot hold, we can prevent the occurrence of deadlocks. Therefore, we can apply prevention techniques to each of the four necessary conditions separately.

Mutual Exclusion

Mutual exclusion means only one process can access the resource at a time. In other words, the number of processes does not share the resources at the same time. Hence, resources are non-sharable mode only.

We can deny this condition with a simple protocol, i.e., Connect all non-sharable resources to sharable resources. Therefore, this condition is not satisfied by the deadlock.

There is a small correction; the number of processes does not share a printer at a time. Therefore, we cannot connect the printer from non-sharable to sharable mode. Hence, we cannot apply this prevention method if the system consists of printers.

Hold and Wait

Hold and wait means, each process in the deadlock state must hold and wait for at least one resource. We can deny this condition with a small protocol, i.e., A process requests the resources only, when the process has none. This protocol is very expensive and time-consuming.

For example, a person wants to copy from a tape drive to a disk file and then take a printout. Initially, the process consisted of the tape drive and disk file, now the process to request the printer to apply the above-said protocol, the process should release the tape and disk file before the request of the printer. Therefore, it is time-consuming. The second protocol is that each process requests and is allocated all its resources before it begins execution.

There are two main disadvantages- first, resource utilization is very poor. Second, starvation is possible. A process that needs several resources may have to wait indefinitely because at least one of the resources it needs is always allocated to some other process.

No Pre-emption

The third necessary condition “No Pre-emption” means resources are not released in the middle of the processing. To ensure that this condition does not hold we use the following protocol.

When a process requests some resources, we first check whether they are available. If they are available, we allocate them.

If not, we check whether they are allocated to some other process that is waiting for additional resources. If so, we pre-empt the resources from the waiting process and allocate them to the requesting process.