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

From: Anthony Williams (anthony_w.geo_at_[hidden])
Date: 2006-12-11 09:56:32

"Peter Dimov" <pdimov_at_[hidden]> writes:

> Anthony Williams wrote:
>
>> 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.
>
> You seem to be implying that ReleaseSemaphore with a count > 1 is not an 
> atomic operation but behaves as a series of ReleaseSemaphore with count == 1 
> calls? Is that correct? Or did I misunderstand something? I'd expect it to 
> atomically wake count threads and decrement the semaphore counter with 
> count. 

If there are N threads waiting on the semaphore, and you do ReleaseSemaphore
with a count >= N, I don't believe that the win32 api guarantees that the
waiting threads will necessarily be moved to "ready" state atomically as part
of the ReleaseSemaphore call.

In particular, even though the user-level code is blocked within
WaitForSingleObject (or similar) in the waiting threads, there might be a
kernel-level APC which takes that thread out of the wait state, does
something, and then returns it to the wait state. If the call to
ReleaseSemaphore occurs concurrently with the processing of the APC, then the
thread will not see the notify until it returns, and the notify may be taken
by another thread that calls WaitForSingleObject on the Semaphore whilst the
first thread is processing the kernel APC.

I believe the following is a valid scenario:

Thread A:

WaitForSingleObject(hSemaphore) // blocks

Thread B:

ReleaseSemaphore(hSemaphore,1)

Thread C:

WaitForSingleObject(hSemaphore) // returns immediately

Thread A still blocked

I can't remember where I got this impression, and I may be wrong.

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