Safety Algorithm

We can now present the algorithm for finding out whether or not a system is in a safe state. This algorithm can be described as follows:

1. Let Work and Finish be vectors of length m and n, respectively. Initialize Work = Available and Finish[i] = false for i = 0, 1, .., n − 1.
2. Find an index i such that both a. Finish[i] == false b. Need(i) ≤ Work If no such I exists, go to step 4.
3. Work = Work + Allocation Finish[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 m × n^2 operations to determine whether a state is safe.

Resource-Request Algorithm

Next, we describe the algorithm for determining whether requests can be safely granted.

Let Request(i) be the request vector for process P(i). If Request(i) [j] == k, then process P(i) wants k instances of resource type R(j). When a request for resources is made by process P(i), the following actions are taken:

1. If Request(i) ≤ Need(i) , go to step 2. Otherwise, raise an error condition, since the process has exceeded its maximum claim.

2. If Request(i) ≤ Available, go to step 3. Otherwise, P(i) must wait, since the resources are not available.

3. Have the system pretend to have allocated the requested resources to process P(i) 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 P(i) is allocated its resources. However, if the new state is unsafe, then P(i) must wait for Request(i), and the old resource-allocation the state is restored.