Deadlock Avoidance in OS

Deadlock Avoidance introduction:

In deadlock prevention, we restrict resource requests to prevent four conditions of deadlocks. Deadlock avoidance is another approach for solving deadlock problems in a computer network system. The term avoidance is a bit confusing. In fact, in this approach better strategies are applied to prevent the occurrence of a deadlock in a system. Deadlock avoidance allows for more concurrency than prevention. With deadlock avoidance, a decision is made dynamically whether the current resource allocation request (if granted) will potentially lead to a deadlock or not on a computer network system.

Deadlock Avoidance Technique:

In the Deadlock Avoidance technique, the operating system needs additional information about how resources are to be requested to avoid a deadlock. The operating system only accepts those requests of processes to allocate resources that will not lead to deadlock.

for this purpose, each request that in making this decision, the operating system should consider

1. the resources currently available.
2. the resources currently allocated to each process
3. the future requests and releases of each system process.

Example:

In a system with one CD-ROM drive and one printer, the operating system might need to know in advance that process P1 will first request the printer and then CD-ROM drive. Similarly, process P2 might first request CD-ROM and then the printer. With the help of this information, the operating system can decide for each request whether or not the process should wait to avoid a possible future deadlock.

Safe State:

A state of a system is said to a safe state if the computer network system can allocate resources to each process in some order by avoiding a deadlock in a system. In other words, we can say that a system is said to be in a safe state if there exists a safe execution sequence.

An execution is an order for process execution such that the process runs until it terminates or is blocked, and all requests for resources are immediately granted if they are available. A safe execution sequence is an execution sequence in which all processes run successfully without facing deadlock.

Unsafe State:

There is a possibility that a system goes from a safe state to an unsafe state. An unsafe state is not a deadlock state but may lead to a deadlock state. On the other hand, a deadlock state is surely an unsafe state. In a safe state. the operating system can avoid deadlock. In an unsafe state, the operating system cannot prevent processes from requesting resources, so the deadlock may occur.

The following important points about a safe state, an unsafe state, and deadlock:

1. If a system is in a safe state, it implies that there will be no deadlocks.
2. If a system is in an unsafe state then there is the possibility of deadlock. 
3. To avoid a deadlock, ensure that a system will never enter an unsafe state.

Resources-Allocation Graph Algorithm:

The Resource-Allocation Graph algorithm is similar to the resource-allocation graph but a new type of edge called a claim edge is introduced in it. The claim edge indicates that a process may request resources in the future. The climb edge is represented in the graph by a dashed line. When a process requests a resource, then the claim edge is converted into a request edge. Similarly, when a process releases a resource, the assignment edge is re-converted into a claim edge. 

Suppose that process P1 requests a resource, the resource allocation graph algorithm states that we use in a computer network system. We send requests and then turn it into a complete processing system

Banker's algorithm:

Banker's algorithm is a resource allocation and deadlock avoidance algorithm in a computer network system. It is used to avoid deadlocks in a system having multiple instances for each resource type. This algorithm was first proposed by Dijkstra in 1965. This algorithm is named as Banker's algorithm because it could be used in a banking network system to ensure that the bank never allocates its available cash or money in such a way that in the future it could no longer satisfy the cash needs of all its customers or clients.

The banker's algorithm has further two parts:

1. Safety algorithms
2. Resource-Request algorithm

Banker's Algorithm for Multiple Resources:

Generally, the Banker's algorithms can be used to handle multiple resources. According to this algorithm, when a new required process enters a computer network system, it must declare the maximum number of instances of each resource network system type that it may be needed in software. This number may not exceed the total number of resources in a computer network system. 

To implement the Banker's algorithm for multiple resources, a particular data structure must be maintained. Suppose "n" be the number of processes and "m" be the data number of resources types in the system. For this case, see need the following data structures:

Available: A vector of length "m" to store available resources.

Max: A matrix of  "n*m" to define maximum demand for each process.

Allocation: A matrix of  "n*m" to store the number of resources of each resource type currently allocated to each process.

Need: A matrix of  "n*m" to store the remaining resources needed by each process.

 

Advantages of Banker's Algorithm:

Some important advantages of Banker's algorithm are as follows:

1. It allows for handling multiple resources.
2. It allows mutual exclusion, hold-and-wait, and no-preemption conditions.
3. A process may be allocated resources without fear of deadlock.

Disadvantages of Banker's Algorithm:

Some important disadvantages of Banker's algorithm are as follows:

1. The system has to make a large number of calculations for making a decision before assigning resources to the processes.
2. The operating system must know the resource requirements for a particular process in advance.
3. This approach may lead a process to starvation while waiting for a long time to get the requested resources.