4.9k views

An operating system uses the Banker's algorithm for deadlock avoidance when managing the allocation of three resource types $X, Y,$ and $Z$ to three processes $P0, P1,$ and $P2.$ The table given below presents the current system state. Here, the Allocation matrix shows the current number of resources of each type allocated to each process and the Max matrix shows the maximum number of resources of each type required by each process during its execution.

$$\begin{array}{cccccccc} &\rlap{\textbf{Allocation}} &&&&& \rlap{\textbf{Max}} \\ &\text{X} & \text{Y} & \text{Z} & \text{}& &\text{X} & \text{Y} & \text{Z} \\ \textbf{P0} & \text{0} & \text{0} & \text{1}&&& \text{8} & \text{4} & \text{3} \\ \textbf{P1} & \text{3} & \text{2} & \text{0} &&& \text{6} & \text{2} & \text{0} \\ \textbf{P2} & \text{2} & \text{1} & \text{1} &&& \text{3} & \text{3} & \text{3} \\ \end{array}$$
There are $3$ units of type $X, 2$ units of type $Y$ and $2$ units of type $Z$ still available. The system is currently in a safe state. Consider the following independent requests for additional resources in the current state:

REQ1: $P0$ requests $0$ units of $X, 0$ units of $Y$ and $2$ units of $Z$

REQ2: $P1$ requests $2$ units of $X, 0$ units of $Y$ and $0$ units of $Z$

Which one of the following is TRUE?

1. Only REQ1 can be permitted.
2. Only REQ2 can be permitted.
3. Both REQ1 and REQ2 can be permitted.
4. Neither REQ1 nor REQ2 can be permitted.

edited | 4.9k views

Option (B)

Request $1$ if permitted does not lead to a safe state.

After allowing Req 1,

$$\begin{array}{llllllllllll} &\text{} \rlap{ \textbf{Allocated}} &&&& \rlap{\textbf{Max}} &&&&\rlap{ \textbf{Requirement}} \\ \textbf{P0} & \text{0} & \text{0} & \text{3}&& \text{8} & \text{4} & \text{3} && \text{8} & \text{4} & \text{0} &&& \\ \textbf{P1} & \text{3} & \text{2} & \text{0} && \text{6} & \text{2} & \text{0} && \text{3} & \text{0} & \text{0} \\ \textbf{P2} & \text{2} & \text{1} & \text{1} && \text{3} & \text{3} & \text{3} && \text{1} & \text{2} & \text{2} \\ \end{array}$$
$\text{Available} : X=3,Y=2,Z=0$

Now we can satisfy $P1's$ requirement completely. So Available becomes : $X=6,Y=4,Z=0.$

Since, $Z$ is not available now, neither $P0's$ nor $P2's$ requirement can be satisfied. So. it is an unsafe state.

by (215 points)
edited
+12
0
why we are allocating 2 units to P1 and subtracting 2 units of X from need of X?
If P1 requests additional 2 units of X, doesn't it make need for P1  3,2,2 ?
+3

Question says

. Consider the following independent requests for additional resources in the current state:

So the requirement  matrix should be updated and not the allocation.Can someone check this?

Requirement matrix should be updated to 8 4 3 for first request.Because the process has request and it does not mean that it is allocated.After then we should apply banker's algorithm and then check

+3
@rahul

I agree with you. but 8 4 4
0
available x=3,y=2,z=2 (why you are taking z=0) at the beginning availability
0

It's given that "Consider the following independent requests for additional resources in the current state"  then why are considering the rest of the possibilities while solving ?

Now we can satisfy P1's requirement completely. So Availabe becomes : X=6,Y=4,Z=0.

Since Z is not available now, neither P0 nor P2's requirement can be satisfied. So its an unsafe state.

0
0
If P0 is requesting for a resource then why are we allocating it?

Furthermore addition and subtraction of resources from certain fields is done abruptly.

0
available x=3,y=2,z=2

This is the current safe state.

 AVAILABLE X=3, Y=2, Z=2 MAX ALLOCATION X Y Z X Y Z P0 8 4 3 0 0 1 P1 6 2 0 3 2 0 P2 3 3 3 2 1 1

Now, if the request REQ1 is permitted, the state would become :

 AVAILABLE X=3, Y=2, Z=0 MAX ALLOCATION NEED X Y Z X Y Z X Y Z P0 8 4 3 0 0 3 8 4 0 P1 6 2 0 3 2 0 3 0 0 P2 3 3 3 2 1 1 1 2 2

Now, with the current availability, we can service the need of P1. The state would become :

 AVAILABLE X=6, Y=4, Z=0 MAX ALLOCATION NEED X Y Z X Y Z X Y Z P0 8 4 3 0 0 3 8 4 0 P1 6 2 0 3 2 0 0 0 0 P2 3 3 3 2 1 1 1 2 2

With the resulting availability, it would not be possible to service the need of either P0 or P2, owing to lack of Z resource. Therefore, the system would be in a deadlock. ⇒ We cannot permit REQ1.   Now, at the given safe state, if we accept REQ2 :

 AVAILABLE X=1, Y=2, Z=2 MAX ALLOCATION NEED X Y Z X Y Z X Y Z P0 8 4 3 0 0 1 8 4 2 P1 6 2 0 5 2 0 1 0 0 P2 3 3 3 2 1 1 1 2 2

With this availability, we service P1 (P2 can also be serviced). So, the state is :

 AVAILABLE X=6, Y=4, Z=2 MAX ALLOCATION NEED X Y Z X Y Z X Y Z P0 8 4 3 0 0 1 8 4 2 P1 6 2 0 5 2 0 0 0 0 P2 3 3 3 2 1 1 1 2 2

With the current availability, we service P2. The state becomes :

 AVAILABLE X=8, Y=5, Z=3 MAX ALLOCATION NEED X Y Z X Y Z X Y Z P0 8 4 3 0 0 1 8 4 2 P1 6 2 0 5 2 0 0 0 0 P2 3 3 3 2 1 1 0 0 0

Finally, we service P0. The state now becomes :

 AVAILABLE X=8, Y=5, Z=4 MAX ALLOCATION NEED X Y Z X Y Z X Y Z P0 8 4 3 0 0 1 0 0 0 P1 6 2 0 5 2 0 0 0 0 P2 3 3 3 2 1 1 0 0 0

The state so obtained is a safe state. ⇒ REQ2 can be permitted. So, only REQ2 can be permitted. Hence, B is the correct choice.

by Loyal (9.9k points)
edited
+1

@ Regina Phalange Here  I think available matrix is wrong . kindly compare with this link

http://quiz.geeksforgeeks.org/gate-gate-cs-2014-set-1-question-41/

by (215 points)
0
HOW? why not c)
+1 vote

Request 1 leads to unsafe state

Request 2 leads to safe state

by Active (1.6k points)

REQ1: p0 : 0 0 2

REQ1(0 0 2) <= need(p0)(8 4 2)

REQ1(0 0 2) <= Available(3 2 2)

Allocation = allocation + REQ1

 p0 0 0 3 p1 3 2 0 p2 2 1 1

Need = Need-REQ1

 p0 8 4 0 p1 3 0 0 p2 1 2 2

Max

 p0 8 4 3 p1 6 2 0 p2 3 3 3

Available = Available-REQ1

 X Y Z 3 2 0

Now solve via safetry Bankers algorithms :

work= Available = 3 2 0

need(p1) <= work

work= work + allocation(p1) = 6 4 0

need(p0) or need(p2) > work .so, it return FALSE . its not safe state .

same method apply for [email protected]

REQ2: p1 : 2 0 0

REQ2(2 0 0) <= need(p1)(8 4 2)

REQ2(2 0 0) <= Available(3 2 2)

Allocation = allocation + REQ2

 p0 0 0 1 p1 5 2 0 p2 2 1 1

Need = Need - REQ2

 p0 8 4 2 p1 1 0 0 p2 1 2 2

Available = Available - REQ2

 X Y Z 1 2 2

Now solve via safetry Bankers algorithms :

work= Available = 1 2 2

need(p1) <= work

work= work + allocation(p1) = 6 4 2

need(p2) <= work

work =  work + allocation(p2) = 8 5 3

need(p0) <= work

work =  work + allocation(p0) = 8 5 4

so , state is safe : safe sequence is  {p1 -> p2 -> p0} . may be more . but its one of them .

so this request of p1 GRANTED

by Junior (987 points)