is non-blocking concurrent programming for real?

Question

I have been reading random links on non-blocking algorithms and uses thereof in concurrent programming. Are there any useful libraries using non-blocking algorithms with C/C++ and what types of concurrent data structures that benefit the most from the use of non-blocking algorithm? Thanks.

Answer 1

There's no such thing as a free lock. All multithreaded algorithms use synchronization. You can get lockless algorithms that don't use explicit locks but rely on atomic operations and other such "non-locks" but the reality is that you have to be an extremely good programmer - and know your target platform and the implementation details of the target CPU - in order to write such an algorithm. The only lockless algorithms I know that actually work are for the 360, written by Microsoft engineers, who had to get the design docs of how the CPU in the 360 implemented locking, before they could succeed.

A C++ lockless algorithm would be applied to way too many CPUs to make such a thing work - you couldn't just write it on top of boost::thread.

Answer 2

boost::thread uses compare-and-swap semantics for shared_mutex on Windows - only if contention occurs is a blocking call made (using semaphores).

Windows itself supports use of a spin count on Critical Sections via InitializeCriticalSectionAndSpinCount to attempt to optimize a bit for high-contention locks on MP systems.

Microsoft really got the religion on threading performance and both managed and native code now have slimline reader-writer locks.

This also gives me another opportunity to plug a book I've been waiting for, since it has a chapter on this topic : C++ Concurrency in Action.