Suppose we use the Banker\'s Algorithm to avoid deadlock. Consider a system that

Question

Suppose we use the Banker's Algorithm to avoid deadlock. Consider a system that has 5 processes P_1, P_2, P_3, P_4, P_5 and four types of resources a, b, c and d; it has 6 units of a, 3 units of b, 4 units of c, 2 units of d. The matrix EXISTING[] denotes the existing resource units and is always (6 3 4 2). AVAILABLE[] the units available for allocation; ALLOCATE[] denotes the units that have been allocated to the processes; NEED[] denotes the units that may still be needed by the processes to complete the tasks. Suppose at a certain state the matrices are as shown below. EXISTING = (6 3 4 2) ALLOCATED = (2 0 1 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 0 0) P_1 P_2 P_3 P_4 P_5 NEED = (1 0 2 1 1 1 1 0 2 1 0 1 1 1 0 1 1 0 0 0) a) What is the AVAILABLE matrix? b) Is the system in a safe state? Why? c) If P_4 makes a request of (0 1 0 0), should the system grant the request? (If not, what should the system do?) You must show your steps clearly to prove that your answer is correct!

Explanation / Answer

1. Available is 1-D Matrix and is the amount of each resource available at that instant. The existing matrix shows the number of each resource. The allocated shows number of resources of each type allocated to each process. Hence the available resouces at the given instant would be the difference of Exisitng and Allocated.

Hence, first the sum of each column of the allocated will be computed to find the total number of resources of each type that are allocated. Then it will be subtracted from the existing matrix.

Allocated = [2+0+1+1+1 0+1+0+1+0 1+0+1+0+1 0+1+0+0+0] = [5 2 3 1]

Therefore, available = [6 3 4 2] - [5 2 3 1] = [1 1 1 1]

2. Let Work = Available = [1 1 1 1]

For P1, Need = [1 1 0 1], and since Need(P1) < Work, P1 is a part of the safe sequence. Also, Work = Work + Allocation(P1) = [1+2 1+0 1+1 1+0] = [3 1 2 1]

Now, P2, Need = [0 1 1 1] and work = [3 1 2 1] and since need<work, P2 is also a part of safe sequence and hence work = work + allocation(P2) = [3 2 2 2]

Similarly, P3 can also be alloted resources. Hence work = [4 2 3 2]

P4 can also be alloted. Work = [5 3 3 2]

P5 can also be alloted. Work = [6 3 4 2]. Since finally, work = existing, all processes have been completed. Hence, the system is in a safe state. Also, the safe sequence is P1,P2,P3,P4,P5.

3. We will use resource request algorithm here. First we check, whether the request matrix is <= need matrix.

Request = [0 1 0 0] and Need(P4) = [1 2 1 0]. Here request < need, hence we go to the next step.

We check whether Request < Available. Available is [1 1 1 1]. Here request < available. Hence we can now allocate the demand of P4. But, we will need to check whether the system is still in safe state or not. If yes, the request can be fulfilled for P4, else if this lands the system in an unsafe mode, then the request can not be fulfilled.

Available = Available - Request(P4) = [1 1 1 1] - [0 1 0 0] = [1 0 1 1].

Allocated(P4) = Allocated(P4) + Request(P4) = [1 1 0 0] + [0 1 0 0] = [1 2 0 0]

Need(P4) = Need(P4) - Request(P4) = [1 2 1 0] - [0 1 0 0] = [1 1 1 0]

Now we will again apply safety algorithm. Here, Available = [1 0 1 1] = Work. But as we can see, Need >= Work for all processes. Hence, the system is not in a safe state. Therefore, the request of P4 cannot be fulfilled.

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.