= Solution
Give the two waiting predicates different <semaphores>. `empty` has one permit initially; `full` has zero. A writer takes the empty permit before touching the slot and transfers permission to a reader by releasing `full`. A reader does the reverse.
``
class SemaphoreMemory[T] extends Memory[T] {
private val empty: Semaphore = new CountingSemaphore(1)
private val full: Semaphore = {
val s = new CountingSemaphore(1)
s.down
s
}
private var slot: Option[T] = None
def write(msg: T): Unit = {
empty.down
slot = Some(msg)
full.up
}
def read: T = {
full.down
val result = slot.get
slot = None
empty.up
result
}
}
``
For a single slot, a separate <mutex> around `slot` is unnecessary. There is a unique circulating permission: either an empty permit is available, a writer holds it, a full permit is available, or a reader holds it. During the transition the sum of available permits can be zero; it is never necessary to assert that it is always one. In particular, the next writer cannot start until the preceding reader has finished reading, cleared the slot and released `empty`.
The <monitor> operations inside each <semaphore> also establish the required <happens-before> relation: the write precedes `full.up`, and a successful subsequent `full.down` makes it visible to the reader. Likewise, the reader's clearing precedes the next writer's successful `empty.down`. Slot accesses therefore need no unsynchronized visibility assumption. The invariant is
$$
\boxed{\text{exactly one slot-access permission, alternating writer then reader}.}
$$
Only writers wait on `empty`, and only readers wait on `full`. With the single-notification <semaphore> implementation in part (a), a state change wakes at most one waiter of the appropriate kind, avoiding the <thundering herd> of part (i). This is an efficiency improvement, not yet a first-come-first-served guarantee.
If one or more readers arrive before the first writer, they block on the initially unavailable `full` <semaphore>. Their waits release its <monitor>, so they do not prevent a writer from obtaining the independent `empty` permit. The first write releases `full` and permits exactly one reader to take that value. Remaining readers wait for later writes; they never see uninitialized storage.
Back to article page
