Safety Algorithm & Resource-Request Algorithm

Safety Algorithm

safety algorithm

The algorithm for finding out whether or not a system is in a safety algorithm 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.

  1. Find an i such that both a. Finisk[i] =false
  2. Needi < Work.

If no such i exists, go to step 4.

  1. Work := Work + Allocationi

 Finisk[i] := true

go to step 2.

  1. If Finish[i] = true for all i, then the system is in a safe state.

This algorithm may require an order of m x n2 operations to decide whether a state is safe.

 

Resource-Request Algorithm

Resource allocation graph

 Let Request be the request vector for process Pi. If Requesti[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 Request < Need, go to step 2. Otherwise, raise an error condition, since the process has

exceeded its maximum claim.

  1. If Request < Available, go to step 3. Otherwise, Pi must wait, since the resources are not

available.

  1. 3. Have the system pretend to have allocated the requested resources to process Pi by

modifying the state as follows:

  Available := Available – Requesti;

Allocationi := Allocationi + Requesti;

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 Request and the old resource-allocation state is restored.

 

Consider a system with five processes P0 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 T0, the following snapshot of the system has been taken:

 

Allocation                     Max                  Available

————                        ——–                ———–

A   B  C                        A  B  C                         A  B  C

P0        0   1   0                         7   5  3              3  3   2

PI         2   0   0                         3   2  2

P2        3   0   2                         9   0  2

P3        2   1   1                         2   2  2

P4        0   0   2                         4   3  3

 

The content of the matrix Need is defined to be Max – Allocation and is

 

Need

——-

A  B  C

P0        7   4  3

P1        1   2  2

P2        6   0  0

P3        0   1  1

P4        4   3  1

We claim that the system is currently in a safe state. Indeed, the sequence <PI, P3, P4, P2, P0> satisfies the safety criteria. Suppose now that process P1 requests one additional instance of resource type A and two instances of resource type C, so Request1 = (1,0,2). To decide whether this request can be immediately granted, we first check that Request1£ Available (that is, (1,0,2) £ (3,3,2)), which is true. We then pretend that this request has been fulfilled, and we arrive at the following new state:

 

Allocation    Need    Available

————                        ——–                ———–

A   B   C                       A  B  C                         A  B  C

P0        0   1    0                        7   4  3              2  3   0

PI         3   0    2                        0   2  0

P2        3   0    2                        6   0  0

P3        2   1    1                        0   1  1

P4        0   0    2                        4   3  1

 

We must determine whether this new system state is safe. To do so, we execute our safety algorithm and find that the sequence <PI, P3, P4, P0, P2> satisfies our safety requirement. Hence, we can immediately grant the request of process PI.

 

However, that when the system is in this state, a request for (3,3,0) by P4 cannot be granted, since the resources are not available. A request for (0,2,0) by Po cannot be granted, even though the resources are available since the resulting state is unsafe.

 

basicittopic

basicittopic

A Computer Science Study for IT students and people of IT community

Leave a Reply