Re: Threads

From: William Kempf (sirwillard_at_[hidden])
Date: 2000-08-21 17:47:21

--- In boost_at_[hidden], "Greg Colvin" <gcolvin_at_u...> wrote:
> From: William Kempf <sirwillard_at_m...>
> > > From: William Kempf <sirwillard_at_m...>>
> > >  --- 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:
> > > > > > > From: "William Kempf" <sirwillard_at_m...>
> > > > > > > > --- In boost_at_[hidden], "Greg Colvin" 
<gcolvin_at_u...> wrote:
> > > > > Makes perfect sense to me.  See the example code below.
> > > > > 
> > > > > > You've set it up so the only way to notify a condition is 
by first 
> > > > > > waiting on a second condition.  I don't see how this 
would even 
> > > > > > work.  Who would notify your "in" condition?  How would 
they insure 
> > > > > > at compile time that the mutex was locked?  I see nothing 
solved here 
> > > > > > and see little purpose in having an "out" condition.
> > > > > 
> > > > > Typically the conditions start out signaled, so the very
> > > > > first attempt to wait on them returns immediately.
> > 
> > CVs aren't like Win32 events.  They don't "remain signaled".  I 
> > realize that our own CVs could behave differently, allowing this 
to 
> > work the way you describe, but see my point below.
> 
> I didn't say they would "remain signaled", just that they would 
start
> out signaled so that when you have a set of blocks in a monitor, 
each
> waiting on a condition, there is some way for one of the blocks to
> start running and signal the others.

Starting out signaled requires the CV to remain signaled, at least 
for this one case.

> > I should also note that your proposal assumes some relationship 
> > between the two CVs.  Often there will be no relationship at 
all.  It 
> > seems like you've simply attempted to find a resolution for a 
single 
> > problem instead of thinking about general useage patterns.
> 
> 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.

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

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)?
 
> > So you're proposing seperate 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.
 
> > > 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.

>  Where this might break down is
> a problem that requires conditional signalling.  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?
 
>    wait(monitor,entry_lambda,condition)
> 
>    wait(monitor,entry_lambda,entry_condition,exit_condtion)
> 
>    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 signalling 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.
 
> > > > 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.

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

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.