'm' processes share 'n' resources of same type. The maximum need of each process does not exceed 'n' and the sum all their maximum needs is always less than m+n. In this setup deadlock can occur or not?

Question

This is a question from Operating System concepts by Silberschatz, Gagne and Galvin. On very first go I could make that in such a situation deadlock can never occur. But doing guess work is a really bad habit and risky to.

So I did some paper work using Banker's Algorithm and somehow concluded that deadlock can never occur.But I need some systematic approach on such question and proper explanation of the answer.

I'm curious to know how you guys would have solved this question.

Thanks in advance.

Answer 1

Consider the worst case- all processes acquire maximum resources but still not able to finish. So, the resources available must be 1 less than than the maximum need, for each of the processes (this ensures none of them can finish).

We are given maximum need is always less than m + n. As per our condition for deadlock, resources available must be 1 less than maximum need for each of 'm' processes => totally the resources available must be less than m + n - m = n.

But 'n' is the available number of resources and hence no deadlock can occur.

Comments

ok...Thanks

---

@Arjun sir  one point is missing in the question that each process need atleast one resource otherwise if

 M=3 and N=4 

P1=4, P2=2,P3=0

then deadlock is possible

---

Can we say if the maximum need of a process is zero, then it is not "sharing" the resources?

Answer 2

Let us assume that this question comes in the exam then I suppose we could try putting a couple of random values into 'm' and 'n' and then make an educated guess here.

Case 1: m = 3, n =5

Now since sum of max needs is less than 'm+n' therefore,

Sum of max needs < 8

There are 3 processes so lets distribute the resources randomly:

5 + 1 + 1 < 8

Now allocating (max-1) resource to each of the above processes we get,

5[4] + 1[0] + 1[0] < 8  ........................Still left with the 5th resource which could be allotted to any of the 3 processes and won't let the deadlock happen.

Case 2: m = 7, n = 8

Sum of max needs < 15

After distribution we get:

5 + 2 + 1 + 2 + 1 + 1 +2 < 15

Allocating (max - 1) resource to each of the above process,

5[4] + 2[1] + 1[0] + 2[1] + 1[0] + 1[0] + 2[1] < 15 ............................Still left with the 8th resource which would never let a deadlock happen.

.

.

.

P.S. : Try yourself for a case where n < m.

Answer 3

Here is a numerical solution for given question.

so let m=4 n=10 max need<(m+n)=13

now let us take two extreme cases:

case 1 case where processes share almost equal resources like 3,3,3,4(total 13)

p1   p2   p3   p4

1      1      1      1(4 resources granted)

1      1      1      1(8 resources granted)

1      1      1      1(12 resources granted)

now both p1,p2 and p3 have satisfied their needs so they can complete and release their own resources.

hence no deadlock.

case 2 now if requests are like 1,1,5,6(total 13)

p1     p2    p3   p4

1       1       1       1

p1 and p2 completes and releases their resources and so now available resources are 13

p3    p4

1       1(2 resources granted)

1       1(4 resources granted)

1       1 (6 resources granted)

1       1(8 resources granted)

1       1(10 resources granted)

p3 completes execution and hence releases resources and so p4 can be completed so no deadlock.

Comments

This is too much brute force

given this question in exam

how will yu solve it under 2 minutes?

there must be a logical pathway for better and intuitive answer

i am not saying your approach is incorrect

but i am curious enough to know the best possible way to approach this problem!

Answer 4

ur approach is correct.using banker's algo you'll see that one process will acquire all needed resources and after completion of work it will release resources hence no deadlock will occur.