Boost logo

Boost :

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
>I was wondering if the following invention of mine might be of use to
> 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:
> 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

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!


Boost list run by bdawes at, gregod at, cpdaniel at, john at