CMSC 412

NOTE 10

March 17, 1999

Binary Semaphores
NEW 2011/08/11:
This note is incorrect.
Please look
here
1. Overview
The semaphore discussed previously is called a counting sempahore.
Another kind of semaphore is the binary semaphore; This is exactly
like a counting semaphore except for the following:

the semaphore value is restricted to 0 and 1.

P succeeds only when the semaphore value is 1.

V does not change the semaphore value when it is 1. (Thus successive Vs
are lost.)
Binary semaphores are sometimes easier to implement. than counting
semaphores. We will not describe implementations of binary semaphores
in terms of lowlevel or OS constructs (these would be similar to
the implementations of counting semaphores). Instead we show how counting
semaphores can be implemented by binary semaphores, which demonstrates
that binary sempahores are as powerful as counting semaphores.
Convention: Unless otherwise mentioned, a semaphore is to be
interpreted as a counting semaphore.
2. Implementing Counting Sempahores using Binary Semaphores
We want to implement counting sempahores using binary semaphores as the
only synchronization construct, that is, without accessing pcbs,
disabling interrupts, etc. We also do not want an implementation that uses
busy waiting.
Consider an implementation of a counting semaphore S. Clearly the implementation
needs to keep track of the value of S, say in an integer variable S.val.
Furthermore, if a process is supposed to wait on S, then the implementation
has to make the process wait. Because binary semaphores are the only synchronization
construct allowed in the implementation, the only way that the implementation
can make the process wait is to have it wait on a binary semaphore, say
S.wait (recall that busy waiting is not acceptable).
These considerations lead us to the following first cut at an implementation:
Counting Semaphore construct

Implementation using Binary Semaphores

Semaphore S initially K 
record S {
integer val initially K,
BinarySemaphore wait initially 0
} 
P(S) 
P(S) {
if S.val = 0
then { P( S.wait ) }
else { S.val := S.val  1
}
} 
V(S) 
V(S) {
if "processes are waiting on S.wait"
then {
V( S.wait ) }
else { S.val := S.val + 1
}
} 
NOTE:

We use P(S) and V(S) to denote wait and signal operations on a semaphore
S regardless of whether S is a counting semaphore or a binary semaphore,
even though they have different effects in the two cases (i.e., P and V
are "overloaded" in the C++ sense). If this is confusing to you, then use
Pb() and Vb() to refer to binary semaphore operations and P() and V() to
refer to counting sempahore operations. So in the table above, P(S.wait)
and V(S.wait) would become Pb(S.wait) and Vb(S.wait).
There are two problems with the above implementation:

It does not protect changes to S.val, that is, if several processes are
executing the body of P(S) or V(S) at the same time. One way is to introduce
a binary semaphore, say S.mutex, to ensure that the bodies of P(S) and
V(S) are mutually exclusive.

How to determine whether "processes are waiting on S.wait" (note that this
is not one of the allowed operations on a semaphore). One way is to keep
track of the number of processes waiting on S.wait in an integer variable,
say S.wCount. The challenge here is to keep S.wCount consistent (or adequately
consistent) with its intended meaning. Of course, S.wCount will also have
to be protected from concurrent updates.
This leads us to the following implementation:
Counting Semaphore construct

Implementation using Binary Semaphores

Semaphore S initially K 
record S {
integer val initially K,
// value of S
BinarySemaphore wait initially 0, // wait
here to wait on S
integer wCount initially 0, // number
of proceses waiting on S
BinarySemaphore mutex initially 1 //
protects val and wCount
} 
P(S) 
P(S) {
P( S.mutex );
if S.val = 0
then { S.wCount := S.wCount
+ 1;
V( S.mutex );
P( S.wait );
}
else { S.val := S.val  1;
V( S.mutex );
}
} 
V(S) 
V(S) {
P( S.mutex );
if S.wCount > 0
then { S.wCount
:= S.wCount  1;
V( S.wait );
V( S.mutex );
}
else { S.val := S.val + 1;
V( S.mutex );
}
} 
NOTE: Because S.wCount is nonzero only if S.val is zero, the two variables
can be combined, leading to the following implementation:
Counting Semaphore construct

Implementation using Binary Semaphores

Semaphore S initially K 
record S {
integer val initially K, // value
of S or # of processes waiting on S
BinarySemaphore wait initially 0, //
wait here to wait on S
BinarySemaphore mutex initially 1 //
protects val
} 
P(S) 
P(S) {
P( S.mutex );
if S.val <= 0
then { S.val := S.val  1;
V( S.mutex );
P( S.wait );
}
else { S.val := S.val  1;
V( S.mutex );
}
} 
V(S) 
V(S) {
P( S.mutex );
if S.val < 0
then { V( S.wait
)};
S.val := S.val + 1;
V( S.mutex );
} 