edited by
21,931 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.
edited by

5 Answers

Best answer
42 votes
42 votes

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
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 votes
1 votes

Request 1 leads to unsafe state

Request 2 leads to safe state

1 votes
1 votes

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

27 votes
27 votes
2 answers
1
22 votes
22 votes
5 answers
4
go_editor asked Sep 28, 2014
13,490 views
A system contains three programs and each requires three tape units for its operation. The minimum number of tape units which the system must have such that deadlocks nev...