6.5 Deadlock avoidance

Deadlock avoidance approach requires that the system has some additional a priori information available. The simplest and most useful model requires that each process declare the maximum number of resources of each type that it may need. The deadlock-avoidance algorithm dynamically examines the resource-allocation state to ensure that there can never be a circular-wait condition. Resource-allocation state is defined by the number of available and allocated resources, and the maximum demands of the processes.

Safe state
A state is safe if the system can allocate resources to each process (up to its maximum) in some order and still avoid a deadlock. When a process requests an available resource, the system must decide if immediate allocation leaves the system in a safe state.

System is in safe state if there exists a sequence P1, P2, ..., Pn of all the processes such that for each Pi, the resources that Pi can still request can be satisfied by currently available resources plus resources held by all the Pj, with j i. If no such sequence exists, then the system state is said to be unsafe. Not all unsafe states are deadlocks but an unsafe state may lead to a deadlock.

Resource-allocation graph algorithm
The resource-allocation graph has request and assignment edges. In addition, there is a claim edge. The claim edge Pi –› Rj indicated that process Pj may request resource Rj and it is represented by a dashed line. Claim edge converts to request edge when a process requests a resource. Request edge converted to an assignment edge when the resource is allocated to the process. When a resource is released by a...

6.5 Deadlock avoidance

...process, assignment edge reconverts to a claim edge. Resources must be claimed a priori in the system.
Suppose that process Pi requests a resource Rj . The request can be granted only if converting the request edge to an assignment edge does not result in the formation of a cycle in the resource allocation graph.
If no cycle exists, then the allocation of the resource will keep the system in a safe state. If a cycle is found, then the allocation will put the system in an unsafe state. Then, the resource will not be allocated to process Pi.

Banker's algorithm
The Banker's algorithm is used when resources have multiple instances. Each process must declare a priori claim maximum use of each resource. When a process requests a resource it may have to wait to determine whether the allocation of these resources will leave the system in a safe state. When a process gets all its resources it must return them in a finite amount of time.

Let n is number of processes, and m is number of resources types. The following data structures are needed:

Available: Vector of length m. If available[j] = k, there are k instances of resource type Rj available.

Max: n x m matrix. If Max[i,j] = k, then process Pi may request at most k instances of resource type Rj.

Allocation: n x m matrix. If Allocation[i,j] = k then Pi is currently allocated k instances of Rj.

Need: n x m matrix. If Need[i,j] = k, then Pi may need k more instances of Rj to complete its task. Note

that Need [i,j] = Max[i,j] - Allocation [i,j]

6.5 Deadlock avoidance

The following algorithm is the safety algorithm for finding out whether or not a system is in a safe state can be described:

1.	Let Work and Finish be vectors of length m and n, respectively. Initialize:

a.

Work = Available

b.

Finish [i] = false for i = 0, 1, ..., n- 1

2.	Find and 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 i, then the system is in a safe state

Requesti is the request vector for process Pi. If Requesti [j] = k then process Pi wants k instances of resource type Rj . The following actions will happen when process Pi requests a resource:

6.5 Deadlock avoidance

1.	If Requesti ≤ Needi go to step 2. Otherwise, raise error condition, since process has exceeded its

maximum claim.

2.	If Requesti ≤ Available, go to step 3. Otherwise Pi must wait, since resources are not available.

3.	Pretend to allocate requested resources to Pi by modifying the state as follows:

Available = Available - Request;
Allocationi = Allocationi + Requesti;
Needi = Needi - Requesti;

If the system in safe state, then the resources are allocated to Pi

If the system in unsafe state, then Pi must wait and the old resource-allocation state is restored.