The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+21 votes
3.1k 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.

  Allocation Max
  $X$ $Y$ $Z$ $X$ $Y$ $Z$
P0 $0$ $0$ $1$ $8$ $4$ $3$
P1 $3$ $2$ $0$ $6$ $2$ $0$
P2 $2$ $1$ $1$ $3$ $3$ $3$

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.
asked in Operating System by Veteran (99.8k points)
edited by | 3.1k views

4 Answers

+25 votes
Best answer

Option (B)

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

After allowing Req 1,

  Allocated Max Requirement
$P0$ $0 \quad 0\quad 3$ $8 \quad 4\quad 3$ $8 \quad 4\quad 0$
$P1$ $3 \quad 2\quad 0$ $6 \quad 2\quad 0$ $3 \quad 0\quad 0$
$P2$ $2 \quad 1\quad 1$ $3 \quad 3\quad 3$ $1 \quad 2\quad 2$

$\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.

answered by (215 points)
edited by
+11
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

+2
@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.

Please explain ?

+8 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=7, 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=10, Y=7, Z=5  
       
  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=18, Y=11, Z=8  
       
  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.   

answered by Loyal (8.3k points)
0

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

+3 votes
Answer is Option (B)
answered by (215 points)
0
HOW? why not c)
+1 vote

Request 1 leads to unsafe state

Request 2 leads to safe state

answered by Active (2k points)


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

38,079 questions
45,572 answers
132,068 comments
49,045 users