= Solution
Represent a <binary semaphore> by a two-element <list> containing the addresses of its busy flag and its waiting <FIFO queue>. A blocked <continuation> belongs to the waiting <FIFO queue>, not the scheduler's runnable <FIFO queue>. These definitions extend the `FunMem` scheduler from the preceding part:
``
val semaphore() =
let val busy = new() in
let val waiting = new() in
busy := false; waiting := nil; busy : waiting : nil;
val acquire(s) =
let val busy = head(s) in
let val waiting = head(tail(s)) in
if !busy then
callcc(lambda (blocked)
waiting := append(!waiting,blocked:nil); dispatch())
else (busy := true; nil);
val release(s) =
let val busy = head(s) in
let val waiting = head(tail(s)) in
if !waiting = nil then (busy := false; nil)
else let val next = head(!waiting) in
waiting := tail(!waiting); enqueue(next); nil
``
A newly created <semaphore> is free. Acquiring it while free marks it busy and immediately returns `nil`. Acquiring it while busy captures the remainder of the caller, appends that <continuation> to the waiting <FIFO queue>, and dispatches a runnable computation. No runnable copy of the blocked caller is retained.
When a waiting caller exists, `release` keeps the busy flag true: the released permit is reserved for that caller. It removes exactly one waiting <continuation> and appends it to the scheduler's runnable <FIFO queue>. It does not invoke `dispatch`, so the releasing computation keeps running. A newcomer cannot steal the reserved permit during the interval before the released caller resumes. That caller's captured <continuation> resumes after `acquire` with `nil`, already possessing the permit.
$$
\boxed{\begin{array}{ll}
\text{free acquire:}&\text{mark busy and continue};\\
\text{busy acquire:}&\text{block outside the runnable queue};\\
\text{release with waiter:}&\text{keep busy and enqueue one waiter};\\
\text{release without waiter:}&\text{mark free}.
\end{array}}
$$
These are <FIFO semaphores>; the question only requires selecting one waiter, so choosing the oldest is a valid stronger discipline. The updates contain no suspension except at the explicit blocking point, making them atomic relative to this <cooperative multitasking> scheduler. As allowed in the paper, invalid releases and executions in which every remaining computation is blocked need no error handling; the latter are <deadlocks>, not a way to make progress.
Back to article page
