Banker's algorithm

From Free net encyclopedia

This page deals with deadlock avoidance. For rounding to nearest even, see Banker's rounding

The banker's algorithm is a theoretical approach avoiding deadlocks in resource scheduling. It requires resource usage limit to be known in advance. This fact is generally not known in practice.

It is usually explained using an analogy to a bank behaviour. The customers are computer processes, money is the resources, and each customer has a credit limit. The banker is the operating system.

The bank relies on that it won't have to allow everyone to maximize their credit at once. The bank further assumes that if a customer maximizes its credit he will be able to finish his business affairs and return all the money back to the bank allowing the bank to serve other customers.

The algorithm keeps the system in a safe state. A system is in a safe state if there is an order in which the resource requests for all processes can eventually be granted, preventing deadlock. The Banker's algorithm works by finding one such state.

Processes ask for resources, they are provided only if the system would remain in the safe state, otherwise the process is suspend until other processes release enough resources.

More formally speaking, a system is in a safe state if there exists a safe sequence. A safe sequence is a set of processes, <<math>P_1,...,P_n</math>>, such that for a process <math>P_i</math>, the resource request for <math>P_i</math> can be satisfied with the currently available resources plus the resources that are held by <math>P_j</math>, where j < i. If there are not enough resources for process <math>P_i</math>, then process <math>P_i</math> can wait until process <math>P_j</math> finishes and releases its resources. Once process <math>P_j</math> finishes and releases its resources, process <math>P_i</math> can then be allocated all its resources, do what it needs to do, release its resources, and terminate. Once process <math>P_i</math> terminates, process P_i+1 can be allocated the resources it needs and do the job it needs to do and so on. If no such sequence exists, then the system is said to be in an unsafe state, though not necessarily deadlocked.

1 Data structures and complexity
2 Safety Algorithm
3 Resource Request Algorithm
4 Reference

[edit]

Data structures and complexity

You then use four arrays: available, allocation, maximum, and need.

Working of banker's algorithm:

Four arrays are used to store the following information in them:

Available [<math>m</math>]: This array stores the total number of available resources for each type, available or allotted both. Available[j] = k means there are k instances of resource type R_j available.
Allocation [<math>m \times n</math>]: or Current Allocation. This array stores the current allocation of each resource type to each process. Allocation [i][j] = k means process P_i has been allocated k instances of resource type R_j.
Maximum Allocation [<math>m \times n</math>]: This array stores the maximum resource demand of each process. Maximum[i][j] = k means process P_i can request at most k instances of resource type R_j.
Need Allocation [<math>m \times n</math>]: This array specifies the needed resource for each process. Need[i][j] = k means process P_i needs k more instances of resource type R_j. It is calculated by subtracting the Maximum Allocation with Current Allocation matrices: Need[i][j] = Maximum[i][j] - Allocation [i][j].

[edit]

Safety Algorithm

The safety algorithm determines whether or not a system is in a safe state.

Let Work and Finish be arrays of length m and n, respectively. Initialize Work to Available and Finish[i] = false, for i = 0, 1,...., n - 1.
Find an i such that
1. Finish[i] == false
2. Need_i ≤ Work
If no such i exists, goto step 4, otherwise do
1. Work = Work + Allocation_i
2. Finish_i = true
3. goto step 2
If Finish[i] == true for all i, then system is in a safe state.

In terms of little O notation, the banker's algorithm is O(n² × m), where n is the processes and m is the resources.

[edit]

Resource Request Algorithm

The resource request algorithm determines whether a resource request can be safely granted. The algorithm is executed by the system whenever a request for resources is made by a process.

Let Request_i be the request array for process P_i. If Request[i][j] == k, then process P_i wants k instances of resource type R_j.

If Request_i > Need_i then raise an error since a process is attempting to request more then its maximum resource claim.
If Request_i > Available_i then block proccess P_i since there are not enough resources to satisfy proccess P_i.
Have the system pretend to allocate the resource to the process by modifying the state as follows:
1. Available = Available - Request_i
2. Allocation_i = Allocation_i + Request_i
3. Need_i = Need_i - Request_i

If the resulting resource allocation state is safe, then the changes are committed and the process is allowed its requested resources. Otherwise, the resulting state is unsafe so the old state is restored and the requesting process, P_i has to wait for Request_i.

[edit]