🧠 Banker’s Algorithm — Class Notes
📘 Introduction
The Banker’s Algorithm is a resource allocation and deadlock avoidance algorithm
developed by Edsger Dijkstra.
It ensures that the system will never enter a deadlock state by simulating resource
allocation in advance and checking if the system remains in a safe state.
🎯 Objective
To allocate resources to processes in a way that avoids deadlock, ensuring that there is
always a sequence in which all processes can complete.
⚙️Key Concepts
Term Meaning
Processes (P1, P2, …, Pn) Active programs requesting resources
Resources (R1, R2, …, Rm) Types of resources (e.g., CPU cycles, memory blocks, I/O devices)
Available Number of available resources of each type
Max Maximum demand of each process
Allocation Currently allocated resources for each process
Need Remaining resource need for each process (Need = Max – Allocation)
🧩 Data Structures Used
Name Description Example
Vector of length m showing available resources of each
Available[m] Available = [3, 2, 2]
type
Max[n][m] Matrix showing the maximum demand of each process Max[P1] = [7, 5, 3]
Allocation[n][m] Matrix showing current resource allocation Allocation[P1] = [0, 1, 0]
Need[n][m] Matrix showing remaining needs of each process Need[P1] = [7, 4, 3]
📊 Formula
[
Need[i][j] = Max[i][j] - Allocation[i][j]
]
🔍 Steps in Banker’s Algorithm
1. Safety Algorithm (Check if System is Safe)
1. Initialize:
o Work = Available
o Finish[i] = false for all i
2. Find an i such that:
o Finish[i] == false
o Need[i] <= Work
3. If found:
o Work = Work + Allocation[i]
o Finish[i] = true
4. Repeat until all processes are finished.
5. If all Finish[i] == true, → System is in a safe state.
2. Resource Request Algorithm
When process Pi requests resources Request[i]:
1. If Request[i] <= Need[i] → proceed. Else, error.
2. If Request[i] <= Available → proceed. Else, wait.
3. Pretend to allocate:
o Available = Available - Request[i]
o Allocation[i] = Allocation[i] + Request[i]
o Need[i] = Need[i] - Request[i]
4. Run the Safety Algorithm.
o If safe → grant request.
o If unsafe → rollback.
💻 Example Table
Process Allocation Max Available Need
P1 [0, 1, 0] [7, 5, 3] [3, 3, 2] [7, 4, 3]
P2 [2, 0, 0] [3, 2, 2] [1, 2, 2]
Process Allocation Max Available Need
P3 [3, 0, 2] [9, 0, 2] [6, 0, 0]
P4 [2, 1, 1] [2, 2, 2] [0, 1, 1]
P5 [0, 0, 2] [4, 3, 3] [4, 3, 1]
✅ Safe sequence example:
→ P2 → P4 → P5 → P1 → P3
🧮 Advantages
Avoids deadlock by careful pre-checks.
Ensures safe system states.
Works well when the number of resources and processes are known in advance.
⚠️Disadvantages
Complex and time-consuming for large systems.
Requires advance knowledge of maximum resource needs.
Low resource utilization if processes request maximum unnecessarily.
Not suitable for real-time systems.
📚 Real-Life Analogy (Bank Example)
A banker (system) loans money (resources) to customers (processes).
Before granting a loan, the banker checks whether all customers can still withdraw
(complete) in the future — ensuring the bank never runs out of money (no deadlock).
🧾 Summary Table
Concept Description
Algorithm Type Deadlock avoidance
Developed By Edsger Dijkstra
Key Idea Grant requests only if system remains in safe state
Components Allocation, Max, Need, Available
Concept Description
Limitation Requires maximum claim in advance
💻 Java Program: Banker's Algorithm Implementation
/*
* Program: Banker's Algorithm in Java
* Author : [Your Name]
* Description:
* This program implements the Banker's Algorithm for
* Deadlock Avoidance in Operating Systems.
*
* It checks if the system is in a safe state and determines
* a safe sequence for process execution.
*/
import java.util.Scanner;
public class BankersAlgorithm {
// Number of processes and resources
private int n; // processes
private int m; // resources
private int[][] allocation; // Allocation Matrix
private int[][] max; // Maximum Demand Matrix
private int[][] need; // Need Matrix
private int[] available; // Available Resources
public BankersAlgorithm(int n, int m) {
this.n = n;
this.m = m;
allocation = new int[n][m];
max = new int[n][m];
need = new int[n][m];
available = new int[m];
}
// Calculate Need Matrix
private void calculateNeed() {
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
need[i][j] = max[i][j] - allocation[i][j];
}
}
}
// Safety Algorithm
private boolean checkSafeState() {
boolean[] finish = new boolean[n];
int[] work = new int[m];
int[] safeSequence = new int[n];
int count = 0;
// Initialize work as available
System.arraycopy(available, 0, work, 0, m);
while (count < n) {
boolean found = false;
for (int i = 0; i < n; i++) {
if (!finish[i]) {
int j;
for (j = 0; j < m; j++) {
if (need[i][j] > work[j]) {
break;
}
}
if (j == m) { // All needs can be satisfied
for (int k = 0; k < m; k++) {
work[k] += allocation[i][k];
}
safeSequence[count++] = i;
finish[i] = true;
found = true;
}
}
}
if (!found) {
System.out.println("\nSystem is NOT in a safe state!");
return false;
}
}
System.out.print("\nSystem is in a SAFE state.\nSafe sequence: ");
for (int i = 0; i < n; i++) {
System.out.print("P" + safeSequence[i]);
if (i < n - 1) System.out.print(" → ");
}
System.out.println();
return true;
}
// Main Method
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.print("Enter number of processes: ");
int n = sc.nextInt();
System.out.print("Enter number of resources: ");
int m = sc.nextInt();
BankersAlgorithm ba = new BankersAlgorithm(n, m);
System.out.println("\nEnter Allocation Matrix:");
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
ba.allocation[i][j] = sc.nextInt();
System.out.println("\nEnter Maximum Demand Matrix:");
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
ba.max[i][j] = sc.nextInt();
System.out.println("\nEnter Available Resources:");
for (int j = 0; j < m; j++)
ba.available[j] = sc.nextInt();
// Compute Need matrix
ba.calculateNeed();
System.out.println("\nNeed Matrix:");
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
System.out.print(ba.need[i][j] + " ");
}
System.out.println();
}
// Check if system is in safe state
ba.checkSafeState();
sc.close();
}
}
🧩 Example Input & Output
Input
Enter number of processes: 5
Enter number of resources: 3
Enter Allocation Matrix:
0 1 0
2 0 0
3 0 2
2 1 1
0 0 2
Enter Maximum Demand Matrix:
7 5 3
3 2 2
9 0 2
2 2 2
4 3 3
Enter Available Resources:
3 3 2
Output
Need Matrix:
7 4 3
1 2 2
6 0 0
0 1 1
4 3 1
System is in a SAFE state.
Safe sequence: P1 → P3 → P4 → P0 → P2
🧠 Explanation
The program first calculates the Need Matrix.
Then it applies the Safety Algorithm to verify if the system is in a safe state.
If yes, it prints a safe sequence for process execution; otherwise, it declares that the
system is unsafe.
