experimental fast-pathed rw-mutex algorithm...

[Chris Thomasson]

Here is a "somewhat" simple, experimental, writer starvation-free and
fast-pathed rw-mutex algorithm that uses DWCAS on 32-bit systems and normal
CAS on 64-bit systems. It does not need to use a internal mutex to protect
the internal state of the lock. All of the bookkeeping can be modified
atomically using a single instruction. This means it has the potential to
outperform virtually all of the mutex based non-distributed rw-mutex
implementations out there...

< scribbling down some pseudo-code >

// assume 64-bit size
struct rw_mutex_t
{
short reads;
short writes;
short r_waits;
short w_waits;
};

static rw_mutex_t mtx = { 0, 0, 0, 0 };
static sem_t r_wset;
static sem_t w_wset;

// updates c with d and returns non-zero on failure
extern dwcas( void *d, void *c, const void *x );

// write lock
rw_mutex_t cmp, xchg;

for ( ;; )
{
cmp = mtx;

do
{
xchg = cmp;

if ( ! cmp.reads && ! cmp.writes )
{
++xchg.writes;
}

else
{
++xchg.w_waits;
}

} while ( dwcas( &mtx, &cmp, &xchg ) );

if ( ! cmp.reads && ! cmp.writes )
{
break;
}

sem_wait( &w_wset );
}

// read lock
rw_mutex_t cmp, xchg;

for ( ;; )
{
cmp = mtx;

do
{
xchg = cmp;

if ( ! cmp.writes && ! cmp.w_waits )
{
++xchg.reads;
}
else
{
++xchg.r_waits;
}

} while ( dwcas( &mtx, &cmp, &xchg ) );

if ( ! cmp.writes && ! cmp.w_waits )
{
break;
}

sem_wait( &r_wset );
}

// write unlock
rw_mutex_t cmp, xchg;

do
{
xchg = cmp;

--xchg.writes;

if ( cmp.w_waits )
{
--xchg.w_waits;
}
else if ( cmp.r_waits )
{
xchg.r_waits = 0;
}

} while ( dwcas( &mtx, &cmp, &xchg ) );

if ( cmp.w_waits )
{
sem_post( &w_wset );
}

else if ( cmp.r_waits )
{
sem_post_multiple( &r_wset, cmp.r_waits );
}

// read unlock
rw_mutex_t cmp, xchg;

do
{
xchg = cmp;

--xchg.reads;

if ( ! xchg.reads && cmp.w_waits )
{
--xchg.w_waits;
}
else if ( cmp.r_waits )
{
xchg.r_waits = 0;
}

} while ( dwcas( &mtx, &cmp, &xchg ) );

if ( ! xchg.reads && cmp.w_waits )
{
sem_post( &w_wset );
}

else if ( cmp.r_waits )
{
sem_post_multiple( &r_wset, cmp.r_waits );
}

Does anybody notice any subtitle/major race-conditions? I just scribbled
this simple algorithm down. I can't really seem to find any just yet, but
just in case:

*** Do not use the code for anything else but experimentation! ***

:)

Thank you.

--
http://appcore.home.comcast.net/
(portable lock-free data-structures)

[Michel]

There is an fast pathed implementation in the sscli from MS.

http://dotnet.di.unipi.it/Content/sscli/docs/doxygen/clr/vm/rwlock_8h.html
http://dotnet.di.unipi.it/Content/sscli/docs/doxygen/clr/vm/rwlock_8cpp.html

It uses only CAS, but fields are smaller.

Something like
uchar - readers
bit - readers signaled
bit - writers signaled
uchar - waiting readers
uchar - waiting writers

Regards
/Michel