Re: Threads

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.  :(