Princeton University
Computer Science Dept.

Computer Science 441
Programming Languages

Andrew W. Appel

Fall 1999

Guards in CML

The concurrent-read-exclusive-write module (program, how to run it) comes in two versions. The first version has each of the interface operations as a simple function that may block until enabled: 
signature CRXW =
sig
  type crxw_lock
  val crxwLock : unit -> crxw_lock
  val beginRead: crxw_lock -> unit
  val endRead: crxw_lock -> unit
  val beginWrite: crxw_lock -> unit
  val endWrite: crxw_lock -> unit
end
This may be inconvenient for some clients, who wish to select another action if the beginRead or beginWrite operation would block. For such clients, there is a more sophisticated interface: 
signature CRXW2 =
sig
  type crxw_lock
  val crxwLock : unit -> crxw_lock
  val beginRead: crxw_lock -> unit event
  val endRead: crxw_lock -> unit event
  val beginWrite: crxw_lock -> unit event
  val endWrite: crxw_lock -> unit event
end
The implementation of CRXW.beginRead is not difficult: 
  fun CRXW.beginRead (LOCK{bR,...}) = send(bR,())
and it's straightforward to modify it to be an event instead of a blocking function: 
  fun CRXW2.beginRead (LOCK{bR,...}) = sendEvt(bR,())
But the beginWrite operation is different: 
  fun CRXW.beginWrite (LOCK{bW,reqW,...}) = 
         (send(reqW,1); send(bW,()))
First it performs a send to register its request to write (send on reqW), then it performs the "real" blocking operation (send on bW). How should this sequence be turned into a selectable event?

The answer is (almost) to use the guard feature of Concurrent ML. Whenever any attempt is made to sync on guard(f), the function f() is executed to calculate the "real" event on which to choose. In the execution of f(), other communications may be performed, such as the Counter.inc of our example: 

  fun CRXW2.beginWrite (LOCK{bWrite,writersWaiting,...}) = 
         guard (fn() => (send(reqW,1); sendEvt(bWrite,())))
Whenever anyone attempts to select on any list of events containing beginWrite(lock), the guard function is executed. This increments the counter and returns the event, wrap(sendEvt(...),...). When the sendEvt(bWrite,()) is selected, then the counter is decremented.

This solution is almost right, but has a bug. What happens if the client performs 

    select[ beginWrite(lock), otherEvt ]
and the otherEvt is selected? Then the counter has been incremented, but the wrapped send never executes, so the counter never gets decremented. To make this work, it is necessary for the beginWrite to be notified that it was not selected. The withNack feature of CML (an enhanced guard that's also given an abort event that it can use to learn that the main event was not selected) can be used for this purpose, as described on page 79 of Reppy's book. 
  fun beginWrite (LOCK{bW,reqW,...}) = 
           withNack(fn nack =>
                     (send(reqW,1); 
		      spawn(fn()=>(sync nack; send(reqW, ~1)));
		      sendEvt(bW,())))
Now the nack event will be enabled if the sendEvt is not chosen, so the counter will be decremented either way.