Deadlock Prevention in Operating System (OS)

Introduction to Deadlock

Consider a one-way road with two cars approaching from opposite directions, blocking each other. The road is the resource, and crossing it represents a process. Since it's a one-way road, both cars can't move simultaneously, leading to a deadlock.

A deadlock in an operating system is an indefinite blocking of processes competing for resources. It occurs when two or more processes require resources that can't be shared simultaneously.

There are four necessary conditions for deadlock. Deadlock happens only when all four conditions occur simultaneously for unshareable single instance resources.

Deadlock Characteristics/Conditions

1. Mutual exclusion
2. Hold and wait
3. No preemption
4. Circular wait.

There are three ways to handle deadlock:

1. Deadlock prevention: The possibility of deadlock is excluded before making requests, by eliminating one of the necessary conditions for deadlock.

   Example: Only allowing traffic from one direction, will exclude the possibility of blocking the road.

2. Deadlock avoidance: The Operating system runs an algorithm on requests to check for a safe state. Any request that may result in a deadlock is not granted.

   Example: Checking each car and not allowing any car that can block the road. If there is already traffic on the road, then a car coming from the opposite direction can cause blockage.

3. Deadlock detection & recovery: OS detects deadlock by regularly checking the system state, and recovers to a safe state using recovery techniques. Example: Unblocking the road by backing cars from one side. Deadlock prevention and deadlock avoidance are carried out before deadlock occurs.

In this article, we will learn about deadlock prevention in OS.

Deadlock prevention is a set of methods used to ensure that all requests are safe, by eliminating at least one of the four necessary conditions for deadlock.

Deadlock Prevention in Operating System

A process is a set of instructions. When a process runs, it needs resources like CPU cycles, Files, or Peripheral device access.

Some of the requests for resources can lead to deadlock.

Deadlock prevention is eliminating one of the necessary conditions of deadlock so that only safe requests are made to OS and the possibility of deadlock is excluded before making requests.

As now requests are made carefully, the operating system can grant all requests safely.

Here OS does not need to do any additional tasks as it does in deadlock avoidance by running an algorithm on requests checking for the possibility of deadlock.

Deadlock Prevention Techniques

Deadlock prevention techniques refer to violating any one of the four necessary conditions. We will see one by one how we can violate each of them to make safe requests and which is the best approach to prevent deadlock.

Mutual Exclusion

Some resources are inherently unshareable, for example, Printers. For unshareable resources, processes require exclusive control of the resources.

A mutual exclusion means that unshareable resources cannot be accessed simultaneously by processes.

Shared resources do not cause deadlock but some resources can't be shared among processes, leading to a deadlock.

For Example: read operation on a file can be done simultaneously by multiple processes, but write operation cannot. Write operation requires sequential access, so, some processes have to wait while another process is doing a write operation.

It is not possible to eliminate mutual exclusion, as some resources are inherently non-shareable,

For Example Tape drive, as only one process can access data from a Tape drive at a time.

For other resources like printers, we can use a technique called Spooling.

Spooling: It stands for Simultaneous Peripheral Operations online.

A Printer has associated memory which can be used as a spooler directory (memory that is used to store files that are to be printed next).

In spooling, when multiple processes request the printer, their jobs ( instructions of the processes that require printer access) are added to the queue in the spooler directory.

The printer is allocated to jobs on a first come first serve (FCFS) basis. In this way, the process does not have to wait for the printer and it continues its work after adding its job to the queue.

We can understand the workings of the Spooler directory better with the diagram given below:

Hold and Wait

Hold and wait is a condition in which a process is holding one resource while simultaneously waiting for another resource that is being held by another process. The process cannot continue till it gets all the required resources.

In the diagram given below:

• Resource 1 is allocated to Process 2
• Resource 2 is allocated to Process 1
• Resource 3 is allocated to Process 1
• Process 1 is waiting for Resource 1 and holding Resource 2 and Resource 3
• Process 2 is waiting for Resource 2 and holding Resource 1

There are two ways to eliminate hold and wait:-

1. By eliminating wait:

   The process specifies the resources it requires in advance so that it does not have to wait for allocation after execution starts.

   For Example: Process1 declares in advance that it requires both Resource1 and Resource2

2. By eliminating hold:

   The process has to release all resources it is currently holding before making a new request.

   For Example: Process1 has to release Resource2 and Resource3 before making request for Resource1

No preemption

Preemption is temporarily interrupting an executing task and later resuming it.

For example, if process P1 is using a resource and a high-priority process P2 requests for the resource, process P1 is stopped and the resources are allocated to P2.

There are two ways to eliminate this condition by preemption:

1. If a process is holding some resources and waiting for other resources, then it should release all previously held resources and put a new request for the required resources again. The process can resume once it has all the required resources.

   For example: If a process has resources R1, R2, and R3 and it is waiting for resource R4, then it has to release R1, R2, and R3 and put a new request of all resources again.

2. If a process P1 is waiting for some resource, and there is another process P2 that is holding that resource and is blocked waiting for some other resource. Then the resource is taken from P2 and allocated to P1. This way process P2 is preempted and it requests again for its required resources to resume the task. The above approaches are possible for resources whose states are easily restored and saved, such as memory and registers.

Circular Wait

In circular wait, two or more processes wait for resources in a circular order. We can understand this better by the diagram given below:

To eliminate circular wait, we assign a priority to each resource. A process can only request resources in increasing order of priority.

In the example above, process P3 is requesting resource R1, which has a number lower than resource R3 which is already allocated to process P3. So this request is invalid and cannot be made, as R1 is already allocated to process P1.

Feasibility of Deadlock Prevention

• Mutual exclusion cannot be eliminated completely because some resources are inherently non-shareable
• Hold and wait cannot be eliminated as we cannot know in advance about the required resources to prevent waiting. It is inefficient to prevent a hold by releasing all the resources while requesting a new one
• Preempting processes can cause inconsistency and starting the process over by putting requests for all resources again is inefficient.
• Eliminating circular wait is the only practical way to prevent deadlock.

Elevate your understanding of operating systems with our Free Operating System course. Enroll today and learn from experts!