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

Best answer
54 votes
54 votes

output shouldn't contain  substring of given form means no concurrent execution  process $P$ as well as $Q$. one semaphore is enough

So ans is (C)

edited by
35 votes
35 votes

Option 1. P(S) at W, V(S) at X, P(T) at Y, V(T) at Z, S and T initially 1 

By using this both process can run at same time since both semaphore value is 1 and resulted 01110 type string.

Option 2. P(S) at W, V(T) at X, P(T) at Y, V(S) at Z, S and T initially 1

By using this both process can run at same time since both semaphore value is 1 and resulted 01110 type string.

Option 3. P(S) at W, V(S) at X, P(S) at Y, V(S) at Z, S initially 1

here only one semaphore is used so only one process enter and run b/c both process start wth P(s).

Option 4. V(S) at W, V(T) at X, P(S) at Y, P(T) at Z, S and T initially 1

Both process can run at same time when first p2 run then p1 run . 

So c is answer

5 votes
5 votes

Output shouldn't contain  substring of given form means no concurrent execution  of processes P and Q. one semaphore enough  implement this functionality.
option C..
All other options produces substring of given format ...

Answer:

Related questions