Dark Mode

Prateek Dwivedi
asked
in Operating System
Jun 27, 2015

26,557 views
5 votes

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.

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.

8 votes

Best answer

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.

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.

0

6 votes

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.

1 vote

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.

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.