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

From: Anthony Williams (anthony_w.geo_at_[hidden])
Date: 2006-10-24 11:14:04

"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.
>>
>> http://boost.cvs.sourceforge.net/boost/boost/boost/thread/win32/read_write_mutex.hpp?revision=1.1.2.8&view=markup&pathrev=thread_rewrite
>
> Do you plan to document the algorithm? 

Yes, later.

Thanks for reviewing, Peter. The final boost code can only be better because
of it. Thanks also to Chris for his pseudo-code.

> I'm interested in the following scenario:
>
> - K active readers are holding the lock
> - a writer is waiting for the above
> - L readers are wating for the writer
>
> Since you seem to only store K+L (Chris's algorithm has separate counts), 
> how do you know when to signal the writer? 

Maybe it's not /quite/ the same algorithm, but it's certainly very similar.

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 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. 

To do that, you should be able to get away with a single bit for waiting
writers, too --- either there are waiting writers, or there aren't. Likewise
for waiting readers. When the last reader, or the only writer unlocks, it
clears both the waiting readers and waiting writers flags, and unblocks all
waiting threads (signals an event). The waiting threads then compete. If a
reader gets there first, then subsequent readers are allowed in until a writer
thread wakes up. Once a writer either gets the lock, or flags that it's
waiting, then the remaining readers are blocked until the next wakeup.

Thoughts?

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