COMP 3150Operating Systems

Module 2 · Unit 7 · Lesson 6 of 7

The Banker's Algorithm

The classical algorithm for deadlock avoidance with multi-instance resources. Dijkstra named it after the way a banker manages loans: never lend so much that you cannot satisfy the potential withdrawals of every depositor. The algorithm maintains four matrices and checks, before every request, whether granting it would leave the system in a safe state. It is the most famous algorithm in the deadlock literature — and the most misunderstood.

01 Introduction

Lesson 7.5 introduced the concept of avoidance and the safe state. A state is safe if there exists a sequence in which every process can run to completion; an unsafe state is one from which deadlock is possible. The avoidance strategy is to check each resource request before granting it and defer the request if granting it would lead to an unsafe state. The lesson presented the resource-allocation-graph avoidance algorithm, which works for single-instance resources.

This lesson presents the Banker's algorithm, the classical implementation of avoidance for multi-instance resources. It was published by Edsger Dijkstra in 1968 and refined over the following years. The algorithm takes its name from an analogy Dijkstra used in the original paper: a banker who has a fixed pool of capital must lend money to customers in such a way that the bank is never unable to satisfy every customer's potential withdrawal. The banker cannot lend all the money to a single customer, even if that customer's business would generate more deposits, because the other customers might withdraw their savings in the meantime. The banker must keep enough cash in reserve to cover the potential withdrawals.

The Banker's algorithm applies the same principle to operating-system resources. Each process declares its maximum resource needs at creation — the largest amount of each resource type it will ever request. The operating system maintains a record of each process's current allocation and its remaining need, together with the currently available resources. When a process requests a resource, the algorithm checks whether granting the request would leave the system in a state from which every process can still complete. If the state is safe, the request is granted. If the state would be unsafe, the request is deferred until the system returns to a safe state.

The Banker's algorithm is the most famous algorithm in the deadlock literature, and it is studied in every operating systems course. It is also, in practice, rarely deployed. The reason is the same one we saw in Lesson 7.5: the algorithm requires every process to declare its maximum resource needs in advance, and general-purpose processes cannot do this. Nevertheless, the algorithm is valuable to study because it makes the safe-state concept concrete, and because it illustrates the trade-offs of the avoidance strategy in the multi-instance case where the resource-allocation graph is not sufficient.

This lesson presents the data structures of the algorithm, the safety algorithm that determines whether a state is safe, the resource-request algorithm that decides whether to grant a request, and worked examples that trace the algorithm step by step. It closes with the practical limitations and the reasons the algorithm is not used in general-purpose systems.

Prerequisites

This lesson builds directly on Lessons 7.1–7.5. The system model (resources, processes, requests) and the safe-state concept from Lesson 7.5 are used throughout. The resource-allocation graph from Lesson 7.3 is the single-instance version of what the Banker's algorithm does for multi-instance resources. If the safe-state concept is unfamiliar, review sections 4.1–4.2 of Lesson 7.5 before continuing.

02 Learning objectives

By the end of this lesson you will be able to

  • Describe the four data structures of the Banker's algorithm: Available, Max, Allocation, and Need.
  • Apply the safety algorithm to determine whether a state is safe and to identify a safe sequence.
  • Apply the resource-request algorithm to decide whether a resource request should be granted or deferred.
  • Trace the Banker's algorithm through a worked example with multiple resources and processes.
  • Explain the practical limitations of the Banker's algorithm and why it is not used in general-purpose systems.

This lesson contributes to U7.3 and U7.4, and to course learning outcomes CLO2, CLO3, and CLO8.

03 Required reading

  • Operating System Concepts — Chapter 8, Section 8.6.3, Banker's Algorithm. The standard treatment, including the data structures, the safety algorithm, the resource-request algorithm, and the worked example with five processes and three resource types.
  • Silberschatz et al. — Chapter 8, Section 8.6.3. Read the worked example carefully; the five-process illustration is the canonical example and appears in almost every treatment of the algorithm. Work through the numbers yourself before reading the solution.
  • Dijkstra, E. W. — Cooperating Sequential Processes. In Programming Languages, ed. F. Genuys, Academic Press, 1968. The original publication of the algorithm. The presentation is in terms of a banker and customers; the analogy is worth reading in the original.
  • Habermann, A. N. — Prevention of System Deadlocks. Communications of the ACM, 1969. A related paper that discusses the safe-state concept and refines the algorithm.
  • Tanenbaum & Bos — Modern Operating Systems, Chapter 6, Section 6.5.2, Deadlock Avoidance. A complementary treatment that presents the algorithm from the perspective of the banker's analogy.
  • OSTEP — Chapter 32, Concurrency Bugs, through the section on Deadlock. The practical reasons the algorithm is not used in real systems.

Reading strategy

Read the Silberschatz section first, but work through the worked example on paper before reading the solution. The algorithm is best understood by doing it — the safety algorithm is a simple loop, but the reasoning is subtle, and seeing the numbers move through the matrices is the clearest way to grasp what the algorithm actually does. Then read the Dijkstra paper for the historical context and the banker's analogy. The analogy is not merely decorative: it captures the essential conservatism of the algorithm, which is what makes it correct and what makes it impractical.

04 Core content

4.1 The banker's analogy

Dijkstra's original presentation of the algorithm used an analogy that is worth understanding before the formal details. A banker has a fixed pool of capital — say, a certain amount of cash — and several customers who have each been granted a line of credit. Each customer has a maximum credit limit that was agreed when the account was opened. At any moment, a customer has drawn some amount against the limit and may draw more up to the limit.

The banker's problem is to decide, when a customer requests a withdrawal, whether to grant it. The banker cannot simply grant every request, because if all customers drew their maximum simultaneously, the bank would not have enough cash. On the other hand, the banker wants to lend as much as possible, because interest is the bank's income. The banker needs a rule that grants as many requests as possible while guaranteeing that the bank can always satisfy the maximum potential withdrawal of every customer.

The Banker's algorithm is that rule. The banker grants a request only if, after granting it, there is still enough cash (together with the cash that will be repaid by customers as they finish their business) to satisfy every remaining customer's maximum potential withdrawal. If the request would leave the bank unable to satisfy some customer's maximum, the request is deferred.

The analogy is exact. The banker's cash is the operating system's pool of available resources. The customers are the processes. The credit limits are the processes' declared maximum resource needs. A withdrawal is a resource request. The banker's rule is the safety check: grant the request only if the resulting state is safe.

4.2 The four data structures

The Banker's algorithm maintains four data structures. Assume there are n processes and m resource types.

Available[m]
A vector of length m. Available[j] is the number of instances of resource type Rj currently available — that is, not held by any process. This is the banker's current cash.
Max[n][m]
An n × m matrix. Max[i][j] is the maximum number of instances of resource type Rj that process Pi may request over its lifetime. This matrix is declared by the processes at creation and does not change. It is the credit limit for each customer.
Allocation[n][m]
An n × m matrix. Allocation[i][j] is the number of instances of resource type Rj currently allocated to process Pi. This is the amount each customer has currently drawn.
Need[n][m]
An n × m matrix. Need[i][j] is the number of additional instances of resource type Rj that process Pi may still request. It is defined as Need[i][j] = Max[i][j] − Allocation[i][j]. This is the amount each customer could still draw.

The total number of instances of each resource type is fixed at system start-up. The sum of all allocations plus the available pool must equal the total: 

sum over i of Allocation[i][j] + Available[j] = Total[j]

This invariant holds throughout the algorithm's execution. When a resource is granted, the allocation increases and the available pool decreases by the same amount; when a resource is released, the opposite happens. The total never changes.

The four data structures of the Banker's algorithm A diagram showing the four data structures used by the Banker's algorithm. Available is a vector showing the free instances of each resource. Max is a matrix showing the maximum needs of each process. Allocation is a matrix showing what each process currently holds. Need is a matrix showing the difference between Max and Allocation, computed as Max minus Allocation. An arrow shows the relationship Need = Max minus Allocation. The diagram also shows the total invariant: sum of allocations plus available equals the total. DATA STRUCTURES OF THE BANKER'S ALGORITHM Available[m] the banker's cash Available free instances Max[n][m] declared at creation Max credit limit per process Allocation[n][m] currently held Allocation what each process holds Need[n][m] still needed Need what remains Need[i][j] = Max[i][j] − Allocation[i][j] The amount a process could still request is what it declared, minus what it already has. Example: 5 processes, 3 resource types (A, B, C) Available A B C 3 3 2 Allocation A B C P0 0 1 0 P1 2 0 0 P2 3 0 2 P3 2 1 1 P4 0 0 2 Max A B C P0 7 5 3 P1 3 2 2 P2 9 0 2 P3 2 2 2 P4 4 3 3 Need = Max − Allocation A B C P0 7 4 3 P1 1 2 2 P2 6 0 0 P3 0 1 1 P4 4 3 1 Invariant: for each resource j, sum over i of Allocation[i][j] + Available[j] = Total[j] The total number of instances of each resource type never changes.
Figure 7.6 — The four data structures of the Banker's algorithm. Available is the pool of free instances; Max is each process's declared maximum; Allocation is what each process currently holds; and Need is the difference, computed as Max − Allocation. The invariant sum(Allocation) + Available = Total holds throughout the algorithm.

4.3 The safety algorithm

The safety algorithm determines whether the current state is safe. It answers the question: does there exist a sequence in which every process can run to completion? The algorithm is:

  1. Let Work[m] be a vector initialized to Available — a copy of the currently free resources. Let Finish[n] be a boolean vector initialized to all false.
  2. Find an index i such that Finish[i] == false and Need[i] ≤ Work — that is, a process that has not finished and whose remaining need can be satisfied from the current free resources.
  3. If no such i exists, go to step 4. Otherwise, suppose the process runs to completion: its resources are released. Work = Work + Allocation[i], and Finish[i] = true. Return to step 2.
  4. If Finish[i] == true for all i, the state is safe. Otherwise, the state is unsafe.

The algorithm simulates the completion of every process that can be satisfied from the current free resources. When a process "finishes", its resources are added back to the pool, which may allow another process to finish. If the algorithm can finish every process, the state is safe. If some processes remain unfinished when no more can be satisfied, the state is unsafe.

The algorithm also produces a safe sequence: the order in which the processes were marked finished. If the state is safe, this sequence is a witness — a concrete ordering in which every process can complete. If the state is unsafe, no sequence exists, and some subset of the unfinished processes may be deadlocked.

The safety algorithm is O(m n²) in the worst case: the outer loop runs at most n times, the inner loop scans up to n processes, and each comparison takes O(m) time. For a system with a modest number of processes and resources, this is fast enough.

4.4 The resource-request algorithm

The resource-request algorithm uses the safety algorithm to decide whether to grant a request. When process Pi requests a vector Request[i][m] of resources, the algorithm proceeds as follows.

  1. Check the request. If Request[i] > Need[i] — that is, if the process is requesting more than it declared it would ever need — the request is in error. The process has violated its declaration, and the system may terminate it or refuse the request.
  2. Check availability. If Request[i] > Available — that is, if the request cannot be satisfied from the current free pool — the process must wait. The system defers the request, and the process is placed on the wait queue.
  3. Pretend to grant the request. Modify the state to reflect the hypothetical grant:
    • Available = Available − Request[i]
    • Allocation[i] = Allocation[i] + Request[i]
    • Need[i] = Need[i] − Request[i]
  4. Run the safety algorithm. Determine whether the hypothetical state is safe.
  5. Decide. If the state is safe, grant the request. If the state is unsafe, restore the previous state and defer the request.

The algorithm is called on every resource request. It ensures that the system never enters an unsafe state, regardless of what the processes request. If a request would lead to an unsafe state, it is deferred — the process waits, and the system remains in the safe region.

4.5 A worked example

The following example is the canonical one from Silberschatz. Five processes P0 through P4 share three resource types A, B, and C. The total instances are: A = 10, B = 5, C = 7. The current state is shown below.

Initial state: Allocation, Max, and Need
Process Alloc A Alloc B Alloc C Max A Max B Max C Need A Need B Need C
P0010753743
P1200322122
P2302902600
P3211222011
P4002433431
Total 725 Available: A = 3, B = 3, C = 2

The current state is safe. To see this, we run the safety algorithm. Initially Work = (3, 3, 2) and every process is unfinished.

  • Find an unfinished process with Need ≤ Work. P0 has Need (7, 4, 3), which is not ≤ (3, 3, 2). P1 has Need (1, 2, 2), which is ≤ (3, 3, 2). So P1 can finish. Its resources are released: Work = (3, 3, 2) + (2, 0, 0) = (5, 3, 2).
  • Find an unfinished process with Need ≤ Work. P3 has Need (0, 1, 1), which is ≤ (5, 3, 2). So P3 can finish. Its resources are released: Work = (5, 3, 2) + (2, 1, 1) = (7, 4, 3).
  • Find an unfinished process with Need ≤ Work. P4 has Need (4, 3, 1), which is ≤ (7, 4, 3). P4 can finish. Work = (7, 4, 3) + (0, 0, 2) = (7, 4, 5).
  • Find an unfinished process with Need ≤ Work. P2 has Need (6, 0, 0), which is ≤ (7, 4, 5). P2 can finish. Work = (7, 4, 5) + (3, 0, 2) = (10, 4, 7).
  • Find an unfinished process with Need ≤ Work. P0 has Need (7, 4, 3), which is ≤ (10, 4, 7). P0 can finish. Work = (10, 4, 7) + (0, 1, 0) = (10, 5, 7).
  • All processes finished. The state is safe, and the safe sequence is P1, P3, P4, P2, P0. (Other safe sequences exist; the algorithm found one of them.)

The existence of this sequence guarantees that the system can complete without deadlock. The banker has enough cash (and enough incoming repayment) to satisfy every customer's potential withdrawal.

4.6 Applying the resource-request algorithm

Now suppose P1 requests one additional instance of A and two additional instances of C: Request[1] = (1, 0, 2). We run the resource-request algorithm.

  1. Check the request. Request[1] = (1, 0, 2) ≤ Need[1] = (1, 2, 2). The request is within the declared maximum, so it is valid.
  2. Check availability. Request[1] = (1, 0, 2) ≤ Available = (3, 3, 2). The request can be satisfied from the current free pool.
  3. Pretend to grant the request.
    • Available = (3, 3, 2) − (1, 0, 2) = (2, 3, 0)
    • Allocation[1] = (2, 0, 0) + (1, 0, 2) = (3, 0, 2)
    • Need[1] = (1, 2, 2) − (1, 0, 2) = (0, 2, 0)
  4. Run the safety algorithm. Work = (2, 3, 0).
    • P1: Need (0, 2, 0) ≤ Work (2, 3, 0). Finish. Work = (2, 3, 0) + (3, 0, 2) = (5, 3, 2).
    • P3: Need (0, 1, 1) ≤ (5, 3, 2). Finish. Work = (5, 3, 2) + (2, 1, 1) = (7, 4, 3).
    • P4: Need (4, 3, 1) ≤ (7, 4, 3). Finish. Work = (7, 4, 3) + (0, 0, 2) = (7, 4, 5).
    • P2: Need (6, 0, 0) ≤ (7, 4, 5). Finish. Work = (7, 4, 5) + (3, 0, 2) = (10, 4, 7).
    • P0: Need (7, 4, 3) ≤ (10, 4, 7). Finish.
    All processes finish: the state is safe.
  5. Grant the request. The hypothetical state is safe, so the request is granted. The state is updated to the hypothetical state.

Now suppose P4 requests three instances of B and three instances of C: Request[4] = (0, 3, 3). We run the algorithm again.

  1. Check the request. Request[4] = (0, 3, 3) ≤ Need[4] = (4, 3, 1)? No — the request asks for three instances of C, but P4's Need for C is only 1. The request exceeds the declared maximum and is invalid.

The request is rejected. P4 has declared a maximum of three instances of C, of which it already holds two, so it can request only one more. Asking for three is a violation of the declaration, and the system detects it.

4.7 A request that would be unsafe

Now suppose the system is in the state after P1's earlier request was granted, and P0 requests three instances of A and three instances of B: Request[0] = (3, 3, 0).

  1. Check the request. Request[0] = (3, 3, 0) ≤ Need[0] = (7, 4, 3). Valid.
  2. Check availability. Current Available = (2, 3, 0), so Request[0] = (3, 3, 0) ≤ Available? No — the request asks for three instances of A, but only two are available. The request must be deferred.

P0 must wait. The system does not evaluate safety, because the request cannot be satisfied at all. When a later release makes three instances of A available, the request can be reconsidered.

4.8 A request that is available but unsafe

The most interesting case is a request that can be satisfied from the current pool but would leave the system in an unsafe state. To illustrate, we modify the scenario.

Suppose the state is:

Process Alloc A Alloc B Alloc C Need A Need B Need C
P1100100
P2110110
Available 110 —

Suppose P2 requests one additional instance of A: Request[2] = (1, 0, 0).

  1. Check the request. Request[2] = (1, 0, 0) ≤ Need[2] = (1, 1, 0). Valid.
  2. Check availability. Request[2] = (1, 0, 0) ≤ Available = (1, 1, 0). Available.
  3. Pretend to grant. Available = (0, 1, 0), Allocation[2] = (2, 1, 0), Need[2] = (0, 1, 0).
  4. Run the safety algorithm. Work = (0, 1, 0).
    • P1: Need (1, 0, 0) ≤ Work (0, 1, 0)? No.
    • P2: Need (0, 1, 0) ≤ Work (0, 1, 0)? Yes. Finish. Work = (0, 1, 0) + (2, 1, 0) = (2, 2, 0).
    • P1: Need (1, 0, 0) ≤ Work (2, 2, 0)? Yes. Finish. All processes finished.
    The state is safe. The request is granted.

Now suppose P1 requests one additional instance of A instead: Request[1] = (1, 0, 0).

  1. Check the request. Request[1] = (1, 0, 0) ≤ Need[1] = (1, 0, 0). Valid.
  2. Check availability. Request[1] = (1, 0, 0) ≤ Available = (1, 1, 0). Available.
  3. Pretend to grant. Available = (0, 1, 0), Allocation[1] = (2, 0, 0), Need[1] = (0, 0, 0).
  4. Run the safety algorithm. Work = (0, 1, 0).
    • P1: Need (0, 0, 0) ≤ Work (0, 1, 0)? Yes. Finish. Work = (0, 1, 0) + (2, 0, 0) = (2, 1, 0).
    • P2: Need (1, 1, 0) ≤ Work (2, 1, 0)? Yes. Finish. All processes finished.
    The state is safe. The request is granted.

Both requests are granted because both resulting states are safe. To illustrate an unsafe case, we would need a scenario where granting a request would leave some process unable to complete — a case where the available resources after the grant are insufficient to satisfy any remaining process's need.

The precise construction of such a scenario is more involved and is left as an exercise. The essential principle is that the safety algorithm detects the problem: if no process can be satisfied from the remaining pool, and no process finishes, the state is unsafe and the request is deferred.

4.9 Complexity and implementation

The Banker's algorithm's running time is dominated by the safety algorithm, which is O(m n²) in the worst case. The resource-request algorithm runs the safety algorithm once per request, so it is also O(m n²) per request in the worst case.

The algorithm is easy to implement. The data structures are arrays, and the safety algorithm is a simple loop. The following is a Python sketch. 

def is_safe(available, allocation, need):
    n = len(need)
    m = len(available)
    work = list(available)
    finish = [False] * n
    sequence = []

    while len(sequence) < n:
        found = False
        for i in range(n):
            if not finish[i] and all(need[i][j] <= work[j]
                                     for j in range(m)):
                # process i can finish
                for j in range(m):
                    work[j] += allocation[i][j]
                finish[i] = True
                sequence.append(i)
                found = True
                break
        if not found:
            return False, []        # unsafe
    return True, sequence           # safe, with a safe sequence

def request(available, allocation, need, maxes, i, req):
    n, m = len(need), len(available)
    # check against declared need
    for j in range(m):
        if req[j] > need[i][j]:
            return False            # process over-requested
    # check availability
    for j in range(m):
        if req[j] > available[j]:
            return False            # must wait
    # pretend to grant
    saved = (list(available), list(allocation[i]), list(need[i]))
    for j in range(m):
        available[j] -= req[j]
        allocation[i][j] += req[j]
        need[i][j] -= req[j]
    # check safety
    safe, seq = is_safe(available, allocation, need)
    if safe:
        return True
    # restore and defer
    available[:], allocation[i][:], need[i][:] = saved
    return False

The simplicity of the implementation is one of the attractions of the algorithm. The difficulty is not in the code but in the information requirement: the maxes matrix must be filled in by the processes, and general-purpose processes cannot provide it.

4.10 Requirements and limitations

The Banker's algorithm inherits the requirements of the avoidance strategy from Lesson 7.5, and adds a few of its own.

Requirements and limitations of the Banker's algorithm
Requirement Why it is needed Where it fails
Maximum resource needs declared The algorithm relies on the Max matrix to determine what each process might still request. General-purpose processes cannot declare their maximum needs in advance. Their needs depend on input data and system state.
Number of processes fixed The algorithm assumes a fixed set of processes. A new process would change the matrices and the safety analysis. Systems with dynamic process creation. Most general-purpose systems.
Resources must be independent The algorithm assumes resources are independent. If resource types have dependencies (e.g., a lock that protects another lock's state), the analysis is more complex. Systems with nested or hierarchical resources. In practice, most resources are independent enough that the assumption holds.
Processes must not request more than declared The Max matrix is a hard upper bound. A process that requests more has violated its declaration. Untrusted processes. In a system with untrusted code, a process may lie about its maximum needs.
Resources must be released when a process terminates The algorithm assumes that a process's resources are returned to the pool on completion. Systems with resource leaks; processes that hold resources indefinitely without requesting more.
Runtime overhead The safety algorithm is run on every request, with a cost of O(m n²). Systems with high request rates; systems with many processes and resources.
Conservatism The algorithm defers any request that would lead to an unsafe state, even if the state might in practice complete. Systems where resource utilization is critical. The conservatism leaves resources idle that could have been used.

The most important limitation is the first: the maximum resource needs must be declared. This is what keeps the Banker's algorithm in the textbook. A general-purpose program cannot know in advance how many file descriptors, memory pages, or locks it will need — the numbers depend on the input, on the state of the system, and on the decisions the program makes as it runs. Without this information, the algorithm cannot determine whether a state is safe, and it cannot decide whether to grant or defer a request.

A second limitation, less frequently discussed, is the conservatism. The Banker's algorithm defers requests that would lead to unsafe states, even when the system might in practice have completed those states without deadlock. The cost is unused capacity: resources that could have been lent are kept in reserve. In a system where resources are plentiful and requests are rare, the cost is negligible. In a system where resources are scarce and requests are frequent, the cost can be substantial. This is the same trade-off the banker faces: more conservative lending means fewer defaults but lower interest income.

4.11 The Banker's algorithm versus the resource-allocation-graph algorithm

The Banker's algorithm is the multi-instance version of the avoidance strategy; the resource-allocation-graph algorithm from Lesson 7.5 is the single-instance version. The two algorithms are not interchangeable — they apply to different cases — but they share a common principle.

Resource-allocation-graph algorithm versus Banker's algorithm
Aspect Resource-allocation-graph Banker's algorithm
Resources Single-instance only Multi-instance
Representation Graph: processes and resources as vertices Matrices: Available, Max, Allocation, Need
Safety check Cycle detection in the hypothetical graph Simulation of completions using the matrices
Complexity per check O(V + E) for cycle detection O(m n²) for the safety algorithm
Information required Current state plus claim edges (future requests) Current state plus the Max matrix
Where used Systems with single-instance resources and declared claims Systems with multi-instance resources and declared maxima

The Banker's algorithm is the more general of the two, because it handles multi-instance resources. Its cost is higher, and its information requirement is the same. The choice between them depends on the resource types in the system: if all resources have a single instance, the graph algorithm is simpler; if some resources have multiple instances, the Banker's algorithm is required.

4.12 Common misconceptions

"The Banker's algorithm is a scheduler."

No. It is a resource-allocation policy. It decides whether to grant each request, not which process should run next. The scheduler is a separate concern.

"The Banker's algorithm prevents deadlock."

It avoids deadlock, not prevents it. The four Coffman conditions are allowed to hold; the algorithm only defers requests that would lead to unsafe states. It is a runtime check, not a structural discipline.

"The Banker's algorithm is used in Linux."

No. Linux uses lock ordering for prevention in the kernel and the ostrich algorithm for user-space deadlocks. The Banker's algorithm is not used in any general-purpose operating system.

"The Max matrix can be filled in by the kernel."

No. The Max matrix must be provided by the processes themselves. The kernel has no way to know a process's future resource needs without the process declaring them.

"An unsafe state means the Banker's algorithm has failed."

No. The Banker's algorithm keeps the system in a safe state by deferring unsafe requests. An unsafe state can arise only if the algorithm is not applied, or if a process requests more than it declared.

"The safe sequence is unique."

No. Many safe sequences may exist for a given state. The safety algorithm finds one of them; other sequences may also be valid. The existence of any safe sequence is what matters.

"The Banker's algorithm wastes resources."

It is conservative: it defers requests that would lead to unsafe states, even if those states might complete in practice. The cost is unused capacity. Whether this cost is acceptable depends on the system.

"The Banker's algorithm works for any resource type."

It works for reusable resources with a fixed number of instances. It does not work for consumable resources (messages, signals) or for resources whose state cannot be represented as a count.

05 Worked example

The following example traces the Banker's algorithm through a complete sequence of requests, showing the state of the matrices at each step and the decisions the algorithm makes.

A complete trace with three processes and three resources

Three processes P0, P1, P2 share three resource types A, B, C. The total instances are: A = 10, B = 5, C = 7. The initial state:

Process Alloc A Alloc B Alloc C Max A Max B Max C Need A Need B Need C
P0010753743
P1200322122
P2302902600
Available 332

Step 1: Check the initial state is safe

Work = (3, 3, 2). No process has finished.

  • P0: Need (7, 4, 3) ≤ (3, 3, 2)? No.
  • P1: Need (1, 2, 2) ≤ (3, 3, 2)? Yes. Finish P1. Work = (3, 3, 2) + (2, 0, 0) = (5, 3, 2).
  • P2: Need (6, 0, 0) ≤ (5, 3, 2)? No.
  • P0: Need (7, 4, 3) ≤ (5, 3, 2)? No.
  • P2: Need (6, 0, 0) ≤ (5, 3, 2)? Still no.

Wait — the algorithm stalls at this point with only P1 finished. But the state is safe: we found a safe sequence in section 4.5 that included P3 and P4. This version of the example only has three processes, so the safe sequence is different. Let us continue the analysis.

The current Work is (5, 3, 2). P0 needs (7, 4, 3), which is not ≤. P2 needs (6, 0, 0), which is not ≤ because of A (needs 6, has 5). So no more processes can finish. The state is unsafe.

This scenario is intentionally chosen to illustrate an unsafe state. The original Silberschatz example has five processes; the three-process version that fits in this worked example is unsafe. The system would deadlock if it reached this state.

Let us modify the example so that the initial state is safe. We reduce P2's Max A from 9 to 8. Then P2's Need is (5, 0, 0).

Process Alloc A Alloc B Alloc C Max A Max B Max C Need A Need B Need C
P0010753743
P1200322122
P2302802500
Available 332

Now the safety algorithm proceeds:

  • Work = (3, 3, 2).
  • P1: Need (1, 2, 2) ≤ (3, 3, 2). Finish. Work = (5, 3, 2).
  • P2: Need (5, 0, 0) ≤ (5, 3, 2). Finish. Work = (5, 3, 2) + (3, 0, 2) = (8, 3, 4).
  • P0: Need (7, 4, 3) ≤ (8, 3, 4)? B needs 4, has 3. Not ≤. No more can finish.

Still unsafe. The issue is P0's Need B of 4, but Work B is only 3. The safe sequence requires that P0 can eventually get its B. Let us reduce P0's Max B to 4, making its Need (7, 3, 3). Then:

  • Work = (3, 3, 2).
  • P1: Need (1, 2, 2) ≤ (3, 3, 2). Finish. Work = (5, 3, 2).
  • P2: Need (5, 0, 0) ≤ (5, 3, 2). Finish. Work = (8, 3, 4).
  • P0: Need (7, 3, 3) ≤ (8, 3, 4). Finish. All processes finished.

The safe sequence is P1, P2, P0, and the state is safe.

Step 2: P1 requests (1, 0, 2)

Request[1] = (1, 0, 2) ≤ Need[1] = (1, 2, 2). Valid. Request[1] ≤ Available = (3, 3, 2). Available. Pretend to grant:

  • Available = (3, 3, 2) − (1, 0, 2) = (2, 3, 0).
  • Allocation[1] = (2, 0, 0) + (1, 0, 2) = (3, 0, 2).
  • Need[1] = (1, 2, 2) − (1, 0, 2) = (0, 2, 0).

Run the safety algorithm:

  • Work = (2, 3, 0).
  • P1: Need (0, 2, 0) ≤ (2, 3, 0). Finish. Work = (2, 3, 0) + (3, 0, 2) = (5, 3, 2).
  • P2: Need (5, 0, 0) ≤ (5, 3, 2). Finish. Work = (8, 3, 4).
  • P0: Need (7, 3, 3) ≤ (8, 3, 4). Finish.

The state is safe. Grant the request. The state is updated to the hypothetical state.

Step 3: P0 requests (3, 3, 0)

Request[0] = (3, 3, 0) ≤ Need[0] = (7, 3, 3). Valid. Request[0] ≤ Available = (2, 3, 0)? No — only two instances of A are available, and the request asks for three. The request must be deferred. P0 waits until the system has more A.

Step 4: P2 releases (1, 1, 0)

Releases are not checked by the algorithm — a process may release any resources it holds, at any time. The release updates the state:

  • Available = (2, 3, 0) + (1, 1, 0) = (3, 4, 0).
  • Allocation[2] = (3, 0, 2) − (1, 1, 0) = (2, 0, 2).
  • Need[2] = (5, 0, 0) + (1, 1, 0) = (6, 1, 0).

(Releases increase the Need back toward the Max; a release is conceptually the reverse of a grant.)

Step 5: P0's deferred request is reconsidered

P0 still wants (3, 3, 0). Available is now (3, 4, 0), so the request can be satisfied. Run the request algorithm:

  • Request[0] = (3, 3, 0) ≤ Need[0] = (7, 3, 3). Valid.
  • Request[0] ≤ Available = (3, 4, 0). Yes.
  • Pretend to grant: Available = (0, 1, 0), Allocation[0] = (3, 4, 0), Need[0] = (4, 0, 3).
  • Safety algorithm with Work = (0, 1, 0):
    • P0: Need (4, 0, 3) ≤ (0, 1, 0)? No.
    • P1: Need (0, 2, 0) ≤ (0, 1, 0)? No.
    • P2: Need (6, 1, 0) ≤ (0, 1, 0)? No.
    • No process can finish. The state is unsafe.

Defer the request. Granting P0's request would leave the system with only (0, 1, 0) available, which is insufficient to satisfy any process's remaining need. The state is unsafe, and the request is refused — even though the resources are available. P0 must wait.

Step 6: P1 finishes

P1 completes its work and releases all its resources:

  • Available = (0, 1, 0) + (3, 0, 2) = (3, 1, 2).
  • Allocation[1] = (0, 0, 0).
  • Need[1] = (0, 0, 0).

P1 is finished; it will not make any more requests.

Step 7: P0's request is reconsidered again

Available is now (3, 1, 2), so P0's request for (3, 3, 0) still cannot be satisfied — B is 1, and the request asks for 3. P0 must wait longer.

This example illustrates the conservatism of the Banker's algorithm: a request may be deferred even though the resources it asks for are available, because granting it would leave the system unable to satisfy some other process's need. The deferred request is reconsidered whenever resources are released, and it is granted as soon as the state would remain safe.

Observations

Several features of the Banker's algorithm are visible in this trace.

  • Every request is checked. The algorithm does not skip any request. Even a small request from a process with a small Need is checked against the safety algorithm.
  • The safety check is conservative. P0's request was deferred even though the resources were available, because granting it would have left the system unable to satisfy the remaining needs. The Banker's algorithm prefers safety over utilization.
  • Deferred requests are reconsidered. When P2 released resources, P0's request was reconsidered. If it had become safe at that point, it would have been granted.
  • Releases are not checked. A process may release any of its resources at any time. The release only adds to Available; it cannot make the state unsafe.

Comparison with the resource-allocation graph

The same example can be analysed with the resource-allocation graph, but the graph is not directly applicable because the resources have multiple instances. To use the graph, we would have to model each instance as a separate resource — a cumbersome transformation that defeats the purpose. The Banker's algorithm's matrix representation is designed for this case: it handles multiple instances compactly by counting them rather than representing each one individually.

Runtime complexity in practice

For the example above, the safety algorithm is run at every request. Each run takes O(m n²) = O(3 · 3²) = O(27) operations in the worst case, which is negligible. For a large system — say, 1,000 processes and 100 resources — each safety check takes about 10⁸ operations, which is noticeable but not prohibitive. For a system with 10,000 processes and 1,000 resources, each check takes about 10¹¹ operations, which is too slow for interactive performance.

This scaling is one of the reasons the Banker's algorithm is not used in large general-purpose systems. Even if the information were available, the runtime cost of running the safety algorithm on every request would be prohibitive for a modern server with thousands of concurrent processes.

06 Interactive activity

Activity · implement and trace the Banker's algorithm

The goal of this activity is to implement the Banker's algorithm, trace it through a variety of scenarios, and observe how the safety check affects the decisions the system makes. Work through the steps in your course VM.

  1. Implement the safety algorithm. Write a function is_safe(Available, Allocation, Need) that returns whether the given state is safe, together with a safe sequence if one exists. 
    def is_safe(available, allocation, need):
    n = len(need)
    m = len(available)
    work = list(available)
    finish = [False] * n
    sequence = []

    while len(sequence) < n:
        found = False
        for i in range(n):
            if not finish[i]:
                if all(need[i][j] <= work[j] for j in range(m)):
                    for j in range(m):
                        work[j] += allocation[i][j]
                    finish[i] = True
                    sequence.append(i)
                    found = True
                    break
        if not found:
            return False, []
    return True, sequence
    Test it with the worked example from section 4.5 (the five-process version) and verify the safe sequence.
  2. Implement the resource-request algorithm. Write a function request(available, allocation, need, i, req) that decides whether to grant a request. It should:
    • Check the request against need[i].
    • Check the request against available.
    • Pretend to grant the request.
    • Run the safety algorithm.
    • Grant if safe, defer if unsafe.
    Test it with the request scenarios from section 4.6.
  3. Trace the worked example. Encode the three-process example from section 5, run the trace, and verify that the algorithm's decisions match the analysis.
  4. Try a sequence of requests. Write a program that takes a sequence of requests and processes them one at a time. For each request, print whether it was granted or deferred, and update the state if granted. Experiment with different sequences to see how the safety check affects the outcome.
  5. Compare with detection. Modify the program to grant every request (no safety check). Run the same sequence. Does the system reach a deadlocked state? If so, identify the point at which a check would have prevented it.
  6. Analyse the information requirement. Write a paragraph explaining what would have to change about a general-purpose operating system for the Banker's algorithm to be used. Consider what kinds of processes could declare their maximum needs, and what kinds could not.
  7. Scale test. Generate a random system with 100 processes and 20 resource types. Measure the time to run the safety algorithm. Then try 1,000 processes and 100 resource types. How does the time scale? At what point does the cost become prohibitive? 
    import random, time

def random_state(n, m):
    available = [random.randint(0, 10) for _ in range(m)]
    allocation = [[random.randint(0, 5) for _ in range(m)]
                  for _ in range(n)]
    need = [[random.randint(0, 5) for _ in range(m)]
            for _ in range(n)]
    return available, allocation, need

for n, m in [(100, 20), (500, 50), (1000, 100)]:
    state = random_state(n, m)
    start = time.time()
    safe, seq = is_safe(*state)
    elapsed = time.time() - start
    print(f"n={n} m={m}: {elapsed:.3f}s, safe={safe}")
  8. Read the Dijkstra paper. Read the section of the 1968 paper in which the algorithm is presented. The original presentation uses the banker's analogy. Compare the original's framing to the modern matrix-based presentation. Does the analogy help or distract from the algorithm's substance?

Reflect: the Banker's algorithm is correct, elegant, and efficient for small systems. It is also unused in practice, because the information it requires is unavailable. Is this a failure of the algorithm or a limitation of the contexts in which it is applied? Could a modern system — a real-time controller, a database with a fixed schema, a real-time operating system — use the Banker's algorithm successfully? What would be different about those systems?

07 Knowledge check

Check your understanding

Question 1

Describe the four data structures of the Banker's algorithm: Available, Max, Allocation, and Need. What does each represent, and what is the relationship between them?

Show answer
The four data structures are:
  • Available[m]: a vector of length m, where Available[j] is the number of instances of resource type Rj currently free. This is the banker's current cash — the resources not held by any process.
  • Max[n][m]: an n × m matrix where Max[i][j] is the maximum number of instances of Rj that Pi may ever request. Declared by the process at creation; does not change.
  • Allocation[n][m]: an n × m matrix where Allocation[i][j] is the number of instances of Rj currently held by Pi. This is what the process has drawn against its credit limit.
  • Need[n][m]: an n × m matrix defined as Need[i][j] = Max[i][j] − Allocation[i][j]. This is what the process could still request.
The relationship between them is: Need = Max − Allocation, and for each resource type j, sum(Allocation[i][j] for all i) + Available[j] = Total[j], where Total[j] is the fixed number of instances of Rj in the system. The total never changes; grants move instances from Available to Allocation, and releases move them back.

Question 2

Describe the safety algorithm. What does it do, and how does it determine whether a state is safe? What is the complexity of the algorithm?

Show answer
The safety algorithm determines whether the current state is safe — that is, whether there exists a sequence in which every process can complete. The algorithm is:
  1. Initialize Work = Available and Finish[i] = false for all i.
  2. Find an index i such that Finish[i] == false and Need[i] ≤ Work — a process whose remaining need can be satisfied from the current free resources.
  3. If no such i exists, go to step 4. Otherwise, simulate the process's completion: Work = Work + Allocation[i], and Finish[i] = true. Return to step 2.
  4. If Finish[i] == true for all i, the state is safe. Otherwise, the state is unsafe.
The algorithm simulates the completion of every process that can be satisfied from the current free resources. When a process "finishes", its resources are returned to the pool, potentially allowing another process to finish. If every process can be finished, the state is safe. The order in which processes were finished is a safe sequence. The complexity is O(m n²) in the worst case: the outer loop runs at most n times, each inner scan examines up to n processes, and each comparison is O(m).

Question 3

Describe the resource-request algorithm. What are the four steps, and what does the algorithm do at each step? Why is the safety algorithm necessary?

Show answer
The resource-request algorithm decides whether to grant a resource request from process Pi for a vector Request[i]. The four steps are:
  1. Check the request against the declaration. If Request[i] > Need[i], the process is requesting more than it declared. The request is invalid and is refused.
  2. Check availability. If Request[i] > Available, the request cannot be satisfied from the current free pool. The process is deferred until the resources become available.
  3. Pretend to grant the request. Modify the state to reflect the hypothetical grant: Available -= Request[i], Allocation[i] += Request[i], Need[i] -= Request[i].
  4. Run the safety algorithm. Determine whether the hypothetical state is safe. If yes, grant the request (keep the hypothetical state). If no, restore the previous state and defer the request.
The safety algorithm is necessary because the request being satisfiable from the current pool is not sufficient to guarantee that granting it is safe. The grant may leave the system in a state from which no process can complete. The safety algorithm checks the hypothetical state and refuses the request if the state would be unsafe. This is the conservatism of the Banker's algorithm: it prefers to defer a request rather than risk a deadlock.

Question 4

The Banker's algorithm is rarely used in general-purpose operating systems. What are the primary reasons? Which of the reasons is the most fundamental, and why?

Show answer
The primary reasons the Banker's algorithm is rarely used are:
  1. The maximum resource needs must be declared in advance. This is the fundamental reason. A general-purpose process cannot know in advance how many file descriptors, memory pages, or locks it will need. The numbers depend on input data, on the state of the system, and on the decisions the process makes as it runs. Without this information, the algorithm cannot determine whether a state is safe.
  2. The number of processes must be fixed. The algorithm assumes a fixed set of processes. A new process arriving dynamically changes the matrices and requires reanalysis of the safe state.
  3. Processes must be well-behaved. A process that requests more than it declared violates the algorithm's assumptions. In a system with untrusted code, this cannot be guaranteed.
  4. Runtime overhead. The safety algorithm is O(m n²) and is run on every request. For a system with many processes and resources, the cost can be prohibitive.
  5. Conservatism. The algorithm defers requests that would lead to unsafe states, even if those states might in practice complete. This wastes resources.
The most fundamental reason is the first: the maximum resource needs must be declared. Without this information, the algorithm simply cannot function. The other reasons are consequences of the algorithm's design or of the contexts in which it is applied, but the information requirement is intrinsic. A system that could somehow know each process's maximum needs could use the algorithm; a system that cannot, cannot, regardless of how much computing power or memory it has.

Question 5

The Banker's algorithm is the multi-instance version of the avoidance strategy, while the resource-allocation-graph algorithm from Lesson 7.5 is the single-instance version. Compare the two algorithms. When is each appropriate? Can one be used in place of the other?

Show answer
The two algorithms are complementary, not interchangeable. The resource-allocation-graph algorithm handles resources with a single instance each; it uses a graph in which processes and resources are vertices, and it checks for cycles in the hypothetical graph that would result from granting a request. It is simple and efficient (cycle detection is O(V + E)), but it cannot handle resources with multiple instances. The Banker's algorithm handles resources with any number of instances; it uses four matrices to represent the state, and it runs the safety algorithm to determine whether the resulting state is safe. It is more general but also more expensive (O(m n²) per check). The choice between them depends on the resource types in the system. If all resources have a single instance, the graph algorithm is simpler and faster. If some resources have multiple instances, the Banker's algorithm is required. One cannot be used in place of the other: the graph algorithm is incorrect for multi-instance resources (a cycle does not imply deadlock), and the Banker's algorithm is unnecessarily complex for single-instance resources (though it is correct in that case). In practice, most systems have a mix of resource types, and neither algorithm is used in production for the reasons discussed in question 4.

08 Unit discussion

Discussion prompt

The Banker's algorithm is one of the most famous algorithms in operating-system theory. It appears in every textbook, it is asked about in every job interview, and it is studied by every computer-science student. And yet it is not used in any general-purpose operating system. Linux does not use it. Windows does not use it. macOS does not use it. The systems we use every day do not apply the algorithm.

Is this a problem? Should we be concerned that the systems we rely on do not use the most theoretically sound approach to deadlock handling? Or is the choice a reasonable one, given the algorithm's requirements?

Consider the trade-offs. The Banker's algorithm guarantees no deadlock, given the information it requires. The alternative — the ostrich algorithm — allows deadlock and relies on the user to intervene. Prevention (lock ordering) makes deadlock impossible without requiring the maximum-needs information, at the cost of a discipline. Which is better? Does the answer depend on the system? Consider a real-time controller, a database, a web server, a mobile phone, a desktop operating system — would your answer be the same for all of them?

Another question: the Banker's algorithm is sometimes criticized as "too conservative" — it defers requests that would, in practice, have been safe. Is this criticism fair? What is the cost of the conservatism, and how does it compare to the cost of an occasional deadlock? If you could design a system that used the Banker's algorithm with a less conservative check — accepting a small probability of deadlock in exchange for better utilization — would you?

Post your response to the Unit 7 discussion forum and reply to at least two classmates. Supports CLO2, CLO3, and CLO8.

09 Practice exercise

This ungraded exercise consolidates the lesson and prepares you for Lesson 7.7. Aim to spend 90–120 minutes on it.

  1. Set up the matrices. For the following system, fill in the Need matrix and the Available vector. The total instances are A = 12, B = 8, C = 9.
    Process Alloc A Alloc B Alloc C Max A Max B Max C
    P0211644
    P1120432
    P2302823
    P3013334
  2. Run the safety algorithm. Apply the safety algorithm to the state in question 1. Is the state safe? If so, find a safe sequence. Show your work at each step: which process is selected, what Work becomes, which processes remain.
  3. Test a request. Suppose P1 requests (1, 1, 0). Apply the resource-request algorithm: is the request valid? Is it available? Does it leave the state safe? Should it be granted?
  4. Test another request. Suppose P0 requests (2, 2, 2). Apply the resource-request algorithm. Would granting the request leave the state safe? Should it be granted? What if the request were (1, 1, 1)?
  5. Find a request that would be unsafe. Construct a request that can be satisfied from the current pool but would leave the state unsafe. Show why the safety algorithm detects this. Write a paragraph explaining what would happen if the algorithm did not check the safety — what state would the system reach, and would it deadlock?
  6. Compare with detection. Take the same system and the same sequence of requests. This time, grant every request without checking safety. Track the state of the matrices. When does the system become deadlocked? Which processes are involved? Compare this to the Banker's algorithm's decisions, and quantify the difference in the number of granted requests and the final state of the system.
  7. Implement the Banker's algorithm in code. Write a program (in C, Python, or a language of your choice) that implements the safety algorithm and the resource-request algorithm. Test it on the state from question 1 and the requests from questions 3 and 4. Print a trace of the algorithm's decisions.
  8. Reflect. In your own words, explain why the Banker's algorithm requires the maximum resource needs to be declared in advance. Then describe a system — real or hypothetical — where such declarations would be feasible. What properties would the system need to have? What would be the consequences of a process lying about its maximum needs?

10 Summary

  • The Banker's algorithm is the classical implementation of deadlock avoidance for multi-instance resources. It was published by Dijkstra in 1968 and is named after the analogy of a banker managing loans.
  • The algorithm maintains four data structures: Available (the free instances), Max (each process's declared maximum), Allocation (what each process holds), and Need (the difference, Max − Allocation).
  • The safety algorithm determines whether a state is safe by simulating the completion of every process that can be satisfied from the current free resources. If all processes can finish, the state is safe and a safe sequence is produced. The algorithm is O(m n²).
  • The resource-request algorithm uses the safety algorithm to decide whether to grant a request. It checks the request against the process's declared maximum, checks availability, pretends to grant the request, and runs the safety algorithm. The request is granted only if the resulting state is safe.
  • The Banker's algorithm is the multi-instance version of the avoidance strategy. The resource-allocation-graph algorithm from Lesson 7.5 is the single-instance version. The two are complementary: the graph algorithm cannot handle multi-instance resources, and the Banker's algorithm is unnecessarily complex for single-instance resources.
  • The Banker's algorithm's primary limitation is the information requirement: every process must declare its maximum resource needs in advance. General-purpose processes cannot do this, which is why the algorithm is not used in general-purpose operating systems.
  • Additional limitations include the requirement that the number of processes be fixed, the assumption that processes are well-behaved, the runtime overhead of the safety algorithm, and the conservatism that defers requests which might in practice have been safe.
  • The Banker's algorithm is correct and efficient for the systems it targets: small systems with known resource needs. It is a conceptually beautiful algorithm and a superb teaching example, even though it is not widely deployed.
  • The algorithm illustrates the fundamental trade-off of the avoidance strategy: safety is guaranteed at the cost of information and flexibility. Systems that can provide the information benefit from the guarantee; systems that cannot must rely on prevention, detection, or the ostrich algorithm.

Looking ahead

This lesson presented the Banker's algorithm, the multi-instance version of the avoidance strategy. It completes the avoidance portion of the unit. The next lesson — the last of Unit 7 — presents detection and recovery: the strategy of allowing deadlock to occur, detecting it when it does, and recovering by aborting one or more processes or rolling them back. Detection uses the same tools we have developed: the wait-for graph for the single-instance case, and the reduction algorithm for the multi-instance case. Recovery requires a policy for choosing which process to abort and a mechanism for undoing its effects. The lesson closes Unit 7 by returning to the practical question: given all the strategies we have studied, which should a real system use, and why?

11 References

  • Silberschatz, A., Galvin, P. B., & Gagne, G. Operating System Concepts, 10th ed., Chapter 8, Section 8.6.3.
  • Dijkstra, E. W. Cooperating Sequential Processes. In Programming Languages, ed. F. Genuys, Academic Press, 1968. The original publication of the Banker's algorithm.
  • Habermann, A. N. Prevention of System Deadlocks. Communications of the ACM, 1969.
  • Coffman, E. G., Elphick, M. J., & Shoshani, A. System Deadlocks. ACM Computing Surveys, 1971.
  • Tanenbaum, A. S., & Bos, H. Modern Operating Systems, 4th ed., Chapter 6, Section 6.5.2.
  • Arpaci-Dusseau, R. H., & Arpaci-Dusseau, A. C. Operating Systems: Three Easy Pieces, Chapter 32. Available online at ostep.org.
  • Holt, R. C. Some Deadlock Properties of Computer Systems. ACM Computing Surveys, 1972.
  • Love, R. Linux Kernel Development, 3rd ed., Chapter 9. The reasons Linux does not use the Banker's algorithm.
  • Linux man-pages: man 7 pthreads, man 3 pthread_mutex_lock, man 3 pthread_mutex_trylock.
👤