Re: [boost] win32 mutex and condition variable algorithms

From: Anthony Williams (anthony_w.geo_at_[hidden])
Date: 2006-09-20 06:34:26

Alexander Terekhov <terekhov_at_[hidden]> writes:

> Anthony Williams wrote:
>> 
>> Alexander Terekhov <terekhov_at_[hidden]> writes:
>> 
>> > Anthony Williams wrote:
>> > [...]
>> >> 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.
>> >
>> > That depends on the definition of "fair". Suppose you're running on
>> > uniprocessor and that A is a higher priority thread than B... why
>> > should it yield to B? Under POSIX rules (which define priority
>> > scheduling for scheduling allocation domains of size 1, aka
>> > "uniprocessor" domains), it shall not. With your handoff logic, A
>> > will yield to B.
>> 
>> Not necessarily. Both A and B will wait for the semaphore. If A is higher
>
> Suppose that B is already waiting on the semaphore. If that is not the 
> case, you'll get the same "starvation" scenario as with more efficient 
> lock but with added overhead of self consuming semaphore signal. 
>
> [...]
>> What if B is higher priority than A?
>
> Then A will yield to B (waiting for the semaphore) on unlock/slow-path 
> (efficient lock) and B will grab the lock (freed by A prior to 
> signaling).

You are assuming that B will wake immediately upon A's release of the
semaphore, and that it can grab it before A does. In your "fast lock"
algorithm, if B doesn't wake immediately (or even if it does, but on another
CPU/core), and A continues to run, A may still grab the lock back again before
B can get it, even though B was already waiting, and B is higher priority. B
can wake up and run some user code, and still not actually get out of the lock
construct.

If A always waits on the semaphore when there is another thread already
waiting, then the OS will get to choose one (and only one) thread to wake, and
that thread will get the lock.

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