# Banker’s Algorithm

Consider a system of $n$ processes and $m$ different types of resources. We define the following vectors and matrices:

Furthermore, the following relationships hold:

- $R_{j}=V_{j}+∑_{i=1}A_{ij}$, for all $j$
- All resources are either available or allocated.

- $C_{ij}≤R_{j}$, for all $i,j$
- No process can claim more than the total amount of resources in the system.

- $A_{ij}≤C_{ij}$, for all $i,j$
- No process is allocated more resources of any type than the process originally claimed to need

The state of the system reflects the current allocation of resources to processes. Consists of:

- 2 vectors: Resource and Available
- 2 matrices: Claim and Allocation

We define 2 kinds of states:

*Safe state*is where there is at least one sequence that does not result in deadlock*Unsafe state*is a state that is not safe

The goal is to always have a safe state.

How to compute?

As yourself, is this a safe state? To figure this out, ask yourself, the very simple question:

*can any one of the four processes be run to completion with the resources available?*

In the example:

- No possible for P1, which needs 2 more units of R1, but there are 0 R1 units left.
- Possible for P2.

So then, you run P2 to completion, and then the resources are freed. You continually ask the question, and if you manage to run all 4 processes to completion, you figure out that the initial state is a safe state.

In this new example, none of the processes can be run to completion. Not enough resources.

#### Pseudocode

Example code from p.305 of SE350 textbook

Global Data Structures

Resource allocation algorithm

Test for safety algorithm (banker’s algorithm)