Banker's Algorithm

operating-systems concurrency

Definition

Banker's Algorithm

The Banker’s algorithm is a resource allocation and deadlock avoidance algorithm that tests for safety by simulating the allocation of predetermined maximum possible amounts of all resources. It ensures that the system always remains in a safe state.

The name comes from the analogy of a bank that never lends more money than it can satisfy if all customers simultaneously demanded their remaining credit lines (using the repayments of finished customers to satisfy the others).

Notation

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

• Resource Vector ($R$): Total resources in the system, $R=(R_1,R_2,\dots ,R_m)$.
• Available Vector ($V$): Resources currently not allocated, $V=(V_1,V_2,\dots ,V_m)$.
• Claim Matrix ($C$): Maximum requirement of each process, where $C_{ij}$ is the maximum need of process $i$ for resource $j$.
• Allocation Matrix ($A$): Current allocation, where $A_{ij}$ is the amount of resource $j$ held by process $i$.
• Required Matrix ($N$): Remaining need, where $N_{ij}=C_{ij}-A_{ij}$.

Safe State Algorithm

To determine if a state is safe:

1. Initialise a working vector $W=V$ and mark all processes as “unfinished.”

2. Find an unfinished process $P_k$ such that its remaining requirements are less than or equal to $W$:

   $$\forall j:N_{kj}\le W_j$$

3. If no such process exists, go to Step 5.

4. If such a process is found, assume it completes, add its currently held resources to $W$ ($W=W+A_k$), mark it as “finished,” and return to Step 2.

5. If all processes are marked “finished,” the state is safe; otherwise, it is unsafe.

Application

When a process $P_k$ requests resources $Q_k$:

1. Verify $Q_{ki}\le N_{ki}$ (request within declared limit).
2. Verify $Q_{ki}\le V_i$ (resources available).
3. Provisional Allocation: Temporarily update $V,A,N$.
4. Safety Check: Run the safe state algorithm.
5. If safe, grant the request; if unsafe, rollback and block the process.

Example

Consider a system with $n=4$ processes and $m=3$ resource categories. The total resource vector is

$$R=(9,3,6)$$

The system state is defined by the following matrices and the available vector $V=(1,1,2)$:

$$C=\stackrel{\text{res.}}{\overbrace{\left[\begin{array}{ccc}3& 2& 2\\ 6& 1& 3\\ 3& 1& 4\\ 4& 2& 2\end{array}\right]}}\}\text{proc.},A=\stackrel{\text{res.}}{\overbrace{\left[\begin{array}{ccc}1& 0& 0\\ 5& 1& 1\\ 2& 1& 1\\ 0& 0& 2\end{array}\right]}}\}\text{proc.}$$

The required matrix $N$ is calculated as $N=C-A$:

$$N=\stackrel{\text{res.}}{\overbrace{\left[\begin{array}{ccc}2& 2& 2\\ 1& 0& 2\\ 1& 0& 3\\ 4& 2& 0\end{array}\right]}}\}\text{proc.}$$

Safety Analysis

To determine if the current state is safe, we simulate the completion of processes using a temporary work vector $W$, starting with the available resources $W=V=(1,1,2)$:

Step 1: Find a Process to Satisfy

We look for an unfinished process whose remaining requirements ($N$) can be met by our current available resources ($W$).

• Comparing $N_1=(2,2,2)$ with $W=(1,1,2)⟹$ Insufficient resources.
• Comparing $N_2=(1,0,2)$ with $W=(1,1,2)⟹$ Satisfied!

Simulation: $P_2$ runs to completion and releases its held resources ($A_2$).

$$W_{new}=W_{old}+A_2=(1,1,2)+(5,1,1)=(6,2,3)$$

Step 2: Find the Next Process

With $W=(6,2,3)$, we check the remaining unfinished processes ($P_1,P_3,P_4$).

• Comparing $N_1=(2,2,2)$ with $W=(6,2,3)⟹$ Satisfied!

Simulation: $P_1$ runs to completion and releases its held resources ($A_1$).

$$W_{new}=W_{old}+A_1=(6,2,3)+(1,0,0)=(7,2,3)$$

Step 3: Continue Search

With $W=(7,2,3)$, we check $P_3$ and $P_4$.

• Comparing $N_3=(1,0,3)$ with $W=(7,2,3)⟹$ Satisfied!

Simulation: $P_3$ runs to completion and releases its held resources ($A_3$).

$$W_{new}=W_{old}+A_3=(7,2,3)+(2,1,1)=(9,3,4)$$

Step 4: Final Process

With $W=(9,3,4)$, only $P_4$ remains.

• Comparing $N_4=(4,2,0)$ with $W=(9,3,4)⟹$ Satisfied!

Simulation: $P_4$ runs to completion and releases its held resources ($A_4$).

$$W_{new}=W_{old}+A_4=(9,3,4)+(0,0,2)=(9,3,6)$$

Conclusion

Since a valid sequence exists ($P_2\to P_1\to P_3\to P_4$) where all processes can eventually be satisfied and finish, the system is in a safe state.