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
>> "Peter Dimov" <pdimov_at_[hidden]> writes:
>>> Peter Dimov wrote:
>>>> Chris Thomasson wrote:
>>>>> "Peter Dimov" <pdimov_at_[hidden]> wrote in message
>>>>>> Chris Thomasson wrote:
>> I have run a test against Peter's "naive" implementation, Peter's
>> implementation of Chris's algorithm, my algorithm from the thread_rewrite
>> branch (v22.214.171.124), my old condition-based algorithm from the
>> branch (v126.96.36.199), and a new variation of my latest offering that has a
>> "waiting exclusive" bit, and blocks readers if that bit is set, in line
>> my last post on the subject. The test is essentially Peter's test, with a
>> 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
>> some REALLY long wait times for readers --- 12 seconds! --- which follows
>> 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
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...
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 Williams Software Developer Just Software Solutions Ltd http://www.justsoftwaresolutions.co.uk
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk