[Threads-devel] wait-free fast-pathed, bounded-time, 100% starvation-free rw-mutex...

Subject: [Threads-devel] wait-free fast-pathed, bounded-time, 100% starvation-free rw-mutex...
From: Chris M. Thomasson (cristom_at_[hidden])
Date: 2009-08-22 22:08:27

I was wondering if the following invention of mine might be of use to Boost:

http://software.intel.com/en-us/forums/intel-threading-building-blocks/topic/65822
(please __read_all__; thank you)

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

http://groups.google.com/group/comp.programming.threads/msg/3e7531657a11baf0

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:

http://msdn.microsoft.com/en-us/library/aa904937(VS.85).aspx

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:

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.

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!

:^)