15 Deadlocks – Avoidance
Mary Anitha Rajam
18.1 Introduction
In a multi-programming environment, many processes compete for a finite number of resources. If the resources requested by a process are not available, the process waits. If the resources requested by this process are held by other waiting processes, the situation may lead to a deadlock. The different ways to handle deadlocks are deadlock prevention, deadlock avoidance, deadlock detection and recovery. In the previous module, we learnt different ways to prevent deadlocks. In this module, we shall see how deadlocks are avoided.
In the previous module, we learnt that a system with resources can be depicted using a resource-allocation graph. In a resource-allocation graph, processes are denoted using circles and resource types are denoted using rectangles. The different instances of each resource type are shown as dots within the rectangles. Processes and resource types are the nodes of the resource-allocation graph. The edges show the dependency between the processes and the resources. If there is an edge from a process to a resource, it means that the process is requesting for an instance of the resource (request edge). If there is an edge from a resource to a process, it means that an instance of the resource is assigned to the process (assignment edge).
18.2. Resource-Allocation Graph Algorithm for Deadlock Avoidance
Fig. 18.1 Resource-Allocation Graph for Deadlock Avoidance (Source: [1])
A variant of the resource-allocation graph is used to avoid deadlocks when the system has only one instance of a resource type. In this graph, a new type of edge is added called the claim edge. A claim edge is represented by a dashed line as shown in Figure 18.1. A claim edge Pi ® Rj indicates that process Pj will request resource Rj. All claim edges must appear in the graph, initially. Resources must be claimed a priori in the system. That is, at the beginning, the system should know the future requests of all the processes. These requests that would be made in future are depicted using claim edges.
A claim edge Pi ® Rj is converted to a request edge when process Pi actually requests for resource Rj. When resource Rj is released by process Pi, the assignment edge Ri ® Pi reconverts to a claim edge Pi ® Rj.
We will now learn how deadlocks can be avoided using this type of resource-allocation graphs. Suppose Pi requests Rj. The resource-allocation graph would have had a claim edge from Pi to Rj. The claim edge is now converted to a request edge Pi ® Rj. The request edge Pi ® Rj is converted to an assignment edge Rj ® Pi. The resource-allocation graph now depicts how the state of the system would have been after the resource Rj is allocated to Pi. The resource-allocation graph is now checked for cycles using the cycle-detection algorithm. If there is no cycle, the system is in a safe state and the resource can be allocated to Pi. If there is a cycle, process Pi has to wait. Pi is not allocated the resource Rj immediately.
Thus, the resource-allocation graph alone is modified and the system is checked for safe state. The actual allocation of resource is not done immediately. Only if the allocation would result in a safe state, the actual allocation of resources is done.
Fig. 18.2 Unsafe State In Resource-Allocation Graph (Source: [1])
Consider the resource-allocation graph in Figure 18.2. P2 requests for resource R2 as shown using the claim edge from P2 to R2 in Figure 18.1. This is converted to an assignment edge in the resource-allocation graph as shown in Figure 18.2. The graph is now checked for cycles. Since there is a cycle, the system understands that allocating R2 to P2 will lead to a deadlock. The only instance of R1 is assigned to P1 and the only instance of R2 is assigned to P2. P2 has requested for R1. It is known from the claim edge that process P1 may request for R2. If P1 requests for R2 (before releasing R1, then both the processes P1 and P2 will wait for a resource held by the other process. The system will go to a deadlocked state. Therefore, R2 is not allocated to P2. Thus, deadlocks are avoided.
This method can be used to avoid deadlocks only if there is a single instance of each resource type. If there are more instances of each resource type, Banker’s algorithm is used for deadlock avoidance.
18.3 Banker’s Algorithm
In the Banker’s algorithm, each process must a priori declare its maximum use. This should be done for any deadlock avoidance algorithm. The maximum resource need of each process must not exceed the total number of resources in the system. When a user requests for resources, the system checks whether the allocation of the request will result in a safe state. If, after the allocation, the system will be in a safe state, resources are allocated. Else, the process waits. When a process gets all its resources it must return them in a finite amount of time.
18.3.1 Data Structures for the Banker’s Algorithm
Let n denote the number of processes and m denote the number of resource types.
• Available: Vector of length m. If Available[j] = k, there are k instances of resource type Rj available.
A B C
3 3 2
In the example shown above, there are three resource types A, B and C. The number of available instances of resource types A, B and C are 3, 3 and 2 respectively.
• Max: n x m matrix. The n rows correspond to n processes and the m columns correspond to the m resource types. If Max[i, j] = k, then process Pi may request at most k instances of resource type Rj
| A B C | |
| P0 | 7 5 3 |
| P1 | 3 2 2 |
| P2 | 9 0 2 |
| P3 | 2 2 2 |
In the example shown above, there are three resource types A, B and C and four processes P0, P1, P2 and P3. The maximum need of process P0 can be 7 instances of resource type A, 5 instances of resource type B and 3 instances of resource type C. Similarly, the maximum need of the other processes P1, P2 and P3 are also shown.
• Allocation: n x m matrix. The n rows correspond to n processes and the m columns correspond to the m resource types. If Allocation[i,j] = k then process Pi is currently allocated k instances of Rj.
| A B C | |
| P0 | 0 1 0 |
| P1 | 2 0 0 |
| P2 | 3 0 2 |
| P3 | 2 1 1 |
In the example shown above, there are three resource types A, B and C and four processes P0, P1, P2 and P3. The number of instances of resource type currently allocated to each process is shown. Process P0 is currently allocated 0 instances of resource type A, 1 instance of resource type B and 0 instances of resource type C. Similarly, the current allocation of the other processes P1, P2 and P3 are also shown.
• Need: n x m matrix. The n rows correspond to n processes and the m columns correspond to the m resource types. This matrix shows the future need of each process. If Need[i, j] = k, then Pi may need k more instances of Rj to complete its task.
Need [i, j] = Max[i, j] – Allocation [i, j]
That is, future need is a process’s maximum need minus the resources currently allocated.
18.3.2 Notations Used:
If X and Y are vectors of length n
- X ≤ Y iff X[i] ≤ Y[i] for all i = 1,2,…,n
That is, the ith element of vector X is less than or equal to the ith element of vector Y, for all i.
Consider the following vectors X and Y
- If X = (1,7,3,2), Y = (0,3,2,1)
In the above Y ≤ X, because each element of vector Y is less than or equal to the corresponding element of vector X. That is, the first element of Y is less than the first element of X and so on.
Y < X, if Y ≤ X and Y≠ X
Each row in the matrices Allocation and Need is treated as a vector. For example, the ith row of matrix Allocation and Need are referred to as Allocationi and Needi respectively.
The Banker’s algorithm comprises a safety algorithm and a resource-allocation algorithm. For a given state of the system, the safety algorithm checks if the system is in a safe state. The safety algorithm is given below:
18.3.3 Safety Algorithm
1. Let Work and Finish be vectors of length m and n respectively. Initialize:
Work = Available
Finish [i] = false for i = 1,2, …, n
2. Find an i such that both:
(a) Finish [i] = false
(b) Needi £ Work
If no such i exists, go to step 4.
3. Work = Work + Allocationi
Finish[i] = true
go to step 2.
4. If Finish [i] == true for all i, then the system is in a safe state.
Whenever a request for resources comes from a process, the system runs the resource-request algorithm and modifies the state of the system in the simulation as if the resource is allocated. The actual state of the system is not modified; the data structures in the algorithm alone are modified. The safety algorithm is run to check if the system still remains in a safe state. The resource-request algorithm for process Pi is given below:
18.3.4 Resource-Request Algorithm for Process Pi
Requesti = request vector for process Pi. If Requesti [j] = k then process Pi wants k instances of resource type Rj.
1. If Requesti £ Needi go to step 2. Otherwise, raise error condition, since process has exceeded its maximum claim.
2. If Requesti £ Available, go to step 3. Otherwise Pi must wait, since resources are not available.
3. Pretend to allocate requested resources to Pi by modifying the state as follows:
Available = Requesti;
Allocationi = Allocationi + Requesti;
Needi = Needi – Requesti;;
The safety algorithm is now run to check if the system is in a safe state with this modified state.
If safe Þ the resources are allocated to Pi.
If unsafe Þ Pi must wait, and the old resource-allocation state is restored
We will understand how the algorithm works by an example as given below.
18.3.5 Example of Banker’s Algorithm
Consider 5 processes P0 through P4; 3 resource types A, B and C. There are 10 instances of A, 5 instances of B and 7 instances of C.
The snapshot at time T0 is given below:
| Allocation | Max | Available | |
| A B C | A B C | A B C | |
| P0 | 0 1 0 | 7 5 3 | 3 3 2 |
| P1 | 2 0 0 | 3 2 2 | |
| P2 | 3 0 2 | 9 0 2 | |
| P3 | 2 1 1 | 2 2 2 | |
| P4 | 0 0 2 | 4 3 3 |
The content of the matrix Need is defined to be Max – Allocation. Matrix Need is given below:
Need A B C
P0 7 4 3
P1 1 2 2
P2 6 0 0
P3 0 1 1
P4 4 3 1
We will first check if the system is in a safe state in the current situation. For this, the safety algorithm is run.
Allocation Need Available
| A B C | A B C | A B C | |
| P0 | 0 1 0 | 7 4 3 | 3 3 2 |
| P1 | 2 0 0 | 1 2 2 | |
| P2 | 3 0 2 | 6 0 0 | |
| P3 | 2 1 1 | 0 1 1 | |
| P4 | 0 0 2 | 4 3 1 |
Vector Work is initialized to Available Therefore, Work = Available = (3,3,2)
Finish[i] = false for i = 0,1,2,3,4 Let i = 0
Is Need0 ≤ Work? No, (7,4,3) is not less than or equal to (3,3,2)
Let i = 1
Is Need1 ≤ Work? Yes, (1,2,2) is less than or equal to (3,3,2)
Therefore, set Finish[1] = true. P1 added to the safe sequence < P1>
Is Need2 ≤ Work? No, (6,0,0) is not less than or equal to (5,3,2)
Work = Work + Allocation1 = (3,3,2) + (2,0,0) = (5,3,2) Let i = 2
Let i = 3
Is Need3 ≤ Work? Yes, (0,1,1) is less than or equal to (5,3,2)
Therefore, set Finish[3] = true , P3 added to safe sequence < P1, P3>
Work = Work + Allocation3 =(5,3,2) + (2,1,1) = (7,4,3)
Work = (7,4,4)
Let i = 4
Is Need4 ≤ Work? Yes, (4,3,1) is less than or equal to (7,4,3)
Set Finish[4] = true , P4 is added to safe sequence < P1 ,P3, P4 >
Work = Work + Allocation4 = (7,4,3) + (0,0,2) = (7,4,5)
Work = (7,4,5)
Now, check again the processes that were not added to the safe sequence. P0
and P2 are remaining.
So, let i = 0
Is Need0 ≤ Work? Yes
Set Finish[0] = true, P0 is added to safe sequence < P1 ,P3, P4 , P0>
Work = Work + Allocation0 =(7,4,5) + (0,1, 0) = (7,5,5)
Work = (7,5,5)
Let i = 2
Is Need2 ≤ Work? Yes
Finish[0] = true , P2 is added to safe sequence <P1 ,P3, P4 , P0 , P2 >
Work = Work + Allocation2 =(7,5,5) + (3,0,2) = (10,5,7)
The system is in a safe state since the sequence < P1, P3, P4, P2, P0> satisfies the safety requirement
Now, let P1 Request (1,0,2)
First, check if Request1 £ Available (that is, (1,0,2) £ (3,3,2)) Þ true.
Also, check if Request1 £ Need1 (that is (1,0,2) £ (1,2,2)) Þ true.
Now, the data structures are changed as if the request of P1 is granted. The future Need of P1 is changed from (1,2,2) to (0,2,0). The Allocation of P1 is changed from (2,0,0) to (3,0,2) and the resources available are changed to (2,3,0)
| Allocation A B C | Need A B C | Available A B C | |
| P0 | 0 1 0 | 7 4 3 | 2 3 0 |
| P1 | 3 0 2 | 0 2 0 | |
| P2 | 3 0 1 | 6 0 0 | |
| P3 | 2 1 1 | 0 1 1 | |
| P4 | 0 0 2 | 4 3 1 |
The system is now checked for a safety sequence. Executing safety algorithm shows that the sequence <P1, P3, P4, P0, P2> satisfies the safety requirement. Therefore, the request of P1 can be granted.
After P1’s request is granted, can request for (3,3,0) by P4 be granted?
No, resources are not available. Only (2,3,0) is available. P4 needs 3 instances of A, but only 2 instances of A are available.
Can request for (0,2,0) by P0 be granted?
P0 Request (0,2,0)
Check if Request0 £ Available
(0,2,0) £ (2,3,0) Þ true.
Also, check if Request0 £ Need0 (that is (0,2,0) £ (7,4,3)) Þ true.
Now, change the data structures as if the request is granted and run the safety algorithm to check for a safe sequence. The future Need of P0 is changed from (7,4,3) to (7,2,3). The Allocation of P1 is changed from (0,1,0) to (0,3,0) and the resources available are changed from (2,3,0) to (2,1,0).
| Allocation A B C | Need A B C | Available A B C | |
| P0 | 0 3 0 | 7 2 3 | 2 1 0 |
| P1 | 3 0 2 | 0 2 0 | |
| P2 | 3 0 1 | 6 0 0 | |
| P3 | 2 1 1 | 0 1 1 | |
| P4 | 0 0 2 | 4 3 1 |
The future need of any of the processes cannot be satisfied with the resources available. Therefore, there is no safe sequence. Therefore, it is understood that the request of P0 should not be granted.
18.5 Summary
This module discussed what is meant by a safe sequence. We learnt how deadlocks can be avoided when there is a single instance for all resource types. We also learnt how deadlocks can be avoided when there are multiple instances of resources using the Banker’s algorithm.
References
- Abraham Silberschatz, Peter B. Galvin, Greg Gagne, “Operating System Concepts”, Ninth Edition, John Wiley & Sons Inc., 2012.