How can I solve this deadlock related problem mathematically?

Question

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:
  Thus no two processes request same set of resources.
• For option B, n = 21, k = 12. Resources requested will be:
  • 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.)

Answer 1

As per the question, all the even processes request only even resources(i.e. Ri & Ri+2) Where as odd processes request: either, odd resources(i.e. Rn-1 & Rn-1-2) when 'n' is even. or, even resources (i.e. Rn-1 & Rn-1-2) when 'n' is odd.

Deadlock can only happen when even and odd processes request overlaps i.e. odd processes have to request even resources which means 'n' must should be odd.

Mathematically,

Let Pn-i be an odd process then,

n-i<=k

or,ceil(n-i)=k here ceil() is ceiling function since the value at max can be equal to k.

i=ceil(n-k)---eqn(i)

For deadlock to happen,

i=n-i-2

substituting value of i from eqn(i), we have,

ceil(n-k)=n-i-2

solving further we get,

k=ceil((n+2)/2) where 'n' is odd

since, 'n' must should be odd option A and C can be ignored now coming to option B substituting n=21 we get k=12 In option D substituting n=41 we get k=22.

so option B is correct.For option D to be in deadlock k should be equal to 22.