So we have the following table of processes , where A, B and $\Gamma$ are the resources.

Here is a pic that i drew with the processes and the resources. So the exact question is this: Using banker's algorithm, calculate the minimum values of $x$ and $y$ in order the system is Deadlock free.

I have done pretty much huge paper work and found that $x,y$ should be the numbers 2 and 3. But in order to find this I run the algorithm on paper several times ; for $[x,y] = [0,0],[0,1],[1,0],[1,1],[1,2]$ etc. until I found that for pair $[x=2, y=3]$ the system is deadlock free!

So, I think that I am missing the point. All this took me like 1 hour or so. Is there a simple method with less paperwork?

A "shortcut" to the solution; first calculate the NEEDED = MAX - ALLOCATEDresources:

    ALLOCATED MAX      NEEDED
A B C     A B C    A B C
P1  0 1 0     7 5 3    7 4 3
P2  2 0 0     3 2 2    1 2 2
P3  3 0 2     9 0 2    6 0 0
P4  2 1 1     2 2 2    0 1 1
P5  0 0 2     4 3 3    4 3 1

AVAILABLE: x y 2


In order to complete P1 we need 4 Bs. But if you observe the column B of ALLOCATED, we see that we can only gain a single B if P4 is executed before P1. So whatever the execution order is, we need more than 3 new Bs (y >= 3).

Furthermore in order to complete P3 we need 6 As, but if you look at column A of ALLOCATED, we see that we can only gain 4 Bs if P2 and P4 are executed before P3. So whatever the execution order is, we need more than 2 new As (x >= 2).

So we have:

AVAILABLE: 2+x' 3+y' 2


and we can start completing processes that need less than (2 3 2) (P4 and P2)

P4: (2 3 2) - (0 1 1) + (2 2 2) = (4 4 3)
P2: (4 4 3) - (1 2 2) + (3 2 2) = (6 4 3)
now also P3 can be completed:
P3: (6 4 3) - (6 0 0) + (9 0 2) = (9 4 5) which are enough resources for
both P1 and P5


So the state is safe even with x'=0 and y'=0 and the solution is x=2, y=3

For $[x,y] = [2,2]$, we get the result. Therefore the minimum is $[x,y] = [2,2]$. We get the correct sequence as $P_3 P_4 P_1 P_2 P_0$ is the safe sequence with $[x,y] = [2,2]$.

• I don't understand your reasoning. Where do you get the value $[x=2,y=2]$ from? – Gilles 'SO- stop being evil' Sep 27 '13 at 17:17