Banker’s Algorithm

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

Furthermore, the following relationships hold:

  1. , for all
    • All resources are either available or allocated.
  2. , for all
    • No process can claim more than the total amount of resources in the system.
  3. , for all
    • 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.


Example code from p.305 of SE350 textbook

Global Data Structures

struct state {
    int resource[m];
    int available[m];
    int claim[n][m];
    int alloc[n][m];

Resource allocation algorithm

if (alloc [i,*] + request [*] > claim [i,*])
    <error>; /* total request > claim*/
else if (request [*] > available [*])
    <suspend process>;
else { /* simulate alloc */
    <define newstate by:
    alloc [i,*] = alloc [i,*] + request [*];
    available [*] = available [*] - request [*]>;
if (safe (newstate))
    <carry out allocation>;
else {
    <restore original state>;
    <suspend process>;

Test for safety algorithm (banker’s algorithm)

boolean safe (state S) {
    int currentavail[m];
    process rest[<number of processes>];
    currentavail = available;
    rest = {all processes};
    possible = true;
    while (possible) {
        <find a process Pk in rest such that
        claim [k,*] – alloc [k,*]<= currentavail;
        if (found) { /* simulate execution of Pk */
            currentavail = currentavail + alloc [k,*];
            rest = rest - {Pk};
    else possible = false;
    return (rest == null);