edited by
12,405 views
61 votes
61 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. $1$
  2. $2$
  3. $3$
  4. $4$
edited by

8 Answers

Best answer
107 votes
107 votes

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

edited by
35 votes
35 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


 

edited by
10 votes
10 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)
reshown by
6 votes
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;

edited by
Answer:

Related questions

75 votes
75 votes
11 answers
1