Condition variables: signal with or without mutex locked?

Hi,

to signal with mutex locked or not, that is the (recurring)
question,.. So I wrote an article about it:
http://www.domaigne.com/blog/computing/condvars-signal-with-mutex-locked-or-not/

Hope this will help some of you.

Cheers,
Loïc
--
My Blog: http://www.domaigne.com/blog
“Computers are useless. They can only give you answers.” -- Pablo
Picasso

On Apr 12, 1:07 pm, Loïc Domaigné <loic.domai...@...com>
wrote:

>to signal with mutex locked or not, that is the (recurring)
>question,.. So I wrote an article about it:

Looks good, but you missed the other case where you cannot signal
after releasing the mutex. If it is imperative that the signal not be
consumed by a thread that chose to block on the condition variable
after you unlocked.

Consider:
pthread_mutex_lock();
if(predicate==4)
{
predicate=5;
pthread_cond_signal();
}
pthread_mutex_unlock();

If there is only one thread blocked on the condition variable and it
chose to block when the predicate was 4, this code is guaranteed to
wake that thread.

However:
bool signal=false;
pthread_mutex_lock();
if(predicate==4)
{
predicate=5;
signal=true;
}
pthread_mutex_unlock();
if(signal) pthread_cond_signal();

This code could wake this thread:
while(predicate==5) pthread_cond_signal();
Leaving the: while(predicate==4) pthread_cond_signal() thread stuck
with a missed wakeup.

The problem is the race condition. An unlock-then-signal can wake a
thread that chose to sleep *after* the unlock.

There are some rules of thumb to avoid this:

1) A pthread_cond_broadcast can always be moved after the unlock.

2) If the condition variable only signals a single predicate value,
the signal can always be moved after the unlock.

3) If any thread blocked on the condition variable can handle the
predicate change, the signal can always be moved after the unlock.

Otherwise, this move can wake the "wrong thread" and cause failures in
code that was previously guaranteed to work.

DS

On Apr 13, 3:36 am, David Schwartz <dav...@...com> wrote:
>On Apr 12, 1:07 pm, Loïc Domaigné <loic.domai...@...com>
>wrote:
>
>>to signal with mutex locked or not, that is the (recurring)
>>question,.. So I wrote an article about it:
>
>Looks good, but you missed the other case where you cannot signal
>after releasing the mutex. If it is imperative that the signal not be
>consumed by a thread that chose to block on the condition variable
>after you unlocked.
>
>Consider:
>pthread_mutex_lock();
>if(predicate==4)
>{
> predicate=5;
> pthread_cond_signal();}
>
>pthread_mutex_unlock();
>
>If there is only one thread blocked on the condition variable and it
>chose to block when the predicate was 4, this code is guaranteed to
>wake that thread.
>
>However:
>bool signal=false;
>pthread_mutex_lock();
>if(predicate==4)
>{
> predicate=5;
> signal=true;}
>
>pthread_mutex_unlock();
>if(signal) pthread_cond_signal();
>
>This code could wake this thread:
>while(predicate==5) pthread_cond_signal();
>Leaving the: while(predicate==4) pthread_cond_signal() thread stuck
>with a missed wakeup.
>
>The problem is the race condition. An unlock-then-signal can wake a
>thread that chose to sleep *after* the unlock.

Hi David,

May you please provide a more complete example of what can break. I am
not sure what "while(predicate==5) pthread_cond_signal();" does mean,
it looks a bit strange...
If you meant:
while (predicate != 5) pthread_cond_wait();
then how this thread can ever get to pthread_cond_wait() provided that
it lock the mutex after the other thread set predicate to 5...

--
Dmitriy V'jukov

On Apr 13, 12:46 am, Dmitriy Vyukov <dvyu...@...com> wrote:

>May you please provide a more complete example of what can break. I am
>not sure what "while(predicate==5) pthread_cond_signal();" does mean,
>it looks a bit strange...
>If you meant:
>while (predicate != 5) pthread_cond_wait();
>then how this thread can ever get to pthread_cond_wait() provided that
>it lock the mutex after the other thread set predicate to 5...

Okay, let me try it again:

Thread A:
while(predicate==0) pthread_cond_wait();

Thread B:
while(predicate==1) pthread_cond_wait();

Thread C:
if(predicate==0)
{
predicate=1;
// pthread_mutex_unlock();
pthread_cond_signal();
}

Now, since we found the predicate to be zero, set it to one, and then
signaled, we are guaranteed to unblock thread A if it was blocked. The
only other thread that could consume the signal is thread B, and it
only blocks when the predicate is 1. The predicate was not one when we
signaled.

But now uncomment the unlock. Now, thread B could sneak in after the
unlock and before the signal. Both threads A and B could be blocked on
the condition variable. If our wakeup is consumed by thread B, thread
A will miss a wakeup.

DS

David Schwartz <davids@...com> wrote in news:b8f8d728-d8cb-4160-
8685-877320108c6a@...com:

>
>But now uncomment the unlock. Now, thread B could sneak in after the
>unlock and before the signal. Both threads A and B could be blocked on
>the condition variable. If our wakeup is consumed by thread B, thread
>A will miss a wakeup.
>


Can't you use broadcast to avoid this?

It was my understanding that if you weren't
checking precisely the same predicate in each
waiter, you need to use broadcast to avoid
this exact problem.

On Apr 14, 7:01 pm, "Eric J. Holtman" <e...@...com> wrote:
>>But now uncomment the unlock. Now, thread B could sneak in after the
>>unlock and before the signal. Both threads A and B could be blocked on
>>the condition variable. If our wakeup is consumed by thread B, thread
>>A will miss a wakeup.
>
>Can't you use broadcast to avoid this?
>
>It was my understanding that if you weren't
>checking precisely the same predicate in each
>waiter, you need to use broadcast to avoid
>this exact problem.

As far as I see, code that signals before unlock works perfectly with
signal().

--
Dmitriy V'jukov

On Apr 14, 8:01 am, "Eric J. Holtman" <e...@...com> wrote:

>Can't you use broadcast to avoid this?

Yes. But you can also signal while holding the mutex.

>It was my understanding that if you weren't
>checking precisely the same predicate in each
>waiter, you need to use broadcast to avoid
>this exact problem.

You have to solve it somehow. Some solutions are 100% guaranteed safe
so long as you signal while holding the mutex. In such a solution,
moving the pthread_cond_signal to after the pthread_mutex_unlock can
cause code that was previously safe to experience missed wakeups.

DS

On Apr 13, 9:29 pm, David Schwartz <dav...@...com> wrote:
>On Apr 13, 12:46 am, Dmitriy Vyukov <dvyu...@...com> wrote:
>
>>May you please provide a more complete example of what can break. I am
>>not sure what "while(predicate==5) pthread_cond_signal();" does mean,
>>it looks a bit strange...
>>If you meant:
>>while (predicate != 5) pthread_cond_wait();
>>then how this thread can ever get to pthread_cond_wait() provided that
>>it lock the mutex after the other thread set predicate to 5...
>
>Okay, let me try it again:
>
>Thread A:
>while(predicate==0) pthread_cond_wait();
>
>Thread B:
>while(predicate==1) pthread_cond_wait();
>
>Thread C:
>if(predicate==0)
>{
> predicate=1;
>// pthread_mutex_unlock();
> pthread_cond_signal();
>
>}
>
>Now, since we found the predicate to be zero, set it to one, and then
>signaled, we are guaranteed to unblock thread A if it was blocked. The
>only other thread that could consume the signal is thread B, and it
>only blocks when the predicate is 1. The predicate was not one when we
>signaled.
>
>But now uncomment the unlock. Now, thread B could sneak in after the
>unlock and before the signal. Both threads A and B could be blocked on
>the condition variable. If our wakeup is consumed by thread B, thread
>A will miss a wakeup.

Ok, now I see. Thank you!
I guess it's quite specific pattern. And according to your rules of
thumb we can fix it by replacing signal() with broadcast().

--
Dmitriy V'jukov

Hi David,

My apologize for the slow follow-up.

>>to signal withmutexlockedor not, that is the (recurring)
>>question,.. So I wrote an article about it:
>
>Looks good, but you missed the other case where you cannot signal
>after releasing themutex. If it is imperative that the signal not be
>consumed by a thread that chose to block on theconditionvariable
>after you unlocked.

Good point. Thanks David for the detailed reply, I have posted your
answer as a comment to my article.

Cheers,
Loïc.
--
My Blog: http://www.domaigne.com/blog

“Should array indices start at 0 or 1? My compromise of 0.5 was
rejected without, I thought, proper consideration.” -- Stan Kelly-
Bootle