Deadlock Avoidance in Operating System:
Deadlock avoidance is a technique used to avoid deadlock. It requires the information about how different processes would request different resources. If given several processes and resources, we can allocate the resources in some order to avoid the deadlock.
1. Safe State:
A state is said to be a safe state if the system may allocate the required resources to each process up to the maximum required in a particular sequence, without facing deadlock. In safe state, deadlock cannot occur. If a deadlock is possible, the system is said to be in an unsafe state. The idea of avoiding a deadlock is to simply not allow the system to enter an unsafe state that may cause a deadlock.
Example:
Consider a system with 24 tape drives and three processes: P0, P1 and P2. Po may require 20 tape-drives during execution, Pi may require 8, and P2 may require up to 18.
Suppose, Po is holding 10 tape drives, Pi holds 4 and Pa holds 4 tape drives. The system is said to be in a safe state, since there is a safe sequence that avoids the deadlock.
Suppose, Po is holding 10 tape drives, Pi holds 4 and Pa holds 4 tape drives. The system is said to be in a safe state, since there is a safe sequence that avoids the deadlock.
| Process | Maximum Required | Current Allocated |
| P0 | 20 | 10 |
| P1 | 8 | 4 |
| P2 | 18 | 4 |
1. Safe Sequence:
This sequence implies that P1 can instantly get all of its needed resources. There are 24 total tape drives. P1 already has 4 and needs 4 more. It can get since there are 6 free tape drives. Once it finishes executing, it releases all 8 resources. At this point, the system has 10 free tape drives. Now P0 can execute since it requires exactly 10 more drives to finish. After it finishes, the system has a total of 20 free tape drives. These can be allocated to P2 and it can proceed since it needs 14 more drives to complete its task.
2. Unsafe Sequence:
Suppose at some time P2 requests 2 more resource to make its holding resources 6. Now the system is in an unsafe state. The system has now 4 free drives and can only be allocated to P1. After P1 returns, it will leave 8 free resources. It is not enough for either P0 or P1 The system enters a deadlock.
There are algorithms that determine if a safe state can be maintained after a resource allocation. The resource will not be allocated that may cause the system to enter an unsafe state resulting in a deadlock.
2. Resource-Allocation Graph Algorithm:
Resource-allocation graph algorithm is used to avoid deadlock. This algorithm uses the resource-allocation graph by introducing a new edge called claim edge. The claim edge is used to indicate that a process may request a resource in future. It is represented by a dashed line. When the process requests that resource, the dashed line is converted to an assignment edge i.e. a solid line. It indicates that the resource has been allocated to the process. After the process releases this resource, the assignment edge is again converted to claim edge. All claim edges of a process are represented in the graph. It requires the knowledge of all resources to be used by a process, before the execution of the process starts.
When a process requests a resource, it is allocated only if converting the request edge to an assignment edge does not form a cycle in the graph. If no cycle is formed, the system is in safe state and the resource will be allocated. But if there is a cycle, the system will, enter an unsafe state and the process will wait for the resource.
3. Banker's Algorithm:
Banker's algorithm is less efficient than resource allocation graph algorithm. But it can be implemented in a system with multiple instances of each resource type. It requires that each new process should declare the maximum number of instances of each required resource type. When a process requests certain resources, the system determines whether the allocation of those resources will leave the system in safe state. If it will, the resources are allocated. Otherwise the process must wait until some other process releases the resources-
The "Banker's algorithm allows the following:
- Mutual exclusion
- Wait and hold
- No preemption
It prevents the following:
- Circular wait
User process may only request one resource at a time. System grants request only if the request will result in a safe state. This algorithm uses different data structures to implement deadlock avoidance. Let n be the number of processes and m be the number of resource types. Following data structures are required:
- Available: A vector of length m indicates number of available resources of each type.
- Max: An n x m matrix indicates the maximum requirement of each process.
- Allocated: An n x m matrix indicates the number of resources of each type currently
allocated to each process.
- Need: An n x in matrix indicates the remaining resource need of each process.
Example:
Assume we have the following resources:
- 5 tape drives
- 2 graphic displays
- 4 printers
- 3 disks
We can create a vector representing our total resources: Total = (5,2, 4, 3). Consider we have already allocated these resources among four processes as demonstrated by the following matrix named Allocated.
Allocated = (4,2,2,3).
We also need a matrix to show the number of each resource still needed for each process. We call this matrix Need.
| Process Name | Tape Drives | Graphics | Printers | Disk Drives |
| Process A | 1 | 1 | 0 | 0 |
| Process B | 0 | 1 | 1 | 2 |
| Process C | 3 | 1 | 0 | 0 |
| Process D | 0 | 0 | 1 | 0 |
Table: Allocation matrix
| ||||
| Process Name | Tape Drives | Graphics | Printers | Disk Drives |
| Process A | 1 | 1 | 0 | 0 |
| Process B | 0 | 1 | 1 | 2 |
| Process C | 3 | 1 | 0 | 0 |
| Process D | 0 | 0 | 1 | 0 |
Table: Need matrix
| ||||
Now the vector Available = (1,0,2,0).
Working of Banker's Algorithm:
1. Find a row in the Need matrix, which is less than the Available vector. If such a row exists, then the process represented by that row may complete with those additional resources. If no such row exists, deadlock is possible.
2. You want to double-check that granting these resources to the process for the chosen row will result in a safe state. Suppose that the process has acquired all its needed resources, executed, terminated, and returned resources to Available vector. Now the value of Available vector should be greater than or equal to the previous value.
3. Repeat steps 1 and 2 until:
- All the processes have successfully reached pretended termination. This indicates that the initial state was safe. OR
- Deadlock is reached. This indicates that the initial state was unsafe.
Following is the working of the above algorithm: .
Iteration 1:
1. Examine the Need matrix. The only row- that is less than the Available vector is the one for Process D.
Need (Process D) = (0,0,1,0) < (1/0, 2,0) = Available
2. If we assume that Process D completes, it will turn over its currently allocated resources, incrementing the Available vector.
| (1, 0, 2, 0) | Current value of available |
| + (1, 1, 0, 1) | Allocation (Process D) |
| (2, 1, 2, 1) | Updated value of Available |
Iteration 2:
1. Examine the Need matrix, ignoring the row for Process D. The only row that is less than the Available vector is the one for Process A.
Need (Process A) = (1,1,0,0) < (2,1,2,1) = Available
2. If we assume that Process A completes, it will turn over its currently allocated resources, incrementing the Available vector.
| (2, 1, 2, 1) | CURRENT VALUE OF AVAILABLE |
| + (2, 0, 1, 1) | Allocation (Process A) |
| (4, 1, 3, 2) | Updated value of Available |
Iteration 3:
1. Examine the Need matrix without the row for Process D and Process A. The only row that is less than the Available vector is the one for Process B.
Need (Process B) = (0,1,1,2) < (4,1,3,2) = Available
2. If we assume that Process B completes, it will turn over its currently allocated resources, incrementing the Available vector.
| (4, 1, 3, 2) | CURRENT VALUE OF AVAILABLE |
| + (0, 1, 0, 0) | Allocation (Process B) |
| (4, 2, 3, 2) | Updated value of Available |
Iteration 4:
1. Examine the Need matrix without the rows for Process A, Process B, and Process D. The only row left is the one for Process C, and it is less than the Available vector.
Need (Process C) = (3,1,0, 0) < (4,2,3,2) = Available
2. If we assume that Process C completes, it will turn over its currently allocated resources, incrementing the Available vector.
| (4, 2, 3, 3) | CURRENT VALUE OF AVAILABLE |
| + (1, 0, 1, 1) | Allocation (Process C) |
| (5, 2, 4, 3) | Updated value of Available |
Notice that the final value of the Available vector is the same as the original Total vector, showing the total number of all resources:
Total = (5, 2,4,2) < (5,2,4,2) = Available
This means that the initial state represented by the Allocation and Need matrices is a safe state. The safe sequence that assures this safe state is .
