01

0 and 10^{n}1 where^{n}nis 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?

The Gateway to Computer Science Excellence

+36 votes

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?

- $P(S)$ at $W, V(S)$ at $X, P(T)$ at $Y, V(T)$ at $Z, S$ and $T$ initially $1$
- $P(S)$ at $W, V(T)$ at $X, P(T)$ at $Y, V(S)$ at $Z, S$ and $T$ initially $1$
- $P(S)$ at $W, V(S)$ at $X, P(S)$ at $Y, V(S)$ at $Z, S$ initially $1$
- $V(S)$ at $W, V(T)$ at $X, P(S)$ at $Y, P(T)$ at $Z, S$ and $T$ initially $1$

0

01

0 and 10^{n}1 where^{n}nis 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?

+37 votes

Best answer

+27 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

+1

If u look at option A then in this u can generate substrings of 01^{n}0^{ }

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 01^{n}0^{ }

Similarly, u can check for option b also.

+4 votes

option C..

All other options produces substring of given format ...

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

+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

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

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.4k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,737 questions

57,279 answers

198,172 comments

104,838 users