Banker's Algorithm

C++ implementation of the Banker's deadlock-avoidance algorithm, written for the Kent State Operating Systems course (2023).

What the Banker's algorithm does

The Banker's algorithm determines whether granting a resource request leaves the system in a safe state. A safe state is one where there exists at least one execution order (a safe sequence) in which every process can eventually obtain all the resources it needs, finish, and release those resources back to the pool. If no such sequence exists, the request is denied to prevent deadlock.

The algorithm computes a need matrix (need[i][j] = max[i][j] - alloc[i][j]) and then simulates allocating resources to each unfinished process in turn, checking whether its needs can be satisfied by the current available pool. Each time a process finishes in the simulation, its allocated resources return to the pool. If all processes finish, the state is safe.

This implementation

• Processes: 5 (P0 through P4)
• Resource types: 3
• Input: input.txt containing the allocation matrix (5x3), the max matrix (5x3), and the available resource vector (1x3)
• Output: either the safe sequence (P1 -> P3 -> ...) or a message that the system is not in a safe state

Input format

input.txt lists three blocks of space-separated integers in order: allocation matrix, max matrix, available resources. No labels or separators.

# Allocation matrix (5 processes x 3 resource types)
0 1 0
2 0 0
3 0 2
2 1 1
0 0 2
# Max matrix (5 processes x 3 resource types)
7 5 3
3 2 2
9 0 2
2 2 2
4 3 3
# Available resources (3 resource types)
3 3 2

The included input.txt produces the safe sequence P1 -> P3 -> P4 -> P0 -> P2.

Build and run

Requires g++ with C++11 or later.

g++ -std=c++11 -o bankers bankersAlgorithm.cpp
./bankers

The program reads input.txt from the current directory. Edit that file to test different system states.