Boost logo

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

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


Anthony Williams
Software Developer
Just Software Solutions Ltd

Boost list run by bdawes at, gregod at, cpdaniel at, john at