Re: [boost] win32 mutex and condition variable algorithms

From: Anthony Williams (anthony_w.geo_at_[hidden])
Date: 2006-09-20 03:29:13

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

> Anthony Williams wrote:
>> "Peter Dimov" <pdimov_at_[hidden]> writes:
>>
>>> Peter Dimov wrote:
>>>
>>>> This is what CRITICAL_SECTIONs do, and I recall being told by
>>>> Alexander Terekhov that it is suboptimal (threads take the slow path
>>>> when they could take the fast path). My tests with a contended queue
>>>> seemed to prove him right.
>>>>
>>>> Unfortunately, I can no longer find his post where he explained that
>>>> with Google.
>>>
>>> Here it is:
>>>
>>> http://aspn.activestate.com/ASPN/Mail/Message/boost/2122746
>>
>> Thanks. I'll have to look at Alexander's proposed swap-based
>> implementation.
>
> I've played with it a bit:
>
> http://www.pdimov.com/cpp/mutex.cpp
>
> but I suspect that there are a few errors in this old code... some of the 
> reads are not atomic but need to be. Maybe we can give it a review and bring 
> it up to Boost standards. 

The case given in Alexander's email above is:

    A: lock [lockcount == 0]
    B: lock [lockcount == 1, slow path]
    A: unlock [lockcount == 0, slow path/post sema]
    A: lock - [lockcount == 1, slow path]

He claims that the second A: lock takes the slow path, when it could have
taken the fast path because the lock is free. I disagree. The lock is NOT
free, since B is waiting on it. If A can take the fast path here, that's
opening the door for B to be starved. By A taking the slow path, both A and B
will wait on the semaphore, and the OS can pick which wakes up.

In your code, we have:
    A: lock [lock_==0, fast path, set lock_ to 1]
    B: lock [lock_==1, slow path]
    B: slow wait [lock_!=0, set lock_ to -1, wait on event]
    A: unlock [lock_<0, set lock_ to 0,post event]
    A: lock [lock_==0, fast path, set lock_ to 1]
    B: event posted, [lock_!=0, set lock_ to -1, wait on event]
    A: unlock [lock_<0, set lock_ to 0,post event]

If A does unlock/lock without any intervening code, those last three lines can
repeat forever:

    A: lock [lock_==0, fast path, set lock_ to 1]
    B: event posted, [lock_!=0, set lock_ to -1, wait on event]
    A: unlock [lock_<0, set lock_ to 0,post event]
    A: lock [lock_==0, fast path, set lock_ to 1]
    B: event posted, [lock_!=0, set lock_ to -1, wait on event]
    A: unlock [lock_<0, set lock_ to 0,post event]
    A: lock [lock_==0, fast path, set lock_ to 1]
    B: event posted, [lock_!=0, set lock_ to -1, wait on event]
    A: unlock [lock_<0, set lock_ to 0,post event]
    A: lock [lock_==0, fast path, set lock_ to 1]
    B: event posted, [lock_!=0, set lock_ to -1, wait on event]
    A: unlock [lock_<0, set lock_ to 0,post event]

>From the OS point-of-view, this is a producer-consumer scheme, with A being
the producer and B the consumer. B is regularly woken, and does processing
until it's next wait. Unfortunately, B never makes any progress.

If A always takes the slow path when we have another waiter, then we give the
OS more scope for ensuring that both A and B get a fair stab.

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