Bankers Algorithm using Java

What is 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. Simply, It is an algorithm used to avoid Deadlock between working

processes, was developed by  Edsger Dijkstra

What about the naming?

As all we know, Banks have many processes that help their customers, and there must be a way to

order these processes with consideration to deadlock and processes overlaping. So, It is named

so because this algorithm is used in banking systems to determine whether a loan can be

granted or not. 

 

How it works?

Banker's Algorithm tests for safety and deadlock by simulating the allocation of predetermined

maximum possible amounts of all resources, and then makes a "s-state" check to test for possible

deadlock. 

 

Banker's Algorithm using Java

Java language is mature enough to handle any alogorithm available, and that because its has many

strengths and advantagesLet us see how Banker's Algorithm is implemented using Java language.

The Problem

Bankers Algorithm Problem illustration

Consider there are n account holders in a bank and the sum of the money in all of their accounts is S.

Everytime a loan has to be granted by the bank, it subtracts the loan amount from the 

total money the bank has. Then it checks if that difference is greater than S.

 

It is done because, only then, the bank would have enough money even if all the n account

holders draw all their money at once.

 

Whenever a new process is created, it must specify the maximum instances of each resource type that it needs, exactly.

 

The Solution

Let us assume that there are n processes and m resource types. Some data structures that are used to implement the banker's algorithm are:

1. Available

It is an array of length m. It represents the number of available resources of each type. If Available[j] = k, then there are k instances available, of resource type R(j).

2. Max

It is an n x m matrix which represents the maximum number of instances of each resource that a process can request. If Max[i][j] = k, then the process P(i) can request atmost k instances of resource type R(j).

3. Allocation

It is an n x m matrix which represents the number of resources of each type currently allocated to each process. If Allocation[i][j] = k, then process P(i) is currently allocated k instances of resource type R(j).

4. Need

It is an n x m matrix which indicates the remaining resource needs of each process. If Need[i][j] = k, then process P(i) may need k more instances of resource type R(j) to complete its task.

 

Sample Code

Following is a simple java implementation for Banker's Algorithm Code:
/*
 PROGRAM: BANKER'S ALGORITHM

 */

import java.io.*;
import java.util.*;

class BankerAlgorithm {
    static int safe[] = new int[20];
    static int unsafe[] = new int[20];

    static boolean safety(int available[], int allocated[][], int need[][], int n1, int m1) {
        int n = n1;
        int m = m1;
        int nd[][] = new int[n][m];
        int work[] = new int[m];
        int alloc[][] = new int[n][m];

        /* Populate the work array with the passed available array */
        for (int i = 0; i < m; i++) {
            work[i] = available[i];
        }

        /** Print Available array */
        System.out.println("*** Available Array /n");
        for( int i = 0; i < work.length; i++ ) {
            System.out.println( work[i] + " " );
        }

        /* Populate the alloc array with the passed allocated array */
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                alloc[i][j] = allocated[i][j];
            }
        }

        /** Print Allocated array */
        System.out.println("*** Allocated Array /n");
        for( int i = 0; i < alloc.length; i++ ) {
            for( int j = 0; j < alloc[i].length; j++ ) {
                System.out.print( alloc[i][j] + " " );
            }
            System.out.println();
        }

        /* Populate the nd array with the passed need array */
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                nd[i][j] = need[i][j];
            }
        }

        /** Print Need Array */
        System.out.println("*** Need Array \n");
        for( int i = 0; i < nd.length; i++ ) {
            for( int j = 0; j < nd[i].length; j++ ) {
                System.out.print( nd[i][j] + " " );
            }
            System.out.println();
        }

        /* Hold the finished processes */
        boolean finish[] = new boolean[n];

        /* Initialize the finished array to false */
        for (int i = 0; i < n; i++) {
            finish[i] = false;
        }

        /* Two counters for the two-dimensional array */
        int check = 0;
        int check1 = 0;

        /**
         * Chek for safey algorithm.
         *
         * 1. Work = available.
         *    Finish = false.
         *
         * 2. Find an i such that,
         *    Finish[i] = false and Needi < Work.
         *    If no such Item, go step 4
         *
         * 3. Work = Work + Allocationi
         *    Finish[i] = true, then repeat step 2
         *
         * 4. If Finish[i] = true for all i , then
         *    the system is in safe.
         */
        do {
            for (int i = 0; i < n; i++) {
                boolean flag = true; /* Temp Flag */
                if ( finish[i] == false ) {
                    for (int j = 0; j < m; j++) {
                        if (work[j] < nd[i][j]) {
                            flag = false;
                        }
                    }

                    /* If available resources are greater than needed, then assign allocated resources
                     for processing */
                    if ( flag ) {
                        for (int j = 0; j < m; j++) {
                            work[j] += alloc[i][j];
                        }
                        safe[check] = i; /* Put the process number (Pi) in the safe array */
                        check++;
                        finish[i] = true;
                    } else {
                        unsafe[check] = i; /* Put the process number (Pi) in the safe array */
                    }
                }
            }

            check1++; /* Navigate to the next process */
        } while ( check < n && check1 < n);

        if (check > n) {
            return false;
        } else {
            return true;
        }
    } // END-safety() function

     /*static boolean reqFunc(int a[], int al[][], int need[][], int req[],  int pid, int n1, int m1) {
              int n = n1;
              int m = m1;
              int avail[] = new int[m];
              int alloc[][] = new int[n][m];
              int need1[][] = new int[n][m];
              int req1[] = new int[m];
              int r = pid;

              for (int i = 0; i < m; i++)
                    req1[i] = req[i];

               for (int i = 0; i < m; i++)
                    avail[i] = a[i];

               for (int i = 0; i < n; i++)
                    for (int j = 0; j < m; j++)
                         alloc[i][j] = al[i][j];

              for (int i = 0; i < n; i++)
                   for (int j = 0; j < m; j++)
                         need1[i][j] = need[i][j];

              boolean flag = true;

              for (int i = 0; i < m; i++) {
                   if (need1[r][i] < req1[i])
                       flag = false;
                   }

              if (flag) {
                  for (int i = 0; i < m; i++)
                        if (avail[i] < req1[i])
                            flag = false;

              if (flag) {
                 for (int i = 0; i < m; i++) {
                      alloc[r][i] += req1[i];
                      need1[r][i] -= req1[i];
                      avail[i] -= req1[i];
                 }

                 if (safety( avail, alloc, need1, n, m ))
                    return true;
            else
                 System.out.println("It leads to deadlock ,so request can't be granted");
             } else
                 System.out.println("process p" + r + "should wait");
              } else
                 System.out.println("Error:process exceeding Limit");
              return false;

       }*/

    /** Main Function */
    public static void main(String args[]) throws IOException {
        InputStreamReader isr = new InputStreamReader(System.in);
        BufferedReader obj = new BufferedReader(isr);

        int n, m; /* n = Number of Processes, m = Number of resources. */
        System.out.println("enter no. of processes: "); /* Enter number of processes. */
        n = Integer.parseInt(obj.readLine());
        System.out.println("enter no. of resources: "); /* Enter number of Resources. */
        m = Integer.parseInt(obj.readLine());

        int availableArr[] = new int[m]; // Array of available instances
        for (int i = 0; i < m; i++) {
            System.out.println("enter no. of available instances resources: " + i);
            /* Enter number of Available instances. */
            availableArr[i] = Integer.parseInt(obj.readLine());
        }

        System.out.println("enter allocation of resources: ");
        /* Allocation Array. */
        int allocArr[][] = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                /* Enter allocation of instances of resources. */
                System.out.println("enter allocation instances of resources: " + j + " for process p" + i);
                /* Enter allocation of instances of resources. */
                allocArr[i][j] = Integer.parseInt(obj.readLine());
            }
        }

        System.out.println("enter maximum of resources: ");
        int maxArr[][] = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                System.out.println("enter max instances of resources:" + j + "for process p" + i);

                /* Enter max instances of resources for a given resource. */
                maxArr[i][j] = Integer.parseInt(obj.readLine());
            }
        }

        /** Print max Array */
        System.out.println("*** max Array \n");
        for( int i = 0; i < maxArr.length; i++ ) {
            for( int j = 0; j < maxArr[i].length; j++ ) {
                System.out.print( maxArr[i][j] + " " );
            }
            System.out.println();
        }

        /* Needed Array. */
        int needArr[][] = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                /* Populate Need Array */
                needArr[i][j] = maxArr[i][j] - allocArr[i][j];
            }
        }

        /**
         * Now, we have the availableArr, maxArr, neededArr, and allocArr
         * Pass them to function safety() for processing
         */
        if ( safety( availableArr, allocArr, needArr, n, m )) {
            System.out.println("System in Safe State");
            System.out.print("System's Safe sequence:");
            for (int i = 0; i < n; i++) {
                System.out.print( "P" + safe[i] + " " );
            }
        } else {
            System.out.println("System in UnSafe State");
            System.out.print("System's Safe sequence:");
            for (int i = 0; i < n; i++) {
                System.out.print( "P" + unsafe[i] + " " );
            }
        }

                /* Use this to test a given request .... Needs documentation and testing ..
                 * If you have any further request for a given process, enter the process no 
                   and the requested resource 
                   System.out.println("do u wanna to hav a request for any process,then enter
                 Process no. and Requesting resources");
                 int processId = Integer.parseInt(obj.readLine());
                 int requestedRes[] = new int[m];
               for (int i = 0; i < m; i++) {
                     requestedRes[i] = Integer.parseInt(obj.readLine());
               }
               if ( reqFunc(availableArr, allocArr, needArr, requestedRes, processId, n, m) ) {
                   System.out.println("request can be granted");
                   for (int i = 0; i < m; i++) {
                         allocArr[processId][i] += requestedRes[i];
                         needArr[processId][i] -= requestedRes[i];
                         availableArr[i] -= requestedRes[i];
               }
               if (safety(availableArr, allocArr, needArr, n, m)) {
                    System.out.println("System in Safe State");
                    System.out.println("System's Safe sequence:");
                    for (int i = 0; i < n; i++)
                          System.out.println(safe[i] + " ");
               } else
                  System.out.println("System in UnSafe State");
               }*/
    }
}

Video Illustration

Many thank s for Ahmad Nasr for this great video, it illustrates the Banker's Algorithm in a simple and great way. and it is a good starter to understand what Banker's Algorithm.

 

Facebook Twitter Google+