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 <P1, P2, P3,…, Pn>. 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., P1, P2, and P3 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 t0, P1 needs only 9 printers, P2 and P3 need 6 each. The table below shows the same.
Process | Current Need | Maximum Need |
---|---|---|
P1 | 9 | 14 |
P2 | 6 | 8 |
P3 | 6 | 13 |
If the processes are executed in the sequence <P2, P1, P3> then the safety condition can be satisfied. The table below shows the sequence of resource allocation and release.
P2 | P1 | P3 | Total Printers Remaining | |
---|---|---|---|---|
At t0 resources are allocated according to current needs. | 6 | 9 | 6 | 3 |
P2 is allocated its maximum requirements. | 6 + 2 = 8 | 9 | 6 | 1 |
P2 completes and returns all resources. | – | 9 | 6 | 9 |
P1 is allocated its maximum requirements. | – | 9 + 5 = 14 | 6 | 4 |
P1 completes and returns all resources. | – | – | 6 | 18 |
P3 is allocated its maximum requirements. | – | – | 6 + 7 = 13 | 11 |
P3 completes and returns all resources. | – | – | – | 24 |
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 = {P1, P2, P3,…Pn} and a set of resources, R = {R1, R2, R3,….Rn}. An edge from process Pi to resource Rj (Pi → Rj) indicates that Pi has requested resource Rj. It is called a ‘request edge’.
Any edge from a resource Rj to a process Pi (Rj → Pi) indicates that Rj is allocated to process Pi. 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 P1 has R1 and requests for R2.
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 Pi to resource Rj (Pi → Rj) indicates that in the future, Pi may request for Rj. 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 (P1 and P2) and two resources (R1 and R2) such that P2 has resource R2 and requests for R1 and P1 has resource R1 and may claim for R2 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 Pi 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 Pi and “need” refers to resources required by Pi. The following algorithm is used to determine whether the request can be safely granted or not.
- Step 1 – If Requesti ≤ Needi, then proceed to step two, otherwise raise an exception saying the process has exceeded its maximum claim.
- Step 2 – If Requesti ≤ Available, then proceed to step three, otherwise block Pi because resources are not available.
- Step 3 – Allocate resources to Pi as follows,
Available = Available – Requesti
Allocationi = Allocationi + Requesti
Needi = Needi – Requesti
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 n2 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’
Needi ≤ 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.
If no such ‘i’ is found jump to step four.
Jump to step two.