The Gateway to Computer Science Excellence

+86 votes

A system has $n$ resources $R_0, \dots,R_{n-1}$, and $k$ processes $P_0, \dots, P_{k-1}$. The implementation of the resource request logic of each process $P_i$ is as follows:

$\text{if} (i\%2==0) \{\\

\quad\text{if} (i<n) \text{ request } R_i;\\

\quad\text{if} (i+2 < n) \text{ request } R_{i+2}; \} \\

\text{else} \{\\

\quad\text{if} (i<n) \text{ request } R_{n-i};\\

\quad\text{if} (i+2 <n) \text{ request } R_{n-i-2}; \}$

In which of the following situations is a deadlock possible?

- $n=40,\: k=26$
- $n=21,\:k=12$
- $n=20,\:k=10$
- $n=41,\:k=19$

+40

Deadlock iff Even and odd process request overlaps at some point. It will happen only if n is odd.

So we have only two options left (B) and (D). If you observe for even no. process resource allocation is happening from forward direction but for odd no. resource it is happening from back word direction. But in option (D) we have more then $2*k$ resources so overlap is not possible. Hence overlap will happen only in (B).

So we have only two options left (B) and (D). If you observe for even no. process resource allocation is happening from forward direction but for odd no. resource it is happening from back word direction. But in option (D) we have more then $2*k$ resources so overlap is not possible. Hence overlap will happen only in (B).

0

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.

It is a mathematical way only. You can check it manually too without using the above formula.Like i said for deadlock to happen the the even and odd processes request should overlap .You can run the loops for both the options B and D as for A and C they can be ignored since, 'n' is even.

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.

It is a mathematical way only. You can check it manually too without using the above formula.Like i said for deadlock to happen the the even and odd processes request should overlap .You can run the loops for both the options B and D as for A and C they can be ignored since, 'n' is even.

+234 votes

Best answer

From the resource allocation logic, it's clear that even numbered processes are taking even numbered resources and all even numbered processes share no more than 1 resource. Now, if we make sure that all odd numbered processes take odd numbered resources without a cycle, then deadlock cannot occur. The "else" case of the resource allocation logic, is trying to do that. But, if n is odd, $R_{n-i}$ and $R_{n-i-2}$ will be even and there is possibility of deadlock, when two processes requests the same $R_i$ and $R_j$. So, only $B$ and $D$ 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$, so on until, $P_{18}$ requests $R_{18}$ and $R_{20}$. At the same time $P_1$ requests $R_{40}$ and $R_{38}$, $P_3$ requests $R_{38}$ and $R_{36}$, so on until, $P_{17}$ requests $R_{24}$ and $R_{22}$. i.e.; there are no two processes requesting the same two resources and hence there can't be a cycle of dependencies which means, 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. (Suppose $P_8$ comes first and occupies $R_8$. Then $P_{11}$ comes and occupies $R_{10}$. Now, if $P_8$ requests $R_{10}$ and $P_{11}$ requests $R_8$, there will be deadlock)

Correct Answer: $B$

Now, in $D$, we can see that $P_0$ requests $R_0$ and $R_2$, $P_2$ requests $R_2$ and $R_4$, so on until, $P_{18}$ requests $R_{18}$ and $R_{20}$. At the same time $P_1$ requests $R_{40}$ and $R_{38}$, $P_3$ requests $R_{38}$ and $R_{36}$, so on until, $P_{17}$ requests $R_{24}$ and $R_{22}$. i.e.; there are no two processes requesting the same two resources and hence there can't be a cycle of dependencies which means, 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. (Suppose $P_8$ comes first and occupies $R_8$. Then $P_{11}$ comes and occupies $R_{10}$. Now, if $P_8$ requests $R_{10}$ and $P_{11}$ requests $R_8$, there will be deadlock)

Correct Answer: $B$

+7

+13 votes

+1 vote

**(k-3)** processes will take 2 resources and other 3 processes will take 1 resource each.

Total **n** resources. Deadlock will arise when : **(((k-3) * 2) + (3*1)) = n**

If k=12, n will be 21.

+1 vote

Even numbered process Pi request even numbered resources Ri and Ri+2. Thus they share no more than 1 resource.

Odd numbered process Pi request

Odd numbered resources Rn−i and Rn−i−2 if nn is even

Even numbered resources Rn−i and Rn−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.

Now easy way to solve this is by finding the resources of even and odd numbered processes by using the given answer.

Taking option B:

Even numbered processes resource allocation-

P0 R0 , R2

P2 R2, R4

P4 R4, R6

P6 R6, R8

P8 R8, R10

P10 R10 , R12

Odd numbered processes resource allocation-

P1 R20, R18

P3 R18, R16

P5 R16, R14

P7 R14, R12

P9 R12, R10

P11 R10, R8

Odd numbered process Pi request

Odd numbered resources Rn−i and Rn−i−2 if nn is even

Even numbered resources Rn−i and Rn−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.

Now easy way to solve this is by finding the resources of even and odd numbered processes by using the given answer.

Taking option B:

Even numbered processes resource allocation-

P0 R0 , R2

P2 R2, R4

P4 R4, R6

P6 R6, R8

P8 R8, R10

P10 R10 , R12

Odd numbered processes resource allocation-

P1 R20, R18

P3 R18, R16

P5 R16, R14

P7 R14, R12

P9 R12, R10

P11 R10, R8

IF YOU SEE BOTH YOU WILL FIND P10 AND P9 REQUESTING SAME RESOURCES WHICH MAY LEAD TO DEADLOCK.****

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.4k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,737 questions

57,370 answers

198,506 comments

105,272 users