How Operating Systems Avoid Deadlocks: Dijkstra's Banker's Algorithm

In multiprogramming systems, allocating shared hardware resources (CPU cores, GPUs, disk drives, mutexes) is a delicate balancing act.

Grant a request too eagerly, and you risk an unrecoverable system freeze.

In 1965, Edsger W. Dijkstra formulated the Banker's Algorithm—an algorithm named by analogy with a small-town banker managing revolving lines of cash credit.

⚡ Safe State vs Unsafe State vs Deadlock

A common misconception is that an Unsafe State is a deadlock. It is not!

┌────────────────────────────────────────────────────────┐ │ ALL SYSTEM STATES │ │ ┌──────────────────────────────────────────────────┐ │ │ │ UNSAFE STATES │ │ │ │ ┌──────────────────────────────────┐ │ │ │ │ │ DEADLOCK │ │ │ │ │ └──────────────────────────────────┘ │ │ │ └──────────────────────────────────────────────────┘ │ │ ┌──────────────────────────────────────────────────┐ │ │ │ SAFE STATES │ │ │ │ (Guaranteed Deadlock-Free Execution Sequence) │ │ │ └──────────────────────────────────────────────────┘ │ └────────────────────────────────────────────────────────┘
  • Safe State: There exists at least one order where every process can obtain its maximum needed resources, finish execution, and release all locks.
  • Unsafe State: Not yet deadlocked, but the OS can no longer guarantee that a worst-case spike in resource claims won't cause a deadlock.
  • Deadlock: A closed dependency cycle has formed. No forward progress is possible.

🧠 The Safety Algorithm in 4 Steps

For n processes and m resource types:

  • Available[m]: Number of unallocated instances.
  • Allocation[n][m]: Resources currently held by each process.
  • Max[n][m]: Peak demand declared by each process.
  • Need[n][m] = Max[n][m] - Allocation[n][m]: Remaining claim. 
# The Safety Check Loop work = available.copy() finish = [False] * num_processes while True: # Find process whose remaining Need can be satisfied by Work  found = False for p in range(num_processes): if not finish[p] and all(need[p][r] <= work[r] for r in range(num_resources)): work += allocation[p] # Process finishes and returns resources!  finish[p] = True safe_sequence.append(p) found = True break if not found: break # If all finish == True, system is in a SAFE STATE!

🚀 Why Modern Cloud Kernels Avoid Strict Avoidance

Banker's Algorithm requires every process to declare its maximum resource needs in advance. In modern web servers and container runtimes with dynamic workloads, predicting peak memory or socket usage upfront is nearly impossible.

Instead, production kernels use Deadlock Detection and Preemption.

🛠️ Step Through Banker's Algorithm Interactively

Want to test custom Allocation, Max, and Available matrices and watch the safety sequence calculate live?

👉 Solve custom Banker's Algorithm matrices on the interactive Binary Dose simulator.