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

From: Chris Thomasson (cristom_at_[hidden])
Date: 2006-10-24 12:03:13

"Anthony Williams" <anthony_w.geo_at_[hidden]> wrote in message 
news:d58h7nlv.fsf_at_yahoo.com...
> "Peter Dimov" <pdimov_at_[hidden]> writes:
>> Anthony Williams wrote:
>>> "Peter Dimov" <pdimov_at_[hidden]> writes:
>>>> Chris Thomasson wrote:
>>>>> Here is the initial experimental pseudo-code that I am thinking
>>>>> about prototyping in IA-32 Assembly:
>>>>>
>>>>> http://groups.google.com/group/comp.programming.threads/browse_frm/thread/5ffb0ed46a4bcb4b
>>>>
>>>> Seems like it can work. Don't you only need one bit for writes
>>>> though?
>>>
>>> It's essentially the same algorithm I've used in my latest offering
>>> on the thread_rewrite branch.

[...]

> The answer to your question is "when all K+L readers have finished". i.e., 
> my
> algorithm gives readers priority.
>
> Maybe this isn't such a good thing; in the "common" scenario of one writer
> thread and many readers, a waiting writer needs to block waiting readers,
> otherwise the writer might starve if the readers overlap each other.
>
> Chris's algorithm goes to the other extreme --- writers always take 
> priority,
> and no readers will take the lock if there are any waiting writers. If 
> there
> is more than one writer thread, then the readers might starve.

The reason I give writer priority is because I anticipated that there will 
be a heck of a lot more readers than writers throughout the entire lifetime 
of the lock... I wanted to be able to get what few writes there may be in 
during periods of heavy and persistent reader activity; lots of readers 
should be implied. If the writes only happen once in a while, then they 
should be given priority over the stampeding heards of reader threads...

I can't really imagine a practical situation in which periods of 
moderate/heavy persistent writer activity that could starve readers... IMHO, 
that could only mean that the rw-mutex is being used improperly; they should 
only be used for "mostly-read" based algorithms...

> The way I see it, the ideal is that a waiting writer will block any fresh
> readers until all the current readers have gone away, but once that 
> happens,
> and the lock is released, the waiting writer and the waiting readers will
> compete equally.

[...]

Well, IMHO:

A rw-mutex usually makes readers block/wait for all "prior writes" and the
"last write broadcasts". A write usually blocks/waits for all "prior
reads/writes", and the "last read signals/last write broadcasts"...

Anyway, I believe that it is sufficient to prevent the starvation of writers 
because a high number of readers is simply implied wrt rw-mutexs... So, it 
naturally seems that writes would be the only thing that could get subjected 
to any kind of starvation...

Again, if your rw-mutex is getting hit with enough writes to even begin to 
start to starve the readers, then the user of the rw-mutex is using it 
improperly... IMHO  of course...