Past exam of the computer science course of the University of Oxford / 2015 / Concurrent programming / 3 / a / Solution 2026-10-31
View more
A counting semaphore holds a nonnegative number of permits. down waits until a permit is available and consumes one; up returns a permit and can release a waiting caller. A binary semaphore restricts the number available to zero or one. Unlike a mutex, a semaphore need not be released by the same software thread that acquired it; this permits producer-to-consumer signalling.
Interpret maxCount as the initial number of permits and, for this bounded implementation, the maximum permitted number of unmatched releases. An up beyond that capacity is a programming error, rather than a blocking operation. Clients obey this release discipline. If an unbounded counting semaphore is desired instead, remove the upper-bound requirement and use a sufficiently wide counter; a capacity-one instance is binary only under the corresponding balanced-use discipline.
class CountingSemaphore(maxCount: Int) extends Semaphore {
  require(maxCount > 0)
  private var count = maxCount
  def down: Unit = synchronized {
    while (count == 0) wait()
    count -= 1
  }
  def up: Unit = synchronized {
    require(count < maxCount, "unmatched semaphore release")
    count += 1
    notify()
  }
}
All accesses to count occur under the same monitor. wait atomically releases that monitor while sleeping, then reacquires it before returning. The while is needed because of spurious wakeups and because another caller can consume the returned permit before the notified caller reacquires the monitor. Only down callers wait here, and they all wait on the same predicate; hence waking one with notify is sufficient. A later up notifies another waiter if necessary. This use of notify will not be safe for the mixed predicates in the next part.[ref]
A binary semaphore initially available is new CountingSemaphore(1). To initialize it unavailable, call its down once during construction, before publishing it to other software threads. Its state obeys
(1)
This implementation provides no first-come-first-served guarantee: a new caller can acquire the monitor before a notified waiter. The following examples assume ordinary successful execution without cancellation or interruption of a partially completed buffer operation.
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