Banker's Algorithm

The Gateway to Computer Science Excellence

+15 votes

A single processor system has three resource types $X, Y$ and $Z$, which are shared by three processes. There are $5$ units of each resource type. Consider the following scenario, where the column **alloc **denotes the number of units of each resource type allocated to each process, and the column **request **denotes the number of units of each resource type requested by a process in order to complete execution. Which of these processes will finish **LAST**?

$$\begin{array}{|l|lll|ll|}\hline &\text{} \rlap{\textbf{alloc}} &&&\rlap{ \textbf{request}} \\\hline &\text{X} & \text{Y} & \text{Z} &\text{X} & \text{Y} & \text{Z} \\\hline \textbf{P0} & \text{1} & \text{2} & \text{1}& \text{1} & \text{0} & \text{3} \\\hline \textbf{P1} & \text{2} & \text{0} & \text{1} & \text{0} & \text{1} & \text{2} \\\hline \textbf{P2} & \text{2} & \text{2} & \text{1} & \text{1} & \text{2} & \text{0} \\\hline \end{array}$$

- $P0$
- $P1$
- $P2$
- None of the above, since the system is in a deadlock

+25 votes

Best answer

The answer is (**C**).

$$\overset{\text{Available Resources}}{\begin{array}{|l|l|l||}\hline

\text{X} & \text{Y} & \text{Z} \\\hline \text{0} & \text{1} & \text{2}

\\\hline\end{array}}$$ Now, $P1$ will execute first, As it meets the needs. After completion, The available resources are updated.

$$\qquad \overset{\text{Updated Available Resources}}{\begin{array}{|l|l|l||}\hline

\text{X} & \text{Y} & \text{Z} \\\hline \text{2} & \text{1} & \text{3}

\\\hline\end{array}}$$

Now $P0$ will complete the execution, as it meets the needs.

After completion of $P0$ the table is updated and then $P2$ completes the execution.

Thus $P2$ completes the execution in the last.

0

please explain me how you get "Available Resources" , even if it is not mention in the question or may be i am not able to fetch that particular point so please help me [email protected]_keeda

+2

Calculate the total allocated resources. 5 instances of X are allocated 4 of Y and 3 of Z.

So the available or left resources are x=5-5=0 :::: y=5-4=1::::z=5-3=2.

Hope it helps.

So the available or left resources are x=5-5=0 :::: y=5-4=1::::z=5-3=2.

Hope it helps.

+1

@ Shubham Aggarwal for this particular question what is other sequence other than P1 -> P0 -> P2 ?

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

50,737 questions

57,397 answers

198,610 comments

105,452 users