mutexes/events

[William.Lott@ARDATH.SLISP.CS.CMU.EDU]

 From Rob's comments, it looks like a quick summary of how to use mutexes
and events (CThread conditions) would be helpful.  So here it is.

When you have multiple threads of control that can modify the same data
structures, you have to have some way to synchronize their activities so
that they don't step on each other toes.   This is not an issue with purely
functional programming, because nothing gets modified.  But Lisp isn't
purely functional, and even if you constrain yourself to a functional
style, the runtime support cannot be functional.  So you need some
mechanism to facilitate this.

To this end, Dijkstra introduced the notion of semaphores.  A semaphore is
just a number with two operations on it P (wait) and V (signal).  (P and V
are the first letters of the Dutch words for wait and signal.)  The
semantics are:

P(s):
  if (s > 0)
    s = s - 1
  else
    suspend this process

V(s):
  if someone is waiting on this semaphore
    wake them up
  else
    s = s + 1

Note: these operations must be atomic.

Semaphores can be used for all sorts of useful things.  You can use them to
protect critical regions of code or data structures, and you can use the
value of the semaphore to encode information (the number of entries in a
queue), and all sorts of other things.  They are immensely useful.  But
that are a bit hard to implement efficiently.

So most threads packages peel off the two most common usages of semaphores.
The most common is the binary semaphore, where the value of s is limited to
0 or 1, and is initialized to 1 (mutex).  The other case is where the
(binary) state of a semaphore is used to represent some condition (event).
You can use mutexes and events to build full blown general semaphores, but
they will (obviously) be less efficient than using the special case if
possible.

For example, assume that you have two or more threads that are trying to
update a single variable.  Ever once in a while, a thread will execute
something like:

 x <- x + 1

But if it reads the value of X, then some other thread gets scheduled and
modifies X, then when the original thread gets control again, it will
overwrite any change the second threads might have made.  So you protect
the variable X with a semaphore:

  P(s)
  x = x - 1;
  V(s)

That way, the second thread will block at the P(s) until the first thread
has finished updating X and executes the V(s).  This is a mutex (which is
short for mutual-exclusion).  P(s) corresponds to mutex-lock(s) and V(s)
corresponds to mutex-unlock(s).

A more complicated case is when the state of a semaphore is used to
represent some condition.  You can use the semaphore to represent the
number of objects in a queue, and use P(s) whenever you extract one, and
use V(s) whenever you insert one.  If you try to extract one too many, then
you block until someone inserts another one.

Well, sometimes the condition you wish to represent doesn't map nicely to a
number, and even if it does, it's kinda sleezy to rely on the arithmetic
behind the semaphore.  It's the kind of thing that theory weenies like
because of the generality, but makes understanding code impossible.  So
CThreads condition objects, which we are calling events, are used to cover
this case.  The event object is really just a name for the event you are
interested in.  For example, you could code the standard producer-consumer
problem as:

(defvar *buffer*)
(defvar *mutex* (make-mutex))
(defvar *buffer-empty* (make-event))
(defvar *buffer-full* (make-event))

(defun producer()
  (loop
    (let ((new-value (compute-new-value)))
      (mutex-lock *mutex*)
      (loop
	(if (null *buffer*)
	    (return)
	    (event-wait *buffer-empty* *mutex*)))
      (setf *buffer* new-value)
      (event-signal *buffer-full*)
      (mutex-unlock *mutex*))))

(defun consumer()
  (loop
    (let ((value
	   (progn
	     (mutex-lock *mutex*)
	     (loop
	       (if *buffer*
		   (return)
		   (event-wait *buffer-full* *mutex*)))
	     (prog1
		 *buffer*
	       (setf *buffer* nil)
	       (event-signal *buffer-empty*)
	       (mutex-unlock *mutex*)))))
      (do-something-with value))))


When the producer produces a value, it will lock the buffer using a mutex,
and check it see if it's empty.  If it is not empty, it needs to wait for
it to become empty.  But if it were to unlock the buffer and then wait,
there is a window where the consumer could remove the value from the buffer
*before* the producer dropped into it's wait, and hence the producer would
not be woken up when the buffer emptied.

Therefore, the event-wait function takes both the event to wait for and the
mutex to unlock.  It must register this process as waiting for the event,
unlock the mutex, and go to sleep atomically.

When the consumer runs, it will lock the mutex, note that there is
something in the buffer, remove it, signal that the buffer is now empty,
and unlock the mutex.  It should unlock the mutex before it does it's
stuff with the value so that the producer can be producing the next value
at the same time.  When the consumer is done with this value, it locks the
mutex, etc, again.  If the buffer is empty, it waits for the producer to
produce the next value.

The reason you have to wrap the event-wait with a loop is to make sure that
nobody else got to the buffer between when the event was signaled and when
the mutex was re-acquired.  This can't happen in the above example, but if
there were multiple producers or consumers it could easily happen.

-William