Banker's Algorithm In Operating System
The Banker’s Algorithm is a classic deadlock-avoidance algorithm used in operating systems to allocate resources safely to multiple processes. It ensures the system never enters an unsafe state, thereby preventing deadlocks.
- Deadlock-avoidance algorithm that allocates resources only if the system will remain in a safe state.
- It Used for deadlock avoidance (not prevention or detection).
- The Banker's Algorithm is a smart way for computer systems to manage how programs use resources, like memory or CPU time.
Safe State
The system is in a safe state if there exists at least one safe sequence of all processes where:
- Each process can obtain all the resources it needs.
- Finish its execution,
- Release its resources for others.
Unsafe State
The system is in an unsafe state if no safe sequence exists. An unsafe state means the system cannot guarantee that all processes will finish without deadlock. It does not mean a deadlock has already occurred, but deadlock is possible if processes request their
Data Structures of Banker's Algorithm
The following Data structures are used to implement the Banker’s Algorithm: Let 'n' be the number of processes in the system and 'm' be the number of resource types.
1. Available[m]:
- It is a 1-D array of size 'm' indicating the number of resources available in the system.
2. Max[n][m]:
- It is a 2-d array of size 'n*m' that defines the maximum demand of each process in a system.
3. Allocation[n][m]:
- It is a 2-d array of size 'n*m' that defines the number of resources of each type currently allocated to each process.
4. Need[n][m]:
- It is a 2-d array of size 'n*m' that indicates the remaining resource need of each process.
- Need = Max - Allocation
Examples:
Example 1: We have 3 types of resources A, B,C And 5 processes (P0-P4). Total resources in the system: A=10, B=5, C=7.
| Process | Max (A,b,c) | Allocation (A,b,c) |
|---|---|---|
| P0 | 7,5,3 | 0,1,0 |
| P1 | 3,2,2 | 2,0,0 |
| P2 | 9,0,2 | 3,0,2 |
| P3 | 2,2,2 | 2,1,1 |
| P4 | 4,3,3 | 0,0,2 |
First, calculate total Allocation Resources: (10-(0+2+3+2+0), 5-(1+0+0+1+0) = 7-(0+0+2+1+2))=(10-7, 5-2, 7-5) = 3, 3, 2
Now calculate need for all process
| Process | Nedd(MAX-Allocation) |
|---|---|
| P0 | 7,4,3 |
| P1 | 1,2,2 |
| P2 | 6,0,0 |
| P3 | 0,1,1 |
| P4 | 4,3,1 |
Safety check sequence:
Find any process with Need ≤ Available.
Currently, the available resources are (3,3,2).
We find that P1 and P3 both have their needs less than or equal to the available resources. We can pick either P1 or P3 first and still reach a safe sequence.
Let’s pick P1 first.
- P1 (Need = 1,2,2) ≤ (3,3,2)
- Finish P1, add its Allocation to Available: (3+2, 3+0, 2+0) = (5,3,2)
- Now available resources=5,3,2
Next, find another process with Need ≤ Available. We find P3 and P4 satisfy this.
Let’s pick P3.
- P3 (Need = 0,1,1) < (5,3,2)
- Available = (2+5,1+3,1+2) = (7,4,3)
With the new available resources (7,4,3), we find P0, P2, and P4 can all proceed:
- P0 (Need = 7,4,3) ≤ (7,4,3)
- Available = (7,5,3)
- P2 (Need = 6,0,0) ≤ (7,5,3)
- Available = (10,5,5)
- P4 (Need = 4,3,1) ≤ (10,5,5)
All can finish. Safe sequence: P1 → P3 → P0 → P2 → P4.
Other valid sequences include:
- P3 → P1 → P0 → P2 → P4
- P1 → P3 → P2 → P0 → P4
- …and others, depending on which ready process is chosen first.
Advantages
- Prevents deadlocks completely.
- Maximizes resource utilization while keeping the system safe.
Disadvantages
- Requires each process to declare maximum resource requirements in advance.
- Overhead: system must check for safety after every request.
- Not suitable when resource needs are unpredictable or when the number of processes/resources changes frequently.