Banker's Algorithm

CSC-264 · Semester IV · Operating Systems

intermediate30 minAvailable

Banker's Algorithm

Check whether the system is in a safe state and find a safe sequence.

Available

A: 3B: 3C: 2

Process	Allocation	Max	Need
P0			743
P1			122
P2			600
P3			011
P4			431

Lab brief

Objective

Compute Need, run the safety algorithm, and decide whether resource requests can be granted without risking deadlock.

Theory & concepts

The banker's algorithm answers two questions. Is the current state safe? And can a given request be granted? Safety means: can every process still finish even if all of them demand their maximum? The check uses Available, Max, Allocation and Need = Max - Allocation.

Rendering diagram…

The banker's algorithm decision path for each request

Work = Available; Finish[i] = false for all i
repeat: find i with !Finish[i] and Need[i] <= Work
        then Work += Allocation[i], Finish[i] = true
safe iff all Finish[i] are true

a request is granted only if the state after granting is still safe

The catch

A process that looks 'finishable' may still deadlock later if it is never scheduled in time — the safety algorithm only proves that a finishing order exists, not that one will be chosen.

Prerequisites

Lesson: Banker's algorithm
Lesson: Deadlock prevention and avoidance

Instructions

1Read the given Allocation, Max and Available tables.
2Compute the Need matrix and check it against the system.
3Run the safety algorithm to find a safe sequence.
4Submit a resource request and observe whether it is granted or denied.

Tasks

Compute Need
Verify Need = Max - Allocation for every process.
Find a safe sequence
Use the safety algorithm on the classic 5-process example.
Evaluate a request
Test Request = (1, 0, 2) and explain the outcome.
Create an unsafe state
Reduce Available and show which request must now be denied.

Self-check

Need values are computed correctly.
The safe sequence is valid and matches the algorithm's output.
The student explains why a denied request would make the state unsafe.

Environment

matrix editorsafety algorithm runnerrequest evaluatorstep-by-step trace