• edited by
44,824 views
224 224 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$

10 Answers

Best answer
434 434 votes
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$
• edited by
22 22 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. 
21 21 votes

The answer

8 8 votes
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

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

• edited by
7 7 votes

Answer is option B

 

• edited by
2 2 votes

(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.

 

Answer:
Position:
Show:

Related questions

94 94 votes
7 answers 7 answers
47.4k
47.4k views
go_editor asked Sep 30, 2014
47,429 views
The following program consists of $3$ concurrent processes and $3$ binary semaphores. The semaphores are initialized as $S0=1, S1=0$ and $S2=0.$$$\begin{array}{|l|l|}\hli...
37 37 votes
3 answers 3 answers
18.8k
18.8k views
go_editor asked Sep 29, 2014
18,822 views
A system uses FIFO policy for system replacement. It has $4$ page frames with no pages loaded to begin with. The system first accesses $100$ distinct pages in some order ...
79 79 votes
10 answers 10 answers
31.6k
31.6k views
go_editor asked Sep 29, 2014
31,642 views
Consider the methods used by processes $P1$ and $P2$ for accessing their critical sections whenever needed, as given below. The initial values of shared boolean variables...
97 97 votes
10 answers 10 answers
41.5k
41.5k views
go_editor asked Apr 21, 2016
41,488 views
A computer system has an $L1$ cache, an $L2$ cache, and a main memory unit connected as shown below. The block size in $L1$ cache is $4$ words. The block size in $L2$ cac...