Project 3 – The banker’s algorithm

PROJECT 3*********************************************
The source codes: Bank.java BankImpl.java TestHardness.java
can be compiled and run from the command line
(or)
can be copy pasted (or imported) into an IDE, under a new project
(or)
the NetBeans project (Project3) can be importedinto NetBeans directly.

NOTE: Make sure that infile.txt is containedwithin the same folder as your source codesto ensure that the file will be found atruntime.
*********************************************
Note: Please rename Bank.txt, BankImpl.txt, and TestHardness.txt to Bank.java, BankImpl.java and TestHardness.java. For this project, we will complete Project Banker’s algorithm as it is described Banker’s algorithm: The resource-allocation-graph algorithm is not applicable to a resource allocation system with multiple instances of each resource type.The deadlock avoidance algorithm that we describe next is applicable to such a system but is less efficient than the resource-allocation graph scheme. This algorithm is commonly known as the banker’s algorithm. The name was chosen because the algorithm could be used in a banking system to ensure that the bank never allocated its available cash in such a way that it could no longer satisfy the needs of all its customers. When a new process enters the system, it must declare the maximum number of instances of each resource type that it may need. This number may not exceed the total number of resources in the system. When a user requests a set of resources, the system must determine whether the allocation of these resources will leave the system in a safe state. If it will, the resources are allocated; otherwise, the process must wait until some other process releases enough resources. Several data structures must be maintained to implement the banker’s algorithm. These data structures encode the state of the resource-allocation system. We need the following data structures, where n is the number of processes in the system and m is the number of resource types: • Available . A vector of length m indicates the number of available resources of each type. If Available [j] equals k, then k instances of resource type Rj are available. • Max. Ann × m matrix defines the maximum demand of each process. If Max[i][j] equals k, then process Pi may request at most k instances of resource type Rj. • Allocation.An n×m matrix defines the number of resources of each type currently allocated to each process. If Allocation [i] [j] equals k, then process Pi is currently allocated k instances of resource type Rj. Deadlocks • Need. Ann × m matrix indicates the remaining resource need of each process. If Need [i] [j] equals k,then process Pi may need k more instances of resource type Rj to complete its task. Note that Need [i] [j] equals Max[i] [j] −Allocation[i][j]. These data structures vary overtime in both size and value. To simplify the presentation of the banker’s algorithm, we next establish some notation. Let X and Y be vectors of length n. We say that X ≤ Y if and only if X[i] ≤ Y[i] for alli = 1, 2, ..., n. For example, if X = (1,7,3,2) and Y = (0,3,2,1), then Y≤X. In addition, Y < X if Y≤X and Y=X. We can treat each row in the matrices Allocation and Need as vectors and refer to them as Allocation and Need. The vector Allocation specifies the resources currently allocated to process Pi; the vector Need specifies the additional resources that process Pi may still request to complete its task. 1 Safety Algorithm We can now present the algorithm for finding out whether or not a system is in a safe state. This algorithm can be described as follows: 1. Let Work and Finish be vectors of length m and n, respectively. Initialize Work = Available and Finish[i]=false for i = 0, 1, ..., n−1. 2. Find an index i such that both a. Finish[i] ==false b. Need ≤Work If no such i exists, go to step 4. 3. Work = Work + Allocation Finish[i]=true Go to step 2. 4. If Finish[i] ==true for all i, then the system is in a safe state. This algorithm may require an order of m×n2 operations to determine whether a state is safe. 2 Resource-Request Algorithm Next,we describe the algorithm for determining whether requests can be safely granted. Let Request be the request vector for process Pi. If Request [j] == k, then process Pi wants k instances of resource type Rj. When are quest for resources is made by process Pi, the following actions are taken: 1. If Request ≤ Need,go to step 2 . Otherwise,raise an error condition,since the process has exceed edits maximum claim. 2. If Request ≤ Available, go to step 3. Otherwise, Pi must wait, since the resources are not available. 3. Have the system pretend to have allocated the requested resources to process Pi by modifying the state as follows: Available= Available- Request; Allocation = Allocation + Request; Need = Need - Request; If the resulting resource-allocation state is safe, the transaction is completed,and process Pi is allocated its resources.However,if then ew state is unsafe, then Pi must wait for Request, and the old resource-allocation state is restored. 3.3 An Illustrative Example To illustrate the use of the banker’s algorithm, consider a system with five processes P0 through P4 and three resource types A,B,and C. Resource type A has ten instances, resource type B has five instances, and resource type C has seven instances.Suppose that,at time T0,the following snap shot of the system has been taken: Allocation Max Available A B C A B C A B C P0 0 1 0 7 5 3 3 3 2 P1 2 0 0 3 2 2 P2 3 0 2 9 0 2 P3 2 1 1 2 2 2 P4 0 0 2 4 3 3 The content of the matrix Need is defined to be Max − Allocation and is as follows: Need ABC P0 743 P1 122 P2 600 P3 011 P4 431 We claim that the system is currently in a safe state. Indeed, the sequence <P1, P3, P4, P2, P0 satisfies the safety criteria. Suppose now that process P1 requests one additional instance of resource type A and two instances of resource type C, so Request1 = (1,0,2). To decide whether this request can be immediately granted, we first check that Request1 ≤ Available—that is, that (1,0,2) ≤ (3,3,2), which is true. We then pretend that this request has been fulfilled, and we arrive at the following new state: Allocation Need Available A B C A B C A B C P0 0 1 0 7 4 3 2 3 0 P1 3 0 2 0 2 0 P2 3 0 2 6 0 0 P3 2 1 1 0 1 1 P4 0 0 2 4 3 1 We must determine whether this new system state is safe. To do so, we execute our safety algorithm and find that the sequence <P1, P3, P4, P0, P2 satisfies the safety requirement. Hence, we can immediately grant the request of process P1. You should be able to see,however, that when the system is in this state,a request for(3,3,0)by P4 cannot be granted,since the resources are not available. Furthermore, a request for (0,2,0) by P0 cannot be granted, even though the resource sare available, since the resulting state is unsafe. We leave it as a programming exercise for students to implement the banker’s algorithm. 1.Read the project description thoroughly before you do anything else. Project description: The Bank The bank will employ the strategy outlined earlier, whereby it will consider requests from n customers for m resources. The bank will keep track of the resources using the following data structures: int numberOfCustomers; // the number of customers int numberOfResources; // the number of resources int[] available; // the available amount of each resource int[] [] maximum; // the maximum demand of each customer int [] [] allocation; // the amount currently allocated // to each customer int[ ] [] need; // the remaining needs of each customer The implementation of this interface will require adding a constructor that is passed the number of resources initially available. For example, suppose we have three resource types with 10, 5, and 7 resources initially available. In this case, we can create an implementation of the interface using the following technique: Bank the Bank = new BankImpl(10,5,7); The bank will grant a request if the request satisfies the safety algorithm outlined . If granting the request does not leave the system in a safe state, the request is denied. Testing Your Implementation You can use the file TestHarness.java, which is available on Wiley Plus, to test your implementation of the Bank interface. This program expects the implementation of the Bank interface to be named BankImpl and requires an input file containing the maximum demand of each resource type for each customer.For example,if there are five customers and three resource types,the input file might appear as follows: 7,5,3 3,2,2 9,0,2 2,2,2 4,3,3 This indicates that the maximum demand for customer0 is 7,5,3;for customer1, 3,2,2; and so forth. Since each line of the input file represents a separate public interface Bank {/** * Add a customer * customerNumber - the number of the customer * maximumDemand - the maximum demand for this customer */ public void addCustomer (int customerNum, int[] maximumDemand); /** * Output the value of available, maximum, * allocation, and need */ public void getState(); /** * Request resources * customerNumber - the customer requesting resources * request - the resources being requested */ public boolean request Resources(int customerNumber, int[] request); /** * Release resources * customerNumber - the customer releasing resources * release - the resources being released */ public void release Resources(int customer Number, int[] release); } customer, the addCustomer() method is to be invoked as each line is read in, initializing the value of maximum for each customer.(In the above example,the value of maximum [0] is initialized to 7,5,3 for customer 0;maximum[1][]is initialized to 3,2,2; and so forth.) Furthermore, TestHarness.java also requires the initial number of resources available in the bank. For example, if there are initially 10, 5, and 7 resources available, we invoke TestHarness.java as follows: java Test Harness infile.txt 10 5 7 where infile.txt refers to a file containing the maximum demand for each customer followed by the number of resources initially available. The available array will be initialized to the values passed on the command line. 2.Your job is to fill out the BankImpl.java file with hints given in the code. Please periodically test your functions as best as you can. 0. Once things start working, you can use the Test Harness program that is included. To run it, type Java TestHarness infile.txt 10 5 7 Or Create a new project configuration from run à set project configuration, and set arguments to be infile.txt 10 5 7. If you input * and press Enter, it will tell you the current state of your bank (as output by your getState() method). If you type RQ 0 2 2 2 then customer 0 will request two of each available resource. Likewise, RL 0 2 2 2 will make customer 0 release two of each resource. Here is an example of my output: run: * Available [10 5 7] Allocation [0 0 0] [0 0 0] [0 0 0] [0 0 0] [0 0 0] Max [7 5 3] [3 2 2] [9 0 2] [2 2 2] [4 3 3] Need [7 5 3] [3 2 2] [9 0 2] [2 2 2] [4 3 3] RQ 4 2 3 5 *2* *3* *5* Customer # 4 requesting 2 3 5 Available = 10 5 7 Approved * Available [8 2 2] Allocation [0 0 0] [0 0 0] [0 0 0] [0 0 0] [2 3 5] Max [7 5 3] [3 2 2] [9 0 2] [2 2 2] [4 3 3] Need [7 5 3] [3 2 2] [9 0 2] [2 2 2] [2 0 -2] RL 4 2 2 2 *2* *2* *2* Customer # 4 releasing 2 2 2 Available = 10 4 4 Allocated = [0 1 3 ]* Available [10 4 4] Allocation [0 0 0] [0 0 0] [0 0 0] [0 0 0] [0 1 3] Max [7 5 3] [3 2 2] [9 0 2] [2 2 2] [4 3 3] Need [7 5 3] [3 2 2] [9 0 2] [2 2 2] [4 2 0] RQ 0 1 3 2 *1* *3* *2* Customer # 0 requesting 1 3 2 Available = 10 4 4 Denied * Available [10 4 4] Allocation [0 0 0] [0 0 0] [0 0 0] [0 0 0] [0 1 3] Max [7 5 3] [3 2 2] [9 0 2] [2 2 2] [4 3 3] Need [7 5 3] [3 2 2] [9 0 2] [2 2 2] [4 4 6]