How many times will process P0 print "0"?

Question

The following program consists of 3 concurrent processes and 3 binary semaphores The semaphore, are initialized as S0=1 S1=0 S2=0

Process P0:

while(1)
{
wait (S0);
print '0';
release (S1);
release (S2);
}

Process P1:

wait(S1);
release (S0);

Process P2:

wait(S2);
release (S0);

How many times will process PO print '0"??

(A) At least twice (b) Exactly tWlce (c) Exactly thrice (d) Exactly once

in this I have a confusion that Process P1 and P2 as will execute once or they will continue after executing once as they are not having while loop like process P0, if they will execute once only then According to me the answer should be (b), and if they will execute again then the answer will be (A)

please help thanks in advance

Answer 1

Initially only P0 can go inside the while loop as S0 = 1, S1 = 0, S2 = 0. P0 first prints '0' then, after releasing S1 and S2, either P1 or P2 will execute and release S0. So 0 is printed again.

Answer 2

P0 will execute first because only S0=1. Hence it will print 0 (for the first time). Also P0 releases S1 and S2. Since S1=1 and S2=1, therefore P1 or P2, any one of them can be executed. Let us assume that P1 executes and releases S0 (Now value of S0 = 1). Note that P1 process is completed. Now S0=1 and S2=1, hence either P0 can execute or P2 can execute. Let us check both the conditions:-

1. Let us assume that P2 executes, and releases S0 and completes its execution. Now P0 executes; S0=0 and prints 0 (i.e. second 0). And then releases S1 and S2. But note that P1 and P2 processes has already finished their execution. Again if P0 tries to execute it goes into sleep condition because S0=0. Therefore, minimum number of times '0' gets printed is 2.

2. Now, let us assume that P0 executes. Hence S0=0, (due to wait(S0)), and it will print 0 (second 0) and releases S1 and S2. Now only P2 can execute, because P1 has already completed its execution and P0 cannot execute because S0 = 0. Now P2 executes and releases S0 (i.e. S0=1) and finishes its execution. Now P0 starts its execution and again prints 0 (thrid 0) and releases S1 and S2 (Note that now S0=0). P1 and P2 has already completed its execution therefore again P1 takes its turn, but since S0=0, it goes into sleep condition. And the processes P1 and P2 which could wakeup P0 has already finished their execution.Therefore, maximum number of times '0' gets printed is 2.

Reference: http://www.btechonline.org/2013/01/gate-questions-os-synchronization.html

Answer 3

The solution proceeds as below:

1. Only process P0 can execute first. That's because semaphore used by process P0 i.e S0 has an initial value of 1. Now when P0 calls wait on S0 the value of S0 becomes 0, implying that S0 has been taken by P0. As far as Process P1 and P2 are concerned, when they call wait on S1 and S2 respectively, they can't proceed because the semaphores are already initialized as taken i.e 0, so they have to wait until S1 and S2 are released!

2. P0 proceeds first and prints 0. Now the next statements release S1 and S2! When S1 is released the wait of process P1 is over as the value of S1 goes up by 1 and is flagged not taken. P1 takes S1 and makes S1 as taken. The same goes with Process P2.

3. Now, only one of P1 or P2 can execute, because either of them can be in the critical section at a given time.. Suppose P2 executes. It releases S0 and terminates.

4. Let P1 execute next.. P1 starts Releases S0 and terminates.

5. Now only P0 can execute because its in a while loop whose condition is set to true, which makes it to run always. P0 executes prints 0 second time and releases S1 and S2. But P1 and P2 have already been terminated so P0 waits forever for the release of S0.

Here's a second solution which prints 0 three times:

1. P0 starts, prints 0 adn releases S1 and S2.

2. Let P2 execute. P2 starts, releases S0 and terminates. After this only P0 or P1 can execute.

3. Let P0 execute. Prints 0 for second time and releases S1 and S2. At this point only P1 can execute.

4. P1 starts, releases S0, P1 terminates. At this point only P0 can execute because its in a while loop whose condition is set to true!

5. P0 starts, prints 0 for the 3rd time and releases S1 and S2. It then waits for someone to release S0 which never happens.

So the answer becomes exactly twice or exactly thrice, which can also be said "atleast twice"!

Please tell me if i am wrong anywhere!!

For more problems on semaphore, refer this

Answer 4

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.

Answer 5

Reading the question and the code I would also say (A). I am assuming that the processes cannot be preempted before completing their task.

It says the initial state is S0=1 S1=0 S2=0, and from what we know P1 and P2 will execute exactly once.

Concurrent processes can be complex and however I try to describe the flow people will find faults with the way I think about it, that is ok, I'm here to learn too.

Now you have a few situations yielding different results depending on order of processes.

P0 -> P1 -> P0 -> P2 -> P0 = Three times

P0 -> P1 -> P2 -> P0 = Twice

P0 -> P2 -> P1 -> P0 = Twice

This gives us the answer of at least twice.

Edit:

All this is made under the assumption of wait() blocking while semaphore == 0 and that release() sets semaphore = 1 because otherwise the code would just mostly be insanity.

If the processes can be interrupted at any time, then things can get interesting.

P0 starts out running because S0=1 at start
P0 print '0';
P0 release(S1);
-- here S1 may take over or not --
P0 release(S2);
-- here S2 may take over or not --
P0 goes back to wait(S0)
-- here P0 continues or if S1 *and* S2 have not run blocks --
-- it may also be that only S1 or S2 ran and now the other will run --

Now I tried figuring out a way to visualize how things would work out, and I failed to find a way good to put it in the code block.

If both S1 and S2 runs as soon as they can, since the semaphores are binary and can be in only one of two states, P0 will only be run twice, however if scheduling is perverse enough to delay either S1 or S2 until P0 has passed wait() once more P0 will run three times.

But I think this question was not meant to have interruptable processes, it just gets messy.

Answer 6

I'm assuming wait() decrements the semaphore and blocks if it becomes <= 0, whereas release increases the counter and wakes up the next process.

Given your code, P1 and P2 execute once (there is no loop around them). This means each of them triggers S0 once. And as P0 blocks waiting on S0 before every print, it will finally print '0' twice.

One more thing to check is the initial state of S0, because P0 will only block if S0 is 0. This is the case given your statement. Therefore, the answer is that P0 will print 0 exactly twice.