Table of Contents
When two processes are running on OS at the same time and one process requests 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.
Do You Read This:
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 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 simply not allowing 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 |
P0 | 20 | 10 |
P1 | 8 | 4 |
P2 | 18 | 4 |
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 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.
Unsafe Sequence
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 into 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.
A resource allocation graph algorithm is used to avoid deadlock. This algorithm uses the resource allocation graph by introducing a new edge called the claim edge. The claim edge is used to indicate that a process may request a resource in the 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 a 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.
Example:
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 a 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:
It prevents the following:
User processes 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:
Assume we have the following resources:
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 | 2 | 0 | 1 | 1 |
Process B | 0 | 1 | 0 | 0 |
Process C | 1 | 0 | 1 | 1 |
Process D | 1 | 1 | 0 | 1 |
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).
Following is the working day of the above algorithm:
Iteration 1:
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 |
Having bad credit can make it challenging to obtain a personal loan, but it's not… Read More
Traveling doesn't have to break the bank. With some careful planning and smart strategies, you… Read More
Are you looking for a job in the fruit packing industry with the added benefit… Read More
Are you considering a move from the United States to Canada? Whether it's for a… Read More
A credit card is a financial tool that allows you to borrow money from a… Read More
Watching sports online for free can be challenging due to the licensing agreements and restrictions… Read More