When two processes are running on OS at the same time and one process request for the resource being used by the other process a deadlock can occur. Because the request cannot be fulfilled until the first process does not release the resource being taken by him.
In this article, you can find detailed knowledge of Deadlock, deadlock avoidance techniques such as Safe state, Unsafe state, Safe Sequence, Unsafe Sequence, Banker’s Algorithms & Resource Allocation Graph Algorithm. Let’s begin!
Deadlock avoidance is a technique used to avoid deadlock. It requires 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.
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 a 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.
Consider a system with 24 tape drives and three processes: P0, P1 and P2, P0 may require 20 tape-drives during execution, P1 may require 8, and P2 may require up to 18.
Suppose, P0 is holding 10 tape drives, P1 holds 4 and P2 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|
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 to 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.
Suppose at some time P2 requests two more resources 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 P2. The system enters in a deadlock.
There are algorithms that determine if a safe state can be maintained after a resource allocation. The resource will be allocated that may cause the system to enter an unsafe state resulting in a deadlock.
Algorithms for Deadlock Avoidance:-
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 sage 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.
Suppose, P2 requests R2. If we allocate R2 to P2, it will create a cycle in the graph and the system will enter an unsafe state. It should not be allocated to P2. The algorithm cannot be applied to a resource allocation system with multiple instances of each resource type.
Banker’s algorithm is less efficient than the 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 the resource type. Following data structures are required:
- Available: A vector of length m indicates the number of available resources of each type.
- Max: An n x m matrix indicates the maximum requirements of each process.
- Allocated: The n x m matrix indicates the number of resources of each type currently allocated to each process.
- Need: The n x m matrix indicates the remaining resource need of each process.
Assume we have the following resources:
- 5 tape drives
- 2 graphic displays
- 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|
Table: Allocation Matrix
|Process Name||Tape Drives||Graphics||Printers||Disk Drives|
Table: Need Matrix
Now the vector available = (1, 0, 2, 0).
Working on Banker’s Algorithm for Deadlock Avoidance
- 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.
- 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.
- Repeat steps 1 and 2 until:
- Al the processes have successfully reached pretended termination. This indicates that the initial state was safe.
- Deadlock is reached. This indicates that the initial state was unsafe.
Following is the working day of the above algorithm:
Examine the Need matrix. The only row that is less than the available vector one for process D.
Need (Process D) =(0, 0, 1, 0) < ( 1, 0, 2, 0) = available
If we assume that process D completes, it will turn over its currently allocated resources, incrementing the general knowledge.
|(1, 0, 2, 0 )||Current values of available|
|(1, 1, 0,1)||Allocation (process D)|
|(2, 1, 2, 1)||Update value of available|