Re: [boost] [thread] RFC standard proposed mutex, read-write mutex, condition

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

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:

http://home.twcny.rr.com/hinnant/cpp_extensions/shared_mutex.cpp

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

Thanks Austin.

-Howard