Boost logo

Boost :

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...>
> > > > > > > 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
> > work the way you describe, but see my point below.
> I didn't say they would "remain signaled", just that they would
> out signaled so that when you have a set of blocks in a monitor,
> 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
> > 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
> 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
> 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

> 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
> > > at the end of each handler. How else to make any progress?
> >
> > This isn't necessarily true. However, the biggest problem is
> > you're addressing the "bounded buffer/producer consumer" problem
> > specifically, with out thinking about how the CV can be used
> > of this single problem domain.
> I'd like to see examples of problems that can't be solved with
> 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

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

Boost list run by bdawes at, gregod at, cpdaniel at, john at