Re: [boost] Re: Threads

From: Greg Colvin (gcolvin_at_[hidden])
Date: 2000-08-21 19:15:11

From: William Kempf <sirwillard_at_[hidden]>
> --- In boost_at_[hidden], "Greg Colvin" <gcolvin_at_u...> wrote:
> ...
> > No, I'm trying to find a safe C++ representation of the "monitor"
> > concept, which previous work in computer science has shown to be a
> > sufficient basis for multi-threaded programming.  I'm using the bounded
> > buffer as the classic example, in which there is one monitor and two
> > related queues (a.k.a. "condition variables").  Of course if the
> > conditions are unrelated they won't be combined in a single wait/notify
> > block.
> 
> I must be totally misunderstanding you.  The code you've submitted is 
> very specific to the classic example.  It does not solve any general 
> case problems.  For instance, assume an unbounded buffer, where the 
> only condition you'll ever wait on is "not empty" and show how the 
> code you posted can be reused to handle this case.

Sorry, but I haven't worked out all the code, just the one
example.  I do think the concept is fairly general, and that
"bounded buffer" is not the only problem whose solution can
be a monitor, a set of condition variables, and a sequence
of transitions from condition to condition.

> I guess my argument is that with out support from the language a 
> monitor is nothing more than a design pattern.  In the classic paper 
> the monitor is a "class" in which the language knows to protect each 
> method with a hidden mutex.  With out language support the mutex can 
> not be hidden and the programmer is responsible for locking the mutex 
> on entry to every method.  

That is a reasonable argument.  I still think we can encapsulate
the design patterns so as to make abuse more difficult, if not
impossible.  I am not yet happy with what I am proposing, but am
hoping we can push in this general direction.

Another possibility, which I think Beman already suggested, is to
expose the mutex as a smart pointer class with an operator-> that
handles the locking.

What we can't do, without language support, is enforce the
discipline that all shared data be accessed atomically.

> Beyond this, the only difference between 
> the monitor pattern we have with our Mutex and ConditionVariable 
> models and the classic paper is that our ConditionVariable requires a 
> while loop with the predicate (which we propose encapsulating within 
> the wait() by using a NullaryPredicate) because of "spurious 
> wakeups".  This isn't much of a consequence (especially if we require 
> the predicate, which isn't required in my current implementation only 
> due to compiler constraints).

Actually, whether you need a while() loop or an if() condition
depends on what scheduling guarantees are available.  And I now see,
contrary to my previous thoughts, that arranging the tests as
while...wait or if...wait allows for a thread to get started when
all the conditions start out unsignaled.  These are exactly the
kinds of details that I want to hide.

> How, exactly, are we lacking here in your eyes?  How would you 
> propose shoring up the areas where we're lacking?  What are the 
> consequences of any such higher level design (remember that the C++ 
> language designers are just as concerned with performance as they are 
> with correctness/safety, and in fact they are usually in favor of 
> performance vs. safety in the cases where it's unsafe only due to 
> programming error)?

I am acquainted with the C++ language designers and their concerns.

> > > So you're proposing separate CV implementations depending on the 
> > > number of conditions used?
> > 
> > I think that zero-, one- and two-condition variants may suffice.
> 
> Only for the simplest of problem domains.  I'm not willing to bet 
> that 3 conditions will be enough for all problems.  One could 
> probably find work arounds if we did limit it to this, but such work 
> arounds would not be optimal.

The four forms I give should work for any set of conditions that can
be arranged as a directed graph.  The example I give is just

   nonempty
    |   ^
    |   |
    V   |
   nonfull

but more states and transitions can be programmed.  I wonder if our
graph library might be of some use here?  Dietmar?

> > > > I don't see any difficulty with more than two conditions.
> > > 
> > > Which "out condition" do you signal?  Both?
> > 
> > Whichever one is made true.  I see each monitor function as causing
> > a transition from an entry state to an exit state, so you can string
> > as many of them together as you like.
> 
> This isn't always true.  In the classic example putting an item on 
> the buffer doesn't necessarily cause a transition to a non-empty 
> state, since we may have already been in a non-empty state.  Granted, 
> in this example a "false signal" in this case won't cause any harm,
> but I'm not sure that all problem domains will result in the same 
> consequences.

I think the "false signal" could be avoided in the implementation if
it really causes a problem.

> >  Where this might break down is
> > a problem that requires conditional signaling.  For that a three-
> > condition variant with a extra expression will be needed.  So in all
> > I see four forms:
> > 
> >    wait(monitor)
> 
> *confused*  What are we waiting for here?

Sorry.  This form should probably just be named lock().  It's for a
monitor that should be entered unconditionally.  We are "waiting" to
be allowed to enter the monitor.

> >    wait(monitor,entry_lambda,condition)
> > 
> >    wait(monitor,entry_lambda,entry_condition,exit_condition)
> > 
> >    wait(monitor,entry_lambda,entry_condition,
> >         exit_lambda,if_exit_condition,else_exit_condition)
> 
> The exit condition waits seem like needless encapsulation.  It's just 
> as safe and easy to explicitly signal the exit conditions yourself.  
> Some non-trivial conditional signaling may also be done more easily 
> with just the wait(monitor,entry_lambda,condition) variant (and 
> actually, instead of a monitor we should pass a lock to insure at 
> compile time that the monitor is locked).  I'm not totally against 
> the other two variants, I'm just not sure that I think they add any 
> safety or utility.

The wait() constructors already encapsulate the lock.

I think that encapsulating the necessary notification patterns is a
net win, but I'm not hard over on it.

> > > > > Again, I see no purpose to signal a second condition on exit of the 
> > > > > wait in a general fashion.  It may work in some specific cases, but 
> > > > > it's pointless in most.
> > > > 
> > > > In a multi-queue setup you will always want to signal a condition
> > > > at the end of each handler.  How else to make any progress?
> > > 
> > > This isn't necessarily true.  However, the biggest problem is that 
> > > you're addressing the "bounded buffer/producer consumer" problem 
> > > specifically, with out thinking about how the CV can be used outside 
> > > of this single problem domain.
> > 
> > I'd like to see examples of problems that can't be solved with monitors
> > and closely related condition variables.
> 
> There are none, and I never claimed there were.  I have claimed that 
> a monitor class would be over kill in some cases (where you must 
> protect shared resources but never wait on a condition) so I'm not in 
> favor of an implementation that fully ties the mutex (or monitor if 
> you prefer that name) and the CV.  The classic paper on monitors 
> agrees with me here, with the only difference being that the 
> mutex/monitor is a language construct and not a variable/object.  We 
> can't avoid this, however, since we're writing a library and not a 
> language.

To be clear, I am no longer insisting that a monitor or mutex be a
condition variable, as I agree with your complaint that this makes the
mutex class unnecessarily "heavy".  I am insisting that each condition
variable be associated with a mutex.

> >  I agree that always tying the
> > signal to monitor exit is limiting.  My point is that it is a common and
> > useful pattern that can be supported safely at compile-time.  It is still
> > an open question whether all necessary patterns can be so supported.
> 
> Well, your original posting of this was as a solution to insuring the 
> mutex was locked by removing the ability to call notify() 
> explicitly.  Since I was wrong about the need to insure the mutex was 
> locked I don't want to harp on this, but that's where my original 
> confusion on your code came in.  The confusion is doubled by your now 
> saying we'll need a wait(monitor,entry_lambda,condition).

This form of wait() constructor is for a design with a single condition
variable.  The same effect could be had by using the two condition form
with entry_condition==exit_condition.

> In any event, yes, it's a useful pattern.  But I'm not sure that it's 
> useful to encapsulate the pattern as you've done.  No safety is loss 
> by explicitly coding this pattern, while the readability and 
> expressiveness may be greatly enhanced by doing so.

I think some safety is lost, as failing to signal conditions is an easy
way to lock up your threads.  Readability is more subjective, but I am
not all that happy with the readability of any application of lambda
expressions that I have seen so far.  It's a difficult tradeoff.