/* * CheckBanker.java (Checks whether Request is satisfiable or no). * * Written by : Nitin Motgi (nmotgi@cs.ucf.edu) * * This file implements routines that process a request sent from * bankers. * * Portions copyright(c) 2000 to School of Electrical Engineering and * Computer Science, UCF, Orlando. * * Use and distribution of this source code are strictly governed by * terms and conditions set by the authors. * * $Id : CheckBanker.java, v1.0.0 02/15/2001. $ * * Revision History: * * 1. Created basic structure Nitin, v1.0.0 02/15/2001. * 2. Added Documentation. Nitin, v1.0.1 02/15/2001. * 3. Added SafetyAlgo(), Hush!!! Nitin, v2.0.0 02/23/2001. * 4. Final Documentation Check, Nitin, v2.0.1 02/23/2001. * 5. Final Variable Name Check, Nitin, v2.0.2 02/23/2001. * 6. Final Functionality Check, Nitin, v2.0.3 02/23/2001. */ import java.lang.*; import java.util.*; import java.io.*; public class CheckBanker{ int Order[]; /* Default constructor does nothing.*/ public CheckBanker(){ } /* Process each request and display an appropriate message.*/ public void ProcessRequest(int nProcesses, int nResources, int[][] Allocation, int[][] Max, int[][] Need, int[] Available, int[][] Request, int nRequestPro){ boolean bState = false; /* Store the order in which the request can be attempted to be completed.*/ Order = new int[nProcesses]; /* Vector.*/ /* Get the Process ID for this request. As index starts from 0 for all the array access it is reduced by one.*/ int nPro = Request[nRequestPro][0]-1; /* Check if the request is inavlid. That is, if the requesting vector is greater than available for if allocation vector for that process plus the request is greater than maximum.*/ bState = false; for(int nIndexC = 1; nIndexC <= nResources; nIndexC++){ if(Available[nIndexC-1] < Request[nRequestPro][nIndexC] || (Allocation[nPro][nIndexC-1] + Request[nRequestPro][nIndexC]) > Max[nPro][nIndexC-1]) { bState = true; break; }/* End if.*/ }/* End for.*/ if(bState == true){ System.out.println("Improper Request cannot process."); return; }/* End if.*/ /* Update all the things as if request was granted.*/ /* Add request to allocation.*/ for(int nIndexC=0; nIndexC < nResources; nIndexC++) Allocation[nPro][nIndexC] += Request[nRequestPro][nIndexC+1]; /* Update Reserve.*/ for(int nIndexC=0; nIndexC < nResources; nIndexC++) Available[nIndexC] -= Request[nRequestPro][nIndexC+1]; /* Update Need.*/ for(int nIndexC=0; nIndexC < nResources; nIndexC++) Need[nPro][nIndexC] = Max[nPro][nIndexC]-Allocation[nPro][nIndexC]; /* Check if there might be "no deadlock state.".*/ if(CheckNoDeadLock(Max,Available,nProcesses,nResources) == true){ /* The system might never get into deadlock as there as resources to satisfy any request in any order.*/ System.out.println("The system will not deadlock."); return; }/* End if.*/ /* The system might deadlock so we need to check whether system is in safe state or unsafe state.*/ boolean Finish[] = new boolean[nProcesses]; for(int nIndex=0; nIndex < nProcesses; nIndex++) Finish[nIndex] = false; bState=false; boolean bExitState = true; for(int nIndex=0; nIndex < nProcesses; nIndex++){ /* Invoke safety algorithm.*/ SafetyAlgo(nIndex,0,nProcesses,nResources,Finish, Need,Allocation,Available); bState = false; for(int nIndexC=0; nIndexC < nProcesses; nIndexC++) if(Finish[nIndexC] == false){ bState = true; break; }/* End if.*/ if(bState == false){ bExitState = false; break; }/* End if.*/ /* Rest all finish.*/ for(int nIndexC=0; nIndexC < nProcesses; nIndexC++) Finish[nIndexC] = false; }/* End of for.*/ if(bExitState == true){ System.out.println("The system is in an unsafe state."); return; }else{ System.out.print("The System is in safe state, <"); for(int nIndexJ=0; nIndexJ will terminate"); }/* End if.*/ }/* End of ProcessRequest.*/ /* This function uses a top-down approach to find which sequence can satisfy the termination process after this request has been allocated. This does it by build a recursion tree. This function calls itself to generate sequece domain in which it will look for a sequence that can terminate. If we find no sequence then it is indicated by all the finish flag being "false". If there was a sequence, then all the finish flags will "true" and Order will have an order in which the sequence can terminate.*/ private void SafetyAlgo(int nIndex, int nOrderNo, int nProcesses, int nResources, boolean[] Finish, int[][] Need, int[][] Allocation, int[] Work){ boolean bState = true; /* Check if Need(j) < Work.*/ for(int nIndexC=0; nIndexC < nResources; nIndexC++){ if(Need[nIndex][nIndexC] > Work[nIndexC]){ bState = false; break; }/* End if.*/ }/* End for.*/ if(bState == true && Finish[nIndex] == false){ Finish[nIndex] = true; Order[nOrderNo] = nIndex+1; /* Update Work Vector.*/ for(int nIndexC=0; nIndexC < nResources; nIndexC++) Work[nIndexC] = Work[nIndexC] + Allocation[nIndex][nIndexC]; /* With this process selected try other combination from here to find whether all will fit.*/ int nIndexW; for(nIndexW=0; nIndexW < nProcesses; nIndexW++){ if (nIndex != nIndexW){ /* Which this request being completed, generate it's children and check which one will satisfy the request completely.*/ SafetyAlgo(nIndexW,(nOrderNo+1),nProcesses,nResources,Finish, Need,Allocation,Work); }/* End if.*/ }/* End for.*/ /* Check if generated child made it possible for a sequence by setting the state in finish to true.*/ bState = false; for(int nIndexC=0; nIndexC < nProcesses; nIndexC++){ if(Finish[nIndexC] == false){ bState = true; break; }/* End if.*/ }/* End for.*/ if(bState == true){ /* If the children of this index were not able to generate the complete sequence, reset the state of current index to false. meaning this path will not lead to termination sequence.*/ Finish[nIndex] = false; Order[nOrderNo] = 0; /* Re-Initliase the state as it was when it was before being set to true.*/ for(int nIndexD=0; nIndexD < nResources; nIndexD++) Work[nIndexD] -= (Allocation[nIndex][nIndexD]); }/* End if.*/ //else{ // return; //} }/* End if.*/ //else{ // return; //} }/* End of SafetyAlgo.*/ /* This function checks whether after allocating a request do we have enough resources such that we can satisfy any request that comes here after by check need against available. If maximum of a resource is less that available then any combination of that resource can be processed. But in case of failure that is max of a resource is less than available, there might be a situation that the request might fail.*/ public boolean CheckNoDeadLock(int[][] Max, int[] Available, int nProcesses,int nResources){ int nMax; /* For each resource.*/ for(int nIndexR=0; nIndexR < nResources; nIndexR++){ nMax = -99999; for(int nIndexP=0; nIndexP < nProcesses; nIndexP++) if(nMax < Max[nIndexP][nIndexR]) nMax = Max[nIndexP][nIndexR]; if(nMax > Available[nIndexR]) return false; }/* End for.*/ return true; }/* End CheckNoDeadLock.*/ }/* End of CheckBanker.*/