Operating System - Banker’s Algorithm

 What is the Banker’s Algorithm?

The Banker’s Algorithm helps the system decide whether to grant or deny resource requests in a way that avoids entering an unsafe state, which could lead to deadlock.Named after a bank that lends money to customers (processes), only if it’s sure it can fulfill all obligations safely in the worst-case scenario.

 Data Structures

For n processes and m resource types, we use:

  1. Available[ ] – Resources available of each type

  2. Max[ ][ ] – Maximum resources each process may need

  3. Allocation[ ][ ] – Resources currently allocated

  4. Need[ ][ ] – Remaining need = Max - Allocation

 Safe State Check (Simplified Algorithm Steps)

  1. Work = Available (temporary copy of available resources)

  2. Finish[i] = false for all processes

  3. Find a process i such that:

    • Finish[i] == false

    • Need[i] <= Work

  4. If found:

    • Pretend it finishes: Work += Allocation[i]

    • Finish[i] = true

    • Repeat Step 3

  5. If all processes can finish (Finish[i] = true for all), the system is in a safe state

 Example

 System:

  • Processes: P0, P1, P2

  • Resources: A, B, C (3 types)

  • Available: A = 3, B = 3, C = 2

 Given Tables:

Max Matrix

Process A B C
P0 7 5 3
P1 3 2 2
P2 9 0 2

Allocation Matrix

Process A B C
P0 0 1 0
P1 2 0 0
P2 3 0 2

Need Matrix (Max - Allocation)

Process A B C
P0 7 4 3
P1 1 2 2
P2 6 0 0

 Step-by-Step Safe State Check

Start with: Work = [3, 3, 2]
Finish = [false, false, false]

  1. Check P1: Need = [1, 2, 2] <= Work [3,3,2] ✅

    • Work becomes: Work = Work + Allocation[P1] = [5, 3, 2]

    • Finish[1] = true

  1. Check P0: Need = [7,4,3] > Work = [5,3,2] ❌

  2. Check P2: Need = [6,0,0] > Work = [5,3,2] ❌

→ Only P1 can finish at this point

  1. No other process can finish → System is not in a safe state

 Unsafe State → Deny Request

If a resource request would lead to this situation, the system denies the request to avoid potential deadlock.

Benefits

  • Avoids entering deadlocks by pre-checking every request

  • Guarantees system safety

 Limitations

  • Requires advance knowledge of maximum resource needs

  • Complex and expensive to implement in large systems