# 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:

*–R*esource-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
starts executing, all of its claim edges must already appear in the*P*

resource-allocation graph.

**Safe Vs Unsafe State**

Suppose the resource-allocation graph of Given bellow, that ** P1** requests

**. While**

*R2***is currently available free and cannot allocate it to**

*R1***, 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**

*P1***and**

*R2***requests**

*P2***, at that time a deadlock will occur.**

*R1*

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

**= number of resources types**

*m*■

**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

**, respectively.**

*n*

*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