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

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.

---

Note: The Question only says what it should not accept and nothing about what it should accept i.e. it never says all the other string apart from given conditon should be satisfied. So strings like 011110 might looks it should accept but it doesnt and question never says to accept also..

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).

---

In that case then 0110 is also not psble but in que it is mention that 01^n0 where n is odd means 01110 is not allowed but n can be even it should print 0110 ?? plz explain.

---

I think in the gist of avoiding the said substring, we also avoided the possibility of some other substring as well.

Which i think is fine as the question does not require for us to cover every type of substring but only avoid these types of substrings.

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

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

---

Why option B is wrong here,  explain

---

In option B.

Since both S and T are initialized to be 1. Both processes can enter CS at the same time. This can result in interleaving that produces: 0101. 

 

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.

Answer 5

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 6

A small approach:-