edited by
8,901 views
22 votes
22 votes

A computer system uses the Banker’s Algorithm to deal with deadlocks. Its current state is shown in the table below, where $P0$, $P1$, $P2$ are processes, and $R0$, $R1$, $R2$ are resources types.
$$\begin{array}{ll} &\rlap{\small{ \textbf{Maximum Need}} }&&&&& \rlap{\small{\textbf{Current Allocation}}} &&&&& \rlap{\small{\textbf{Available}}}  \\
  & \textbf{R0} & \textbf{R1} & \textbf{R2} &&& \textbf{R0} & \textbf{R1} & \textbf{R2} &&& \textbf{R0} & \textbf{R1} & \textbf{R2} \\ \textbf{P0} & \text{4} & \text{1} & \text{2} &&\textbf{P0} & \text{1} & \text{0} & \text{2} &&& \text{2} & \text{2} & \text{0} \\  \textbf{P1} & \text{1} & \text{5} & \text{1} && \textbf{P1} & \text{0} & \text{3} & \text{1} \\ \textbf{P2} & \text{1} & \text{2} & \text{3} &&\textbf{P2} & \text{1} & \text{0} & \text{2} \\\end{array}$$

  1. Show that the system can be in this state

  2. What will the system do on a request by process $P0$ for one unit of resource type $R1$?

edited by

3 Answers

Best answer
26 votes
26 votes

$$\overset{\text{Allocation}}{\begin{array}{|l|l|l|l|}\hline \text{} & \text{R0} & \text{R1} & \text{R2} \\ \hline \text{P0} & \text{1} & \text{0} & \text{2} \\\hline  \text{P1} & \text{0} & \text{3} & \text{1} \\\hline  \text{P2} & \text{1} & \text{0} & \text{2} \\\hline   \end{array}}\qquad \overset{\text{MAX NEED}}{\begin{array}{|l|l|l|l|}\hline \text{} & \text{R0} & \text{R1} & \text{R2} \\ \hline \text{P0} & \text{4} & \text{1} & \text{2} \\\hline  \text{P1} & \text{1} & \text{5} & \text{1} \\\hline  \text{P2} & \text{1} & \text{2} & \text{3} \\\hline   \end{array}}\qquad \overset{\text{Future Need}}{\begin{array}{|l|l|l|l|}\hline \text{} & \text{R0} & \text{R1} & \text{R2} \\ \hline \text{P0} & \text{3} & \text{1} & \text{0} \\\hline  \text{P1} & \text{1} & \text{2} & \text{0} \\\hline  \text{P2} & \text{0} & \text{2} & \text{1} \\\hline   \end{array}}$$

Available $=(2\quad 2 \quad0)$

$P1(1\quad 2\quad 0)$'s needs can be met. P1 executes and completes releases its allocated resources.

$A=(2\quad 2\quad 0)+(0\quad 3\quad 1)=(2 \quad5\quad 1)$

Further  $P2 (0\quad 2\quad 1)$ s needs can be met.

$A=(2\quad 5\quad 1)+(1\quad 0\quad 2)=(3\quad 5\quad 3)$

next $P0$ s needs can be met.

Thus safe sequence exists $P1 P2 P0.$


Next Request $P0(0 1 0)$

$$\overset{\text{Allocation}}{\begin{array}{|l|l|l|l|}\hline \text{} & \text{R0} & \text{R1} & \text{R2} \\ \hline \text{P0} & \text{1} & \text{0+1=1} & \text{2} \\\hline  \text{P1} & \text{0} & \text{3} & \text{1} \\\hline  \text{P2} & \text{1} & \text{0} & \text{2} \\\hline   \end{array}} \qquad \overset{\text{MAX NEED}}{\begin{array}{|l|l|l|l|}\hline \text{} & \text{R0} & \text{R1} & \text{R2} \\ \hline \text{P0} & \text{4} & \text{1} & \text{2} \\\hline  \text{P1} & \text{1} & \text{5} & \text{1} \\\hline  \text{P2} & \text{1} & \text{2} & \text{3} \\\hline   \end{array}}\qquad \overset{\text{Future Need}}{\begin{array}{|l|l|l|l|}\hline \text{} & \text{R0} & \text{R1} & \text{R2} \\ \hline \text{P0} & \text{3} & \text{0} & \text{0} \\\hline  \text{P1} & \text{1} & \text{2} & \text{0} \\\hline  \text{P2} & \text{0} & \text{2} & \text{1} \\\hline   \end{array}}$$

Available $=(2\quad 2-1=1\quad 0)$

Here, also not a single request need by any process can be made.

  1. System is in safe state.
  2. Since request of $P0$ can not be met,system would delay the request and wait till resources are available.
edited by
9 votes
9 votes
The system is in safe state and hence allowed by Banker's algorithm. P1 can now finish with the available resource and then P2's request can be satisfied and then P0's.

If P0 request one unit of R1, we cannot give it. That would make only 1 more R1 available and hence P1 cannot finish its execution with the remaining available R1. Also, P2 doesn't have enough R2 left and P0 doesn't have enough R0 left to complete their execution. So, system can go to dead state.

Related questions

38 votes
38 votes
2 answers
1
Kathleen asked Oct 9, 2014
9,811 views
A file system with a one-level directory structure is implemented on a disk with disk block size of $4K$ bytes. The disk is used as follows:$$\begin{array}{|l|}\hline \te...