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

Here P1 and P2 don't have a while loop, so they run only once

---

if this question didn't made sense, see clearly

$P1$ and $P2$ are not inside a $while(true)$ loop so they'd execute only once

---

so  min printed zeroes is 2 and max could be printed is 3

 

Answer 1

First $P_0$ will enter the while loop as $S_0$ is $1.$ Now, it releases both $S_1$ and $S_2$ and one of them must execute next. Let that be $P_1.$ Now, $P_0$ will be waiting for $P_1$ to finish. But in the mean time $P_2$ can also start execution. So, there is a chance that before $P_0$ enters the second iteration both $P_1$ and $P_2$ would have done release $(S_0)$ which would make $S_1$ $1$ only (as it is a binary semaphore). So, $P_0$ can do only one more iteration printing $'0'$ two times.

If $P_2$ does release $(S_0)$ only after $P_0$ starts its second iteration, then $P_0$ would do three iterations printing $'0'$ three times.

If the semaphore had $3$ values possible (an integer semaphore and not a binary one), exactly three $'0's$ would have been printed.  

Correct Answer: A, at least twice

Comments

in the code of p0 :

while (true) {
A: wait (S0);
print '0';
release (S1); ---------------- preempts from here
B: release (S2);
}

if any process preempts from here, then will it magically starts from point A, or after resuming, will it start from point B?

then after executing p1, how process p0 starts from point A?

then how it can print 3 times 0? shouldn't it print exactly twice?

---

if p1/p2 run before p0 then they will go in block state and then p0 runs which will print 0 and release s1,s2. Then as there is no signal/up will they ever unblock or only one zero will get printed. please explain anyone

---

how p1 and p2 can run until s1 and s2 have value = 1 , initially s1 and s2 both are 0, wait() won't allow until p1 runs and you have the value of s1 and s2 as 1 only then p1 and p2 will be able to enter c.s.

Answer 2

Option A is True.
Initially P0 will execute because only S0=1. It will print single 0.

Now when S1 and S2 are releases by P0 then any one of them can be executed.

Let us suppose P1 executes and releases S0(Now value of S0 is 1).

Now there are two possibilities either P0 or P2 can execute.

Let us take P2 executes and releases S0, so at the end P0 execute and print 0 (means two 0's) but if P0 executes before P2 then total of 3 0's will print(one at the time of P0 and then P2 which releases S0 so P0 executes again).
So the perfect answer is at least two 0's.

ref@ http://stackoverflow.com/questions/12069305/how-many-times-will-process-p0-print-0

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.

---

question is not clear to me.

---

beautiful!

Answer 3

Minimum no. of time 0 printed  is twice when execute in this order (p0 p1 p2 p0)

Maximum no. of time 0 printed is thrice when execute in this order (p0 p1 p0 p2 p0)

Comments

But at least twice >=2 means it can be printed 100times  also but here it should  be at least twice and atmost thrice right?(>=2 and <=3)

---

how maximum is 3? it can print 0 infinite times also

---

not possible because P1 and P2 can’t run infinite times so release (S0) is executed one -one time by P1 and P2.Zeros are printed  2 or 3 times depending on the S0 value. So at least 2 is the right answer.

---

Yes exactly, summary

P0 has while(true) → P0 can execute repeatedly.
P1 has no loop → P1 executes once, then terminates.
P2 has no loop → P2 executes once, then terminates.

Hence, min = atleast 2 and max = 3

Answer 4

The answer is A.

Comments

Ok..I understand what you are trying to say. I was just computing all the possible cases that may arise. If you consider mine ( where P0 can only iterate once) along with the other two cases (where P0 iterates twice and thrice) then I thought it would indicate "atleast once" as the answer.

---

Yes, if that case would be included there, then it will be "atleast once".

---

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.

Answer 5

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 6

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.