edited by
14,665 views
55 votes
55 votes

Suppose we want to synchronize two concurrent processes $P$ and $Q$ using binary semaphores $S$ and $T$. The code for the processes $P$ and $Q$ is shown below.

$$\begin{array}{|l|l|}\hline \text{Process P:}  &  \text{Process Q: } \\\hline  \text{ while(1) \{ } & \text{while(1) \{} \\  \text{W:} & \text{Y:} \\  \text{ print ‘0';} & \text{ print ‘1';} \\  \text{ print ‘0';} & \text{ print ‘1';} \\   \text{X:} & \text{Z:} \\   \text{\}} & \text{\}} \\\hline   \end{array}$$

Synchronization statements can be inserted only at points $W, X, Y,$ and $Z$

Which of the following will ensure that the output string never contains a substring of the form $01^n0$ and $10^n1$ where $n$ is odd?

  1. $P(S)$ at $W, V(S)$ at $X, P(T)$ at $Y, V(T)$ at $Z, S$ and $T$ initially $1$
  2. $P(S)$ at $W, V(T)$ at $X, P(T)$ at $Y, V(S)$ at $Z, S$ and $T$ initially $1$
  3. $P(S)$ at $W, V(S)$ at $X, P(S)$ at $Y, V(S)$ at $Z, S$ initially $1$
  4. $V(S)$ at $W, V(T)$ at $X, P(S)$ at $Y, P(T)$ at $Z, S$ and $T$ initially $1$
edited by

7 Answers

2 votes
2 votes

A small approach:-

0 votes
0 votes
with the option B even we are not able to produce that string.option B might also Correct.but one semaphore is enough that is why i have taken the ans C better ans is C but B might also correct if option C is not given
0 votes
0 votes

We will show substring 010 or 101 is possible using some options given.

Assume S=1 and T=1

And consider these execution sequences:
 

Option (A)

  • Process P executes W: P(S) [so S becomes 1->0] and preempts.
  • Process Q executes Y: P(T) [so T becomes 1->0] and preempts. 
  • Now both P and Q can resume their execution in their respective CS in any order, and thus sequences "010..." or "101..." can be printed.


Option (B)

  • Process P executes W: P(S) [so S becomes 1->0] and preempts.
  • Process Q executes Y: P(T) [so T becomes 1->0] and preempts.
  • Now both P and Q can resume their execution in their respective CS in any order, and thus sequences "010..." or "101..." can be printed.


Option(D)

  • Process Q executes Y: P(S) [so S becomes 1->0] and preempts. 
  • Process P executes W: V(S) [so S becomes 0->1] and preempts.
  • Now both P and Q can resume their execution in their respective CS in any order, and thus sequences "010..." or "101..." can be printed.



Option (C) is thus the suitable answer.
You need not fully understand the code logic in an exam-setting. Sometimes option elimination helps.

Answer:

Related questions