Self-checkedTier 1 14 min reados.deadlock-avoidance-bankers

Deadlock avoidance and the Banker's algorithm

Granting requests only when the system stays safe: safe and unsafe states, the Allocation, Max, Need and Available matrices, the safety algorithm, the resource-request algorithm, the relation between unsafe states and deadlock, and the claim-edge version for single-instance resources.

Why it exists

Prevention denies one of the four deadlock conditions and so wastes resources or restricts programs. Avoidance is less restrictive: it lets all four conditions hold but looks, at every request, at whether granting the request could lead the system into a state from which deadlock is unavoidable. It needs advance knowledge: each process declares the maximum number of units of each resource it will ever need. The Banker's algorithm (Dijkstra, named after a bank that never lends more than it can cover) is the standard method for resources with several instances. GATE asks you to compute the Need matrix, decide whether a state is safe, find a safe sequence, decide whether a request can be granted, and answer questions about safe and unsafe states.

Prerequisites

Deadlock: conditions and resource allocation graphs

You need the four conditions, the resource allocation graph and the idea of a process finishing and releasing what it holds, from deadlock conditions.

Precise definitions

Safe state. The system is in a safe state if there is an order $\langle P_1, P_2, \ldots, P_n \rangle$ of all the processes, a safe sequence, such that for each $P_i$ the resources it may still request can be satisfied by the currently free resources plus the resources held by all the $P_j$ with $j < i$ . In words: the processes can be run to completion one after another, each finding enough resources when its turn comes (because the earlier ones have finished and returned theirs). If no such order exists the state is unsafe.

Relation to deadlock.

A safe state is not deadlocked and cannot lead to deadlock if the system always follows the safe sequence logic (grants only requests that keep it safe).
An unsafe state is not necessarily deadlocked; it may lead to deadlock. (Processes might not ask for their maximum, or might release early, so the worst case need not happen.)
Every deadlocked state is unsafe. Safe $\subset$ not deadlocked; deadlock $\subset$ unsafe.

The avoidance rule: never let the system enter an unsafe state. A request is granted only if the resulting state is safe; otherwise the process waits, even if the resources are free.

Data structures ( $n$ processes, $m$ resource types):

Name	Size	Meaning
Available	$m$	units of each type that are free now
Max	$n \times m$	the maximum demand of each process
Allocation	$n \times m$	units each process holds now
Need	$n \times m$	$\text{Need} = \text{Max} - \text{Allocation}$ : what each may still request

Conservation: for every resource type, $\text{Available} + \sum_i \text{Allocation}_i = \text{Total}$ .

Safety algorithm.

$\text{Work} = \text{Available}$ ; $\text{Finish}[i] = \text{false}$ for all $i$ .
Find an $i$ with $\text{Finish}[i] = \text{false}$ and $\text{Need}_i \le \text{Work}$ (componentwise). If none exists, go to step 4.
$\text{Work} = \text{Work} + \text{Allocation}_i$ ; $\text{Finish}[i] = \text{true}$ ; go to step 2.
If $\text{Finish}[i]$ is true for every $i$ the state is safe (the order in which processes were chosen is a safe sequence); otherwise unsafe.

The order of choice among eligible processes does not matter for the verdict: if any safe sequence exists, any greedy choice will find one, since finishing a process only increases Work. The cost is $O(m n^2)$ .

Resource-request algorithm for a request $\text{Request}_i$ by process $P_i$ :

If $\text{Request}_i > \text{Need}_i$ : error (the process exceeded its declared maximum).
If $\text{Request}_i > \text{Available}$ : $P_i$ must wait (the resources are not free).
Pretend to grant: $\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$ .
Run the safety algorithm on the pretended state. If safe, grant the request. If not, restore the old state and make $P_i$ wait.

Single-instance version. With one instance per resource type, avoidance can use the resource allocation graph with claim edges (dashed edges $P_i \to R_j$ meaning $P_i$ may request $R_j$ some time). A request is granted only if converting its request edge to an assignment edge does not create a cycle in the graph (counting claim edges). No cycle means the state is safe.

Limitations. Maximum needs must be known in advance; the number of processes and resources must be fixed; processes must return resources in finite time; the check costs time at every request.

How it works

The first animation runs the safety algorithm on a state with five processes and three resource types (totals A = 8, B = 9, C = 6). At each step it finds the first unfinished process whose Need fits in Work, lets it "finish" and adds its Allocation to Work. Watch Work grow as the processes finish in the order P1, P0, P2, P3, P4: the state is safe. (There are 12 different safe sequences; the algorithm finds the first.)

Banker's safety algorithm on a state with five processes: start

Algorithm run by script, not typed

process	alloc A	alloc B	alloc C	max A	max B	max C	need A	need B	need C	finish
P0	2	1	2	4	4	2	2	3	0	-
P1	3	2	1	3	4	1	0	2	0	-
P2	2	0	0	4	2	0	2	2	0	-
P3	1	2	1	3	4	3	2	2	2	-
P4	0	2	1	1	5	5	1	3	4	-

total (A B C)

8 9 6

available (A B C)

0 2 1

work (A B C)

safe sequence so far-

Step 0

Resources A, B, C have totals (8, 9, 6). Allocation is what each process holds now, Max is the most it may ever ask for, Need = Max - Allocation, and Available = Total - total allocation = (0, 2, 1). A state is SAFE if the processes can be run to completion one after another in some order, each getting its full remaining Need from what is then available.

0 / 7

computed by script: graph analysis and the Banker's algorithm, one event or one check per step. python3 scripts/gen-os-deadlock-traces.py

Now a request. P0 asks for one more unit of B. It is a legal request (within its Need) and the unit is free, but granting it would leave Available at (0, 1, 1), and then no process's Need fits in Work: the pretended state is unsafe, so the request is denied and the allocation restored, even though the resource was free.

A request that would make the state unsafe is denied: start

Algorithm run by script, not typed

process	alloc A	alloc B	alloc C	max A	max B	max C	need A	need B	need C	finish
P0 ◀	2	1	2	4	4	2	2	3	0	-
P1	3	2	1	3	4	1	0	2	0	-
P2	2	0	0	4	2	0	2	2	0	-
P3	1	2	1	3	4	3	2	2	2	-
P4	0	2	1	1	5	5	1	3	4	-

total (A B C)

8 9 6

available (A B C)

0 2 1

work (A B C)

safe sequence so far-

Step 0

The system is in the state shown. P0 now asks for the extra resources (0, 1, 0). The Banker's algorithm does NOT grant a request just because the resources are free: it grants it only if the system would still be in a safe state.

0 / 6

computed by script: graph analysis and the Banker's algorithm, one event or one check per step. python3 scripts/gen-os-deadlock-traces.py

A request that is safe: P1 asks for the same unit. After the pretended grant P1's Need is (0, 1, 0), which still fits in Work (0, 1, 1), so P1 can finish and the rest follow: the request is granted.

A request that keeps the state safe is granted: start

Algorithm run by script, not typed

process	alloc A	alloc B	alloc C	max A	max B	max C	need A	need B	need C	finish
P0	2	1	2	4	4	2	2	3	0	-
P1 ◀	3	2	1	3	4	1	0	2	0	-
P2	2	0	0	4	2	0	2	2	0	-
P3	1	2	1	3	4	3	2	2	2	-
P4	0	2	1	1	5	5	1	3	4	-

total (A B C)

8 9 6

available (A B C)

0 2 1

work (A B C)

safe sequence so far-

Step 0

The system is in the state shown. P1 now asks for the extra resources (0, 1, 0). The Banker's algorithm does NOT grant a request just because the resources are free: it grants it only if the system would still be in a safe state.

0 / 11

computed by script: graph analysis and the Banker's algorithm, one event or one check per step. python3 scripts/gen-os-deadlock-traces.py

Worked examples

EX 1Need and Available

Easy

For the state in the animation: Max for P0 is (4, 4, 2) and Allocation (2, 1, 2), so Need $= (2, 3, 0)$ . Similarly P1: (3, 4, 1) $-$ (3, 2, 1) $=$ (0, 2, 0); P2: (4, 2, 0) $-$ (2, 0, 0) $=$ (2, 2, 0); P3: (3, 4, 3) $-$ (1, 2, 1) $=$ (2, 2, 2); P4: (1, 5, 5) $-$ (0, 2, 1) $=$ (1, 3, 4). Adding the allocations per resource type: A: $2 + 3 + 2 + 1 + 0 = 8$ ; B: $1 + 2 + 0 + 2 + 2 = 7$ ; C: $2 + 1 + 0 + 1 + 1 = 5$ . With totals $(8, 9, 6)$ , Available $= (8 - 8,\; 9 - 7,\; 6 - 5) = (0, 2, 1)$ .

EX 2The whole algorithm, by program

Medium

A C program implements the safety algorithm and the request algorithm, and counts the safe sequences by brute force.

#include <stdio.h>
 
#define N 5
#define M 3
 
static const int total[M] = {8, 9, 6};
static const int max_[N][M] = {{4, 4, 2}, {3, 4, 1}, {4, 2, 0}, {3, 4, 3}, {1, 5, 5}};
static const int alloc0[N][M] = {{2, 1, 2}, {3, 2, 1}, {2, 0, 0}, {1, 2, 1}, {0, 2, 1}};
 
static int alloc[N][M], need[N][M], avail[M];
 
static void setup(void) {
    for (int k = 0; k < M; k++) avail[k] = total[k];
    for (int i = 0; i < N; i++)
        for (int k = 0; k < M; k++) { alloc[i][k] = alloc0[i][k]; avail[k] -= alloc0[i][k]; }
    for (int i = 0; i < N; i++)
        for (int k = 0; k < M; k++) need[i][k] = max_[i][k] - alloc[i][k];
}
 
static int fits(int i, const int *work) {
    for (int k = 0; k < M; k++) if (need[i][k] > work[k]) return 0;
    return 1;
}
 
/* the textbook safety algorithm; returns 1 and fills seq if the state is safe */
static int safe(int *seq) {
    int work[M], done[N] = {0}, count = 0;
    for (int k = 0; k < M; k++) work[k] = avail[k];
    for (;;) {
        int pick = -1;
        for (int i = 0; i < N && pick < 0; i++) if (!done[i] && fits(i, work)) pick = i;
        if (pick < 0) break;
        for (int k = 0; k < M; k++) work[k] += alloc[pick][k];
        done[pick] = 1;
        seq[count++] = pick;
    }
    return count == N;
}
 
/* brute force: count the finishing orders in which every process finds its Need available when its turn comes */
static int count_orders(int *work, int *done, int depth) {
    if (depth == N) return 1;
    int total_orders = 0;
    for (int i = 0; i < N; i++) {
        if (done[i] || !fits(i, work)) continue;
        int next[M];
        for (int k = 0; k < M; k++) next[k] = work[k] + alloc[i][k];
        done[i] = 1;
        total_orders += count_orders(next, done, depth + 1);
        done[i] = 0;
    }
    return total_orders;
}
 
/* the resource-request algorithm: returns 1 if granted */
static int request(int p, const int *req) {
    for (int k = 0; k < M; k++) if (req[k] > need[p][k]) return 0;
    for (int k = 0; k < M; k++) if (req[k] > avail[k]) return 0;
    for (int k = 0; k < M; k++) { avail[k] -= req[k]; alloc[p][k] += req[k]; need[p][k] -= req[k]; }
    int seq[N];
    if (safe(seq)) return 1;
    for (int k = 0; k < M; k++) { avail[k] += req[k]; alloc[p][k] -= req[k]; need[p][k] += req[k]; }
    return 0;
}
 
int main(void) {
    int seq[N];
    setup();
    printf("available (%d, %d, %d)\n", avail[0], avail[1], avail[2]);
    if (safe(seq)) {
        printf("safe; the safety algorithm finds:");
        for (int i = 0; i < N; i++) printf(" P%d", seq[i]);
        printf("\n");
    } else printf("unsafe\n");
    int work[M] = {avail[0], avail[1], avail[2]}, done[N] = {0};
    printf("number of safe sequences: %d\n", count_orders(work, done, 0));
    int r0[M] = {0, 1, 0};
    printf("P0 requests (0, 1, 0): %s\n", request(0, r0) ? "granted" : "denied");
    setup();
    printf("P1 requests (0, 1, 0): %s\n", request(1, r0) ? "granted" : "denied");
    printf("P1 now holds (%d, %d, %d), available (%d, %d, %d)\n", alloc[1][0], alloc[1][1], alloc[1][2], avail[0], avail[1], avail[2]);
    return 0;
}

available (0, 2, 1)
safe; the safety algorithm finds: P1 P0 P2 P3 P4
number of safe sequences: 12
P0 requests (0, 1, 0): denied
P1 requests (0, 1, 0): granted
P1 now holds (3, 3, 1), available (0, 1, 1)

Reading it. The program reproduces the animations: the state is safe with sequence P1, P0, P2, P3, P4, and a brute-force count over all orders finds 12 safe sequences. The request by P0 is denied; the same request by P1 is granted. A request that is legal and for free resources can still be refused: the test is the safety of the resulting state.

EX 3Why was the first request denied?

Medium

After pretending to grant P0's request, Available is $(0, 1, 1)$ and the Needs are P0 $(2, 2, 0)$ , P1 $(0, 2, 0)$ , P2 $(2, 2, 0)$ , P3 $(2, 2, 2)$ , P4 $(1, 3, 4)$ . Compare each with Work $= (0, 1, 1)$ : P0 needs 2 of A (none free); P1 needs 2 of B (only 1 free); P2, P3, P4 all need at least 1 of A or 2 of B. No process can be guaranteed to finish, so no safe sequence exists: unsafe. For the granted request, P1's Need drops to $(0, 1, 0)$ , which fits $(0, 1, 1)$ ; P1 finishes and returns $(3, 3, 1)$ , making Work large enough for everyone.

EX 4Smallest Available for a safe state

GATE level

One resource type, three processes with Allocation $(2, 3, 1)$ and Max $(5, 6, 4)$ , so Need $= (3, 3, 3)$ . What is the smallest Available that makes the state safe? The first process to run needs 3 units, so Work must be at least 3: Available = 3. With 3 units any process can go first, and each finished process returns at least 1 more than it needed back, so everything finishes: 6 safe sequences. With Available = 2 no Need (3) fits and the state is unsafe, although the system has $2 + 6 = 8$ units in all. (Found by trying every Available value and every order.)

EX 5Unsafe is not deadlock, and safe needs the rule

GATE level

Take the denied state of the second animation. It is unsafe but not deadlocked: there is no deadlock yet because processes have not asked for their maxima. A search over all the ways the five processes could request one more unit at a time shows that, if the request were granted, a deadlock can be reached: the unsafe state really is dangerous. Conversely, a safe state is safe only as long as the system keeps refusing unsafe requests: in 117 of 500 random safe states, granting requests whenever the resources were free (without the safety check) reached a deadlock, whereas applying the Banker's rule never did. So the two statements to remember are: unsafe means deadlock is possible; and safe means deadlock can be avoided, by following the safe sequence logic.

Cheat box

Need $=$ Max $-$ Allocation. Available $=$ Total $-$ sum of Allocation.
Safe: there is an order in which every process finds Need $\le$ Work (Work starts at Available and grows by each finished process's Allocation).
Safety algorithm: pick any unfinished $P_i$ with Need $_i \le$ Work; Work $+=$ Allocation $_i$ ; repeat. All finished: safe. Cost $O(mn^2)$ .
Request: Request $\le$ Need, Request $\le$ Available, pretend, check safety, grant or restore.
Safe $\Rightarrow$ no deadlock; unsafe $\Rightarrow$ deadlock possible (not certain); deadlock $\Rightarrow$ unsafe.
Avoidance needs maximum claims in advance. Single instance: claim edges, grant only if no cycle.

Traps and GATE patterns

Connections

Builds on

Deadlock: conditions and resource allocation graphs

Unlocks

Producer-consumer, readers-writers, dining philosophersuses Deadlock: conditions and resource allocation graphsuses Deadlock detection and recoverycontrasts with

Across subjects

No cross-subject links yet.

Within this subject

Deadlock: conditions and resource allocation graphsuses Deadlock detection and recoverycontrasts-with Producer-consumer, readers-writers, dining philosophersuses Semaphoresuses

Avoidance builds on the resource allocation graph and the necessary conditions of deadlock conditions; the alternative is to let deadlock occur and use detection and recovery, whose detection algorithm is the safety algorithm with the processes' current requests in place of their Needs. Semaphores and the philosophers' forks of the classic problems are resources of this kind, but processes there cannot declare their maximum claims in advance, which is why those problems use ordering and limits instead.

PYQs

13 previous year questions from your book. I re-solved each one myself (8 by running or simulating, 5 by reasoning only); the book's key is shown next to my answer. All PYQs

GATE 2026 · MSQQ1 · page 330 of the book

With respect to deadlocks in an operating system,
which of the following statements is/are FALSE?

(a)Banker's algorithm is used to prevent deadlocks
(b)Deadlock formation can be prevented by ensuring that the hold and wait condition is not allowed
(c)An assignment edge in a resource allocation graph is marked from a process to a resource
(d)A safe state guarantees that all processes can finish without formation of a deadlock

GATE 2026 · NATQ2 · page 330 of the book

Consider a system consisting of k instances of a
resource R, being shared by 5 processes.

Assume:
● Each process requires a maximum of two
instances of resource R.
● A process can request or release only one
instance at a time.
● A process can request the second instance only
after acquiring the first instance.

The minimum value of k for the system to be
deadlock-free is ______.

GATE 2019 · MCQQ5 · page 331 of the book

Consider the following snapshot of a system
running  n concurrent processes. Process i is
holding Xi instances of a resource R, 1 ≤ i ≤ n.
Assume that all instances of R are currently in use.
Further, for all i process i can place a request for at
most Yi additional instances of R while holding the
Xi instances it already has. Of the n processes, there
are exactly two processes p and q such that Yp = Yq
= 0. Which one of the following conditions
guarantees that no other process apart from p and q
can complete execution?

(a)Min (Xp, Xq) ≥ Min {Yk | 1 ≤ k ≤ n, k ≠ p, k ≠ q}
(b)Xp + Xq< Max {Yk | 1 ≤ k ≤ n, k ≠ p, k ≠ q
(c)Min (Xp, Xq) ≤ Max {Yk | 1 ≤ k ≤ n, k ≠ p, k ≠ q}
(d)Xp + Xq< Min {Yk | 1 ≤ k ≤ n, k ≠ p, k ≠ q}

GATE 2018 · MCQ · 1 markQ6 · page 331 of the book

In a system, there are three types of resources: E, F
and G. Four processes P0, P1, P2 and P3 execute
concurrently. At the outset, the processes have
declared their maximum resource requirements
using a matrix named Max as given below. For
example, Max [P2, F] is the maximum number of
instances of F that P2 would require. The number of
instances of the resources allocated to the various
processes at any given state is given by a matrix
named Allocation.

Consider a state of the system with the Allocation
matrix as shown below, and in which 3 instances of
E and 3 instances of F are the only resources
available.

Allocation

E
F
G
P0
1
0
1
P1
1
1
2
P2
1
0
3
P3
2
0
0

Max

E
F
G
P0
4
3
1
P1
2
1
4
P2
1
3
3
P3
5
4
1

From the perspective of deadlock avoidance, which
one of the following is true?

(a)The system is in safe state.
(b)The system is not in safe state, but would be safe if one more instance of E were available.
(c)The system is not in safe state, but would be safe if one more instance of F were available.
(d)The system is not in safe state, but would be safe if one more instance of G were available.

GATE 2018 · NAT · 2 marksQ7 · page 331 of the book

Consider a system with 3 processes that share 4
instances of the same resource type. Each process can
request a maximum of K instances. Resource
instances can be requested and released only one at a
time. The largest value of K that will always avoid
deadlock is _________.

GATE 2017 · MCQQ9 · page 332 of the book

A system shares 9 tape drives. The current
allocation and maximum requirement of tape drives
for three processes are shown below:

Proces
s
Current
Allocation
Maximum
Requirement
P1
3
7
P2
1
6
P3
3
5

Which of the following best describes the current
state of the system?

(a)Safe, Deadlocked
(b)Safe, Not Deadlocked
(c)Not Safe, Deadlocked
(d)Not Safe,Not Deadlocked

GATE 2015 · MCQQ10 · page 332 of the book

A system has 6 identical resources and N processes
competing for them. Each process can request at
most 2 resources. Which one of the following
values of N could lead to a deadlock?

(a)1
(b)2
(c)3
(d)6

GATE 2014 · MCQQ12 · page 332 of the book

A system contains three programs and each requires
three tape units for its operation. The minimum
number of tape units which the system must have
such that deadlocks never arise is _________.

GATE 2014 · MCQQ13 · page 332 of the book

An operating system uses the Banker's algorithm for
deadlock avoidance when managing the allocation
of three resource types X, Y, and Z to three
processes P0, P1, and P2. The table given below
presents the current system state. Here, the
Allocation matrix shows the current number of
resources of each type allocated to each process and
the Max matrix shows the maximum number of
resources of each type required by each process
during its execution.

Allocation
Max

X
Y
Z
X
Y
Z
P 0
0
0
1
8
4
3
P 1
3
2
0
6
2
0
P 2
2
1
1
3
3
3

There are 3 units of type X, 2 units of type Y and 2
units of type Z still available. The system is currently
in a safe state. Consider the following independent
requests for additional resources in the current state:

REQ1: P0 requests 0 units of X,

0 units of Y and 2 units of Z

OPERATING SYSTEMS

REQ2: P1 requests 2 units of X,

0 units of Y and 0 units of Z

Which one of the following is TRUE?

(a)Only REQ1 can be permitted.
(b)Only REQ2 can be permitted.
(c)Both REQ1 and REQ2 can be permitted.
(d)Neither REQ1 nor REQ2 can be permitted.

GATE 2008 · MCQ · 2 marksQ17 · page 334 of the book

Which of the following is NOT true of deadlock
prevention and deadlock avoidance schemes?

(a)In deadlock prevention, the request for resources is always granted if the resulting state is safe
(b)In deadlock avoidance, the request for resources is always granted if the resulting state is safe
(c)Deadlock avoidance is less restrictive than deadlock prevention
(d)Deadlock avoidance requires knowledge of resource requirements a priori

GATE 2007 · MCQ · 2 marksQ18 · page 334 of the book

A single processor system has three resource types
X, Y, and Z, which are shared by three processes.
There are 5 units of each resource type.

The column alloc denotes the number of units of
each resource type allocated to each process, and
the column request denotes the number of units of
each resource type requested by a process in order
to complete execution.

Which of these processes will finish LAST?

alloc (X Y Z)
request (X Y Z)
P0
1 2 1
1 0 3
P1
2 0 1
0 1 2
P2
2 2 1
1 2 0

(a)P0
(b)P1
(c)P2
(d)None of the above, since the system is in a deadlock.

GATE 2006 · MCQ · 2 marksQ19 · page 334 of the book

Consider the following snapshot of a system running
n processes. Process i is holding xi instances of a
resource R, for 1 ≤ i ≤ n. Currently, all instances of R
are occupied. Further, for all i, process i has placed a
request for an additional yi instances while holding
the xi instances it already has. There are exactly two
processes p and q such that yp = y_q = 0.

Which one of the following can serve as a necessary
condition to guarantee that the system is not
approaching a deadlock?

(a)min(xp, xq) < maxk≠p,q yk
(b)xp+ xq≥mink≠p,q yk
(c)max(xp, xq) > 1
(d)min(xp, xq) > 1

GATE 2005 · MCQ · 2 marksQ20 · page 334 of the book

Suppose n processes, P1,...,Pn, share m identical
resource units, which can be reserved and released
one at a time. The maximum resource requirement of
process Pi is si, where si>0.

Which one of the following is a sufficient condition
for ensuring that deadlock does not occur?

(a)∀i, si < m
(b)∀i, si < n
(c)∑ si < (m + n) n i=1
(d)∑ si < (m × n) n i=1 OPERATING SYSTEMS

Self-check

Question 1

Total resources (10, 5), Allocation P0 (3, 1), P1 (4, 2), Max P0 (7, 3), P1 (6, 4). What is Available and what is each Need?

Show answer

Available $= (10, 5) - (7, 3) = (3, 2)$ . Need P0 $= (4, 2)$ , Need P1 $= (2, 2)$ .

Question 2

Is that state safe?

Show answer

Work $= (3, 2)$ . P1's Need $(2, 2) \le (3, 2)$ : P1 runs, Work $= (3, 2) + (4, 2) = (7, 4)$ . P0's Need $(4, 2) \le (7, 4)$ : P0 runs. Safe, with the sequence P1, P0.

Question 3

A state is unsafe. Is the system deadlocked?

Show answer

Not necessarily. Deadlock is possible but depends on what the processes actually request and when they release.

Question 4

Why does the Banker's algorithm refuse a request for free resources?

Show answer

Because after granting it no safe sequence would exist: the system could not guarantee that every process can finish, so it might end in deadlock.

Revision card

One-screen revision

Need $=$ Max $-$ Allocation; safe = a finishing order exists; unsafe $\neq$ deadlock; deadlock $\Rightarrow$ unsafe.
Safety: Work $=$ Available; pick Need $\le$ Work; Work $+=$ Allocation.
Request: $\le$ Need, $\le$ Available, pretend, test, restore if unsafe.
Needs advance maximum claims; $O(mn^2)$ .

References

·Silberschatz, Galvin, Gagne, Operating System Concepts, Chapter 8 Deadlocks (deadlock avoidance: safe state, resource-allocation-graph algorithm, banker's algorithm)
·Tanenbaum and Bos, Modern Operating Systems, Chapter 6 Deadlocks (deadlock avoidance, the banker's algorithm)
·Stallings, Operating Systems: Internals and Design Principles, Chapter 6 Concurrency: Deadlock and Starvation (deadlock avoidance)

Verification

The safety algorithm is compared in scripts/enum-checks/os_deadlock.py with a brute-force search over every order in which the processes could finish, on 3000 random states (1632 safe), and shown to find a safe sequence whenever one exists whichever eligible process it picks (every maximal greedy path completes in a safe state). The request algorithm is compared with brute-force safety of the pretended state on 471 random legal requests (274 granted). The page's state has 12 safe sequences (listed by the search and counted by the C program on this page, npm run verify:c, and tests/os-deadlock-traces.test.ts). The statement that the Banker's rule never lets a safe state reach deadlock, while granting requests blindly from a safe state did reach a deadlock in 117 of 500 random states, is established by exhaustively exploring the states reachable when processes ask for one unit at a time. The minimum-available example is found by search. The Banker's algorithm assumes a fixed number of processes and resources, known maximum claims and that a process returns what it holds in finite time; real systems rarely satisfy these, which is why it is a textbook algorithm rather than a common one. Textbook chapter titles are from memory. SECOND PASS (2026-11-02, done by the assistant, not a human check): every Self-check question was solved before the printed answer was read and all agreed; the definitions, worked examples, cheat box and traps were read claim by claim and the numbers re-derived by hand. No defect found. Status raised to self-checked; verified needs a textbook or human check.

last verified: never

My notes (saved in this browser)

Deadlock: conditions and resource allocation graphs

Memory management: partitioning and fragmentation

process	alloc A	alloc B	alloc C	max A	max B	max C	need A	need B	need C	finish
P0	2	1	2	4	4	2	2	3	0	-
P1	3	2	1	3	4	1	0	2	0	-
P2	2	0	0	4	2	0	2	2	0	-
P3	1	2	1	3	4	3	2	2	2	-
P4	0	2	1	1	5	5	1	3	4	-

process	alloc A	alloc B	alloc C	max A	max B	max C	need A	need B	need C	finish
P0	2	1	2	4	4	2	2	3	0	-
P1	3	2	1	3	4	1	0	2	0	-
P2	2	0	0	4	2	0	2	2	0	-
P3	1	2	1	3	4	3	2	2	2	-
P4	0	2	1	1	5	5	1	3	4	-

process	alloc A	alloc B	alloc C	max A	max B	max C	need A	need B	need C	finish
P0	2	1	2	4	4	2	2	3	0	-
P1	3	2	1	3	4	1	0	2	0	-
P2	2	0	0	4	2	0	2	2	0	-
P3	1	2	1	3	4	3	2	2	2	-
P4	0	2	1	1	5	5	1	3	4	-