Boost logo

Boost :

Subject: [boost] wait-free fast-pathed, bounded-time, 100% starvation-free rw-mutex...
From: Chris M. Thomasson (cristom_at_[hidden])
Date: 2009-08-21 10:44:44

I was wondering if the following invention of mine might be of use to Boost:
(please __read_all__; thank you)

Here are some performance numbers wrt my algorithm versus NPTL on Linux
(fedora 10), and OpenSolaris:

My invention has some very interesting properties that simply do not exist
for 99% of all the other rw-mutex algorithms I have seen to date. It's 100%
starvation free and has bounded wait time for readers and writers. Heck,
even the Microsoft rw-mutex algorithm in Vista does not come close to that:

They clearly state that their algorithm is not fair. The algorithm I have
observed in OpenSolaris does not meet this goal as well.

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

Please take not that there are absolutely no loops in the algorithm; this is
one reason why it's bounded time and starvation free.

Also, it has conditional reader-to-writer upgrades and non-conditional
writer-to-reader downgrade capabilities. This is something that does not
exist in the Microsoft implementation, or even the OpenSolaris, or basically
any Linux implementation I have observed. Same goes for OSX.

Therefore, I think this particular algorithm might be of use to Boost.

Any thoughts?

Thank you all for you're valuable time; I really do appreciate it!


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