Re: [boost] A fast-pathed rw-mutex algorithm for Boost...

From: Howard Hinnant (hinnant_at_[hidden])
Date: 2006-10-26 11:54:38

On Oct 26, 2006, at 6:04 AM, Anthony Williams wrote:

> "Cory Nelson" <phrosty_at_[hidden]> writes:
>
>> Is there a reason for wanting a priority?  Why not make the lock  
>> fair.
>>  I'd rather have locks take out a ticket so everything is  
>> processed in
>> a FIFO order, with no starvation.
>
> I think it would be better with no priority, too. I'm working on an  
> algorithm
> for that.
>
> FIFO means that the OS has no say in the wakeup order; it'd be  
> better if all
> the waiting threads could block on the same OS sync object, so the  
> OS gets to
> choose which to wake.

Here is my implementation of Terekhov's *fair* read/write algorithm,  
with upgradable thrown in.  This algorithm is just as you say:  The  
OS alone decides who gets to run next.

http://home.twcny.rr.com/hinnant/cpp_extensions/upgrade_mutex.html

If you don't like the "upgradable" part, it strips out cleanly from  
the code.  Just delete everything that refers to "upgradable" and  
you've got a read/write mutex using Terekhov's algorithm (and rename  
the mutex).

Algorithm in a nutshell:

There are two gates.  Everyone (readers and writers) wait at gate 1  
for entry.  When a reader gets into gate 1, he has read ownership.   
When a writer gets into gate 1, he waits at gate 2 before getting  
write ownership.  While a writer is inside of gate 1, no readers or  
writers are allowed to pass gate 1.

The above algorithm is shown implemented with just mutex and  
condition variables.  The same algorithm is of course implementable  
using atomics for the "quick path" and I've done that on PPC (but I  
don't own that code).

-Howard