The Gateway to Computer Science Excellence

+25 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**?

- Only REQ1 can be permitted.
- Only REQ2 can be permitted.
- Both REQ1 and REQ2 can be permitted.
- Neither REQ1 nor REQ2 can be permitted.

+28 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.

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 ?

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

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 ?

+14 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.

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

0 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 [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**

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.3k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.1k
- Non GATE 1.5k
- Others 1.5k
- Admissions 595
- Exam Queries 576
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 17

50,647 questions

56,459 answers

195,378 comments

100,274 users