Re: [boost] wait-free fast-pathed, bounded-time, 100% starvation-free rw-mutex...

Subject: Re: [boost] wait-free fast-pathed, bounded-time, 100% starvation-free rw-mutex...
From: Chris M. Thomasson (cristom_at_[hidden])
Date: 2009-08-22 06:34:37

"Chris M. Thomasson" <cristom_at_[hidden]> wrote in message 
news:h6mbsp$8ts$1_at_ger.gmane.org...
>I was wondering if the following invention of mine might be of use to 
>Boost:
[...]
> Another nice property is that the algorithm has wait-free fast-paths. If 
> readers hit a fast-path, then they are going to get wait-free access to 
> the protected data-structure. The same goes for writers. The underlying 
> operation is a single atomic fetch-and-add operation:
>
> http://software.intel.com/en-us/forums/intel-threading-building-blocks/topic/65822/reply/87849
>
>
> In fact, the algorithm only needs fetch-and-add; no stupid CAS-loops are 
> required.

I need to clarify a couple of points here. The following version of the 
algorithm:

http://software.intel.com/en-us/forums/intel-threading-building-blocks/topic/65822/reply/87849/

does use CAS for the conditional read-to-write upgrade (e.g., 
`rwmutex_win::tryrdtowr()'), however it uses a constant for the comparand 
and is not used in a loop. Now, the upgrade functionality is simply not 
required aspect of the algorithm, therefore CAS is not required.

One other point, there are architectures that simply do not provide 
fetch-and-add directly (e.g., SPARC). They instead provide CAS or LL/SC 
which can be used to implement fetch-and-add. So, on those architectures, 
the implementation will be using CAS or LL/SC loops, which will degrade the 
wait-free fast-path property down to lock-free. IMVHO, it's not really my 
algorithms fault, I instead blame the architectures that do not have native 
fetch-and-add instructions!

;^)