Re: A simple monitor for Boost

From: William Kempf (sirwillard_at_[hidden])
Date: 2000-08-09 17:31:25

--- In boost_at_[hidden], "Greg Colvin" <gcolvin_at_u...> wrote:
> 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/

A monitor won't always work.  Monitors are usually used for internal 
synchronization, which can be too fine grained for some things.  All 
in all, though, you're correct.  The monitor is the current "best 
practice".  Remember, though, a monitor is nothing more than a mutex 
and a condition variable working together.  These are still the 
principle primitives.  Since they can also be used with out a monitor 
concept for certain tasks I don't think it's appropriate to define 
only a monitor and not the primitives the monitor is built up on.

> 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();

Check out J/Threads (do a web search) for an implementation very 
similar to this in C++.  It models the monitor concept off of the 
Java language.  It's a great concept, I just don't think it's 
the "only right choice".  For instance, many classes will need to 
protect shared resources but they'll never have a need to wait for a 
condition.  By tying the mutex and condition variable permanently 
into a monitor construct with out the individual constructs you're no 
longer as efficient as you could be in such a case.  Further, 
multiple conditions may be used to produce more efficient waits, 
while a monitor class is confined to a single condition to wait on.
 
> 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;
>       }
>    };

Personally, I don't like the derivation from shared.  I'd prefer 
containment.  Especially since shared would have no virtual functions 
(other than the d-tor) in your example.

> 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.

That's why I prefer a recursive mutex.  However, if the condition 
variable were defined appropriately it could use a mutex of either 
type.  So the monitor could be of either type.
 
> 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.

The performance optimization is valid in some cases.  I'm not against 
a monitor concept, only against it's existance with out the existance 
of the mutex and condition variable that it wraps.
 
> 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.

You have to be careful of starvation or race conditions with this 
approach.
 
> 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.

I don't see much for criticism here.  I just think the monitor is one 
of those higher level concepts that should be addressed only after 
the building blocks it's based on are defined.  Especially since I 
don't think you can do with out the building blocks for some designs.

William Kempf