Adventures in lock-free programming

I’ve been intrigued by the idea of lock-free programming since I discovered that C++0x (as it was then) was to gain library facilities for standardised, portable lock-free programming. The new <atomic> header enables us to perform atomic reads and writes on a restricted set of types, and to use atomic operations as synchronisation primitives in lock-free programming.
I am still new to this topic, and have approximately equal measures of interest in the possibilities and fear of the complexity and difficulty, but wish to expose the list of writings I have found informative in my learnings. Get in touch if you know of any good additions to this list as I will be updating it with further discoveries.

volatile vs. volatile [Herb Sutter]

An explanation of what ordered atomic variables do. Also covers the use of volatile in C++ for ‘unusual’ memory semantics.

The Trouble With Locks [Herb Sutter]

Lock-based programming, our status quo, is difficult for experts to get right. Worse, it is also fundamentally flawed for building large programs.

Lock-free programming is difficult for gurus to get right.

Herb explains why lock-based programming is difficult, brittle, and why locks are not generally composable.

Lock-Free Code: A False Sense of Security [Herb Sutter]

Herb dissects a lock-free queue implementation to show the flaws in its design, discussing the twin requirements of atomicity and ordering on any lock-free variable. He exposes the points in the lock-free algorithm in which instruction re-ordering can break the queue’s invariants.

Writing Lock-Free Code: A Corrected Queue [Herb Sutter]

The typical coding pattern to use is to do work off to the side, then “publish” each change to the shared data with a single atomic write or compare-and-swap.

In the sequel to A False Sense of Security Herb shows a lock-free queue implementation with a working implementation based on atomic variables.

Writing a Generalized Concurrent Queue [Herb Sutter]

In this final part of the series Herb writes a generalized queue structure; he does this without mutexes (mutices?), but uses atomic variables equivalently with no relaxation of the barriers for each read/write operation.

Apply Critical Sections Consistently [Herb Sutter]

Herb shows how to express a critical section with several different synchronisation primitives, and shows some example code too.

Memory Barriers Are Like Source Control Operations [Jeff Preshing]

This article uses the analogy of source code control to explain the different memory barriers (fences). This was a great one for me, though I can’t honestly say I completely grok it yet… Jeff’s other articles linked from that page are also good background on the subject.

C++ atomics and memory ordering [Bartosz Milewski]

Bartosz provides a much more readily understandable description of C++11’s different memory_order enum values than the standard; anyone who understands all of section 1.10 Multi-threaded executions and data races has my respect.

C++ Concurrency in Action: Practical Multithreading [Anthony Williams]

I’ve only just begun reading this loan from a colleague, and so far am very impressed by the clarity with which concepts and techniques are explained and demonstrated. It was written for the new, standard thread support facilities by the creator of the just::thread C++11 implementation who also helped guide the standardisation of threads and other language features.