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