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.
Thank you all for you're valuable time; I really do appreciate it!
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk