From: William Kempf (sirwillard_at_[hidden])
Date: 2000-08-22 09:40:30
--- 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:
> > ...
> > 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.
The "sequence of transitions" is the key part. You can't guess how
many transitions will be required. Nor can you guess what
conditional logic will need to be used to select which transition to
follow. I can see a higher level design that might allow you to
define these transitions, but I have two things to say about this:
your current working example simply won't scale, and personally I
doubt that such a high level design will be any easier to code than
the explicit transitioning approach used in the classic paper.
> > 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.
It's not possible to eliminate all abuse. If that's your goal then
you'll never get there. Now I agree that we need to make mistakes as
difficult as possible, but I've not yet seen you define where the
pitfalls and traps exist. With out that starting point you can't
hope to make things more difficult to make mistakes.
Right now, to my mind we have 4 pitfalls. A programmer may forget to
lock the mutex on entry to a method; a programmer may forget to
signal other threads; a notify_one() can result in deadlock if
certain strict rules aren't followed (1); monitors in the classic
design won't prevent race conditions in "transactional calls" to an
object.
I'm not sure that there's much we can do to insure a method is
locked. The proxy pattern/smart pointer approach can help here, but
it's not something that can be enforced by the library.
Forgetting to signal other threads is, IMHO, a severe logic mistake
that simply shouldn't occur. I'm not sure that the library
implementation can truly fix this issue either. Your design pattern
will work, but it very much appears to me that it's just that, a
pattern. Not all patterns can be encapsulated in reusable
components, and this particular one sounds to me like it shouldn't be.
I've already suggested that we remove notify_one() to Jeremy. This
would eliminate this potential misuse, though it might result in less
optimal code for some constructs.
The final problem is the most important and most difficult one to
address, IMHO. It's going to require some innovation, and call me a
pessimist but I simply don't think Boost will be the source of this
innovation. Too many people have been trying to figure out how to
solve this one for too long. With out language support, I don't
think it will be possible.
> 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.
This is a very old technique. It can be a useful one, but it doesn't
solve all of the problems (mot notably it won't solve the problem of
multiple calls on an object needing to occur synchronously).
Further, it requires some discipline from the programmer.
> > 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.
It's more than a scheduling issue. For instance, the pthread
conditions explicitly allow a library to issue "spurious wakeups".
This means that a thread may return from a wait() even with out the
condition being signaled, which means the predicate may still be
false. I'm not sure we can, or should, insure that our own
conditions can't have spurious wake ups.
> 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.
In other words, you're attempting to use a "wait" as the initial lock
on the monitor. This may be an interesting idea to think on, but
it's not the classic design of a monitor. In the classic design, a
wait is used to relinquish the monitor to other threads until some
condition occurs, at which time we'll re-aquire the monitor's lock.
> > 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.
I didn't mean to imply that you weren't. However, you didn't answer
any of the questions raised.
> > > 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.
Again, it's an interesting idea but I'm not at all sure that it's
appropriate.
> I think that encapsulating the necessary notification patterns is a
> net win, but I'm not hard over on it.
I'd agree, except that I simply don't think this is a pattern that
can be encapsulated in a generic re-usable way.
> 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.
You'll have to explain, in detail, what you mean by that.
> > > 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.
No. If entry_condition were ever equal to exit_condition in your
pattern you'd have a busy wait. A busy wait is something that
absolutely must be avoided in code. A busy wait can cause a single
thread to hog nearly 100% of the CPU resulting in very poor
performance of every thread/process running. The whole point of
thread primitives such as the CV is to allow a thread to do a non-
busy wait. If a busy wait would work there'd be no need for a CV.
You could instead write code such as this:
void foo::bar()
{
for(;;)
{
mutex::lock lk(*this);
if (m_flag == true)
break;
}
}
> > 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.
It's no more difficult to fail to signal a condition with your
pattern, since you include a wait() with out an exit condition (which
you must do).
> 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.
For complex conditional signaling no form of lambda expression will
be as readable as explicitly coding it, IMHO.
Bill Kempf
(1) To use notify_one() the CV must be waited on using only one
predicate. The classic bounded buffer coded with a single CV would
be open to deadlock using notify_one() instead of notify_all() since
there are two predicates waited on; full and notfull. The classic
paper uses a notify_one() style and never addresses this issue, but
it also carefully uses mutliple CVs, one for each predicate.