bankers algorithm

Bankers Algorithm Implement the Banker's algorithm (see next page) for deadlock avoidance. 1) Read following inputs from a file - [login to view URL] a. the number of process and number of resource b. Read allocation and max for each process and each resource 2) Write outputs to a file – [login to view URL] a. whether this system is safe or not b. if safe, sequence of processes 3) Submit the source code, [login to view URL], and output.txt. Formats of [login to view URL] and [login to view URL] [login to view URL] ========================================================= 5 <= number of process, P0 ~ P4 4 <= number of resource, A ~ D 0 0 1 2 <= Allocation 1 0 0 0 1 3 5 4 0 6 3 2 0 0 1 4 0 0 1 2 <= Max 1 7 5 0 2 3 5 6 0 6 5 2 0 6 5 6 1 5 2 0 <= Available [login to view URL] ========================================================= Safe P0 – P2 – P1 – P3 – P4 Data Structures for the Banker’s Algorithm Let n = number of processes, and m = number of resources types. ■ Available: Vector of length m. If available [j] = k, there are k instances of resource type Rj available ■ Max: n x m matrix. If Max [i,j] = k, then process Pi may request at most k instances of resource type Rj ■ Allocation: n x m matrix. If Allocation[i,j] = k then Pi is currently allocated k instances of Rj ■ Need: n x m matrix. If Need[i,j] = k, then Pi may need k more instances of Rj to complete its task Need [i,j] = Max[i,j] – Allocation [i,j] Safety Algorithm 1. Let Work and Finish be vectors of length m and n, respectively. Initialize: Work = Available Finish [i] = false for i = 0, 1, …, n- 1 2. Find an i such that both: (a) Finish [i] = false (b) Needi ≤ Work If no such i exists, go to step 4 2. Work = Work + Allocationi Finish[i] = true go to step 2 4. If Finish [i] == true for all i, then the system is in a safe state