The Banker’s algorithm, developed by Edsger Dijkstra, is a resource allocation and
deadlock avoidance algorithm.
When a new process enters a system, it must declare the maximum number of instances of each
resource type that it may ever claim; clearly, that number may not exceed the total number of
resources in the system. Also, when a process gets all its requested resources it must return them in
a finite amount of time.
For the Banker's algorithm to work, it needs to know three things:
• How much of each resource each process could possibly request ("MAX")
• How much of each resource each process is currently holding ("ALLOCATED")
• How much of each resource the system currently has available ("AVAILABLE")
Resources may be allocated to a process only if the amount of resources requested is less than or
equal to the amount available; otherwise, the process waits until resources are available. Let n be the
number of processes in the system and m be the number of resource types. Then 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 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 Pi may need k more instances of resource type Rj to complete the task.
Also, Need[i, j] = Max[i, j] – Allocation[i, j]