The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+72 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?

  1. $n=40,\: k=26$
  2. $n=21,\:k=12$
  3. $n=20,\:k=10$
  4. $n=41,\:k=19$
asked in Operating System by Veteran (96.2k points)
edited by | 7.6k views
Please remove the GATE2018 tag from the question
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).

4 Answers

+178 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$
answered by Veteran (408k points)
edited by

just a small correction Sir there will be no P19 in case (D) as k=19 so P will be from 0 to 18

Thanks for the correction :)
Thanks..fantastic answer
very clear explanation arjun sir
at option, to reach to P8 and P11...just trial and error of any other method?
check answer given by ishaan sood
Thqqq soo much ..crystal clear explanation...
great explanation
Can you plz explain dat more elaborately???
Thanks sir ji
How can we tackle such questions in exam.. Seriously!! :(
+10 votes
Option B is answer

No. of resources, n = 21
No. of processes, k = 12

Processes {P0, P1....P11}  make the following Resource requests:
{R0, R20, R2, R18, R4, R16, R6, R14, R8, R12, R10, R10}

For example P0 will request R0 (0%2 is = 0 and 0< n=21). 

Similarly, P10 will request R10.

P11 will request R10 as n - i = 21 - 11 = 10.

As different processes are requesting the same resource, deadlock
may occur. 
answered by Junior (835 points)
+9 votes

The answer

answered by (397 points)
+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.


answered by (21 points)


Please explain your method in detail.



Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
49,576 questions
54,181 answers
71,142 users