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

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
> news:41B9816CBF7F0249AEED3F2B4FE1A5A958B8_at_lnpdtdc1.pdt.ms.com...
> >> 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
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