"Peter Dimov" <pdimov@mmltd.net> 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