Deadlock Avoidance in Operating System

Deadlock avoidance in operating system, is a general approach to deal with deadlock. In deadlock avoidance, the operating system analyzes each process’s resource request and determines whether granting the request would lead to deadlock or not. The system only grants the requested resource to the process only if the deadlock is impossible.

In this section, we will discuss deadlock avoidance in detail. We will also discuss the banker’s algorithm with an example. So let’s start with the content.

Content: Deadlock Avoidance in Operating System

1. What is Deadlock Avoidance?
2. Safe and Unsafe State of System
3. Bankers Algorithm with Example
4. Advantages and Disadvantages

What is Deadlock Avoidance in Operating System?

Deadlock avoidance is a technique used to avoid deadlock and ensure that it never occurs. The technique requires prior information about what resources a process will request and use during its lifecycle. With this information, the operating system is able to make decisions for each request:

• Whether the process should wait or not.
• Whether the request can be granted or delayed.

With the additional or prior knowledge, the system can decide whether to entertain a new request or not to be in a safe state.

Deadlock avoidance is not conservative as deadlock prevention. The deadlock prevention method is much more conservative. As it implies different types of restrictions or conditions on the processes and resources. Because of this, the system becomes slow, and resource utilization and system throughput get reduced.

On the other hand, the deadlock avoidance method does not constrain the resource request; instead, it finds at least one safe path to ensure that the system is safe and deadlock never occurs.

Before proceeding further, let us clearly understand the concept of state and safe state.

Safe and Unsafe State

The state of a system expresses the current allocation of available resources to the processes. We can represent the state of a system with the help of two vectors, Resource and Available and the two matrices, Claim and Allocation.

The vector, Resource, defines the total amount of each resource available with the system. For example, the vector ‘R’ above shows that the system has three resources, R1, R2, and R3, where resource R1 has 9 instances, R2 has 3 instances, and R3 has 6 instances.

The vector Available defines the total amount of each resource still available with the system, and that is not allocated to any process. For example, the vector ‘V’ above shows that currently, the resources R1, R2, R3 are left with 0, 1, and 1 instances, respectively.

Claim matrix C defines the requirement of each process towards each of the resources. For example, the Claim matrix ‘C’ above shows that process P1 claims or requires maximum 3 instances of resource R1, 2 instances of resource R2 and 2 instances of resource R3.

Similarly, allocation matrix A defines the current allocation of resources to the processes. For example, the allocation matrix ‘A’ above shows that the system has allocated 1 instance of resource R1, 0 instances of resource R2 and 0 instances of resource R3 to process P1.

Knowing about the state of the system lets us discuss what the safe state and the unsafe state are.

Safe State

A safe state is where there is at least one sequence in which, if the resources are allocated to the processes, it won’t end up in a deadlock. With the safe sequence, all the processes can be executed successfully.

Unsafe State

An unsafe state is where the system will end up with a deadlock.

An algorithm identifies the state of the system to determine whether the deadlock can occur. Also, it provides recovery if deadlock indeed occurs. We refer to this algorithm as Banker’s Algorithm or deadlock avoidance algorithm.

Bankers Algorithm With Example

The deadlock avoidance technique requires the operating system to know what resources the processes would claim during their lifecycle. So, it could decide whether allocating a resource to the current request is safe or not, and it only allocates resources if it is safe and there is no chance of deadlock. For this, it uses a banker’s algorithm.

Let us consider that the system has prior knowledge of the following:

• The system has three resources R1, R2 and R3. R1 has 9 units, R2 has 3, and R3 has 6 units (resource vector).
• After the current allocation (allocation matrix A), the system is left with only 1 unit of resource R2 and 1 unit of resource R3 (Available vector V).

Now with the current request (claim matrix C), the algorithm has to identify whether granting the request would leave the system in a safe state or not.

Is this a Safe State?

To identify whether the system would be in a safe state or not? It has to determine that with the available resources (Available vector V) can, any of the four processes can complete its execution. It means whether the difference between the maximum requirement (claim matrix) and current allocation (allocation matrix A) for any process be met with the available resources V with the system.

In terms of matrices and vectors, the condition that must satisfy for process i, to complete its execution with the available resources is:

Cij – Aij ≤ Vj, for all j

So, let’s check it for process 1. The claim matrix shows that process P1 requires 2, 2, and 2 units of resource R1, R2, and R3, respectively. The system could not fulfil this request as it has only 0, 1, and 1 unit of resource R1, R2 and R3, respectively.

Further, we check the condition for process P2. It requires 0, 1, and 1 units of resource R1, R2 and R3, respectively. This time the system could satisfy the request, and P2 can execute.

After P2 completes execution, it returns all the resources to the resource pool, thereby modifying all the matrices and the available vector.

Now, again the system analyzes if it can satisfy the need of any of the remaining processes. In this case, the system could satisfy the request of all the remaining processes. So below is the state after process P1 completes execution and releases resources back to the resource pool.

Below is the system state after process P3 executes.

Finally, the system state after process P4 executes.

Thus, the banker’s algorithm ensures that the system is always in a safe state. So, in the bankers’ algorithm, whenever a process requests a set of resources, the system grants those resources and updates the system state. Now, the system analyses whether it is in a safe state or not. If yes, it further grants the resource request of another process. If not, it blocks the process until the system states are safe to grant the request.

Advantages of Deadlock Avoidance

• The deadlock avoidance technique is not as conservative as deadlock prevention.
• No need to preempt or roll back the processes.

Disadvantages of Deadlock Avoidance

• The system must have prior knowledge about the maximum resource requirement of each process in the system.
• The processes requesting the resources must be independent of each other. Such that the order of their execution must be unconstrained of any synchronization requirement.
• The number of resources in the system must be fixed.
• No process must exit the system while holding the resources.
• Processes can get locked for a long duration.

So, this is all about deadlock avoidance in the operating system. The technique analyzes the resource request of the process and identifies a safe path so that the system does not get into a deadlock.

We have also learned how the banker’s algorithm help in determining a safe sequence in which if processes are allocated resources, the system will not get into a deadlock.