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