Boost logo

Boost :

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

    | ^
    | |
    V |

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.

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