From: Dave Handley (dave.handley_at_[hidden])
Date: 2006-10-25 04:23:39
> Date: Tue, 24 Oct 2006 10:48:27 -0700
> From: "Chris Thomasson" <cristom_at_[hidden]>
> Subject: Re: [boost] A fast-pathed rw-mutex algorithm for Boost...
> To: boost_at_[hidden]
> Message-ID: <ehliu9$p9$1_at_[hidden]>
> "Dave Handley" <dave.handley_at_[hidden]> wrote in message
> >> Date: Tue, 24 Oct 2006 09:03:13 -0700
> >> From: "Chris Thomasson" <cristom_at_[hidden]>
> >> Subject: Re: [boost] A fast-pathed rw-mutex algorithm for Boost...
> >> To: boost_at_[hidden]
> >> Message-ID: <ehlcp0$3vf$1_at_[hidden]>
> > I've not looked at the code in question - but the way I see it a
> > 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
> > locks getting involved - and should only start to block new read
> > at the point at which it acquires the lock.
> > If you do this (and have reasonable selection of which waiting
> > serviced first) then you can avoid starvation on both sides under
> > circumstances.
> My current code gives writers priority because there is not going to
> lot of frequent writes anyway... However, it would be trivial to make
> 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
> 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
> system... This is fairly portable because nearly all 32-bit
> have a DWCAS, but hardly any 64-bit architecture has DWCAS; as long as
> don't use pointers your okay:
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
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.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk