# Safety Algorithm & Resource-Request Algorithm

**Safety Algorithm**

The algorithm for finding out whether or not a system is in a safety algorithm can be described as follows:

- Let
*Work*and*Finish*be vectors of length*m*and*n,*respectively. Initialize

* Work *:= *Available *and *Finisk[i] :=false *for *i *= 1,2, …, *n.*

- Find an
*i*such that both a.*Finisk[i] =false* *Need*_{i}__<__*Work.*

If no such ** i **exists, go to step 4.

*Work*:=*Work*+*Allocation*_{i}

* Finisk[i] *:= *true*

go to step 2.

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

This algorithm may require an order of *m *x *n ^{2} *operations to decide whether a state is safe.

** **

**Resource-Request Algorithm**

** **Let *Request *be the request vector for process *Pi. *If *Request _{i}[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:

- If
*Request*__<__*Need,*go to step 2. Otherwise, raise an error condition, since the process has

exceeded its maximum claim.

- If
*Request*__<__*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_{i};

Allocation_{i} := Allocation_{i} + Request_{i};

Need_{i} := Need_{i} – Request_{i};

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.