Boost logo

Boost :

From: Howard Hinnant (howard.hinnant_at_[hidden])
Date: 2007-08-22 14:50:55

On Aug 22, 2007, at 2:24 PM, Austin Bingham wrote:

> Overall I really like the work you've done here.
> I have a question about the scheduling of shared v. exclusive locks on
> shared_mutex. Suppose I have several shared locks already established
> and then an exclusive lock is tried. Are subsequent shared lock
> attempts
> deferred until after theexclusive lock has released? Or is the
> exclusive
> lock deferred until after all shared locks (regardless of when they
> were
> made) are released? Or is this even defined?
> It may be easiest to just leave the scheduling undefined, and perhaps
> that is the intent of the proposal. Whether it's defined or not,
> though,
> it should be documented.
> It might be useful, however, if the scheduling policy were
> configurable.
> It seems that such a policy could be established on the shared_mutex
> itself.

I have two answers:

1. This is somewhat of a shocking answer, so please read through the
second answer before passing judgement: The proposal purposefully
does not mention shared vs exclusive priority. And I would prefer not

2. The implementation uses an algorithm which I attribute to
Alexander Terekhov. This is a completely fair algorithm, letting the
OS scheduler decide which thread is next in line, regardless of
whether that thread is seeking shared or exclusive locking. I've beat
on this algorithm for years now, stress testing and watching for
starvation. I've never seen it starve a reader or a writer.
Alexander, if you're listening: REALLY NICE JOB!!! :-)

Imho, Alexander's algorithm makes the issue of reader/writer priority
moot. If Alexander's algorithm is the automobile, reader/writer
policies are the buggy whip. They just aren't needed anymore. I just
can't say enough good things about this work.

In a nutshell it is a two-gate system. Both readers and writers all
wait at the first gate for entry. If no one is yet beyond the first
gate, the OS gets to decide who to let in. When a reader gets past
the first gate, it has the read lock. When a writer gets past the
first gate, it does not yet have the write lock. It must now wait at
the second gate until all readers beyond the first gate give up their
read lock. While a writer is past the first gate, no one else is
allowed to pass through the first gate.

The algorithm is implemented here for shared_mutex, and modified
appropriately for upgrade_mutex:

> Again, this is really excellent and I'm genuinely excited to see
> this progress. Thanks for all the hard work!

Thanks Austin.


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