GATE CSE 2003 | Question: 81

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.

$$\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?

• 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$ and $T$ initially $1$
• C. $P(S)$ at $W, V(S)$ at $X, P(S)$ at $Y, V(S)$ at $Z, S$ initially $1$
• D. $V(S)$ at $W, V(T)$ at $X, P(S)$ at $Y, P(T)$ at $Z, S$ and $T$ initially $1$

Comments

01ⁿ0 and 10ⁿ1 where n is odd?

Doesn't it mean that n can be even,  i.e 00,11,0110,1001,...are possible. And for these sequences, we need concurrent execution. Is it right?

---

Earlier I also thought the same... But I think the question is only asking us to check the given case.

Eg if I consider 1001... So according to our point of view it should be possible for part c),  but it's not produced.

Hence I think for the cases  mentioned only we should check.

---

Option B :

                           S=1,T=1;

P(S); // s=0
print 0;
print 0;
	P(T); //  T=0
	print 1;
	print 1;
	V(S); // V=1
V(T);   T=1
	print 1;
print 0;

 

so print sequence : 001110   here 01110 is substring

 

---

Option Elimination is the best approach here.

Answer 1

A small approach:-

Answer 2

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

Comments

Option B) can generate the Sequence , see this:

Process P executes 1st line by performing down on 'S' (as S=1 given) and print '0' and then pre-empt
Process Q comes under execution, executes 1st Line by performing down on 'T" (As T=1 given) and print '1' and then pre-empt
now, Process P again comes under execution executes 2nd line and print '0'
Therefore generating 010 , in the same way it can generate 101 too! SO option B) is wrong

---

how option a and option b will it generate 01110?

---

I think option a can generate 01110 

Let P executed and printed 00 , then Q got chance and printed 11. now again Q got chance and printed 1 and then preempted. Now P got cpu and printed 00. So the string is 0011100.

01110 is a substring of 0011100

Answer 3

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.