Deadlock avoidance — Banker's algorithm: Question bank

Before you start, refresh the vocabulary these traps lean on: Deadlock — Coffman conditions, Deadlock prevention, Deadlock detection and recovery, Resource Allocation Graph, and Process scheduling.

True or false — justify

An unsafe state is the same as a deadlocked state.

False — an unsafe state only means no safe sequence is currently guaranteed, so deadlock could become unavoidable; the processes may still all be running and might even finish if requests arrive in a lucky order.

Every safe state avoids deadlock right now.

True — "safe" means at least one ordering exists in which every process finishes, so by definition nobody is permanently stuck at this instant.

A deadlocked state is always unsafe.

True — if processes are already deadlocked, no ordering lets them all finish, which is exactly the definition of unsafe (unsafe is the broader set; deadlocked is a subset of it).

Banker's algorithm can be run without knowing each process's maximum demand.

False — the whole method rests on

N ee d = M a x - A l l oc a t i o n

; without

M a x

you cannot compute

N ee d

and cannot check whether a process could still finish, so avoidance is impossible.

If a state is safe, granting any request keeps it safe.

False — a grant lowers

A v ai l ab l e

and can destroy the only safe sequence; that is precisely why you must re-run the Safety Algorithm on the pretend state after every request.

A single safe sequence is enough to declare the state safe.

True — safety only requires that at least one ordering works; the algorithm stops the moment it completes one such sequence and need not find all of them.

Two different safe sequences describe two different states.

False — the same state can admit several valid safe sequences; they are just alternative escape plans for the identical allocation, not different systems.

Banker's algorithm prevents deadlock by breaking a Coffman condition.

False — that is prevention; Banker's is avoidance: it leaves all four Deadlock — Coffman conditions intact and instead refuses any request that would lead to an unsafe state.

If $A v ai l ab l e$ is the zero vector, the state must be unsafe.

False — if some process's

N ee d

is also zero (it already holds its

M a x

), it can finish and release resources, restarting the pool; safety depends on the whole configuration, not just the free pool.

Spot the error

A student writes: "When process $P_{i}$ finishes in the simulation, do $W or k = W or k + M a x [i]$ ."

Wrong resource returned — a process only ever held

A l l oc a t i o n [i]

, not

M a x [i]

; its extra

N ee d

was already borrowed from

W or k

in the "can it finish?" test, so returning

M a x

would invent resources that never existed.

A student checks a request with: "If $R e q u es t_{i} \leq A v ai l ab l e$ , grant it immediately."

Two errors — it skips the

R e q u es t_{i} \leq N ee d_{i}

safety/validity check, and it skips re-running the Safety Algorithm on the resulting state; fitting in

A v ai l ab l e

says nothing about whether everyone can still finish afterward.

A student compares vectors as " $N ee d_{i} \leq W or k$ if the sum of $N ee d_{i}$ is $\leq$ the sum of $W or k$ ."

Wrong comparison —

\leq

here is componentwise: it must hold for every resource type separately. A process short by even one unit of a single resource cannot proceed, regardless of totals.

A student sets $W or k = 0$ at the start of the Safety Algorithm.

Wrong initialization —

W or k

starts at

A v ai l ab l e

, the resources actually free right now; starting at zero pretends nothing can ever be lent, breaking the very first "can a process finish?" test.

A student concludes "the request was refused, so the system is deadlocked."

Confusing refusal with deadlock — refusal means the grant would be unsafe, so

P_{i}

simply waits; the current state is untouched and still safe, no deadlock has occurred.

A student computes $N ee d_{i} = A l l oc a t i o n_{i} - M a x_{i}$ .

Subtraction reversed —

N ee d = M a x - A l l oc a t i o n

(ceiling minus what you already hold). Reversing it gives negative numbers and misreads how much each process can still demand.

A student says " $R e q u es t_{i} > N ee d_{i}$ just means $P_{i}$ waits in the queue."

Wrong handling — asking beyond your declared

M a x

is a violation/error, not a resource shortage; it must be flagged as a bug, not politely queued like a legitimate wait.

Why questions

Why does the banker verify safety by pretending to grant, instead of checking the current state?

Because the danger only appears in the resulting state — the grant reduces

A v ai l ab l e

and changes

A l l oc a t i o n

and

N ee d

, so you must inspect the post-grant configuration to know whether a safe sequence still survives.

Why is Banker's algorithm called "conservative"?

Because it refuses some requests that would in fact never lead to deadlock in practice; it only cares that a safe sequence is guaranteed, so it errs on the side of caution and can reduce resource utilization.

Why must $M a x$ be declared in advance rather than discovered as processes run?

The algorithm reasons about worst-case future demand to guarantee an escape plan exists; without knowing the ceiling it cannot rule out a future request that would trap the system.

Why does adding $A l l oc a t i o n [i]$ (not $N ee d [i]$ ) to $W or k$ correctly model a finishing process?

A finishing process releases everything it physically held, which is exactly

A l l oc a t i o n [i]

; its

N ee d

was temporarily borrowed from

W or k

to let it finish, so returning only

A l l oc a t i o n

keeps the bookkeeping balanced.

Why is avoidance often preferred over detection-and-recovery in critical systems?

Avoidance guarantees deadlock never happens, so there is no costly rollback, victim termination, or lost work; Deadlock detection and recovery lets deadlock occur first and then pays the price of fixing it.

Why can't Banker's algorithm handle resources that appear or vanish at runtime?

It assumes a fixed total of each resource type to compute a fixed

A v ai l ab l e

; if the total changes unpredictably, the "escape plan" it guaranteed may no longer hold.

Edge cases

What happens when a process's $N ee d$ is already the zero vector?

It can finish immediately no matter what

W or k

is (zero

\leq

anything componentwise), releasing its

A l l oc a t i o n

and enlarging the pool — often the process that unblocks a tight state.

What if a request $R e q u es t_{i}$ is the zero vector?

All three checks pass trivially and the state is unchanged, so it is granted; a zero request neither helps nor harms safety.

A brand-new process arrives with $A l l oc a t i o n = 0$ but a large $M a x$ . Is the state automatically unsafe?

No — with nothing allocated its

N ee d

equals its

M a x

, and as long as that

N ee d

can be satisfied somewhere in a sequence (possibly last, after others release), the state can still be safe.

If every process holds exactly its $M a x$ (all $N ee d = 0$ ), what is the state?

Trivially safe — every process can finish in any order since no one needs anything more; the pool only grows as each releases its held resources.

A state has $A v ai l ab l e$ large enough for several processes but one process needs more of a resource than exists in the entire system. What does this imply?

That is an inconsistent/invalid configuration —

M a x

should never exceed the system total; the Banker's model assumes each

M a x [i] [j]

is at most the total units of resource

j

Two processes each need one more unit of the same single-unit resource, and none is free. Safe or not?

Unsafe (a classic deadlock setup) unless a third process can finish first and release that resource; with only these two and nothing free, neither can proceed and no safe sequence exists.

Recall One-line self-test before you leave

Can you state, in your own words, the single difference between "unsafe" and "deadlocked"? ::: Deadlocked = stuck now with no ordering possible; unsafe = the algorithm can't guarantee an ordering, so deadlock might become forced — unsafe is the larger set that contains all deadlocked states plus risky-but-still-running ones.