The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+32 votes
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$
in Operating System by Veteran (98.5k points)
edited by | 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

 

5 Answers

+33 votes
Best answer

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
+26 votes

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

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?
+4 votes

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

by (445 points)
+4 votes

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)
0 votes
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
Answer:

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
49,833 questions
54,800 answers
189,503 comments
80,723 users