The Gateway to Computer Science Excellence
+38 votes
3.8k views

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. $1$
  2. $2$
  3. $3$
  4. $4$
in Operating System by Boss (16.3k points)
edited by | 3.8k views
+1
here alternate order of acces is required, which can can be imposed by using just two binary semaphores
+1
The answer is 2 because one semaphore will ensure that only one process access any resource at a time and the other ensures priority as per given condition.

Is this way of thinking or approach correct?
0
co begin co end precedence graph approach ,,can be implement
0
0
Use of resources is serial execution.

6 Answers

+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}$$

by Loyal (7.8k points)
edited by
0
Yes, this is the right answer.
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.
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 :)
+1
@sachin : You should read question first .
+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
+1

@abhijit

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.

 

+1
you cannot change the sequence r1-r2-r3-r4
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
YES
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!
0
How to think??

only intution or any logical concept
0

@MRINMOY_HALDER try taking case and do it

+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? 

0
Read the question order for using the 4 process is given in the question.

Coming to the statement "there are no other scheduling constraints between the process" means that other than the given order of request completion of resources, there is no other scheduling like
0
$P_{2}.R_{1} \rightarrow (P_{1}.R_{1} \rightarrow P_{1}.R_{2}) \rightarrow (P_{2}.R_{2} \rightarrow P_{2}.R_{3}) \rightarrow (P_{1}.R_{3} \rightarrow P_{1}.R_{4}) \rightarrow P_{2}.R_{4}$

 

+24 votes

Two semaphore requires x=0 , y =0   where V( ) = signal() and P() = wait() 
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


 

by Boss (16.5k points)
edited by
0
can anybody explain what does the question is trying to say with the statement

"p2 must complete the use of r1 before p1 gets access of r1"

does it mean that once process p1 gets the access of r1 process p2 won't be able to get it back.....

not able to understand this statement
0
can we think like , this question is of binary semaphore  it can take be maximum 2 semaphores (0,1 combo.)

and then get the ans? after putting the 4 different values
+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;

by (425 points)
edited by
0
Ok but ASAP
0
here you have missed two points

1st you should have mentioned binary semaphore intilazed with ,M=1 ,X=0

2nd after resoure R3 (in P2) it should be V(X) P(M) then R4

3rd after R4 (in P1) it should be V(M) P(X)

draw step by step then check thats correct way
+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)
by Boss (29.1k points)
reshown by
0 votes

S=0,Q=0

P1                                                                        P2

V(S) P(S)
P(Q) R1
R1 V(Q)
R2 P(S)
V(S) R2
P(Q) R3
R3 V(Q)
R4 P(S)
V(S) R4
   

ANSWER IS 2

by Junior (787 points)
–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);

by Active (1.5k points)
+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 .

+1
For that to happen there must be a condition that after each instruction by P2, P1 will try for the lock release and vice-verse. But that condition is not satisfied.
+1
P2 use R1 and then give Signal and then preempt
P1 will use  R1,R2 and perform Signal which will make S=1 and then it continues to execute and performs Wait on S (making S=0) Use R3, Use R4 ... So the sequence is broken ..therefore we need atleast two semaphores!
Answer:

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
50,737 questions
57,374 answers
198,512 comments
105,287 users