Computer Engineering is coming soon

We're still writing and reviewing the notes for every subject, and we'll open it when every subject is ready. Meanwhile you can practise aptitude, ask Aria about any subject, or see the branches that are ready.

Banker's algorithm

Banker's algorithm is a deadlock-avoidance method that grants resource requests only when doing so leaves the system in a safe state (one where a sequence of process completions exists).

Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.

Why it matters

Banker's algorithm is a classic deadlock-avoidance technique used when multiple instances of limited resources must be allocated safely so that deadlock is avoided. You may see it in some specialized kernel resource managers or embedded/real-time systems where processes can declare maximum needs ahead of time and in educational or research settings; it is rarely used in general-purpose operating systems or mainstream database transaction managers.

Key ideas

  • Safe state: a system state is safe if there exists at least one ordering (sequence) of all processes such that each process can obtain all its remaining needed resources using currently available resources plus resources released by earlier processes in that order. If the system is in a safe state, deadlock cannot occur if processes follow declared maximums.
  • Unsafe state: not necessarily deadlocked, but the system might enter deadlock if certain future requests arrive. The Banker's algorithm forbids entering an unsafe state.

Key variables and matrices (for M resource types and N processes):

  • Total (T): total number of instances of each resource type in the system. Vector length M.
  • Available (A): number of free instances of each resource currently available. Vector length M.
  • Max (Max): for each process i, a vector of maximum demand of each resource type. Matrix N×M.
  • Allocation (Alloc): for each process i, how many instances of each resource type are currently allocated. Matrix N×M.
  • Need (Need): for each process i, remaining need defined as Need[i] = Max[i] − Alloc[i]. Matrix N×M.

Assumptions behind the algorithm (must hold for correctness):

  1. Each process must state its maximum resource demand (Max) before the algorithm runs.
  2. Resources are non-preemptible: once given to a process, they cannot be taken back until the process releases them voluntarily.
  3. Multiple instances of each resource type are possible.
  4. A process may request resources several times; each request must be ≤ its declared Need.
  5. For all i and j, Max[i][j] ≤ Total[j] (a process’s maximum claim for any resource type cannot exceed the total instances in the system).

Exact statement of the algorithms (written so you can reproduce in an exam):

Safety algorithm (to test a state):

  1. Let Work = Available (a copy). Let Finish[i] = false for all processes i.
  2. Find an i such that Finish[i] == false and Need[i] ≤ Work (vector comparison: Need[i][j] ≤ Work[j] for all j = 1..M).
  3. If no such i exists, stop. If all Finish[i] are true, the state is safe; otherwise it is unsafe.
  4. If such i exists, set Work = Work + Allocation[i]; set Finish[i] = true; go to step 2.

Request algorithm (to decide a single request Request[i]):

  1. If Request[i] ≤ Need[i] then continue; else error (process asked more than declared maximum).
  2. If Request[i] ≤ Available then hypothetically allocate: Available' = Available − Request[i]; Allocation'[i] = Allocation[i] + Request[i]; Need'[i] = Need[i] − Request[i]; else do not grant Request[i] now (process must wait).
  3. Run the safety algorithm on the hypothetical state (Available', Allocation', Need').
  4. If the hypothetical state is safe, commit the allocation (make the change permanent) and grant Request[i]; otherwise do not grant Request[i] now (process must wait).

Why safety implies no deadlock (sketch of proof often expected in exams):

  • If the state is safe, by definition there exists a sequence Px1, Px2, ..., Pxn such that each process's Need is ≤ Available plus resources released by earlier processes in sequence. Let the first process in sequence run to completion (it can because its Need is ≤ Available). When it finishes it releases its Allocation to Available, increasing Available for the next in sequence. Repeat for each process; all can finish one by one — hence no deadlock.
  • The Banker's algorithm ensures that every granted request leads to a safe state, so the system cannot move to a state where deadlock is inevitable.

Diagram(s) to draw in exam answers:

  • Draw three labeled matrices or tables side-by-side: Allocation, Max, and Need (Need = Max − Allocation). Label rows P0..PN−1 and columns R0..RM−1.
  • Draw vector Available above or to the right of matrices.
  • To illustrate a safe sequence, draw an arrow sequence P1 → P3 → P4 → ... and under each arrow show how Available changes: Available1 = Available0 + Allocation[P1], etc. Label each step with numbers.

Formulas

Need[i][j] = Max[i][j] − Allocation[i][j] — Need for process i and resource j; units: units (count of resource instances). Applies always when Max and Allocation are known.

Available[j] = Total[j] − Σ_i Allocation[i][j] — Available for resource j; units: units (count). Applies when Total is known.

(Vector inequality) X ≤ Y means X[j] ≤ Y[j] for all j — used when comparing Need and Available.

No other special numeric constants or SI units are needed (resources are counts, not physical units).

Worked examples

Example 1 — find a safe sequence (textbook standard) Given:

  • Total resources: A = 10, B = 5, C = 7 (vector T = [10,5,7]).
  • Allocation matrix (rows P0..P4): P0: [0, 1, 0] P1: [2, 0, 0] P2: [3, 0, 2] P3: [2, 1, 1] P4: [0, 0, 2]
  • Max matrix: P0: [7, 5, 3] P1: [3, 2, 2] P2: [9, 0, 2] P3: [2, 2, 2] P4: [4, 3, 3]

Step 1 — compute Available: sum Allocation column-wise = [7,2,5]. Available = Total − sum = [10−7, 5−2, 7−5] = [3, 3, 2]. Step 2 — compute Need = Max − Allocation per row: P0 Need = [7,4,3] P1 Need = [1,2,2] P2 Need = [6,0,0] P3 Need = [0,1,1] P4 Need = [4,3,1]

Step 3 — safety algorithm: Start Work = Available = [3,3,2], Finish all false.

  • Find a process with Need ≤ Work: P1 ([1,2,2]) ≤ [3,3,2]. Choose P1. Work ← Work + Alloc[P1] = [3,3,2] + [2,0,0] = [5,3,2]. Mark P1 finished.
  • Next: find Need ≤ Work: P3 ([0,1,1]) ≤ [5,3,2]. Choose P3. Work ← [5,3,2] + [2,1,1] = [7,4,3]. Mark P3 finished.
  • Next: P4 ([4,3,1]) ≤ [7,4,3]; Work ← [7,4,3] + [0,0,2] = [7,4,5]. Mark P4 finished.
  • Next: P0 ([7,4,3]) ≤ [7,4,5]; Work ← [7,4,5] + [0,1,0] = [7,5,5]. Mark P0 finished.
  • Next: P2 ([6,0,0]) ≤ [7,5,5]; Work ← ... Mark P2 finished. All processes finish. Safe sequence found: P1, P3, P4, P0, P2.

Final answer (bold as exam-style): System is safe. One safe sequence is P1 → P3 → P4 → P0 → P2.

Example 2 — deciding a request Start with the same state as Example 1. Suppose process P1 requests Request[P1] = [1,0,2]. Decide if grant. Step 1: Check Request ≤ Need[P1] = [1,2,2]. Yes, [1,0,2] ≤ [1,2,2]. Step 2: Check Request ≤ Available = [3,3,2]. Yes, [1,0,2] ≤ [3,3,2]. Step 3: Hypothetical allocate: Available' = [3,3,2] − [1,0,2] = [2,3,0]. Allocation'[P1] = [2,0,0] + [1,0,2] = [3,0,2]. Need'[P1] = [0,2,0]. Step 4: Run safety algorithm on hypothetical state: Work = [2,3,0]. Find process with Need ≤ Work: P1 ([0,2,0]) ≤ [2,3,0], so finish P1 and Work ← Work + Alloc'[P1] = [2,3,0] + [3,0,2] = [5,3,2]. Now proceed as in Example 1 and all processes can finish. Hypothetical state is safe.

Final answer: The request can be safely granted.

(You can show a negative example by choosing a Request that exceeds Available or that leaves no safe sequence; the same steps detect it.)

Common mistakes

  • Not copying Available into Work for the safety check, then accidentally modifying the real Available when simulating.
  • Assuming unsafe = deadlocked. Unsafe means the system might reach deadlock later; it is not necessarily blocked now.
  • Not updating Available after you hypothetically allocate when running the safety algorithm.
  • Mixing up rows (processes) and columns (resource types) when drawing matrices.

For your exam

Question types you will see:

  • Definitions: define Banker's algorithm, safe state, Need, Available.
  • Short notes: explain assumptions, why the algorithm needs maximum claims in advance.
  • Derivations/proofs: show why a safe state guarantees no deadlock (short inductive argument), or prove correctness of the request algorithm.
  • Numericals: given Total, Allocation and Max, compute Available and Need and show a safe sequence (draw matrices and show steps of the safety algorithm). Another common numerical: given a request, show whether it is granted.
  • Diagrams: draw Allocation/Max/Need tables and show Available vector; draw arrows for the safe sequence showing Available changes.

What a full-marks answer includes:

  • Clear definitions of terms used (Available, Allocation, Max, Need, safe state).
  • Explicit assumptions of the algorithm.
  • For algorithm questions: write the safety and request algorithms step by step (as above).
  • For numericals: show all calculations (Available, Need), show each step of the safety algorithm (which process chosen and how Work changes), and final conclusion (safe/unsafe or request granted/denied).

Quick check

  1. Define a safe state in one sentence.
  2. Write the formula for Need[i][j].
  3. If Request[i] ≤ Available but hypothetical state is unsafe, should the request be granted? Answer in one word.

Answers: 1) A state where there exists an ordering of processes such that each can finish with available plus earlier released resources. 2) Need[i][j] = Max[i][j] − Allocation[i][j]. 3) No.

Finished this topic? Mark it so your progress, study plan and readiness keep up.

Stuck on something here?