Deadlock refers to a situation in which one process is waiting for a resource that is currently under the control of some other process. Hence, it results in the permanent blocking of the processes. This situation can be avoided by avoiding the entry of a deadlock by using various deadlock avoidance techniques.

Deadlock avoidance does not impose any rules but, here each resource request is carefully analyzed to see whether it could be safely fulfilled without causing deadlock. The drawback of this scheme is its requirement of information in advance about how resources are to be requested.

Different algorithms require different types and amounts of information, some require a maximum number of resources that each process requires. The following are the various deadlock avoidance algorithms.

Safe State :

Consider a system consisting of several processes like <P₁, P₂, P₃,…, P_n>. Each of them requires certain resources immediately and also specifies the maximum number of resources that they may need in their lifetime.

Using this information, we need to build a “safe sequence” which is a sequence of processes where their resource request can be satisfied without having a deadlock occur. If there exists any such safe sequence, then the system is said to be in a “safe state” during which deadlock cannot occur. An unsafe state may lead to deadlock but not always. There are some sequences in the unsafe state which can lead to deadlock.

Example for Safe State :

For example, consider a system with 24 printers and three processes i.e., P₁, P₂, and P₃ requiring 14, 8, and 13 printers respectively. This is the maximum need they require, it is not always the case that they require all of them at once. At a particular time t₀, P₁ needs only 9 printers, P₂ and P₃ need 6 each. The table below shows the same.

If the processes are executed in the sequence <P₂, P₁, P₃> then the safety condition can be satisfied. The table below shows the sequence of resource allocation and release.

The above shows one of the safe sequences, there may be many safe sequences for the same example. In the beginning, the system will be in a safe state, then processes are allocated to resources according to their current need. Thereafter, whenever a process requests, the algorithm must decide whether the allocation is safe or unsafe and accordingly the action should be taken.

Resource Allocation Graph :

It is a directed graph, given as G = (V, E) containing a set of vertices V and edges E. The vertices are divided into two types, i.e., a set of processes, P = {P₁, P₂, P₃,…P_n} and a set of resources, R = {R₁, R₂, R₃,….R_n}. An edge from process P_i to resource R_j (P_i → R_j) indicates that P_i has requested resource R_j. It is called a ‘request edge’.

Any edge from a resource R_j to a process P_i (R_j → P_i) indicates that R_j is allocated to process P_i. It is called an “assignment edge” when a request is fulfilled it is transformed into an assignment edge. Processes are represented as circles and resources as rectangles. The below figure is an example of the graph where process P₁ has R₁ and requests for R₂.

For avoiding deadlocks using resource allocation graph, it is modified slightly by introducing a new edge called “claim edge”. It is an edge from process P_i to resource R_j (P_i → R_j) indicates that in the future, P_i may request for R_j. The direction of the arrow is same as the request edge but with a dashed line as shown below.

Example for Resource Allocation Graph :

To describe the usage of this graph in deadlock avoidance, let us consider as example graph shown below consisting of two processes (P₁ and P₂) and two resources (R₁ and R₂) such that P₂ has resource R₂ and requests for R₁ and P₁ has resource R₁ and may claim for R₂ in future. This action can create a cycle in the graph which means deadlock is possible and the system is in an unsafe state. Hence, the allocation should not be done.

Banker’s Algorithm :

It is used to avoid deadlocks when multiple instances of each resource type are present. This is not possible, using the methods like safe state and resource allocation graphs. It is similar to a banking system where a bank never allocates cash in such a way that it could not satisfy the needs of all its customers and also it cannot allocate more than what is available. Here, customers are analogous to processes, cash to resources, and bank to the operating system.

A process must specify in the beginning the maximum number of instances of each resource type it may require. It is obvious that this number should not be more than the available. When the process requests resources, the system decides whether allocation will result in deadlock or not. If not, resources are allocated otherwise process has to wait.

The following are the various data structures that have to be created to implement Banker’s algorithm. If ‘n’ is the number of processes and ‘m’ is the number of resources.

• Max : A ‘n × m’ matrix indicating the maximum resources required by each process.
• Allocation : A ‘n × m’ matrix indicating the number of resources already allocated to each process.
• Need : A ‘n × m’ matrix indicates the number of resources required by each process.
• Available : It is a vector of size ‘m’ which indicates the resources that are still available (not allocated to any process).
• Request : It is a vector of size ‘m’ which indicates that process P_i has requested some resources.

Each row of matrices “allocation” and “need” can be referred to as vectors. Then “allocation” indicates the resources currently allocated to process P_i and “need” refers to resources required by P_i. The following algorithm is used to determine whether the request can be safely granted or not.

• Step 1 – If Request_i ≤ Need_i, then proceed to step two, otherwise raise an exception saying the process has exceeded its maximum claim.
• Step 2 – If Request_i ≤ Available, then proceed to step three, otherwise block P_i because resources are not available.
• Step 3 – Allocate resources to P_i as follows,
  Available = Available – Request_i
  Allocation_i = Allocation_i + Request_i
  Need_i = Need_i – Request_i

Safety Algorithm :

The job of the banker’s algorithm is to perform allocation, it will not see whether this allocation has resulted in a safe or unsafe state. It is the safety algorithm that is called immediately after the banker’s algorithm to check for the system state after allocation. The following is the safety algorithm that requires m x n² operations to find the system state.

• Step 1 – Assume work and finish as vectors of length ‘m’ and ‘n’ respectively.
  Work = Avaiable
  Finish[i] = ‘false’
• Step 2 – Find ‘i’ such that,
  Finish[i] = ‘false’
  Need_i ≤ Work

  If no such ‘i’ is found jump to step four.

• Step 3 –
  Work = Work + Allocation
  Finish[i] = ‘true’

  Jump to step two.

• Step 4 – If finish[i] = True for all then the system is in a safe state.