From: William Kempf (sirwillard_at_[hidden])
Date: 2000-08-21 09:37:16
--- In boost_at_[hidden], jsiek_at_l... wrote:
>
> Looks like we'll need to do some more research to figure out:
>
> 1. Can CV's be implemented portably without the lock during notify()
> restriction? (yes for pthreads, maybe for Win32?)
> 2. Are there any performance trade-offs?
> (no lock is better with pthreads, Win32?)
> 3. Should the boost CV interface require lock during notify()?
I opened up this can of worms :(. Let me tell you where I stand on
this.
I "borrowed" the implementation of CVs from ACE, since it's one of
the few implementations that pays attention to fairness and
correctness. (The code is sufficiently changed that I don't think
there's been any copyright violations, but since this was test code I
wasn't overly concerned on this front.) After Jeremy and I got to a
point where we felt the models where sufficient (I hope I'm not
putting words into Jeremy's mouth here) I started to look for holes
in my implementation. I found a race condition in notify(). At
first I suspected I'd done something wrong in my translation from the
ACE implementation and so I looked there, and found the same race
condition. Douglas Schmidt is a leading authority on this particular
topic, and ACE has been in production for some time, so I doubted
that I'd found a race condition bug. Thinking on the problem I
realized that there'd be no race condition if notify() were called
while within the protection of the outer mutex lock. So, being
curious I checked the one and only book on pthreads that I have. I
posted the quote previously that led me to believe pthreads had such
a restriction on useage. So, I jumped to a (wrong) conclusion.
If the pthread standard says what Jeremy quoted then either I'm miss
reading my book or it is flatly wrong. In any event, in light of
this I looked closer at the implementation to see if we could
eliminate the race condition. With careful use of the internal mutex
and use of InterlockedIncrement and InterlockedDecrement instead in
two key places I've eliminated the race condition. So, I think I'm
satisfied that I've brought up a non-issue. I'm still quite
surprised that I've found what appears to be a bug in ACE and have a
query out to Douglas Schmidt on this topic. (Maybe there's some
subtle issue I'm missing that prevents the race condition from
occuring? I don't think so, but it is quite surprising that I
stumbled across this.)
I guess performance wise there's a very slight performance boost from
not holding the external mutex during the call to notify() now. I'm
not sure this needs to be documented, however, as it seems like an
over optimization technique to me.
I guess I'm also in favor of not requiring the lock during notify()
now. I appologize for the lengthy debate that occured over a non-
issue because of my mistake.
> William Kempf writes:
> > I'm not an expert on pthreads. Everything that I do know comes
from
> > Pthreads Programming, O'Reilly & Associates, Inc. (a Nutshell
book).
> > To quote them, from page 82:
> >
> > "It all sounds complicated, but what if the mutex and the
condition
> > variable weren't linked? If the condition were signaled without
a
> > mutex, the signaling thread might signal the condition before
the
> > waiting thread begins waiting for it -- in which case the
waiting
> > thread would never wake up."
> >
> > > Perhaps the problem came from how you were implementing CVs
> > > on Win32?
> >
> > The implementation I have is based on the implementation
designed by
> > Douglas Schmidt (sp?) for the ACE framework. He's one of the
leading
> > authorities on this subject. There is a definate race condition
in
> > this implementation if the external mutex isn't locked during
the
> > call to notify().
> >
> > Sounds like this is a non-issue for pthreads, at least according
to
> > the quote you gave from the standard. I must admit to be
confused on
> > this subject now, though. :(