Re: [boost] A fast-pathed rw-mutex algorithm for Boost...

From: Anthony Williams (anthony_w.geo_at_[hidden])
Date: 2006-10-26 03:46:17

"Chris Thomasson" <cristom_at_[hidden]> writes:

> "Anthony Williams" <anthony_w.geo_at_[hidden]> wrote in message 
> news:wt6ok7ow.fsf_at_yahoo.com...
>> "Peter Dimov" <pdimov_at_[hidden]> writes:
>>> Peter Dimov wrote:
>>>> Chris Thomasson wrote:
>>>>> "Peter Dimov" <pdimov_at_[hidden]> wrote in message
>>>>> news:001801c6f7bd$c32f62a0$6607a8c0_at_pdimov2...
>>>>>> Chris Thomasson wrote:
>
> [...]
>
>> Hi,
>>
>> I have run a test against Peter's "naive" implementation, Peter's
>> implementation of Chris's algorithm, my algorithm from the thread_rewrite
>> branch (v1.1.2.8), my old condition-based algorithm from the 
>> thread_rewrite
>> branch (v1.1.2.4), and a new variation of my latest offering that has a
>> "waiting exclusive" bit, and blocks readers if that bit is set, in line 
>> with
>> my last post on the subject. The test is essentially Peter's test, with a 
>> mod
>> to count the max time any reader or any writer spends waiting, in order to
>> check for starvation.

>> The next thing to note is that the total runtimes of the remainder are all
>> comparable. I would have to run longer tests to really tell them apart.

I'm running some longer tests now, to see how it comes out.

>> The next thing to note is that Peter's implementation of Chris's algorithm 
>> has
>> some REALLY long wait times for readers --- 12 seconds! --- which follows 
>> from
>> the "writer priority" nature of the algorithm.
>
> 12 Seconds? Something is off kilter wrt the writer frequency 
> per-writer-thread and/or the critical-section the writes make use of... 
> IMHO, this would prompt me to revise my applications synchronization 
> scheme...

It's just a consequence of writer priority when there's more than one
writer. The particular trouble spots were when there is 4 writer threads, so
there's pretty much always a writer waiting.  I would revise the rwmutex to be
"fairer" as a first port of call.

> Okay, FWIW... Here some pseudo-code for an alter version of my algorithm 
> that gives strict priority to the readers...

I thought we all agreed that was a bad plan. That's why I'm trying to revise
my algorithm to not do this.

Incidentally, I've just been reviewing the read-write lock algorithm in
Butenhof's "Programming with POSIX Threads", and he uses a reader-priority
algorithm. He does say that it might not be suitable for all uses, however,
and shows how to change it to writer-priority.

> This "newly augmented algorithm" should do better on Peters test... 
> Hopefully!!!

I'll add it to the list. 

The test I'm running does cover a wide variety of scenarios, with 0, 1, 2 or 4
writers, each matched against 0, 1, 2, 4, 16 or 64 readers, so it's not biased
--- a "reader priority" algorithm should give high "write wait" times when
there's lots of readers, just as a "writer priority" algorithm will give high
"read wait" times when there's more than one writer.

Anthony
-- 
Anthony Williams
Software Developer
Just Software Solutions Ltd
http://www.justsoftwaresolutions.co.uk