Abstract:

In concurrency, it’s often better to ask for forgiveness than for permission. Lock-based approaches pessimistically assume contention and ask for permission first, which often slows everybody down. A new breed of optimistic concurrency control relies on doing work on the side and carefully merging changes into shared structures assuming it succeeds most of the time. The result? Faster, more scalable concurrent code.

As always, that’s not the full story - solutions that are better through and through are a rare commodity in our métier. With new benefits also come new risks. Also, the programming model is oddly different, as are the challenges. There are no more critical sections, deadlocks, or livelocks, but now that everything is free-flowing it’s more difficult to keep threads from hanging on old data.

This talk is a thorough introduction to lock-free concurrency using the compare-and-swap (CAS) primitive. We’ll design together an efficient lock-free stack, and we’ll sketch more intricate container implementations.