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

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)

Comments

0110 can be produced then how no concurrent execution?

---

When You consider Option (C) it has only one semaphore. so, no it cannot produce 0110.

NOTE: we just have to see that 01n0 and 10n1 where n is odd must not be produced by any schedule you don’t need to check if all the other combinations of 0’s and 1’s are being produced(Like in the case of TOC).

Answer 2

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

Comments

@akash 010 can occur but not 01110 in option B..correct me if I am wrong. I agree question only asks about n being odd...but justed wanted to know did I miss anything.

---

Can you explain me option b?

---

I also don't think 01110 is possible in option B because after printing 11 it can't print futther 1s as semaphore T value is only incremented by process P

Answer 3

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 4

C) At a time one process will down S and after printing make S up.