Re: [boost] win32 mutex and condition variable algorithms

From: Anthony Williams (anthony_w.geo_at_[hidden])
Date: 2006-09-19 12:08:53

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

> Anthony Williams wrote:
>
>> The mutex is simple, and you can see the code in
>> boost/thread/win32/basic_mutex.hpp on the thread_rewrite branch.
>>
>> The algorithm is:
>>
>> init():
>>   active_count=0;
>>   no semaphore
>>
>> lock():
>>   atomic increment active_count
>>   if new active_count ==1, that's us, so we've got the lock
>>   else
>>        get semaphore, and wait
>>        now we've got the lock
>>
>> unlock():
>>   atomic decrement active_count
>>   if new active_count >0, then other threads are waiting,
>>       so release semaphore.
>
> 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.

I'm not sure how it could be faster. If a thread takes the slow path that's
because another thread already has the lock. It's possible that that other
thread is just about to release it, but we can't know that.

> Unfortunately, I can no longer find his post where he explained that with 
> Google. 

If there's a faster algorithm, I'd certainly like to see it, so it would be
good if you could find the link.

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