# GATE2003-81

5.1k 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
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.
2

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)

edited by
0
0110 can be produced then how no concurrent execution?

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 .

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?

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

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

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
1
how option a and option b will it generate 01110?
0

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

## Related questions

1
2.9k 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. Process P: Process Q: while(1) { while(1) { W: Y: print '0'; print '1'; print '0'; print '1'; X: Z: } } Synchronization statements can be ... $P(S)$ at $W, V(S)$ at $X, P(T)$ at $Y, V(T)$ at $Z, S$ initially $1$ , and $T$ initially $0$
A processor uses $\text{2-level}$ page tables for virtual to physical address translation. Page tables for both levels are stored in the main memory. Virtual and physical addresses are both $32$ bits wide. The memory is byte addressable. For virtual to physical address translation, the $10$ most ... the page tables of this process is $\text{8 KB}$ $\text{12 KB}$ $\text{16 KB}$ $\text{20 KB}$
A uni-processor computer system only has two processes, both of which alternate $10$ $\text{ms}$ CPU bursts with $90$ $\text{ms}$ I/O bursts. Both the processes were created at nearly the same time. The I/O of both processes can proceed in ... first scheduling Static priority scheduling with different priorities for the two processes Round robin scheduling with a time quantum of $5$ $\text{ms}$
In a system with $\text{32 bit}$ virtual addresses and $\text{1 KB}$ page size, use of one-level page tables for virtual to physical address translation is not practical because of the large amount of internal fragmentation the large amount of external fragmentation the large memory overhead in maintaining page tables the large computation overhead in the translation process