The Gateway to Computer Science Excellence

+38 votes

Two concurrent processes $P1$ and $P2$ use four shared resources $R1, R2, R3$ and $R4$, as shown below.

$$\begin{array}{|l|l|}\hline \textbf{P1} & \textbf{P2} \\ \text{Compute: } & \text{Compute;} \\ \text{Use $R1;$ } & \text{Use $R1;$} \\ \text{Use $R2;$ } & \text{Use $R2;$}\\ \text{Use $R3;$ } & \text{Use $R3;$} \\ \text{Use $R4;$ } & \text{Use $R4;$} \\\hline \end{array}$$

Both processes are started at the same time, and each resource can be accessed by only one process at a time The following scheduling constraints exist between the access of resources by the processes:

- $P2$ must complete use of $R1$ before $P1$ gets access to $R1$.
- $P1$ must complete use of $R2$ before $P2$ gets access to $R2$.
- $P2$ must complete use of $R3$ before $P1$ gets access to $R3$.
- $P1$ must complete use of $R4$ before $P2$ gets access to $R4$.

There are no other scheduling constraints between the processes. If only binary semaphores are used to enforce the above scheduling constraints, what is the minimum number of binary semaphores needed?

- $1$
- $2$
- $3$
- $4$

+1

here alternate order of acces is required, which can can be imposed by using just two binary semaphores

+67 votes

Best answer

Answer is (**B**)

It needs two semaphores. $X=0 ,Y=0$$$\small \begin{array}{|l|}\hline \text{P1} & \text{P2} \\\hline \text{P(X)}& \text{} \\ \text{} & \text{R1} \\ \text{} & \text{V(X)} \\ \text{R1} & \text{P(Y)} \\ \text{R2} & \text{} \\ \text{V(Y)} & \text{} \\ \text{P(X)} & \text{R2}\text{} \\ \text{} & \text{R3} \\ \text{} & \text{V(X)} \\ \text{R3} & \text{P(Y)} \\ \text{R4} & \text{} \\ \text{V(Y)} & \\&\text{R4} \\ \hline \end{array}$$

0

Please help me understand that, is there any schedule that P1 must access first R1 then R2 then R3 and at last R4 and same with P2, or the resources can be accessed in any order?

my understanding is that they can be accessed in any order.

Moreover, as per the solution does it mean that R1 of P2, R2 of P1, R3 of P2 and R4 of P1 does not have any restriction and can be accessed without checking any semaphore values?

If above two statements are true, then suppose currently P1 is executing R2, then P1 will execute V(Y) and Y becomes 1.

Now P2 can choose to execute R2 or R4. Lets say P2 chose R4 and executed it, but its not at all necessary that P1 has executed R4 yet, but it is a required condition. Then how does it work?

Please clarify my doubt and help me understand this problem.

my understanding is that they can be accessed in any order.

Moreover, as per the solution does it mean that R1 of P2, R2 of P1, R3 of P2 and R4 of P1 does not have any restriction and can be accessed without checking any semaphore values?

If above two statements are true, then suppose currently P1 is executing R2, then P1 will execute V(Y) and Y becomes 1.

Now P2 can choose to execute R2 or R4. Lets say P2 chose R4 and executed it, but its not at all necessary that P1 has executed R4 yet, but it is a required condition. Then how does it work?

Please clarify my doubt and help me understand this problem.

0

Solution provided by you is correct, it took a while to understand me. Because i did not notice x and y set to Zero initially.

Thnx :)

Thnx :)

+3

Can we do in this way. x=0 and y=0

P1 P2

_______________________

R2 R1

R4 R3

V(x) V(y)

P(y) P(x)

R1 R2

R3 R4

P1 P2

_______________________

R2 R1

R4 R3

V(x) V(y)

P(y) P(x)

R1 R2

R3 R4

+1

Doesn't your solution indicate that P1 cannot access R1 even after P2 has done using R1? P1 has to wait until P2 finishes using both R1 and R3. Also the order of execution for both the processes should be R1,R2,R3 and R4 as concluded from the Answer.

0

is it correct that answer will always be 2 bianry semaphores irrespective of number of resource and one process uses one before another alternatively (same as what happens in this questions.

0

Ya initially i also do the same way but order of execution is matter here.becoz there might be chance that a resource is completely depends on previous one.

+1

Which part of the question implies that the order of consuming resources R1, R2, R3, R4 must be the same? i.e. why cannot one do R2,R3, R1,R4 etc? Please help!

+1

P1 | P2 |
---|---|

R1 | |

R1 | |

R3 | |

R3 | |

R2 | |

R2 | |

R4 | |

R4 |

Can someone explain how the solution for the above situation works? Why is everyone making an assumption that R1, R2, R3, R4 come in this order?

There are no other scheduling constraints between the processes.

They have even mentioned that there are no constraints other than these. So isn't the answer going to be 4?

+24 votes

P1 P2

Use R1

V(x)

P(x)

Use(R1)

Use(R2)

V(y)

P(y)

Use(R2)

Use(R3)

V(x)

P(x)

Use(R3)

Use(R4)

V(y)

P(y)

Use(R4)

**Option B**

+6 votes

option B)

P1 P2

P(X); | P(M);

R1; | R1;

R2; | V(X);

V(M); | P(M);

P(X); | R2;

R3; | R3;

R4; | V(X);

V(M); | R4;

+6 votes

2 Semaphores are enough to satisfy the above requirement

**Consider two binary semaphores S and T initially 0 and 1.**

Below is the order in which we can synchronize processes P1 and P2 according to the given criteria.

P1 |
P2 |

P(S) | P(T) |

R1 | R1 |

V(S) | V(S) |

P(S) | P(T) |

R2 | R2 |

V(T) | V(T) |

P(S) | P(T) |

R3 | R3 |

V(S) | V(S) |

P(S) | P(T) |

R4 | R4 |

V(T) | V(T) |

0 votes

–3 votes

I think it can be done by 1 semaphore . Let semaphore s=0 initially.

P1 P2

Wait(S);

Use(R1) ; Use(R1) ;

Signal(S);

Wait(S);

Use(R2); Use(R2);

Signal(S);

Wait(S);

Use(R3); Use(R3);

Signal(S);

Wait(S);

Use(R4); Use(R4);

Signal(R4) Signal(R4);

+6

One problem is there:

P2:

Signal(S);

Wait(S);

P1:

Wait(S);

When P2 does signal, we can't be sure whether the waiting P1's wait succeed or the wait of the P2 succeed.

0

Whoever starts the execution doesn't matter because S is initially 0 . So P1 at line 1 will be spin locked. then when at line 3 after Signal(S) by P2 , P1 gets the access imidiately .

- 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,397 answers

198,610 comments

105,454 users