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

From: Peter Dimov (pdimov_at_[hidden])
Date: 2006-10-26 12:39:55

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.

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

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). 
(This redundant wakeup may not be visible in a benchmark, but it can steal 
CPU from other busy non-contending threads in a real application.)

(I see a significant amount of CAS failures even when waking up only 
readers; again, this doesn't affect the timing of the specific benchmark, 
and I'm not sure that it's actually a problem.)

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.