3
$\begingroup$

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.

Table

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?

Thanks a lot in advance!

$\endgroup$
1
$\begingroup$

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

$\endgroup$
-1
$\begingroup$

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]$.

$\endgroup$
  • 1
    $\begingroup$ I don't understand your reasoning. Where do you get the value $[x=2,y=2]$ from? $\endgroup$ – Gilles Sep 27 '13 at 17:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.