Skip to content
Tutorials Center
My learning

Topics

Lesson 34 of 66 ยท Deadlocks

Deadlock Avoidance and the Banker's Algorithm

Learn safe and unsafe states, run the safety algorithm and the resource-request algorithm step by step, and see the banker's algorithm avoid every deadlock in Python.

Prevention rules out deadlocks by restricting how resources are requested, which often wastes resources. Avoidance is more flexible: the system allows all four conditions but looks at each request and grants it only if the system can still reach a state in which every process can finish. For that, it needs advance information: each process must declare the maximum it may ever need of each resource.

The best-known avoidance method is Dijkstra's banker's algorithm. The name comes from a bank that never lends out so much money that it cannot satisfy the largest remaining credit lines of its customers.

Safe and unsafe states

A safe state is one in which there exists at least one safe sequence: an order of all processes P_a, P_b, ... such that each process can obtain what it still needs from the free resources plus whatever the processes earlier in the sequence will release when they finish.

  • Safe state: deadlock is not present and the system can guarantee it can avoid one.
  • Unsafe state: deadlock is possible (not certain: processes might happen to release resources in time).
  • Deadlock state: a subset of unsafe states, where it has already happened.
flowchart LR
    S["Safe states"] --- U["Unsafe states"]
    U --- D["Deadlock"]
    S:::safe
    classDef safe fill:#d9f2d9,stroke:#2e7d32,color:#000

Avoidance keeps the system inside the safe region. Deadlock lives inside the unsafe region.

The data structures

With n processes and m resource types, the algorithm keeps:

Structure Shape Meaning
Available vector of m Free instances of each type right now
Max n x m Maximum demand declared by each process
Allocation n x m Instances each process holds now
Need n x m Max - Allocation: what each process may still request

The safety algorithm

To decide whether the current state is safe:

  1. Set Work = Available and mark all processes unfinished.
  2. Find an unfinished process whose Need <= Work. If none exists, go to step 4.
  3. Pretend it runs to completion and releases everything: Work += Allocation[i], mark it finished, go to step 2.
  4. If all processes are finished, the state is safe (the order found is a safe sequence); otherwise it is unsafe.

Our example: 4 processes, 3 resource types (A, B, C) with totals 7, 5, 6.

Python Is the state safe?

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The free pool is [3, 1, 2]. P0 needs [3, 2, 1], but only one unit of B is free, so it must wait; P1 needs [1, 1, 2] and can go first. The algorithm finds the sequence P1, P0, P2, P3. Other safe sequences may exist, but one is enough to prove safety.

The resource-request algorithm

When process P_i asks for a vector Request:

  1. If Request > Need[i], error: the process exceeded its declared maximum.
  2. If Request > Available, the process waits (not enough resources now).
  3. Otherwise pretend to grant: Available -= Request, Allocation[i] += Request, Need[i] -= Request, then run the safety algorithm.
  4. If the resulting state is safe, the grant becomes real. If it is unsafe, roll back and make the process wait, even though the resources are physically available.
Python Grant or deny a request

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The interesting case is P0 asking for [3, 0, 0]. Three units of A are free, but after granting them, nobody could be guaranteed to finish, so the request is denied and P0 waits. This is the difference between avoidance (looks ahead) and simply "grant if available".

How well does it work?

Let us compare the banker's policy with a naive one ("grant any request that fits in what is free") on random workloads: 4 processes with random maximum demands on 3 resource types, each asking for one unit at a time. A run is a deadlock if unfinished processes remain and no request can be granted.

Python Banker's algorithm versus naive granting

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Naive granting deadlocks in most of these workloads (the random maximum demands are deliberately large). The banker's algorithm never does, because it only ever moves between safe states. (In this model, maximum demands never exceed the totals; if a process could declare more than exists, no algorithm could help.)

Limits of the banker's algorithm

  • Every process must declare its maximum demand in advance, which is rarely known for general programs.
  • The number of processes and resources must stay fixed, and processes must release resources in finite time.
  • It costs O(m x n^2) operations per request.
  • It can leave resources idle (denied requests) even when granting them would have been harmless.

For these reasons, general-purpose systems seldom use it. It remains important for understanding safe states, in databases and real-time systems with known resource budgets, and as a classic exam topic.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What is a safe sequence?

    If such an order exists the state is safe: the processes can all finish one after another.
  2. 2. How is the Need matrix computed?

    Need is what a process may still request: its declared maximum minus what it already holds.
  3. 3. A request fits in Available but the resulting state is unsafe. What does the banker's algorithm do?

    Avoidance looks ahead: only requests leading to a safe state are granted.
  4. 4. Is every unsafe state a deadlock?

    In an unsafe state a deadlock may or may not occur depending on how processes behave. Avoidance simply refuses to take that risk.
  5. 5. Which information must be known in advance for the banker's algorithm?

    Max is an input of the algorithm. This requirement is the main reason it is rarely used in general-purpose systems.

Summary

  • Avoidance keeps the system in safe states, where some order lets every process finish.
  • The banker's algorithm uses Available, Max, Allocation and Need = Max - Allocation.
  • The safety algorithm searches for a safe sequence; the request algorithm pretends to grant, then checks safety.
  • Unsafe means deadlock is possible, not certain.
  • It needs advance maximum claims and fixed numbers of processes, so it is used mostly in specialised settings.

Next: Deadlock Detection, Recovery and the Ostrich Algorithm