How do Binary Semaphores proceed?

Question

I was studying binary semaphores when the following question turned up:

Suppose there are 3 concurrent processes and 3 binary semaphores... The semaphores are intitialised as S0=1, S1=0, S2=0. The processes have the following code:

Process P0:                   Process P1:                       Process P2:

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

Now the question is how many times the process will print 0 ?

Let me explain How i was solving it.. suppose the first three statements of the three processes be executed concurrently! i.e, the while statement of process p0, wait(S1) of process p1 and wait(S2) of process P2.. Now, the wait(S1) and wait(S2) will both make the semaphore values -1 and the processes P1 and P2 will be blocked.. Then wait(S0) of Process P0 will be executed. When this happens S0's value becomes 0 and the process P0 moves into blocked state, as a result all the processes will be blocked and in a deadlock state!! But unfortunately thats not the answer. . Please tell me where I am wrong and how the solution proceeds ? :|

EDIT:

I was wrong in my approach to binary semaphores.. they can take only 0 and 1!

Chandeep Chandeep · Accepted Answer · 2012-10-18T03:40:44

Ok .. so here i am answering my own question :P ..

The solution proceeds as below:

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!
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.
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.
Let P1 execute next.. P1 starts Releases S0 and terminates.
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:

P0 starts, prints 0 adn releases S1 and S2.
Let P2 execute. P2 starts, releases S0 and terminates. After this only P0 or P1 can execute.
Let P0 execute. Prints 0 for second time and releases S1 and S2. At this point only P1 can execute.
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!
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!!

How do Binary Semaphores proceed?

1 Answers