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

From: Anthony Williams (anthony_w.geo_at_[hidden])
Date: 2006-12-11 04:06:06

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.

Anthony
-- 
Anthony Williams
Software Developer
Just Software Solutions Ltd
http://www.justsoftwaresolutions.co.uk