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.