The Banker’s algorithm is a resource allocation & deadlock avoidance algorithm developed by Edsger Dijkstra that test for safety by simulating the allocation of pre-determined maximum possible amounts of all resources. Then it makes a “safe-state” check to test for possible deadlock conditions for all other pending activities, before deciding whether allocation should be allowed to continue.
The Banker’s algorithm is run by the operating system whenever a process requests resources. The algorithm prevents deadlock by denying or postponing the request if it determines that accepting the request could put the system in an unsafe state (one where a deadlock could occur).
For the Banker’s algorithm to work, it needs to know three things:
- How much of each resource could possibly request by each process?
- How much of each resource is currently holding by each process?
- How much of each resource the system currently has available.
Resources may be allocated to a process only if it satisfies the following conditions:
- request ≤ max, else set error as the process has crossed maximum claim made by it.
- request ≤ available, else process waits until resources are available.
Several data structures must be maintained to implement the banker’s algorithm. These data structures encode the state of the resource allocation system. Let n be the number of processes in the system and m be the number of resource types. We need the following data structures:
Available: A vector of length m indicates the number of available resources of each type. If Available[j] = k, there are k instances of resource type Rj available.
Max: An n x m matrix defines the maximum demand of each process. If Max[i,j] = k, then process Pi may request at most k instances of resource type Rj.
Allocation: An n x m matrix defines the number of resources of each type currently allocated to each process. If Allocation[i,j] = k, then process Pi is currently allocated k instances of resource type Rj.
Need: An n x m matrix indicates the remaining resource need of each process. If Need[i,j] = k, then process Pi may need k more instances of resource type Ri to complete its task. Note that Need[i,j] = Max[i,j] – Allocafion[i,j].
These data structures vary over time in both size and value. The vector Allocation specifies the resources currently allocated to process Pi; the vector Needi specifies the additional resources that process Pi may still request to complete its task.