in Operating System edited by
21,827 views
44 votes
44 votes

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.
in Operating System edited by
21.8k views

5 Answers

42 votes
42 votes
Best answer

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.

edited by

4 Comments

https://en.wikipedia.org/wiki/Banker%27s_algorithm#Requests

For those who are confused read the above section in the wiki article, I’m just elaborating what it said.

Whenever a new request arrives, We check if it is possible i.e. we have enough resource instances in the available vector to satisfy the request. If it is possible, We assume the request is granted. So we allocate the request in the allocation matrix (also remove resource instances from the available vector appropriately) and check if the system is in a safe state given the allocation. If not (i.e. system is in an unsafe state), deny the request and put it on a waiting list.

Ex. We have available vector, (X, Y, Z) = (3, 2, 2).  In REQ1, P0 requests 2 units of Z and we assume the request is granted. So available vector becomes (3, 2, 0) and in the allocation matrix, for P0 we add 2 units of Z so it becomes 3 (see above answer for the allocation matrix). Now we can satisfy P1’s requirement, the available vector becomes (6, 4, 0). We cannot satisfy either P0 or P2’s requirement. So REQ1 leads to an unsafe state. So REQ1 cannot be permitted and We revert back to when our system was in a safe state. Similarly, we can also see REQ2 can be permitted. So option B) is the answer.

0
0
Allocated P0 (P not) is 0 0 1 not

0 0 3  so this is wrong answer
0
0

@SABAREESH V It’s (0 0 3) After allowing Req 1. So it’s correct.

0
0
25 votes
25 votes

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.   

edited by

1 comment

@ 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/

2
2
1 vote
1 vote

Request 1 leads to unsafe state

Request 2 leads to safe state

by
1 vote
1 vote

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 REQ@

 

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

Answer:

Related questions