OS Notes
HubFunctions of Operating SystemsHistory of Operating SystemsObjectives of Operating SystemsTypes of Operating Systems — Operating SystemsWhat is an Operating SystemThe Booting ProcessThe KernelOperating System ServicesOperating System StructureSystem CallsUser Mode vs Kernel ModeContext SwitchingInterprocess Communication (IPC)MultithreadingProcess Control Block (PCB)Introduction to ProcessesProcess SchedulingProcess StatesThreadsCritical Section ProblemDining Philosophers ProblemMonitorsMutex LocksProducer-Consumer ProblemReaders-Writers ProblemSemaphoresIntroduction to Process SynchronizationBanker\Deadlock AvoidanceDeadlock DetectionIntroduction to DeadlocksDeadlock PreventionDeadlock RecoveryNecessary Conditions for DeadlockResource Allocation GraphContiguous Memory AllocationDemand PagingMemory Management IntroductionPage Replacement AlgorithmsPagingSegmentationThrashingVirtual Memory — Operating SystemsDisk Scheduling - I/O OptimizationDisk Structure - Physical OrganizationRAID - Redundant Array of Independent DisksSecondary Storage - Persistent StorageStorage Virtualization - Abstract StorageSwap Space Management - Virtual MemoryDirectory StructureFile Allocation MethodsFile ConceptsFile ProtectionFile System ImplementationFile System IntroductionFree Space ManagementDevice DriversDisk Scheduling AlgorithmsDMA - Direct Memory AccessInterruptsI/O HardwareI/O SoftwareCPU Scheduling Interview QuestionsLinux Interview QuestionsMemory Management Interview QuestionsOperating System CheatsheetOperating System Interview Questions — Operating SystemsAndroid Operating System — Operating SystemsEmbedded OS Case StudyiOS Operating System — Operating SystemsLinux ArchitectureWindows ArchitectureGlossary of Terms — Operating SystemsImportant Formulas — Operating SystemsQuick Revision Notes — Operating SystemsRecommended Books — Operating SystemsFCFS Scheduling - First Come First ServedMultilevel Feedback Queue SchedulingMultilevel Queue SchedulingPriority SchedulingRound Robin SchedulingScheduling Algorithm ComparisonCPU Scheduling ConceptsSJF Scheduling - Shortest Job FirstCloud Operating Systems - Architecture and ImplementationDistributed Operating Systems - Design and ConceptsEmbedded Operating Systems - Real-time and Resource-ConstrainedMobile Operating Systems - Android, iOS, and WindowsNetwork Operating Systems - NOS ArchitectureReal-Time Operating SystemsVirtualization - Containers and Virtual MachinesAdvanced Virtualization - Full and Para-virtualizationBasic Linux Commands - Command Line UsageLinux File System - ext4 and othersLinux Introduction - OS OverviewPermissions and Security - Linux SecurityProcess Management in Linux - Process ControlShell Scripting - Bash ProgrammingUser Management - Users and GroupsBankerCPU Scheduling Simulator ProjectMini Operating System ProjectPage Replacement SimulatorShell Scripting ProjectsAccess Control - Permission ModelsAuthentication - User VerificationAuthorization - Access ControlMalware and Threats - Security ThreatsOS Security Basics - Threats and ControlsProtection Mechanisms - Security ImplementationSecurity Best Practices - OS Hardening
Complete explanation of the Banker\
Introduction
Imagine you are a banker with limited cash reserves. Multiple customers have approved credit lines (maximum needs). When a customer requests a loan, you must decide: "If I give this loan, will I still have enough cash to satisfy all other customers if they simultaneously request their full credit limits?" If the answer is yes, you approve the loan. If not, you ask the customer to wait. This is exactly how the Banker's Algorithm works.
The Banker's Algorithm, developed by Edsger Dijkstra in 1965, is the most famous deadlock avoidance algorithm. It handles systems with multiple resource types, each having multiple instances. When a process requests resources, the algorithm determines whether granting the request would leave the system in a safe state.
Data Structures
The algorithm maintains four key data structures. Let n = number of processes, m = number of resource types.
| Available[m] | Vector of available instances of each resource type |
| Maximum[n][m] | Maximum demand of each process for each resource |
| Allocation[n][m] | Resources currently allocated to each process |
| Need[n][m] | Remaining resource need of each process |
| Relationship | Need[i][j] = Maximum[i][j] - Allocation[i][j] |
The Safety Algorithm
This algorithm checks whether the current state is safe (a safe sequence exists):
Example
// Safety Algorithm
int is_safe_state() {
int Work[m], Finish[n];
// Step 1: Initialize
for (int j = 0; j < m; j++)
Work[j] = Available[j];
for (int i = 0; i < n; i++)
Finish[i] = 0; // false
// Step 2: Find a process that can finish
int found;
do {
found = 0;
for (int i = 0; i < n; i++) {
if (!Finish[i]) {
// Check if Need[i] <= Work
int can_finish = 1;
for (int j = 0; j < m; j++) {
if (Need[i][j] > Work[j]) {
can_finish = 0;
break;
}
}
if (can_finish) {
// Step 3: Process i can finish
for (int j = 0; j < m; j++)
Work[j] += Allocation[i][j];
Finish[i] = 1; // true
found = 1;
// Record i in safe sequence
}
}
}
} while (found);
// Step 4: Check if all finished
for (int i = 0; i < n; i++)
if (!Finish[i]) return 0; // UNSAFE
return 1; // SAFE
}
The Resource Request Algorithm
When process Pi makes a request Request[i]:
Example
int resource_request(int i, int Request[]) {
// Step 1: Validate request
for (int j = 0; j < m; j++) {
if (Request[j] > Need[i][j]) {
printf("Error: Request exceeds declared maximum!\n");
return ERROR;
}
}
// Step 2: Check if resources are available
for (int j = 0; j < m; j++) {
if (Request[j] > Available[j]) {
// Resources not available — process must wait
return WAIT;
}
}
// Step 3: Tentatively allocate
for (int j = 0; j < m; j++) {
Available[j] -= Request[j];
Allocation[i][j] += Request[j];
Need[i][j] -= Request[j];
}
// Step 4: Check if resulting state is safe
if (is_safe_state()) {
return GRANTED; // Keep the allocation
} else {
// Rollback — restore old state
for (int j = 0; j < m; j++) {
Available[j] += Request[j];
Allocation[i][j] -= Request[j];
Need[i][j] += Request[j];
}
return WAIT; // Process must wait
}
}
Complete Worked Example
System with 5 processes (P0-P4) and 3 resource types (A=10, B=5, C=7 total instances):
Initial State
| Process | Allocation (A B C) | Maximum (A B C) | Need (A B C) |
|---|---|---|---|
| P0 | 0 1 0 | 7 5 3 | 7 4 3 |
| P1 | 2 0 0 | 3 2 2 | 1 2 2 |
| P2 | 3 0 2 | 9 0 2 | 6 0 0 |
| P3 | 2 1 1 | 2 2 2 | 0 1 1 |
| P4 | 0 0 2 | 4 3 3 | 4 3 1 |
Available = Total - Sum(Allocation) = (10,5,7) - (7,2,5) = (3, 3, 2)
Finding the Safe Sequence
Work = (3, 3, 2), Finish = [F, F, F, F, F]
Iteration 1: Check each process:
- P0: Need(7,4,3) ≤ Work(3,3,2)? 7>3, NO
- P1: Need(1,2,2) ≤ Work(3,3,2)? Yes! P1 can finish.
- Work = (3,3,2) + (2,0,0) = (5, 3, 2), Finish[P1] = T
Iteration 2:
- P0: Need(7,4,3) ≤ Work(5,3,2)? 7>5, NO
- P2: Need(6,0,0) ≤ Work(5,3,2)? 6>5, NO
- P3: Need(0,1,1) ≤ Work(5,3,2)? Yes! P3 can finish.
- Work = (5,3,2) + (2,1,1) = (7, 4, 3), Finish[P3] = T
Iteration 3:
- P0: Need(7,4,3) ≤ Work(7,4,3)? Yes! P0 can finish.
- Work = (7,4,3) + (0,1,0) = (7, 5, 3), Finish[P0] = T
Iteration 4:
- P2: Need(6,0,0) ≤ Work(7,5,3)? Yes! P2 can finish.
- Work = (7,5,3) + (3,0,2) = (10, 5, 5), Finish[P2] = T
Iteration 5:
- P4: Need(4,3,1) ≤ Work(10,5,5)? Yes! P4 can finish.
- Work = (10,5,5) + (0,0,2) = (10, 5, 7), Finish[P4] = T
All processes finished! Safe sequence: P1 → P3 → P0 → P2 → P4
Now: P1 Requests (1, 0, 2)
Check: Request(1,0,2) ≤ NeedP1? Yes (1≤1, 0≤2, 2≤2) Check: Request(1,0,2) ≤ Available(3,3,2)? Yes (1≤3, 0≤3, 2≤2)
Tentatively allocate:
- Available = (3,3,2) - (1,0,2) = (2, 3, 0)
- Allocation[P1] = (2,0,0) + (1,0,2) = (3, 0, 2)
- Need[P1] = (1,2,2) - (1,0,2) = (0, 2, 0)
Run safety algorithm on new state... (I will spare the details but the sequence P1→P3→P0→P2→P4 still works)
Result: SAFE → Request GRANTED
Time Complexity
- Safety Algorithm: O(n² × m) — for each of n iterations, check n processes across m resources
- Resource Request: O(n² × m) — dominated by the safety check
For a system with 100 processes and 10 resource types, this is 100,000 operations per request — fast enough for most systems.
Limitations of the Banker's Algorithm
- Maximum needs must be declared in advance — Many processes do not know this
- Fixed number of processes — Processes cannot dynamically enter/leave
- Fixed number of resources — Devices cannot be added/removed
- Processes must eventually terminate — Infinite loops break the assumption
- Conservative — May deny safe requests, reducing utilization
Key Takeaways
- The Banker's Algorithm decides whether granting a resource request keeps the system safe
- It maintains Available, Maximum, Allocation, and Need matrices
- The Safety Algorithm finds if a safe sequence exists by simulating process completions
- A request is granted only if the resulting state remains safe; otherwise, the process waits
- Time complexity is O(n²×m), practical for moderate system sizes
- Main limitation: requires advance declaration of maximum resource needs
- Despite limitations, it is the definitive example of deadlock avoidance in OS education
Exam Focus
Revise definitions, diagrams, examples, and short-answer points for Banker\.
Interview Use
Prepare one clear explanation, one practical example, and one common mistake for this Operating Systems topic.
Search Terms
operating-systems, operating systems, operating, systems, deadlocks, bankers, algorithm, banker\
Related Operating Systems Topics
Continue learning this concept
DeadlocksDeadlock AvoidanceUnderstanding deadlock avoidance through safe state analysis, safe sequences, and the concept of unsafe states that may lead to deadlock. Foundation for the Banker\DeadlocksDeadlock DetectionAlgorithms for detecting deadlocks in operating systems including single-instance detection using wait-for graphs, multi-instance detection algorithm, and when to invoke detection.DeadlocksIntroduction to DeadlocksUnderstanding deadlocks in operating systems — what they are, why they occur, real-world examples, system model, and overview of handling strategies including prevention, avoidance, and detection.DeadlocksDeadlock PreventionStrategies for deadlock prevention by eliminating each of the four necessary conditions: mutual exclusion, hold and wait, no preemption, and circular wait with practical implementation approaches.DeadlocksDeadlock RecoveryMethods for recovering from deadlocks including process termination strategies, resource preemption, rollback mechanisms, and selecting victim processes for minimum cost recovery.DeadlocksNecessary Conditions for DeadlockThe four necessary conditions for deadlock: mutual exclusion, hold and wait, no preemption, and circular wait. Detailed explanation with examples of each condition.