In this project, you will write a Java/C++ program that implements the bankerâs algorithm discussed in Section 8.6.3. Several customers request and release resources from the bank. The banker will grant a request only if it leaves the system in a safe state. A request is denied if it leaves the system in an unsafe state. The bank will employ the strategy outlined in Section 8.6.3, 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 customers 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 functionality of the bank appears in the interface shown in Figure 7.13 (Java). 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, 7 resources initially available. In this case, we can create an implementation of the interface using the following code, Bank bankExample = new BankImpl(10, 5, 7);
The bank will grant a request if the request satisfied the safety algorithm outlined in 8.6.3. If granting the request does leave the system in a safe state, the request is denied.
8.6.3 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 thread 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 thread must wait until some other thread 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 threads 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. An n à m matrix defines the maximum demand of each thread. If Max[i][j] equals k, then thread Ti 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 thread. If Allocation[i][j] equals k, then thread Ti is currently allocated k instances of resource type Rj.
Need. An n à m matrix indicates the remaining resource need of each thread. If Need[i][j] equals k, then thread Ti 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 over time 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 all i = 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 Allocationi and Needi. The vector Allocationi specifies the resources currently allocated to thread Ti; the vector Needi specifies the additional resources that thread Ti may still request to complete its task.