The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

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

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

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

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

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 ?

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

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/

- All categories
- General Aptitude 1.3k
- Engineering Mathematics 5.5k
- Digital Logic 2.1k
- Programming & DS 4k
- Algorithms 3.4k
- Theory of Computation 4.2k
- Compiler Design 1.6k
- Databases 3.1k
- CO & Architecture 2.7k
- Computer Networks 3.1k
- Non GATE 1.1k
- Others 1.4k
- Admissions 501
- Exam Queries 449
- Tier 1 Placement Questions 19
- Job Queries 62
- Projects 12

38,079 questions

45,572 answers

132,068 comments

49,045 users