GATE CSE 2010 | Question: 45

Question

The following program consists of $3$ concurrent processes and $3$ binary semaphores. The semaphores are initialized as $S0=1, S1=0$ and $S2=0.$
$$\begin{array}{|l|l|}\hline \text{Process P0}  &  \text{Process P1} & \text{Process P2} \\ \hline  \text{while (true) \{} & \text{wait (S1);} & \text{wait (S2);} \\  \text{    wait (S0);} & \text{release (S0);} & \text{release (S0);} \\  \text{   print ‘0';} & &  \\  \text{   release (S1);} & & \\  \text{   release (S2);} & \text{} & \text{} \\ \text{\}}  &  \text{}   \\\hline \end{array}$$
How many times will process $P0$ print '$0$'?

• A. At least twice
• B. Exactly twice
• C. Exactly thrice
• D. Exactly once

Comments

@Arjun sir yeah that’s what I meant, it’s not exactly the same thing. 

So just because there exists an order of execution that can print two 0s, they’re saying “at least twice”. Got it. 

---

Is it necessary to expect P1 or P2, suppose neither P1 nor P2 executed, than S0 will not be set to 1 and hence we can say that '0' will be printed only once.

So shouldn't the option be like "Atleast once" ?

Please correct if I am wrong.

---

They are already scheduled in the CPU, so unless all the semaphore variables are set to 0 all of them will try to be executed.

Answer 1

a is most appropriate ans here

Comments

because of the word concurrent we can execute both the process together, but my doubt is if s=1 then can we release(s) again? because it is a binary semaphore & already its value is 1. please someone explain

---

Hi, here atleast 1 cannot be the answer because, in any order we try to execute the 3 processes, say if P0 executes first then after its execution, S1=S2=1, and S0=0, so if P0 executes again since its in while I can execute again, it gets blocked and waiting for someone to releaseS0.

then whenever P1 or P2 get a chance they will not be blocked since S1=S2=1, so they will release S0 and make S0=1,

Now there r 2 cases, either P1 and P2 occur one after the other then finally P0 comes in this case S1=1 only so only once P0 can execute and it will print second 0.

Or P1 then P0 then again P2 then P0, in this way P0 gets two more times to run so total 3 zeros. So anyhow atleast 2 two times its printed.

Answer 2

Initial condition : S0=1, S1=0, S2=0,

so process P1 and P2 have to wait and only P0 can execute first.

After completing one iteration of the while loop, 0 is printed once.

Now the semaphore variables are – S0=0, S1=1, S2=1

In the minimalist case – P1 and P2 both will be incrementing S0 in one go, so after both P1 and P2 complete execution,

S0=1, S1=0, S2=0

now again P0 will be executed and print 0.

After that it will set S0=0.

So in the worst case S0 will be printed twice.

S0 willbe printed atleast twice.