Deadlock Avoidance: Banker's Algorithm

A Different Philosophy: Avoid Unsafe States, Rather Than Ban Conditions Outright

Unlike prevention (covered in the previous note), which permanently rules out one of the four required conditions, avoidance allows all four conditions to potentially exist - but carefully checks, before granting any resource request, whether granting it could ever lead toward a deadlock.

Safe States vs Unsafe States

A state is "safe" if there exists at least one possible order in which every process could still finish, even in the worst case. A state is "unsafe" if no such guaranteed order can be found - note that an unsafe state doesn't mean a deadlock has already happened, only that one has become genuinely possible.

The Banker's Algorithm: Checking Before Every Allocation

Before granting a resource request:
  1. Pretend the request is granted (hypothetically only)
  2. Check: does a safe sequence still exist where every process could eventually finish?
  3. If yes  -> actually grant the request
  4. If no   -> deny it for now, process must wait

The Banker's Algorithm (named for how a bank should only lend money if it can still satisfy all customers in some order) simulates granting a request before actually doing so, only proceeding if the resulting state would still be safe.

An Intuitive Worked Example

Total resources available: 10
Process A: currently holds 3, maximum ever needed: 9
Process B: currently holds 2, maximum ever needed: 4

If Process A requests 2 more (bringing it to 5):
  Remaining available: 10 - 5 - 2 = 3
  Can Process A finish with 3 more available? It still needs 9-5=4 more. NOT YET.
  Can Process B finish with 3 more available? It needs 4-2=2 more. YES - grant Process B's remaining need, it finishes and releases everything.
  Now check Process A again with resources freed by B - if it can now finish, the state is SAFE.

What the Banker's Algorithm Requires to Actually Work

Every process must declare its maximum possible resource need in advance, before it starts - information the OS uses to run these safety checks. This is a genuine practical limitation, since many real applications don't know or declare their maximum resource needs upfront.

Prevention vs Avoidance: The Core Trade-off

Prevention is simpler to implement but more restrictive and often wastes resource utilization. Avoidance is more flexible and can achieve better utilization, but requires upfront knowledge of maximum resource needs and constant runtime checking overhead - a genuine trade-off between simplicity and flexibility.