Banker's Algorithm

operating-systems concurrency

Definition

Banker's Algorithm

The Banker’s algorithm is a deadlock avoidance algorithm that ensures the system always remains in a safe state by testing whether resource requests would leave the system capable of completing all processes.

The name derives from a bank that never lends more than it can satisfy if all customers simultaneously demanded their remaining credit lines — using repayments from completed customers to satisfy others.

Data Structures

For a system with $n$ processes and $m$ resource types:

Symbol	Name	Definition
$R$	Resource vector	Total resources: $R=(R_1,\dots ,R_m)$
$V$	Available vector	Free resources: $V=(V_1,\dots ,V_m)$
$C$	Claim matrix	Maximum need: $C_{ij}$ = max of process $i$ for resource $j$
$A$	Allocation matrix	Currently held: $A_{ij}$ = amount of resource $j$ held by process $i$
$N$	Need matrix	Remaining requirement: $N_{ij}=C_{ij}-A_{ij}$

Safety Algorithm

The algorithm determines whether a state is safe by simulating process completion.

Bool isSafe()
    W = V                                    // work vector
    Finish[0..n-1] = {false, ..., false}     // all unfinished
    
    while (exists i such that !Finish[i] && N[i] <= W) {
        W = W + A[i]                         // process i completes
        Finish[i] = true
    }
    
    return (all i: Finish[i])                // true if all can finish

Greedy Completion

A state is safe if we can find an ordering of processes where each process can obtain its remaining needs from currently available resources plus those released by earlier processes in the sequence.

Resource Request Protocol

When process $P_k$ requests resources $Q$:

Bool request(int k, Vector Q)
    if (Q > N[k]) return false          // exceeds declared maximum
    if (Q > V) return false             // insufficient resources available
    
    // Tentative allocation
    V = V - Q
    A[k] = A[k] + Q
    N[k] = N[k] - Q
    
    if (isSafe()) {
        return true                     // grant request
    } else {
        // Rollback
        V = V + Q
        A[k] = A[k] - Q
        N[k] = N[k] + Q
        return false                    // block process
    }

Examples

Safety Check

System: $n=4$ processes, $m=3$ resource types, $R=(9,3,6)$, $V=(1,1,2)$.

$$C=\left[\begin{array}{ccc}3& 2& 2\\ 6& 1& 3\\ 3& 1& 4\\ 4& 2& 2\end{array}\right],A=\left[\begin{array}{ccc}1& 0& 0\\ 5& 1& 1\\ 2& 1& 1\\ 0& 0& 2\end{array}\right],N=C-A=\left[\begin{array}{ccc}2& 2& 2\\ 1& 0& 2\\ 1& 0& 3\\ 4& 2& 0\end{array}\right]$$

$W=(1,1,2)$. Only $P_2$ satisfies $N_2=(1,0,2)\le W$.

• $P_2$ finishes: $W=(1,1,2)+(5,1,1)=(6,2,3)$.
• $P_1$ satisfies $N_1\le W$: $W=(6,2,3)+(1,0,0)=(7,2,3)$.
• $P_3$ satisfies $N_3\le W$: $W=(7,2,3)+(2,1,1)=(9,3,4)$.
• $P_4$ satisfies $N_4\le W$: completes.

All processes complete in order $⟨P_2,P_1,P_3,P_4⟩$. The state is safe.