6,445 views

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

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

I agree with @VS comment.Questions says it has requested the resource.It does mean it is allocated.If request means allocated,then why do we need deadlock avoidance at all.Request will be satisfied if banker's algo allows.In this case it will [email protected] sir.Please verify above comment once
@rahul and VS-No Banker's algorithm doesn't work like that.It pretends to allocate the process the resource it demands and then checks to see whether after allocation that resource to a process, a safe sequence exists or not. If it exists, then in actual the request for resources of this process is granted, otherwise, it is rejected.

@Ayush Upadhyaya, Banker’s doesn’t ‘pretend’. Pretending to allocate resources is done by ‘Resource Request’ algorithm. I agree with @VS

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

The before/after part is not clear for me. It is not visible in the table. But in b) system will be in deadlock was a mistake. System can go to "deadlock" is right.

@Arjun sir

No, answer would not be same.

I don't know whether I am right or not.But, if I go by the language of the question

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

Now, assuming we are talking about additional 1 unit of request by Po.

ALLOCATION

 R0 R1 R2 P0 1 0 2 P1 0 3 1 P2 1 0 2
 R0 R1 R2 P0 4 1 2 P1 1 5 1 P2 1 2 3
 R0 R1 R2 P0 3 1+1 0 P1 1 2 0 P2 0 2 1

Now, I believe future need should be updated,as the process is requesting additional 1 unit of R1.

It is no where written in question that resource R1 is allocated to Po or not.

But, here and here gateoverflow.in/1800/gate2014-1_31

We have already allocated the resource.

Now, if I go by my understanding then we have a safe state here for part(b)

Safe Sequence : P1-->P2-->P0

i) system will be in safe state and safe sequence is PP2P0