Boost logo

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
>> "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 Williams
Software Developer
Just Software Solutions Ltd

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