Subj : Re: experimental fast-pathed rw-mutex algorithm...
To   : comp.programming.threads
From : Michel
Date : Sat May 28 2005 11:09 am

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

Chris Thomasson wrote:
> 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.
> 
> 
> 
>

.