Re: [boost] [thread] condition::notify with unlocked mutex

From: Yuval Ronen (ronen_yuval_at_[hidden])
Date: 2006-12-11 07:01:09

Anthony Williams wrote:
> Yuval Ronen <ronen_yuval_at_[hidden]> writes:
> 
>> Anthony Williams wrote:
>>> Yuval Ronen <ronen_yuval_at_[hidden]> writes:
>>>
>>>> Roland Schwarz wrote:
>>>>> Yuval Ronen wrote:
>>>>>> I will gladly put my code here to be scrutinized by the experts on this forum (after the weekend, as the code is at work, and I'm
>>>>>> at home now :-) ), but I fear that they will little incentive to do it.
>>>>> Can't tell. Possibly yes. You will need to try.
>>>> Ok, if anyone is still interested, here's my implementation of CV for Windows. It's very simple, maybe too simple, and I guess it's
>>>> far less interesting than the code just posted by Chris Thomasson, but here it is anyway.
>>>>
>>>> 	void wait()
>>>> 	{
>>>> 		assert(m_mutex.isLocked());
>>>> 		m_waitersCount++; // line A
>>>> 		m_mutex.unlock(); 
>>>> 		m_sem.lock(); // line B
>>>> 		m_mutex.lock(); // line C
>>>> 	}
>>>>
>>>> 	void broadcast()
>>>> 	{
>>>> 		assert(m_mutex.isLocked());
>>>> 		if (m_waitersCount > 0)
>>>> 		{
>>>> 			m_sem.unlock(m_waitersCount); // line D
>>>> 			m_waitersCount = 0;
>>>> 		}
>>>> 	}
>>> Unfortunately, it is susceptible to the "stolen wakeup" problem. If
>>> m_waitersCount is non-zero, the semaphore is incremented on line D. This will
>>> wake the appropriate number of waiting threads, but not immediately. Threads
>>> waiting on a semaphore will not be woken until they are next scheduled. Thus,
>>> a new thread might call wait, increment the waitersCount (line A) and acquire
>>> the (line B) before all the threads currently waiting have been woken.
>> I have to admit that I didn't understand the problem. Your description 
>> sounds exactly like what should've happen. At the end, all threads that 
>> were waiting before the call to broadcast() are woken, and the new 
>> thread is waiting. Just as it should. What have I missed?
> 
> Thread A:
> 
> locks mutex
> Enters wait()
> Runs line A, waitersCount=1
> Unlocks mutex
> Runs line B, blocks.
> 
> Thread B:
> 
> locks mutex
> Enters wait()
> Runs line A, waitersCount=2
> unlocks mutex
> Runs line B, blocks.
> 
> Thread C:
> 
> locks mutex
> Enters broadcast()
> Runs line D: Unlock semaphore(2) // 2 threads waiting
> waitersCount=0
> unlocks mutex
> 
> Thread A:
> 
> wakes on line B, sem count is now 1
> locks mutex on line C
> unlocks mutex
> 
> Thread D:
> 
> locks mutex
> Enters wait()
> Runs line A, waitersCount=1
> unlocks mutex
> Runs line B, sem count is 1, so acquires it and sets to 0
> locks mutex on line C
> 
> Thread B:
> 
> remains blocked on line B
> 
> Thread D has stolen the wakeup intended for thread B, even though it entered
> "wait" after the broadcast.

Ah, I see. What you're saying, IIUC, is that calling Win32's 
ReleaseSemaphore to release a waiting thread, and then calling 
WaitForSingleObject, might block either of the threads, and we don't 
know which. I've looked at MSDN to see if this is true, but couldn't 
find any explicit reference to this situation. I guess that if you say 
it can happen, then you know what you're talking about.

The question is whether this is a bad thing. If the threads both wait on 
the same predicate (which from now on is a pre-condition of this CV 
implementation, and is not a huge disadvantage, IMO), then maybe it 
doesn't really matter.