Bankers Algorithm
Data Structures
For a system with n processes and m resource types:
1. Available[m]
o Vector of length m.
o Available[j] = number of available instances of resource type Rj.
2. Max[n][m]
o Matrix of maximum demand of each process.
o Max[i][j] = maximum demand of process Pi for resource Rj.
3. Allocation[n][m]
o Matrix of resources currently allocated.
o Allocation[i][j] = number of instances of Rj allocated to process Pi.
4. Need[n][m]
o Remaining resource needs.
o Need[i][j] = Max[i][j] – Allocation[i][j].
Algorithms
1. Safety Algorithm
Determines if system is in a safe state.
Input: Available, Max, Allocation, Need.
Output: Is the system safe? Safe sequence if it exists.
Steps:
1. Work = Available; Finish[i] = false for all i.
2. Find an index i such that:
o Finish[i] == false
o Need[i] ≤ Work
3. If found:
o Work = Work + Allocation[i]
o Finish[i] = true
o Repeat step 2.
4. If all Finish[i] == true → system is in a safe state.
2. Resource-Request Algorithm
Executed when process Pi requests resources Request[i].
1. If Request[i] ≤ Need[i] → valid. Else → error.
2. If Request[i] ≤ Available → may proceed. Else → wait.
3. Pretend to allocate:
4. Available = Available – Request[i]
5. Allocation[i] = Allocation[i] + Request[i]
6. Need[i] = Need[i] – Request[i]
7. Run Safety Algorithm:
o If safe → grant request.
o Else → rollback, make Pi wait.
