Re: Threads

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.