The Banker's Algorithm: Deadlock Avoidance in Operating Systems

Verified Sources

May 28, 2026

In multi-programmed computer systems, processes share resources such as CPU, memory, and I/O devices. When multiple processes request resources simultaneously, a deadlock can occur. To maintain system stability, operating systems employ various strategies, one of the most famous being deadlock avoidance .

The Banker's Algorithm is a classic resource allocation and deadlock avoidance algorithm developed by Edsger Dijkstra in 1965 . It is named after the banking system, where a banker ensures that the bank never runs out of cash to satisfy the needs of its clients, provided they do not all request their maximum credit limits simultaneously.

The algorithm maintains the system in a safe state. If a resource allocation request leads to an unsafe state, the request is denied or deferred, even if the resources are currently free .

Edsger Dijkstra's Banker's Algorithm - Historical background of Dijkstra's resource allocation and deadlock avoidance strategy. ↩ ↩²
Banker's Algorithm - GeeksforGeeks - Explanation of data structures, safety algorithm, and resource request algorithm. ↩

Deadlock Avoidance: Banker's Algorithm with Example

Key Data Structures

To implement the Banker's Algorithm, the operating system maintains several vectors and matrices, where $n$ represents the number of processes and $m$ represents the number of resource types :

Available: A 1D array of size $m$ $m$ indicating the number of available resources of each type.
- If $\text{Available}[j] = k$ , there are $k$ instances of resource type $R_j$ currently unallocated.
Max: A 2D array of size $n \times m$ $n \times m$ defining the maximum demand of each process.
- If $\text{Max}[i][j] = k$ , process $P_i$ may request at most $k$ instances of resource type $R_j$ .
Allocation: A 2D array of size $n \times m$ $n \times m$ defining the number of resources currently allocated to each process .
- If $\text{Allocation}[i][j] = k$ , process $P_i$ is currently holding $k$ instances of resource type $R_j$ .
Need: A 2D array of size $n \times m$ $n \times m$ indicating the remaining resource allocation required by each process.
- This need matrix is calculated using the relation: $\text{Need}[i][j] = \text{Max}[i][j] - \text{Allocation}[i][j]$

Banker's Algorithm - GeeksforGeeks - Explanation of data structures, safety algorithm, and resource request algorithm. ↩ ↩²

The Safety Algorithm

1
Step 1
Let $\text{Work}$ be a vector of length $m$ and $\text{Finish}$ be a vector of length $n$ . Initialize $\text{Work} = \text{Available}$ and $\text{Finish}[i] = \text{false}$ for all $i = 0, 1, \dots, n-1$ .
2
Step 2
Search for an index $i$ such that both:

$\text{Finish}[i] == \text{false}$

$\text{Need}_i \le \text{Work}$

If no such $i$ exists, proceed to Step 4.
3
Step 3
If a process $P_i$ is found, assume it completes its execution and releases its resources. Update the state: $\text{Work} = \text{Work} + \text{Allocation}_i$ $\text{Finish}[i] = \text{true}$

Return to Step 2 to evaluate other processes.
4
Step 4
If $\text{Finish}[i] == \text{true}$ for all $i = 0, 1, \dots, n-1$ , then the system is in a Safe State. If there exists any $i$ where $\text{Finish}[i] == \text{false}$ , the system is in an Unsafe State.

The Resource-Request Algorithm

1
Step 1
Let $\text{Request}_i$ be the request vector for process $P_i$ . If $\text{Request}_i \le \text{Need}_i$ , proceed to Step 2. Otherwise, raise an error condition since the process has exceeded its maximum claim.
2
Step 2
If $\text{Request}_i \le \text{Available}$ , proceed to Step 3. Otherwise, process $P_i$ must wait, as the requested resources are not currently available.
3
Step 3
The operating system temporarily alters the state to simulate the allocation: $\text{Available} = \text{Available} - \text{Request}_i$ $\text{Allocation}_i = \text{Allocation}_i + \text{Request}_i$ $\text{Need}_i = \text{Need}_i - \text{Request}_i$
4
Step 4
Run the Safety Algorithm on the simulated state. If the resulting state is safe, the transaction is completed, and the resources are formally allocated to $P_i$ . If the state is unsafe, the simulation is rolled back, and $P_i$ is forced to wait.

Unsafe State vs. Deadlock

An unsafe state is not equivalent to a deadlock. An unsafe state merely means that the operating system cannot guarantee that a deadlock will not occur. If processes release resources before requesting their maximum limits, the system can still run to completion without deadlocking even starting from an unsafe state. However, a deadlock state is a point of no return where execution is permanently stalled.

The Banker's Algorithm is a [deadlock avoidance]{def='A dynamic method where the OS decides whether to grant a resource request based on whether it keeps the system in a safe state.'} strategy. It requires processes to declare their maximum resource requirements in advance. The OS dynamically checks safety before granting any request, ensuring the system never enters an unsafe state. Time complexity is $O(m \times n^2)$ .

Banker's Algorithm - GeeksforGeeks - Explanation of data structures, safety algorithm, and resource request algorithm. ↩

Resource Profile for Process $P_1$

Comparison of current Allocation, remaining Need, and Max claim for resource types A, B, and C.

Evolution of Deadlock Handling Strategies

Deadlock Prevention

1960s

Early operating systems used static [deadlock prevention]{def='A set of methods that ensure at least one of the four necessary conditions for deadlock cannot hold.'} strategies, such as ordering resource acquisition or requiring all resources to be requested at once. This led to very low resource utilization."

Banker's Algorithm (Avoidance)

1965

Edsger Dijkstra introduced the Banker's Algorithm , shifting the focus to dynamic [deadlock avoidance]{def='A dynamic method where the OS decides whether to grant a resource request based on whether it keeps the system in a safe state.'}. By keeping the system in a safe state, resource utilization improved, though declaring maximum resources in advance remained difficult."

Edsger Dijkstra's Banker's Algorithm - Historical background of Dijkstra's resource allocation and deadlock avoidance strategy. ↩

Detection & Recovery

1970s-1980s

Systems began adopting Detection and Recovery algorithms. Instead of avoiding deadlocks proactively, systems allowed free allocation and ran periodic background checks, recovering via process termination or resource preemption."

The Ostrich Algorithm

Modern Era

Most modern general-purpose operating systems (like Linux, Windows, and macOS) employ the 'Ostrich Algorithm' for deadlocks—ignoring the problem under the assumption that deadlocks occur rarely and the cost of prevention/avoidance is too high."

Practical Limitations

Although elegant in theory, the Banker's Algorithm is rarely used in modern general-purpose operating systems because:

Processes must know and declare their maximum resource needs in advance, which is practically impossible for dynamic applications.
The number of active processes ( $n$ ) and resources ( $m$ ) is assumed to be fixed, whereas modern systems have highly dynamic process creation and destruction.
The algorithm runs with a time complexity of $O(m \times n^2)$ , which is too computationally expensive to run on every single resource request.

Knowledge Check

Question 1 of 4

Q1Single choice

What is the time complexity of the safety algorithm in the Banker's Algorithm, where $n$ is the number of processes and $m$ is the number of resource types?

$O(n \times m)$

$O(n^2 \times m)$

$O(n \times m^2)$

$O(n^3)$

Explore Related Topics

Banker's Algorithm Safe-State Analysis for Processes $P_0$ Through $P_4$

The course walks through a full Banker's‑algorithm safety analysis for processes  $P_0$ – $P_4$ , computing the Need matrix and using the work‑vector test to verify a safe state and a valid completion order.

Need matrix: $P_0\;(0,0,0,0)$ , $P_1\;(0,7,5,0)$ , $P_2\;(1,0,0,2)$ , $P_3\;(0,0,2,0)$ , $P_4\;(0,6,4,2)$ .
Starting work $Work = Available = (1,5,2,0)$ ; each step selects a process with $Need \le Work$ , releases its allocation, and updates $Work$ .
All processes finish, yielding a safe sequence $\langle P_0, P_2, P_1, P_3, P_4\rangle$ .
A safe state requires only one such sequence; it does not mean every immediate allocation is safe.
Exam tip: test processes with minimal or zero Need first to unlock the rest.

Semaphore and the Dining-Philosophers Solution Using Monitors

The content contrasts low‑level semaphores with high‑level monitors and shows how a monitor‑based solution avoids deadlock in the Dining Philosophers problem.

A semaphore offers atomic $wait$ / $signal$ on a counter, but misordered calls can cause deadlock or race conditions.
A monitor bundles shared state with procedures and uses condition variables ( $x.wait()$ , $x.signal()$ ) to wait for logical predicates rather than resource counts.
The monitor algorithm maintains an array $state[i]\in\{THINKING, HUNGRY, EATING\}$ and a condition variable $self[i]$ per philosopher; $test(i)$ grants $EATING$ only if both neighbors are not eating.
Because monitor entry is mutually exclusive and $test$ is invoked on neighbours after $putdown(i)$ , the solution guarantees safety (no adjacent eaters) and deadlock freedom, while starvation freedom depends on fairness of signaling.

Dijkstra's Algorithm

Dijkstra's algorithm finds the shortest‑path distances from a single source to all reachable vertices in a weighted graph whose edge weights are non‑negative, using a greedy selection of the minimum‑distance unsettled vertex and edge relaxation.

Keeps a tentative distance array and a min‑priority queue; extracting the smallest distance finalizes that vertex’s shortest path.
Correct only for non‑negative edges; negative weights invalidate the greedy invariant.
With an adjacency‑list and binary heap the time is O((V+E) log V); matrix scans give O(V²) and Fibonacci heaps can achieve O(E + V log V).
Storing a predecessor array allows reconstruction of actual shortest paths and early termination when a specific target is settled.
Fundamental in routing, navigation, and as a subroutine in many larger graph algorithms.

Research more with Coursify

The Banker's Algorithm: Deadlock Avoidance in Operating Systems

AI Summary

Footnotes

Deadlock Avoidance: Banker's Algorithm with Example

Key Data Structures

Footnotes

The Safety Algorithm

The Resource-Request Algorithm

Unsafe State vs. Deadlock

Footnotes

Resource Profile for Process P1P_1P1​

Evolution of Deadlock Handling Strategies

Deadlock Prevention

Banker's Algorithm (Avoidance)

Footnotes

Detection & Recovery

The Ostrich Algorithm

Practical Limitations

Knowledge Check

Explore Related Topics

Resource Profile for Process $P_1$