0
$\begingroup$

I came across following problem:

A system has n resources R0,…,Rn-1,and k processes P0,….Pk-1.The implementation of the resource request logic of each process Pi is as follows:

if (i % 2 == 0) {
      if (i < n) request Ri
      if (i+2 < n) request Ri+2
}
else {
      if (i < n) request Rn-i
      if (i+2 < n) request Rn-i-2
}

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

The given solution takes following form:

  • Even numbered process $P_i$ request even numbered resources $R_i$ and $R_{i+2}$. Thus they share no more than 1 resource.
  • Odd numbered process $P_i$ request
    • Odd numbered resources $R_{n-i}$ and $R_{n-i-2}$ if $n$ is even
    • Even numbered resources $R_{n-i}$ and $R_{n-i-2}$ if n is odd.
  • In this example, for deadlock to occur, two processes must request same set of processes. For this, we need n to be odd so that some odd numbered process will request same set of even numbered resources as some even numbered process.
  • Thus option A and C are not possible as they have even n.
  • For option D, n = 41, k = 19. Resources requested will be: enter image description here
    Thus no two processes request same set of resources.
  • For option B, n = 21, k = 12. Resources requested will be: enter image description here
    • P7 and P10 request same set of resources R12 and R14.
    • P9 and P8 request same set of resources R10 and R12.
    • P11 and P6 request same set of resources R8 and R10.
      These pairs can cause deadlock if one of them come first and request one of the resources and then other comes and requests other resource and lastly both request the respective remaining resource.

I was guessing whether I can solve this mathematically to speed up. I thought following

  • When i is even, Pi requests $R_i$ and $R_{i+2}$
  • When i is odd, Pi requests $R_{n-i}$ and $R_{n-i-2}$
  • Then I though I need to equate as follows:
    • $i = n-i-2 \rightarrow 2i=n-2$
    • $i+2 = n-i \rightarrow 2i=n-2$
  • Then try out for option A as:
    • $40-2 = 38 \rightarrow i=19$
  • But later I realize, this was simply stupidity and remained directionless.

I still dont know whether I can solve this problem quickly mathematically without forming those tables. Is it possible?

(Sorry for more mathematical problem than the one involving Operating Systems or Computer Science concepts.)

$\endgroup$

Your Answer

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

Browse other questions tagged or ask your own question.