100 COSC 3355 RAINWATER COURSE ASSIGNMENT II I Write a program in Java or C++ which implements the deadlock detection algorithm as discussed in class: Data Structures: • Available: •

Allocation: • Request: A vector of length m indicates the number of available resources of each type. An n x m matrix defines the number of resources of each type currently allocated to each process. An n x m matrix indicates the current request of each process. If Request[i][j] = k, then process Pi is requesting k more instances of resource type Rj. . Work & Finish: Vectors of length m and n, respectively. Algorithm: 1. Initialize Work ← Available. For i = 1, 2, n, if Allocation; # 0, then Finish[i] ← false; otherwise, Finish[i] ← true. .../ 2. Find an index i such that both (a) (b) Finish [i] Request == false Work 3. if no such i exists, go to step 4. Work Work + Allocationi Finish [i] < true go to step 2 4. If Finish[i] state. ... == false, for some i, 1 ≤ i ≤ n, then the system is in a deadlock Moreover, if Finish[i] == false, then process Pi is deadlocked. The less-than-or-equal relation (≤) between two vectors is defined as follows: let X and Y be vectors of length n. We say that X ≤ Y if and only if x[i] ≤ y[i] Vi = 1, 2, n. The rows of the Allocation and Request matrices are treated as vectors and are referred to as Allocation; and Requesti in the algorithm. For each test case, the pro- gram should output the Available, Allocation, and Request matrices along with an indi- cation of whether the system is in a deadlock state. If the system is in a deadlock state, those processes which are deadlocked should also be indicated. Note that multi- ple input data sets may require you to execute your program multiple times data sets include the following system states: single instance of each resource type (no dead- lock), single instance of each resource type (deadlock), multiple instances of each re- source type (no deadlock), and multiple instances of each resource type (deadlock). System Resource Allocation Graphs for these are provided in a separate addendum file. Be sure to follow the techniques of good programming style and use extensive comments to provide for internal documentation of your source program. You will be required to separately provide your source program file(s), your input data file(s), and your out- put file(s) (or screenshots of the output) via Canvas submission. Please submit these deliverables on or before the assignment due date. Also, be sure to include copies of the system resource-allocation graphs used for each input test case.