Deadlock Avoidance Algorithms
Deadlock Avoidance Algorithms
There are two types of deadlock avoidance algorithms on the basis of their resources
- Algorithm which is used for single instance of a resource type is:
–Resource-allocation graph - Algorithm which is used for Multiple instances of a resource type is given as:
– Banker’s algorithm
Resource Allocation Graph Algorithm
The algorithm which is used in dead avoidance in case when there is only instance of each resource class is known as RAG algorithm.
- A new type of Edge is presented which is called Claim Edge.
- Claim edge Pi → Rj specified that process Pj can request resource Rj in the future; is denoted by a dashed line.
- Claim edge transforms to request edge when a process requests a resource.
- Request edge converted to an assignment edge when the resource is allocated to
the process - Whenever a resource is set free by a process then assignment edge re-converts to a claim
edge, resources should be claimed a priori in the system - Before a process P starts executing, all of its claim edges must already appear in the
resource-allocation graph.
Safe Vs Unsafe State
Suppose the resource-allocation graph of Given bellow, that P1 requests R2. While R1 is currently available free and cannot allocate it to p1, then this action will generate a cycle in the graph. On the other side A cycle shows that the system is in an unsafe state. In case if P1 requests R2 and P2 requests R1, at that time a deadlock will occur.
Suppose that process Pi requests for a resource Rj. The request may be granted only if modifying the request edge to an assignment edge does not result in the creation of a cycle in the resource allocation graph.
Banker’s Algorithm
The RAG algorithm is un-applicable to a resource allocation system which has multiple instances of every resource type. Banker’s Algorithm is normally less efficient than the RAG scheme. The name of this algorithm was chosen because the algorithm could be used in a banking system to make sure that the bank never allotted its available cash in such a way that it could no longer satisfy need of all its customers. Once, a new process enters the system, it must state the maximum number of instances of respectively resource type that it may need. This number cannot go above the total number of resources in the system. When a Process requests a set of resources then the system must define whether the allocation of these resources would leave the system in a safe state. If it would then the resources are allocated else, the process must wait up until some other process releases enough resources. When a process acquires all its resources it must return them in a predictable amount of time
Let say n = number of processes, and m = number of resources types
■ Available: A vector with length m specifies the number of available resources of each type. If Available[j] = k, there are k instances of resource type Rj available.
■ Max. An n x m matrix expresses the maximum demand of each process. If Max[i,j] = k, then process Pi can request at most k instances of resource Rj.
■ Allocation. An n x m matrix describes the number of resources of each type presently allocated to each process. If Allocation[i,j] = k then process Pi is currently allocated k instances of resource type Rj.
■ Need. An n x m matrix specifies the remaining resource need for each process. If
Need[i,j] = k, then process Pi may require k more instances of resource type Rj to complete its task.
Note: Need[i,j] = Max[i,j] – Allocation[i,j]
Safe State
An Algorithm for finding out whether or not a system is in a safe state.
1. Let Finish and Work are two vectors of length m and n, respectively.
Initialize:
Work = Available
Finish [i] = false for i = 0, 1, …, n- 1
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 the values of i, then the system is in a safe state
