Page 143 - DCAP103_Principle of operating system

Principles of Operating Systems

Notes that Need[i,j] = Max[i,j] - Allocafion[i,j]. These data structures vary over time in both size and
value. To simplify the presentation of the banker’s algorithm, let us establish some notation.
Let X and Y be vectors of length n. We say that X 5 Y if and only if X[i] 5 Y[i] for all i = 1, 2,
..., n. For example, if X = (1,7,3,2) and Y = (0,3,2,1), then Y 5 X. Y < X if Y IX and Y$X. We can
treat each row in the matrices Allocation and Need as vectors and refer to them as Allocationi
and Needi, respectively. The vector Allocation; specifies the resources currently allocated to
process Pi; the vector Need, specifies the additional resources that process Pi may still request
to complete its task. Safety Algorithm The algorithm for finding out whether or not a system is
in a safe state can be described as follows:

1. Let Work and Finish be vectors of length m and n, respectively. Initialize Work := Available
and Finisk[i] :=false for i = 1,2, ..., n.
2. Find an i such that both a. Finisk[i] =false b. Needi 5 Work. If no such i exists, go to step 4.
3. Work := Work + Allocationi Finisk[i] := true go to step 2.

4. If Finish[i] = true for all i, then the system is in a safe state. This algorithm may require
an order of rn x n2 operations to decide whether a state is safe.

4.6.14 Resource-Request Algorithm
Let Requesti be the request vector for process Pi. If Request;[j] = k, then process Pi wants k
instances of resource type Rj. When a request for resources is made by process Pi, the following
actions are taken:
1. If Requesti 5 Needi, go to step 2. Otherwise, raise an error condition, since the process
has exceeded its maximum claim.
2. If Requesti 5 Available, go to step 3. Otherwise, Pi must wait, since the resources are not
available.
3. Have the system pretend to have allocated the requested resources to process Pi by
modifying the state as follows:
Available := Available - Request,;
Allocationi := Allocation; + Request;;
Needi := Needi - Requesti;
If the resulting resource-allocation state is safe, the transaction is completed and process Pi is
allocated its resources. However, if the new state is unsafe, then Pi must wait for Requesti and
the old resource-allocation state is restored.

Consider a system with five processes Po through P4 and three resource
types A, B, C. Resource type A has 10 instances, resource type B has 5
instances, and resource type C has 7 instances. Suppose that, at time To,
the following snapshot of the system has been taken:

Allocation Max Available
A B C A B C A B C
P 0 0 1 0 7 5 3 3 3 2
P 1 2 0 0 3 2 2
P 2 3 0 2 9 0 2
P 3 2 1 1 2 2 2
P 4 0 0 2 4 3 3

136 LOVELY PROFESSIONAL UNIVERSITY