GATE2010 q46 Revision as of 13:13, 11 December 2013 by Arjun Suresh (talk | contribs) (→‎Solution) (diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

A system has <math>n</math> resources <math>R_0 ,..., R_n-1</math> , and <math>k</math> processes <math>P_0 ,.....P_{k-1}</math> . The implementation of the resource request logic of each process <math>P_i</math> . is as follows:

if (<math>i% 2==0</math>) {
  if (<math>i<n</math>) request <math>R_i</math> ;
  if (<math>i+2<n</math>)request <math>R_{i+2}</math> ;
}
else {
  if (<math>i<n</math>) request <math>R_{n-i}</math> ;
  if (<math>i+2<n</math>) request <math>R_{n-i-2}</math> ;
}

In which one of the following situations is a deadlock possible?

(A) n = 40,k = 26

(B) n = 21,k = 12

(C) n = 20,k = 10

(D) n = 41,k = 19

Solution

From the resource allocation logic, it's clear that even numbered processes are taking even numbered resources and all even numbered processes take 2 resources. Now, if we make sure that all odd numbered processes take odd numbered resources, then deadlock cannot occur. The "else" case of the resource allocation logic, is trying to do that. But, if n is odd, <math>R_{n-i}</math> and <math>R_{n-i-2}</math> will be even and there is possibility of deadlock. So, only <math>B</math> and <math>D</math> are the possible answers.

From the resource allocation logic, it's clear that maximum two processes can share a resource and hance the dependency cycle can have maximum two edges.

Now, in D, we can see that P_0 requests R_0 and R_2, P_2 requests R_2 and R_4 and so on until, P_18 requests R_18 and R_20. At the same time P_1 requests R_40 and R_38, so on until P_19 requests R_22 and R_20. i.e.; there are no two processes requesting the same two resources and hence there can't be a cycle (of length two) of dependencies and hence no deadlock is possible.

But for B, P_8 requests R_8 and R_10 and P_11 also requests R_10 and R_8. Hence, a deadlock is possible.

Tweet