Re: [boost] win32 mutex and condition variable algorithms (was:[threads] Permission given to change to Boost.License)

From: Martin Bonner (martin.bonner_at_[hidden])
Date: 2006-09-19 11:33:43

----Original Message----
From: boost-bounces_at_[hidden]
[mailto:boost-bounces_at_[hidden]] On Behalf Of Anthony Williams
Sent: 19 September 2006 15:39 To: boost_at_[hidden]
Subject: [boost] win32 mutex and condition variable algorithms
(was:[threads] Permission given to change to Boost.License) 

> "Peter Dimov" <pdimov_at_[hidden]> writes:
> 
>> Inventing mutex and condition variable algorithms is a slight cause
>> of concern, I have to admit. The easiest way to get a free review of
>> the algorithms is to post the code on comp.programming.threads and
>> hope that someone of the experts there has enough time to look at
>> them. CVs in particular have proven to be quite hard to implement
>> correctly, and Alexander Terekhov's "8a" algorithm has emerged as a
>> de-facto standard. 
> 
> The mutex is simple, and you can see the code in
> boost/thread/win32/basic_mutex.hpp on the thread_rewrite branch.
> 

I'm missing something here (I hope).

> The algorithm is:
> 
> init():
>    active_count=0;
>    no semaphore
> 
> lock():
>    atomic increment active_count

At this point, thread2 atomically increments active_count as well, so it
is now 2.

>    if new active_count ==1, that's us, so we've got the lock
>    else
>         get semaphore, and wait
Both threads will go into this branch.  Why don't they wait forever?
>         now we've got the lock
> 
> unlock():
>    atomic decrement active_count
>    if new active_count >0, then other threads are waiting,
>        so release semaphore.

Alternatively,

        Thread A		Thread B

        locks mutex

                                atomic increment active_count (in lock)

        atomic decrements active_count (in unlock)
        new active_count > 0, so other threads are waiting
        release semaphore
        ... oops.  What semaphore?

Please tell me I have missed something!
-- 
Martin Bonner
Martin.Bonner_at_[hidden]
Pi Technology, Milton Hall, Ely Road, Milton, Cambridge, CB4 6WZ,
ENGLAND Tel: [phone]