Re: Threads

From: William Kempf (sirwillard_at_[hidden])
Date: 2000-08-24 08:48:13

--- In boost_at_[hidden], "Greg Colvin" <greg_at_c...> wrote:
> From: William Kempf <sirwillard_at_m...>
> > --- In boost_at_[hidden], "William Kempf" <sirwillard_at_m...> wrote:
> > > --- In boost_at_[hidden], Jens Maurer <Jens.Maurer_at_g...> wrote:

There's several posts in my queue here, and I've not read any yet.  
So, hopefully I won't repeat anything anyone else has said.

> I think you should wait on "not_empty" rather than "full", but that
> is just a nit with your names.

I'd agree.  I took the names from example code somewhere else and 
just didn't bother to change them.
 
> > This is a *lot* less complex than the equivalent to a pthread 
> > condition which must allow a notify_all().  However, notify_one() 
> > isn't as safe or flexible as notify_all().  With notify_one() you 
> > must always use one predicate for one condition.
> 
> Yes, though I think you can fake notify_all by having your own list
> of threads and notifying each one.

Faking it is of no concern to me.  If notify_all() is more flexible 
and safer than notify_one() than it should be a part of the model 
we're designing, regardless of how it has to be implemented.
 
> > The point of all of this?  I'm not sure that we should exactly 
> > conform to the classic monitor.  I think that notify_all() is 
safer 
> > and more expressive than notify_one().
> 
> Isn't there a "thundering herd" performance hit for notify_all
> that notify_one avoids?

Possibly.  For a lot of constructs the thundering herd will actually 
produce the desired effect, or may simply be more efficient.  In 
other cases the performance hit will be negligible simply because of 
the number of threads waiting.  There are cases in which the 
thundering herd will reduce performance, and possibly to a point 
that's simply unacceptable (especially in real time systems).  For 
this reason I'm not really in favor of removal of notify_one().  
However, I do think we should discourage it's use in general because 
of the potential for deadlock present because of the strict rule 
of "one predicate to one condition".

That aside, the point is really that notify_all() should be included 
regardless of whether or not notify_one() is present or even 
encouraged.  So we're making a change to the classic model here, 
which seems reasonable.  If that's reasonable, then so might the 
change to allow for notify() outside of the monitor lock be 
reasonable.

> >  By the same reasoning, it 
> > *might* be safer and more efficient to allow notifications 
outside of 
> > the mutex lock (this assumes there isn't truly a race condition 
by 
> > doing so).
> 
> I'm not sure what efficiency is gained by allowing notify outside
> the lock, but I am fairly sure there is a danger of a race.  
Consider
> what might happen if you unlocked the mutex just before your signal
> calls above.  How to know that the condition being signaled is still
> true when the wait ends?

Efficiency is gained because the lock doesn't have to be acquired.  
Acquiring a synch lock can be an expensive operation.

That particular race condition is resolved by the fact that we're in 
a while() loop instead of an if() statement.  This is an idiom that 
I'm not sure we can (or at least want to) eliminate even if we 
eliminate the race condition.  If notify_all() is included the while 
is required because some other thread may have changed the predicate 
condition by the time we've acquired the mutex lock again.  Even with 
out notify_all() the pthread implementation must allow for "spurious 
wakeups" in order to allow for signal handlers (at least that's my 
understanding of why spurious wakeups are allowed).  This means that 
a thread blocked on a wait() may be awakened even with out the 
condition having been signaled.  There are ways that we could work 
around this, so we aren't stuck with the same requirements as 
pthreads, but in this case I see little harm in doing so and it would 
make implementations much easier to code.
 
> By the way, I am currently looking at an interesting alternative
> to the "monitor" approach being worked on for Java
>    http://www.cs.ukc.ac.uk/projects/ofa/jcsp/ 
> This amounts to a Java library modelled on the Occam programming
> language, which itself is modeled on Hoare's Communicating
> Sequential Processes.

Thanks for the reference.  I'll have to take a closer look at it.

Bill Kempf