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 low-level 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 );` `}`