Page 142 - DCAP103_Principle of operating system

Unit 4: Process Management-III

Figure 4.13: Resource-Allocation Graph for Deadlock Avoidance Notes

If no cycle exists, then the allocation of the resource will leave the system in a safe state. If a
cycle is found, then the allocation will put the system in an unsafe state. Therefore, process
Pi will have to wait for its requests to be satisfied. To illustrate this algorithm, we consider
the resource-allocation graph of Figure 4.13. Suppose that P2 requests R2. Although R2 is
currently free, we cannot allocate it to P2, since this action will create a cycle in the graph.
A cycle indicates that the system is in an unsafe state. If PI requests R2, and P2 requests
R1, then a deadlock will occur.
4.6.13 Banker’s Algorithm

The resource-allocation graph algorithm is not applicable to a resource-allocation system with
multiple instances of each resource type. The deadlock-avoidance algorithm that we describe
next is applicable to such a system, but is less efficient than the resource-allocation graph scheme.
This algorithm is commonly known as the banker’s algorithm. The name was chosen because
this algorithm could be used in a banking system to ensure that the bank never allocates its
available cash such that it can no longer satisfy the needs of all its customers. When a new process
enters the system, it must declare the maximum number of instances of each resource type that
it may need. This number may not exceed the total number of resources in the system. When
a user requests a set of resources, the system must determine whether the allocation of these
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 enough resources. Several data structures
must be maintained to implement the banker’s algorithm. These data structures encode the
state of the resource-allocation system. Let n be the number of processes in the system and rn
be the number of resource types. We need the following data structures: Available: a vector of
length rn indicates 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 rn matrix defines the maximum demand of each process. If Max[i,j] = k, then
process Pi may request at most k instances of resource type.
Ri . Allocation: An n x rn matrix defines the number of resources of each type currently 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 rn matrix indicates the remaining resource need of each process. If Need[i,j]
= k, then process Pi may need k more instances of resource type Ri to complete its task. Note

LOVELY PROFESSIONAL UNIVERSITY 135