Re: [boost] read_write_mutex fundamentally broken in 1.33?

From: Howard Hinnant (hinnant_at_[hidden])
Date: 2005-09-08 17:17:24

On Sep 8, 2005, at 5:56 PM, Ion Gaztañaga wrote:

>> So, do we yank read_write_mutex from 1.33.1 and, err, start over?
>
> What about avoiding policies, or making independent read-write locks,
> one for reader priority, other for writers priority and other for fifo
> priority? Or a templatized priority policy. Or just pick a default
> implementation like pthreads and don't guarantee anything.
>
> There are simple implementations of read-write locks available in books
> that we can use without thinking very much, for example, I can remember
> one from "Programming with posix threads" and another one from "Unix
> network programming vol.2", one with reader prioriy and another with
> writer priority. All these where made using posix conditions and
> mutexes, and the implementation is quite simple. ACE has its own
> implementation if I'm not wrong.
>
> I think that runtime policy has an overhead and complexity. But this
> would require changing, Boost.Threads read-write lock interface,
> something that I don't know we like to do.
>
> On the other hand, I don't know if reader/writer priority is very
> important, since I think posix does not define anything about this.

If priority policy is the overriding issue, I recommend considering 
Alexander Terekhov's algorithm summarized here:

http://home.twcny.rr.com/hinnant/cpp_extensions/rw_perf.html

> ... use an algorithm inspired by Alexander Terekhov which attempts to 
> side step the issue of reader priority or writer priority by having 
> all threads initially wait at the same entry gate. This leaves the 
> priority for entry into the first gate up to the thread scheduler. 
> Once the first gate is entered by a writer thread, it blocks until all 
> threads currently holding read locks have released those locks. While 
> the writer thread is blocked on the second gate, no new read locks can 
> be acquired.

I've implemented and beat this algorithm to death with experiments.  
Personally I know of no better way to implement a read/write lock.

-Howard