# GATE2010-45

9.2k views

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$'?

1. At least twice
2. Exactly twice
3. Exactly thrice
4. Exactly once

edited
0
if s is a binary semaphore and the initial value of s is 1 then can 'signal' be performed on s ?  what will happen if signal(s) is performed?
0
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
0
when p0 execute second time  it will  free s1,and s2 so agian there will  chance to run p0 again n  this process continue forever and infinite zero will be printed ?
0
If there hadn't been the while loop in P0 then answer would have been Exactly once?
0
Given a binary semaphore 's' with initial value = 1. V(s) / UP(s) / signal(s) can still be performed. The process performing signal(s) on such a semaphore will check if there's some other process in the blocked queue (which is not possible since value of s is 1) and then it will set the value of s to 1. i.e. The value of 's' in such a scenario doesn't change.
1
P0->P1->P0->P2->P0 //3 times

OR

P0->P1->P2->P0 //2 times

So, at least  2 times
0
is zero can be printed infinte times also ? p0 while loop always satisfy the condition when p1 p2 runs once .

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

selected by
2
atleast 1 is never possible?
0

Can't understand "If the semaphore had 3 values possible, exactly three '0's would have been printed" How we can comment "exactly 3 0's " ?

2
@Gate-Keeda At least 1 is possible (because it holds for exactly 3 also). But less than 2 is not possible here.
3
@shree Here semaphore can have value either 0 or 1 only (because it is a binary semaphore). If we allow, 0, 1 and 2 as the values then both P1 and P2 will both release S0 (thus incrementing it twice), and thus P0 will execute totally 3 times. Thus exactly 3 0's will be printed.
4
Why it is mandatory to again execute P0? what if I just execute each process once?
11
In P0 there is an infinite while loop
0
sorry to bother you much. But I'm not getting why atleast once is not possible? Because it isn't in the options?
13
It will print 0 at least 2 times (in any circumstance). Now, even if "at least one" is there in option, at least 2 is the better answer.
2
sorry i didn't get it.why exaxtly 3 0's ?.it will keep on executing wait and release and a infinte number of 0's can be printed.
18
Infinite times 0 could not printed bcoz process P1 and P2 are not under while loop means they are executed only once. when process P0 execute second time it release s1 and s2 but process P1 and P2 not executed second time and program terminated.
0
Is it neccesary to execute process 1 and 2?What if p1 and p2 don't want to execute
0
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.
0
Can anyone please tell why there is no preemption here? ....means I understood both the cases and both are without consideration of preemption....please someone help...

Thanks
0

@Arjun sir plz make that bracket in bold trust me half of the doubts will be vanished.

(as it is a binary semaphore)

0

@Arjun sir Can someone please explain the answer is given as atleast 2, it means that infinite zeroes can also be printed, but my question is how can p1 and p2 be executed again and again because there is no while loop in those processes.(They will be executed once and complete the processes) P.S. :- I know one condition can be until all semaphores are zero they can be executed. But I want to know is this the method they are following???

0
There is a while loop, and if it is not there still it can execute because of wait and release operation
1

### @Arjun sir, here it is asked that at least how many times the 0 will be printed, then then answer is at least 2 times, "if the question was how many times" then the answer would be infinity. Please clarify.

0

Say P0 started execution and It executed While loop once, then Process P1 started execution and preempted after executing  wait (S1); and then P2 started execution and preempted after executing wait(S2); then when P1 starts execution again, it will be blocked at wait(S0); so, cannot we say that At least one would be a better option here if provided?

Thank you!

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.

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

reshown
0
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.
0
question is not clear to me.
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)

reshown by
0
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)
0
Is atleast one possible? if not, why?
0
You are saying that the least possibility is 1 rt?

First, we need to also have a look at the options and answer accordingly.

We have to try the maximum times we can execute P0.

Here we can execute P0 atleast twice. i.e. >=2.
0
yes, I was asking if "atleast one" was in option, it would have been correct or not?
0
yes. It would have been more correct than atleast twice.
0
Semaphores S0, S1, S2 have their own block queue or is it common for all?
4
Answer should be either 2 or 3. So, at least 2. 1 is never possible.
0
every semaphore has its own separate queue...
0
@Arjun Sir, what if P2 and P3 do not execute?
0

@MINIPanda,

I think you are asking for P1 and P2 . If they will not execute then P0 will be executed only once and it will wait for release(S0).

0
Oh yes it will be P1 and P2.

And if that is the case then had "at least once" been in the options, it would have been more appropriate right?
0
@MINIPanda,

as you are saying P1 and P2 don't execute, then after the first iteration of P0 who will perform release(S0) for next iteration of it :)

0
@MINIPanda,

don't get confused with "atleast".In the options "atleast" is there only bcoz P0 can be executed either twice or thrice so merging both choices we are getting "atleast twice"
0
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.
0
Yes, if that case would be included there, then it will be "atleast once".
0
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.
a is most appropriate ans here
0
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
0
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.

## Related questions

1
6.8k views
Consider the methods used by processes $P1$ and $P2$ for accessing their critical sections whenever needed, as given below. The initial values of shared boolean variables $S1$ and $S2$ ... properties achieved? Mutual exclusion but not progress Progress but not mutual exclusion Neither mutual exclusion nor progress Both mutual exclusion and progress
A system has $n$ resources $R_0, \dots,R_{n-1}$, and $k$ processes $P_0, \dots, P_{k-1}$. The implementation of the resource request logic of each process $P_i$ ... $n=40,\: k=26$ $n=21,\:k=12$ $n=20,\:k=10$ $n=41,\:k=19$
A system uses FIFO policy for system replacement. It has $4$ page frames with no pages loaded to begin with. The system first accesses $100$ distinct pages in some order and then accesses the same $100$ pages but now in the reverse order. How many page faults will occur? $196$ $192$ $197$ $195$