Date: Tue, 24 Oct 2006 10:48:27 -0700 From: "Chris Thomasson" <cristom@comcast.net> Subject: Re: [boost] A fast-pathed rw-mutex algorithm for Boost... To: boost@lists.boost.org Message-ID: <ehliu9$p9$1@sea.gmane.org>
"Dave Handley" <dave.handley@morganstanley.com> wrote in message news:41B9816CBF7F0249AEED3F2B4FE1A5A958B8@lnpdtdc1.pdt.ms.com...
Date: Tue, 24 Oct 2006 09:03:13 -0700 From: "Chris Thomasson" <cristom@comcast.net> Subject: Re: [boost] A fast-pathed rw-mutex algorithm for Boost... To: boost@lists.boost.org Message-ID: <ehlcp0$3vf$1@sea.gmane.org>
[...]
I've not looked at the code in question - but the way I see it a well behaved readers/writer lock should do the following:
1) If a single writer is waiting, further attempts to acquire read locks should wait until the writer has locked and unlocked. 2) If a second writer starts to wait, it should not prevent other read locks getting involved - and should only start to block new read locks at the point at which it acquires the lock.
If you do this (and have reasonable selection of which waiting thread is serviced first) then you can avoid starvation on both sides under all circumstances.
My current code gives writers priority because there is not going to be a lot of frequent writes anyway... However, it would be trivial to make it work like you describe...
This can easily be done with atomics and a single 32 bit ref count.
Yeah... However, I don't really have any problems with using DWCAS when I am not dealing with pointers... A DWCAS algorithm that does not deal with pointers on a 32-bit system is 100% compatible with normal CAS on a 64-bit system... This is fairly portable because nearly all 32-bit architectures have a DWCAS, but hardly any 64-bit architecture has DWCAS; as long as you don't use pointers your okay:
http://groups.google.com/group/comp.arch/browse_frm/thread/71f8e0094e353 e5
The way our code operates with a single 32 bit ref count is that the ref count is signed. When a reader wants to acquire the lock, it checks the sign, if 0 or +ve it increments the ref count and acquires the lock. If -ve it waits until the ref count is zero (which happens when the writer releases the lock). When a reader wants to release the lock, it checks the sign, incrementing if -ve and decrementing if +ve. When a writer wants to acquire the lock, it checks the sign. If 0 or +ve, it flips the sign and decrements the ref count (so 0 becomes -1 and 1 becomes -2 etc.). It then waits until the ref count hits -1, at which point it has got the lock. If the sign is -ve it waits. When a writer wants to release the lock, the ref count must be -1, it simply sets it to 0. If we look at the ref count, positive values give us a count of the number of readers that currently hold the lock. Zero means no-one has the lock, and -1 means a single writer has the lock. Other negative values, mean that a writer is waiting, and we have abs(ref_count)-1 readers currently holding the lock preventing the writer from acquiring it. The only information we don't have in this ref count is the numbers of readers or writers waiting on the lock. Dave