EE328-Project 9: Banker’s Algorithm Solved

1.1 DESCRIPTION
WriteaproblemthatrealizetheresourceallocationanddeadlockavoidancealgorithmBanker’s Algorithm. You can see the detail in the end of chapter 7 of OPERATING SYSTEM CONCEPTS WITH JAVA (Eighth Edition), page 344.

2 ALGORITHM
2.1 RESOURCE TYPES
Several data structures must be maintained to implement the banker’s algorithm. These data structuresencodethestateoftheresource-allocationsystem. Weneedthefollowingdatastructures, 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
An n ×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.

Need
An n × 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] = Max[i][j]− Allocation[i][j].

2.2 SAFETY ALGORITHM
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.
Find an index i such that bothFinish[i] == false
Needi ≤Work
If no such i exists, go to step 4.

Work =Work + Allocationi
Finish[i] = true Go to step 2.

If Finishi[i] == true for all i, then the system is in a safe state.
2.3 RESOURCE-REQUEST ALGORITHM
Let Requesti be the request vector for process Pi. If Requesti == k, then process Pi wants k instancesofresourcetypeRj. WhenarequestforresourcesismadebyprocessPi, thefollowing actions are taken:

If Requesti ≤ Needi, go to step 2. Otherwise, raise an error condition, since the process has exceeded its maximum claim.
If Requesti ≤ Available, go to step 3. Otherwise, Pi must wait, since the resources are not available.
Have the system pretend to have allocated the requested resources to process Pi by modifying the state as follows:
Available = Available −Requesti

Allocationi = Allocationi +Requesti

Needi = Needi −Requesti

Iftheresultingresource-allocationstateissafe, thetransactioniscompleted, andprocess Pi is allocated its resources. However, if the new state is unsafe, then Pi must wait for Requesti, and the old resource-allocation state is restored.

2.4 IMPLEMENTATION
The program requires a txt file to read in matrix Max and the initial Allocation matrix is a zero matrix. The user is required to input a formatted txt file and the Available vector like

java TestHarness < input f ile > 10 5 7

to execute the algorithm.

Then the program will ask the user to input a command iteratively. The user can use "status" to check current matrices an "exit" to quit the program. In order to request or release resources the user have to obey the format:

[request || release] < customer # > <resource #1 > <#2 > <#3 >

And the result will be returned in the command line window.

3 RESULTS
3.1 ENVIRONMENT
Windows 10
Java Development Kit 1.8.0_131
Eclipse
3.2 SCREENSHOTS OF THE RESULT

We use command line to compile and execute the program. The result is shown in Fig. 3.1.

3.3 THOUGHTS
The given interface helps me a lot when finishing this project. In this way the code becomes more standardized and neat.

Figure 3.1: Screenshot of Banker’s Algorithm