3.2k views

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 | 3.2k views
0

01n0 and 10n1 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?

0
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.
+1

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

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)

by Boss (30.9k points)
edited by

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 .

by Veteran (62.2k points)
+1

Prashant how option  1 & 2 generate this strings...elaborate ur logic

+1

If u look at option A then in this u can generate substrings of 01n0

Assume P process performs down on S, it will be allowed because S value initially is 1 and then it executes first print statement in p process, 0 is printed after this line, context switch occurs Process Q also allowed to perform down on T because its initial value is 1 and then it also print the first statement in Q process and 1 is printed in after this line and then again context switch occurs and process p comes for execution and prints 0 again.Now 010 is substring of 01n0

Similarly, u can check for option b also.

0
@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.
0
Can you explain me option b?

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

by (445 points)

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

by Veteran (60k points)
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
by
+1
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

1
2