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

From: Anthony Williams (anthony_w.geo_at_[hidden])
Date: 2006-10-26 13:06:21

"Peter Dimov" <pdimov_at_[hidden]> writes:

> Howard Hinnant wrote:
>
>> 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
>
> There are two interesting decisions in a read/write mutex. The first is what 
> happens when a writer is blocked in wrlock() waiting for readers and another 
> reader tries to rdlock(). POSIX leaves this implementation defined in the 
> general case; however, if priority scheduling is supported, the reader 
> "shall" obtain a lock if and only if it's of a higher priority compared to 
> the waiting writer (or all writers, if there's more than one).
>
> If we assume equal priority for simplicity, this means that rdlock "shall" 
> block. This is detectable by a conformance test, by the way, since tryrdlock 
> fails if and only if rdlock blocks.

Agreed.

> This is the "gate 1" part, and all of the algorithms I've been experimenting 
> with also have this property. If the 'writer pending' bit is set, no readers 
> are allowed to obtain a lock. However if another, higher-priority writer 
> arrives after the pending bit is already set, I still grant write access to 
> the first writer, which is probably a violation of POSIX [TPS]. :-)

I'm experimenting with having the pending readers and pending writers blocking
on the same sync object; then the OS gets to choose which to wake, and it can
order by priority. Readers still block if there's pending writers, regardless
of priority, though.

> The other interesting decision is what happens on unlock (two subparts, last 
> reader unlocks, or writer unlocks.) Your implementation seems to use the 
> "thundering herd" approach of waking all. This is fair, but may be wasteful 
> if you wake up several writers, or a writer and several readers and the 
> writer manages to pass through gate 1 (everyone else must block again). 

> Another approach is to wake up one writer in rdunlock and all readers in 
> wrunlock (alternating between readers and writers). I also have a third 
> option in mind that I haven't tested yet.

I'm experimenting with ways of waking only one writer, but potentially all
readers.

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