Boost logo

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.

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).


Boost list run by bdawes at, gregod at, cpdaniel at, john at