The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+27 votes
4.4k 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.$

Process $P0$ Process $P1$ Process $P2$
while (true) {
    wait (S0);
    print '0';
    release (S1);
    release (S2);
}
wait  (S1);
release (S0);
wait  (S2);
release (S0);

How many times will process $P0$ print '$0$'?

  1. At least twice
  2. Exactly twice
  3. Exactly thrice
  4. Exactly once
asked in Operating System by Veteran (101k points)
edited by | 4.4k views
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

5 Answers

+40 votes
Best answer

There are lots of complicated answers, writing just for the simplifications:
There are only $2$ possible execution sequence here:

  1. $P_0\to P_1\to P_0\to P_2\to P_0 \qquad P_0$ is executed thrice here will print $0$ thrice.
  2. $P_0\to P_1\to P_2\to P_0\qquad P_0$ is executed twice only.

Hence, answer is "at least twice".

answered by Boss (17k points)
edited by
+3
in binay semaphore can we do up operations (signal) any number of times?
+1
the process P0 will print 0 at least twice and at most thrice...
0
I understood the first explanation but can after p0, p1 and p2 be performed regularly?

I mean to say that if p1 releases the lock and make semaphore S0 value 1 then can now again p2 also release the lock ? or It needs to wait until S0 again decremented?

If I am right then in your second example also 0 will be printed three times.
0
is it necessary for p0 to go again if it is not willing to go then how a is the answer
+26 votes

First P0 will enter the while loop as S0 is 1. Now, it releases both S1 and S2 and one of them must execute next. Let that be P1. Now, P0 will be waiting for P1 to finish. But in the mean time P2 can also start execution. So, there is a chance that before P0 enters the second iteration both P1 and P2 would have done release (S0) which would make S1 1 only (as it is a binary semaphore). So, P0 can do only 1 more iteration printing '0' two times.
If P2 does release (S0) only after P0 starts its second iteration, then P0 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.  

answered by Veteran (357k points)
+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 " ?

+1
@Gate-Keeda At least 1 is possible (because it holds for exactly 3 also). But less than 2 is not possible here.
+1
@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.
+2
Why it is mandatory to again execute P0? what if I just execute each process once?
+4
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?
+4
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.
+1
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.
+3
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
+7 votes

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.


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

answered by Loyal (6k points)
reshown by
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 votes
The answer is A.
answered by Boss (19.7k points)
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?
+3
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 :)

So for your case "only one time" will be the answer.
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.
0 votes
a is most appropriate ans here
answered by Active (4.4k points)
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
Answer:

Related questions



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

39,529 questions
46,674 answers
139,826 comments
57,596 users