A simple monitor for Boost

From: Greg Colvin (gcolvin_at_[hidden])
Date: 2000-08-09 13:12:16

What is the simplest, safest language construct we know of for managing
concurrent access to data?  I would say the monitor, as developed and
described by Per Hansen and Tony Hoare in the 1970s, and implemented in
many programming languages since then.  The classic 1974 paper by Hoare
remains one of the best introductions
   http://www.acm.org/classics/feb96/
and Hansen's 1993 review is also very useful
   http://www.acm.org/pubs/citations/proceedings/plan/154766/p1-hansen/

The idea of a monitor is that data to be shared between threads of
execution must be accessed only via member functions of a monitor class.
The language runtime arranges that only one thread at a time can be
running in any member function of a monitor, and provides a mechanism
for threads to synchronize execution by waiting for a condition to be
true.

I suggest that a simple monitor interface is what we need for Boost,
and that a more complicated design will only cause problems.  Why?
First, concurrent programming is difficult at best, and a simpler
interface makes it easier to reason about program correctness.  Second,
we need to be able to implement this interface on many platforms which
will not all provide the same primitives.  The more features we add the
more difficult it may be to efficiently implement every feature on every
platform.  My suggestion is grounded in over two decades of experience
with concurrent programming, most recently including the implementation
of concurrency primitives for a very portable Java virtual machine.

How to provide monitors in C++?  If we were extending the language we
could follow Concurrent Pascal by adding "shared" and "await" as
keywords.  Here is how one could write Hansen's standard buffer example
with such an extension:

   shared class buffer {
      int p,c,full;
      vector buf;
   public:
      buffer(int n) : p(0),c(0),full(0),buf(n) {}
      void send (int m) {
         await (full == buf.size());
         buf[p] = m;
         p = (p+1)%buf.size();
         ++full;
      }
      int receive() {
         await (full == 0);
         int i = buf[c];
         c = (c+1)%buf.size();
         --full;
         return i;
      }
   };

In this example two or more threads can communicate through the shared
buffer with send and receive calls.  When a sending thread detects an
empty buffer it blocks, releases the monitor, and awaits a non-empty
buffer.  When a receiving thread detects a full buffer it blocks,
releases the monitor, and awaits an empty buffer.

Since we are not extending C++, but merely writing a library, we need
an interface to do the job of the "shared" and "await" keywords.  Here
is the simplest monitor interface I can imagine so far:

   class shared {
   protected:
      struct entry {
         entry(monitor*);
         ~entry();
      };
      void wait();
   };

Deriving a class from the "shared" base class does half the work of the
"shared" keyword, by associating shared data with a monitor class.  To
control the scope of the monitor we need the separate entry class.  The
intended discipline for the use of this class is to declare an entry at
the top of every accessible member function of the derived class.  The
wait function can do the job of the "await" keyword by way of the idiom
    while (!condition)
      wait();

To illustrate, here is Hansen's standard buffer example written to the
proposed interface:

   class buffer : shared {
      int p,c,full;
      vector<int> buf;
   public:
      buffer(int n) : p(0),c(0),full(0),buf(n){}
      void send (int m) {
         entry top(this);
         while (full == buf.size())
            wait();
         buf[p] = m;
         p = (p+1)%buf.size();
         ++full;
      }
      int receive() {
         entry top(this);
         while (full == 0)
            wait();
         int i = buf[c];
         c = (c+1)%buf.size();
         --full;
         return i;
      }
   };

I propose that our monitors should be recursive.  That is, it is OK for
a thread to enter the same monitor more than once.  For some underlying
thread packages this is already true, and if not it is trivial to use
a counter.  In my experience recursive monitors are much easier to use.

I do not propose explicit queues for waiting on condition variables.
Instead the monitor itself provides a single implicit queue.  In my
experience the use of explicit queues is a performance optimization at
best, and a source of error and confusion at worst.

I do not propose specific notification of waiters.  Rather, leaving the
scope of a monitor automatically notifies all waiters.  I am aware that
this can cause a "thundering herd" performance problem, but I am also
aware that failure to notify the appropriate waiter is a common cause of
deadlock.

I expect this proposal to be criticized for missing some "essential"
feature.  If so, such a feature can be added.  Before doing so let us
be sure that it is truly essential, and that it can be implemented
on every platform we can imagine porting to.

Greg Colvin