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

From: Dave Handley (dave.handley_at_[hidden])
Date: 2006-10-24 12:10:06

> 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]>
> 
<big snip>
> 
> > 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...
> 

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.

This can easily be done with atomics and a single 32 bit ref count.

Dave