GATE CSE 2003 | Question: 80

Question

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.

Process P:	Process Q:
while(1){ W: print '0'; print '0'; X: }	while(1){ Y: print '1'; print '1'; Z: }

 

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

Which of the following will always lead to an output staring with $\text{‘}001100110011\text{’}$?

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

• B. $P(S)$ at $W, V(T)$ at $X, P(T)$ at $Y, V(S)$ at $Z, S$ initially $1,$ and $T$ initially $0$

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

• D. $P(S)$ at $W, V(S)$ at $X, P(T)$ at $Y, V(T)$ at $Z, S$ initially $1$ , and $T$ initially $0$

Comments

Can you edit the question ? Option B of question 80 has typo ! How can be T be 0 & 1 at same time ?

---

Similar type of concept is asked in GATE 2022 (IIT KGP)

Answer 1

To get pattern $001100110011$

Process P should be executed first followed by Process Q.

So, at Process $P$ :  $\mathbf{W}$ $P(S)$   $\mathbf{X}$  $V(T)$ 

And at Process $Q$ : $\mathbf{Y}$ $P(T)$    $\mathbf{Z}$ $V(S)$

With $\mathbf{S=1}$ and  $\mathbf{T=0}$ initially ( only $\mathbf{P}$ has to be run first then only $\mathbf{Q}$ is run. Both processes run on alternate way starting with $\mathbf{P}$)

So, answer is (B).

Comments

your option Y has problem it should have been P(T)

---

Hence, the correct code becomes:-

Process P:	Process Q:
while(1){ P(S) print '0'; print '0'; V(T) }	while(1){ P(T) print '1'; print '1'; V(S) }

 

---

For option(d), process Q will starve for eternity

 

Answer 2

starting with  001100110011 means alternative sequence of process P and Q..
Process P should start execution so at W, P(s) where S=1..
to get alternate sequence X and Y are operation on same semaphore i.e. T.

option B or C.
bt process Q shouldn't start execution before process P ..
means Initial value T=0

W : P(s)         X : V(T)           Y : P(S)             Z : V(S)
S =  1    T = 0

Answer 3

Answer is B)

It cant be C) because If T = 1 then P(T) at Y for process Q can be executed before process P by decrementing T by 1 and print 11... which is not required.

Comments

why option a is not valid  s = t =1  at W,  P(s) = 0  and at X , print 00 V(S) =1 AGAIN   at Y , P(T) =0 PRINT 11  at  Z V(T) = 1  KINDLY EXPLAIN  is there issue of while loop , in process p  or why we can not prempt  after process P to process Q than  to P  again

---

Option a) is not correct because. 

In the question they asked for "Which of the following will always lead to an output staring with 001100110011 ? "

Always lead meaning at every possible solution it must lead to 001100110011,

But in option a) s and t initialized to 1 hence it might also start from Q then to P --> which gives o/p as "110011001100" 

therefore, option b) is correct.

‘001100110011’