Banker's Algorithm

Deadlock Avoidance in C

Goal:

Determine whether a given system is in a safe or unsafe state by comparing process resource allocation with maximum needs and available resources.

Overview of Banker's Algorithm:

Banker's Algorithm is a deadlock avoidance algorithm to make sure resource allocation does not enter an unsafe state.

In the input.txt

you provide the amount of processes, amount of resource types, as well as the allocation and max resources of each type for each process. Lastly it includes the remaining resources left after allocations.

The algorithm works by

first calculating the need matrix which is Max minus Allocation. Next it finds processes who's max needs do not exceed the available resources. for each one it finds, it will add its allocation back to available and mark that process as finished (and keeping track of the order processes are completed).

In conclusion,

if all processes can eventually run, the system is in a safe state. If at any point no runnable process exists, the system is in an unsafe state.

Compiling and running

Compile:

gcc main.c -o banker

Run:

./banker input.txt

Input.txt File Format:

process_count resource_count

MAX_P0_A MAX_P0_B MAX_P0_C
...
MAX_P4_A MAX_P4_B MAX_P4_C

ALLOC_P0_A ALLOC_P0_B ALLOC_P0_C
...
ALLOC_P4_A ALLOC_P4_B ALLOC_P4_C

AVAILABLE_A AVAILABLE_B AVAILABLE_C

Example

Input.txt

5 3 7 5 3 3 3 2 9 0 2 2 2 2 4 3 3 0 1 0 2 0 0 3 0 2 2 2 1 0 0 2 3 2 2

Console output

Result

The system is in a safe state, with the safe sequence: P3 P4 P1 P2 P0.