Re: [boost] Re: A simple monitor for Boost

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

From: "William Kempf" <sirwillard_at_[hidden]>
> --- 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.

What do you mean by "a monitor won't always work"?  That some
algorithm cannot be coded, or just that some efficiency may
be lost?

My experience with Java has been that the primitives are just
to difficult to use, and that successful multi-threaded apps
wind up reinventing the monitor.

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

I'll check it out, but Hansen's argument is that Java doesn't
really have monitors.

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

I am not dead set against explicit conditions and notifications,
but want to be very convinced before adding them.

> > 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 like the derivation because it more closely models the concept
of a monitor as a class with shared data needing protection.  But
if we made the members public rather than protected then containment
would be easier.

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

What is the added value of a non-recursive mutex? 
  
> > 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.

Could you elaborate?
  
> > 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.

Again, I'd like to know jsut what designs those are.  I remain
fearful of providing too primitive an interface.  And there is
more that one way to build a monitor, depending on what the
primitives are on a given system.