Past exam of the computer science course of the University of Oxford / 2015 / Concurrent programming / 3 / b / iii / Solution 2026-10-31
View more
A FIFO semaphore must reserve a released permit for the oldest waiter. Merely waking the oldest caller is insufficient if a newcomer can consume the permit first. Keep an explicit FIFO queue of private wait records, and transfer the permit directly to the oldest record. Each record has its own monitor, so releasing a permit wakes exactly its chosen recipient.
class FifoBinarySemaphore(initiallyAvailable: Boolean) extends Semaphore {
  private final class Waiter { var granted = false }
  private val queue = scala.collection.mutable.Queue[Waiter]()
  private var available = initiallyAvailable

  def down: Unit = {
    val mine: Option[Waiter] = synchronized {
      if (available) {
        assert(queue.isEmpty)
        available = false
        None
      } else {
        val w = new Waiter
        queue.enqueue(w)
        Some(w)
      }
    }
    mine.foreach { w =>
      var interrupted = false
      w.synchronized {
        while (!w.granted) {
          try { w.wait() }
          catch { case _: InterruptedException => interrupted = true }
        }
      }
      if (interrupted) Thread.currentThread().interrupt()
    }
  }

  def up: Unit = synchronized {
    if (queue.nonEmpty) {
      val w = queue.dequeue()
      // available stays false: this permit is reserved for w.
      w.synchronized {
        w.granted = true
        w.notify()
      }
    } else {
      require(!available, "unmatched binary-semaphore release")
      available = true
    }
  }
}
The wait loop is deliberately uninterruptible with interruption status restored after acquisition: abandoning a queued wait record would otherwise strand its reserved permit. A caller that acquires must still complete the buffer operation. granted is read and written under the wait record's own monitor. The persistent flag prevents a lost wake-up if up runs after registration but before the caller begins waiting. Spurious wakeups simply repeat the loop.
The outer monitor serializes registration and the FIFO queue. A caller either consumes a genuinely free permit when nobody is queued, or appends one record. up removes exactly the front record and leaves available false, even if its owner has not yet resumed. A newcomer must queue behind existing records instead of stealing the handoff. The outer-to-inner lock ordering in up is safe because waiting callers release the outer monitor before acquiring their private monitors; no caller holds a private monitor while trying to reacquire the outer one.
Now use the same buffer body as in (ii), replacing only the initialization of its two fields:
private val empty: Semaphore = new FifoBinarySemaphore(true)
private val full: Semaphore = new FifoBinarySemaphore(false)
This is a complete implementation when inserted in SemaphoreMemory: its write and read methods remain exactly the displayed methods. Pending writers obtain empty-slot permissions in registration order on empty; pending readers obtain full-slot permissions in registration order on full. Each handoff permits just one caller to access the slot, so
(1)
First-come-first-served means the order in which concurrent calls register under the monitor; two overlapping calls have no externally determined order. The guarantee is separate for the two kinds of caller. A global order combining reads and writes cannot be required: an initial read must wait while a later write supplies its value. Subject to eventual scheduling and the arrival of matching operations of the opposite kind, no registered caller is overtaken by a later caller of its own kind. The design avoids broadcast wakeups as well as barging.
Read the full article
Past exam of the computer science course of the University of Oxford / 2015 / Principles of programming languages / 2 / e / Solution 2026-10-31
View more
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.
(1)
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.
Read the full article