View source for GATE2010 q46 ← GATE2010 q46

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[edit]

From the resource allocation logic, it's clear that even numbered processes are taking even numbered resources and all even numbered resources are taken by 2 processes. Now, if we make sure that all odd numbered processes take odd numbered resources, then dead lock 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.

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.