Prerequisite: Banker’s Algorithm

The banker’s algorithm is a resource allocation and deadlock avoidance algorithm that tests for safety by simulating the allocation for predetermined maximum possible amounts of all resources, then makes an “s-state” check to test for possible activities, before deciding whether allocation should be allowed to continue.

Following **Data structures** are used to implement the Banker’s Algorithm:

Let **‘n’ **be the number of processes in the system and **‘m’ **be the number of resources types.

**Available : **

- It is a 1-d array of size
**‘m’**indicating the number of available resources of each type. - Available[ j ] = k means there are
**‘k’**instances of resource type**R**_{j}

**Max :**

- It is a 2-d array of size ‘
**n*m’**that defines the maximum demand of each process in a system. - Max[ i, j ] = k means process
**P**may request at most_{i}**‘k’**instances of resource type**R**_{j.}

**Allocation :**

- It is a 2-d array of size
**‘n*m’**that defines the number of resources of each type currently allocated to each process. - Allocation[ i, j ] = k means process
**P**is currently allocated_{i}**‘k’**instances of resource type**R**_{j}

**Need :**

- It is a 2-d array of size
**‘n*m’**that indicates the remaining resource need of each process. - Need [ i, j ] = k means process
**P**currently allocated_{i}**‘k’**instances of resource type**R**_{j} - Need [ i, j ] = Max [ i, j ] – Allocation [ i, j ]

Allocation_{i} specifies the resources currently allocated to process P_{i} and Need_{i} specifies the additional resources that process P_{i} may still request to complete its task.

Banker’s algorithm consist of Safety algorithm and Resource request algorithm

**Safety Algorithm**

The algorithm for finding out whether or not a system is in a safe state can be described as follows:

- Let Work and Finish be vectors of length ‘m’ and ‘n’ respectively.

Initialize: Work= Available

Finish [i]=false; for i=1,2,……,n - Find an i such that both

a) Finish [i]=false

b) Need_i<=work

if no such i exists goto step (4) - Work=Work + Allocation_i

Finish[i]= true

goto step(2)

- If Finish[i]=true for all i,

then the system is in safe state.

**Safe sequence is the sequence in which the processes can be safely executed.**

In this post, implementation of Safety algorithm of Banker’s Algorithm is done.

## C++

`// C++ program to illustrate Banker's Algorithm ` `#include<iostream> ` `using` `namespace` `std; ` ` ` `// Number of processes ` `const` `int` `P = 5; ` ` ` `// Number of resources ` `const` `int` `R = 3; ` ` ` `// Function to find the need of each process ` `void` `calculateNeed(` `int` `need[P][R], ` `int` `maxm[P][R], ` ` ` `int` `allot[P][R]) ` `{ ` ` ` `// Calculating Need of each P ` ` ` `for` `(` `int` `i = 0 ; i < P ; i++) ` ` ` `for` `(` `int` `j = 0 ; j < R ; j++) ` ` ` ` ` `// Need of instance = maxm instance - ` ` ` `// allocated instance ` ` ` `need[i][j] = maxm[i][j] - allot[i][j]; ` `} ` ` ` `// Function to find the system is in safe state or not ` `bool` `isSafe(` `int` `processes[], ` `int` `avail[], ` `int` `maxm[][R], ` ` ` `int` `allot[][R]) ` `{ ` ` ` `int` `need[P][R]; ` ` ` ` ` `// Function to calculate need matrix ` ` ` `calculateNeed(need, maxm, allot); ` ` ` ` ` `// Mark all processes as infinish ` ` ` `bool` `finish[P] = {0}; ` ` ` ` ` `// To store safe sequence ` ` ` `int` `safeSeq[P]; ` ` ` ` ` `// Make a copy of available resources ` ` ` `int` `work[R]; ` ` ` `for` `(` `int` `i = 0; i < R ; i++) ` ` ` `work[i] = avail[i]; ` ` ` ` ` `// While all processes are not finished ` ` ` `// or system is not in safe state. ` ` ` `int` `count = 0; ` ` ` `while` `(count < P) ` ` ` `{ ` ` ` `// Find a process which is not finish and ` ` ` `// whose needs can be satisfied with current ` ` ` `// work[] resources. ` ` ` `bool` `found = ` `false` `; ` ` ` `for` `(` `int` `p = 0; p < P; p++) ` ` ` `{ ` ` ` `// First check if a process is finished, ` ` ` `// if no, go for next condition ` ` ` `if` `(finish[p] == 0) ` ` ` `{ ` ` ` `// Check if for all resources of ` ` ` `// current P need is less ` ` ` `// than work ` ` ` `int` `j; ` ` ` `for` `(j = 0; j < R; j++) ` ` ` `if` `(need[p][j] > work[j]) ` ` ` `break` `; ` ` ` ` ` `// If all needs of p were satisfied. ` ` ` `if` `(j == R) ` ` ` `{ ` ` ` `// Add the allocated resources of ` ` ` `// current P to the available/work ` ` ` `// resources i.e.free the resources ` ` ` `for` `(` `int` `k = 0 ; k < R ; k++) ` ` ` `work[k] += allot[p][k]; ` ` ` ` ` `// Add this process to safe sequence. ` ` ` `safeSeq[count++] = p; ` ` ` ` ` `// Mark this p as finished ` ` ` `finish[p] = 1; ` ` ` ` ` `found = ` `true` `; ` ` ` `} ` ` ` `} ` ` ` `} ` ` ` ` ` `// If we could not find a next process in safe ` ` ` `// sequence. ` ` ` `if` `(found == ` `false` `) ` ` ` `{ ` ` ` `cout << ` `"System is not in safe state"` `; ` ` ` `return` `false` `; ` ` ` `} ` ` ` `} ` ` ` ` ` `// If system is in safe state then ` ` ` `// safe sequence will be as below ` ` ` `cout << ` ```
"System is in safe state.
Safe"
``` ` ` `" sequence is: "` `; ` ` ` `for` `(` `int` `i = 0; i < P ; i++) ` ` ` `cout << safeSeq[i] << ` `" "` `; ` ` ` ` ` `return` `true` `; ` `} ` ` ` `// Driver code ` `int` `main() ` `{ ` ` ` `int` `processes[] = {0, 1, 2, 3, 4}; ` ` ` ` ` `// Available instances of resources ` ` ` `int` `avail[] = {3, 3, 2}; ` ` ` ` ` `// Maximum R that can be allocated ` ` ` `// to processes ` ` ` `int` `maxm[][R] = {{7, 5, 3}, ` ` ` `{3, 2, 2}, ` ` ` `{9, 0, 2}, ` ` ` `{2, 2, 2}, ` ` ` `{4, 3, 3}}; ` ` ` ` ` `// Resources allocated to processes ` ` ` `int` `allot[][R] = {{0, 1, 0}, ` ` ` `{2, 0, 0}, ` ` ` `{3, 0, 2}, ` ` ` `{2, 1, 1}, ` ` ` `{0, 0, 2}}; ` ` ` ` ` `// Check system is in safe state or not ` ` ` `isSafe(processes, avail, maxm, allot); ` ` ` ` ` `return` `0; ` `} ` |

## Python3

`# Python3 program to illustrate ` `# Banker's Algorithm ` ` ` `# Number of processes ` `P ` `=` `5` ` ` `# Number of resources ` `R ` `=` `3` ` ` `# Function to find the need of each process ` `def` `calculateNeed(need, maxm, allot): ` ` ` ` ` `# Calculating Need of each P ` ` ` `for` `i ` `in` `range` `(P): ` ` ` `for` `j ` `in` `range` `(R): ` ` ` ` ` `# Need of instance = maxm instance - ` ` ` `# allocated instance ` ` ` `need[i][j] ` `=` `maxm[i][j] ` `-` `allot[i][j] ` ` ` `# Function to find the system is in ` `# safe state or not ` `def` `isSafe(processes, avail, maxm, allot): ` ` ` `need ` `=` `[] ` ` ` `for` `i ` `in` `range` `(P): ` ` ` `l ` `=` `[] ` ` ` `for` `j ` `in` `range` `(R): ` ` ` `l.append(` `0` `) ` ` ` `need.append(l) ` ` ` ` ` `# Function to calculate need matrix ` ` ` `calculateNeed(need, maxm, allot) ` ` ` ` ` `# Mark all processes as infinish ` ` ` `finish ` `=` `[` `0` `] ` `*` `P ` ` ` ` ` `# To store safe sequence ` ` ` `safeSeq ` `=` `[` `0` `] ` `*` `P ` ` ` ` ` `# Make a copy of available resources ` ` ` `work ` `=` `[` `0` `] ` `*` `R ` ` ` `for` `i ` `in` `range` `(R): ` ` ` `work[i] ` `=` `avail[i] ` ` ` ` ` `# While all processes are not finished ` ` ` `# or system is not in safe state. ` ` ` `count ` `=` `0` ` ` `while` `(count < P): ` ` ` ` ` `# Find a process which is not finish ` ` ` `# and whose needs can be satisfied ` ` ` `# with current work[] resources. ` ` ` `found ` `=` `False` ` ` `for` `p ` `in` `range` `(P): ` ` ` ` ` `# First check if a process is finished, ` ` ` `# if no, go for next condition ` ` ` `if` `(finish[p] ` `=` `=` `0` `): ` ` ` ` ` `# Check if for all resources ` ` ` `# of current P need is less ` ` ` `# than work ` ` ` `for` `j ` `in` `range` `(R): ` ` ` `if` `(need[p][j] > work[j]): ` ` ` `break` ` ` ` ` `# If all needs of p were satisfied. ` ` ` `if` `(j ` `=` `=` `R ` `-` `1` `): ` ` ` ` ` `# Add the allocated resources of ` ` ` `# current P to the available/work ` ` ` `# resources i.e.free the resources ` ` ` `for` `k ` `in` `range` `(R): ` ` ` `work[k] ` `+` `=` `allot[p][k] ` ` ` ` ` `# Add this process to safe sequence. ` ` ` `safeSeq[count] ` `=` `p ` ` ` `count ` `+` `=` `1` ` ` ` ` `# Mark this p as finished ` ` ` `finish[p] ` `=` `1` ` ` ` ` `found ` `=` `True` ` ` ` ` `# If we could not find a next process ` ` ` `# in safe sequence. ` ` ` `if` `(found ` `=` `=` `False` `): ` ` ` `print` `(` `"System is not in safe state"` `) ` ` ` `return` `False` ` ` ` ` `# If system is in safe state then ` ` ` `# safe sequence will be as below ` ` ` `print` `(` `"System is in safe state."` `, ` ` ` ```
"
Safe sequence is: "
``` `, end ` `=` `" "` `) ` ` ` `print` `(` `*` `safeSeq) ` ` ` ` ` `return` `True` ` ` `# Driver code ` `if` `__name__ ` `=` `=` `"__main__"` `: ` ` ` ` ` `processes ` `=` `[` `0` `, ` `1` `, ` `2` `, ` `3` `, ` `4` `] ` ` ` ` ` `# Available instances of resources ` ` ` `avail ` `=` `[` `3` `, ` `3` `, ` `2` `] ` ` ` ` ` `# Maximum R that can be allocated ` ` ` `# to processes ` ` ` `maxm ` `=` `[[` `7` `, ` `5` `, ` `3` `], [` `3` `, ` `2` `, ` `2` `], ` ` ` `[` `9` `, ` `0` `, ` `2` `], [` `2` `, ` `2` `, ` `2` `], ` ` ` `[` `4` `, ` `3` `, ` `3` `]] ` ` ` ` ` `# Resources allocated to processes ` ` ` `allot ` `=` `[[` `0` `, ` `1` `, ` `0` `], [` `2` `, ` `0` `, ` `0` `], ` ` ` `[` `3` `, ` `0` `, ` `2` `], [` `2` `, ` `1` `, ` `1` `], ` ` ` `[` `0` `, ` `0` `, ` `2` `]] ` ` ` ` ` `# Check system is in safe state or not ` ` ` `isSafe(processes, avail, maxm, allot) ` ` ` `# This code is contributed by ` `# Shubham Singh(SHUBHAMSINGH10) ` |

**Output:**

System is in safe state. Safe sequence is: 1 3 4 0 2

**Illustration : **

Considering a system with five processes P0 through P4 and three resources types A, B, C. Resource type A has 10 instances, B has 5 instances and type C has 7 instances. Suppose at time t0 following snapshot of the system has been taken:

We must determine whether the new system state is safe. To do so, we need to execute Safety algorithm on the above given allocation chart.

Following is the resource allocation graph:

Executing safety algorithm shows that sequence < P1, P3, P4, P0, P2 > satisfies safety requirement.

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.

## leave a comment

## 0 Comments