Re: A simple monitor for Boost

From: William Kempf (sirwillard_at_[hidden])
Date: 2000-08-10 09:38:04

--- In boost_at_[hidden], "Greg Colvin" <gcolvin_at_u...> wrote:
> From: "William Kempf" <sirwillard_at_m...>
> > --- 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?

Well, it's a tad over stated on my part.  A monitor can work for most 
everything if exposed.  However, the classical monitor talks only 
about internal synchronization of an object.  Internal 
synchronization won't always work, thus I over stated that a monitor 
won't always work.  I probably should retract that particular comment.

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

Java supports monitors, of a sort.  The model is flawed, causing the 
problems you've encountered.  Hopefully we won't make the same 
mistakes.  IMO, a monitor can not replace a mutex in C++, it can only 
complement it.  A monitor is much more complex than a mutex, so if 
you never wait within the code it's way too heavy of a 
synchronization object.  Also, despite the dangers in doing so, 
having multiple conditions that can be waited on can be an important 
optimization in some algorithms.  I'm not as convinced of this as I 
am of the importance of the mutex, so it may be that we need to not 
include a condition type and only include the monitor.
 
> > 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.

J/Threads have a monitor that's as complete as the one you've given 
here.  I need to read Hansen's argument to fully understand why he 
thinks Java doesn't really have monitors (I plan to do so later 
today).  However, the monitor within J/Threads that is used to 
emulate the code in Java has the same interface that you've described 
here.

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

I'm more concerned with not dropping mutex entirely in favor of 
monitor than I am about dropping conditions.
 
> > 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.

Completely hiding the monitor prevents you from doing external 
synchronization.  This means that to successfully perform 
transactional calls in a thread safe manner you have to do further 
object abstractions.  This is a pain to code and often leads to 
performance issues.  It also leads you down the path where I stated 
earlier that monitors can't always be used.  Depending on the class I 
might be inclined to expose the monitor on the public interface.  If 
we go this route you need to be concerned about the destructor in the 
monitor class.  It eitehr needs to be virtual, leading to overhead 
that I'd like to avoid in some cases, or it must be protected which 
would lead to the monitor only being useful in derivation.  It might 
not be bad to force it's use through derivation, but I'm not inclined 
to agree with out some convincing.

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

Performance on some platforms.  Don't get me wrong... I'm personally 
not arguing this point.  Others, however, are.
   
> > > 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?

Not with out getting into specifics on implementation.  I'm not 
saying that this isn't the semantics that we want, I'm just warning 
you that the implementation can be more difficult to code with out 
starvation on some platforms.