Re: Threads

From: William Kempf (sirwillard_at_[hidden])
Date: 2000-08-25 08:51:25

--- In boost_at_[hidden], "Greg Colvin" <greg_at_c...> wrote:
> From: William Kempf <sirwillard_at_m...>
> > --- In boost_at_[hidden], "Greg Colvin" <greg_at_c...> wrote:
> > > From: William Kempf <sirwillard_at_m...>
> > > > --- In boost_at_[hidden], "Greg Colvin" <greg_at_c...> wrote:
> > > > > From: William Kempf <sirwillard_at_m...>
> > > > In corner cases this may not be true.  For instance, trying 
to 
> > > > implement a Win32 Event using a monitor the implementation of 
Signal()
> > > > could be greatly optimized by using InterlockedIncrement to 
change 
> > > > the "boolean" flag to true and calling the CVs notify_all() 
outside 
> > > > of a monitor lock.  This is just the simplest example I can 
think 
> > > > of... there may be more corner cases.  Not a great reason to 
require 
> > > > this, I know.  But the fact that it's going to be problematic 
to do 
> > > > any more than call it "undefined behavior" to call notify() 
outside 
> > > > of a monitor lock is impetus enough for me to at least 
attempt to 
> > > > define it as safe.
> > > 
> > > This is another reason I like my idea of wrapping up the lock,
> > > wait, and notify in a single constructor.  It means that the
> > > user can't get into undefined behavior, and the implementer
> > > has maximum freedom to optimize.
> > 
> > However, this puts restrictions on the user.  This results in the 
> > optimal code above not being an option.
> 
> I think it is indeed an option: in the constructor you aquire the
> lock and wait, in the destructor you release the lock and notify.
> The choice of primitives and order of operations is up to you.  So
> if you want to use an interlocked increment outside the mutex you
> can, with confidence that the user won't slip another mutex in
> between.

The key to what you said here was "outside of the mutex".  In other 
words, a mutex is still locked here, which eliminates the 
optimization of having used InterlockedIncrement.  If the mutex must 
be locked it would be more efficient to simply use operator++ within 
the mutex lock.

>  Also up to you is whether to use a while..wait in the
> constructor and notify_all in the destructor, or to use an if..wait
> in the constructor and a notify_one in the destructor.

Of course the if..wait is dependent on our removing spurious wake ups.

> >  It also means that there's 
> > only two places within the monitor that you can wait, the 
beginning 
> > and the end.  I can see design patterns where you'd wait in the 
> > middle.
> > 
> > If there's truly a danger for undefined behavior I might be 
persuaded 
> > to agree to a wait_and_lock object though it still bothers me 
that a 
> > notify will be part of this scheme.  It doesn't seem natural or 
> > expressive enough.
> 
> I'll do some more research, but in the examples I have seen the wait
> is always at the beginning and the notify is always at the end.
> Anyway, this object needn't be the *only* way to wait and notify.

Most examples are short and designed to illustrate the concept, so 
this is likely true.  However, it shouldn't be too hard to think 
about a case where some object state must be queried, and maybe even 
modified, before waiting on a condition.

If the mutex is recursive it would be easy to insure this by breaking 
out the code into two methods.  Just a thought.

> I'm reviewing our (well documented!) graph library, and wondering
> more and more if we can't make some use of it here.  It seems that
> a well designed monitor amounts to a cyclic graph with conditions at
> the nodes and the code that waits on one condition and notifies
> others as the edges.  It seems further that being deadlock-free is a
> deducible property of the graph.

I'll have to check the library out.  Graph theory isn't something I'm 
overly familiar with, and I'd bet a lot of other people aren't 
either.  I'm a little concerned that this will add complexity to an 
already overly complex topic.

Bill Kempf