Introduction to Lock-Free Algorithms

Leave a comment

Slides are at http://concurrencykit.org/presentations/lockfree_introduction/.

Recently I’ve been interested in formalizing a course structure for the practical application of non-blocking data structure design and implementation. As part of this effort, I will be giving public Tech Talks here at AppNexus. The first talk was “Introduction to Lock-Free Algorithms” and it went reasonably well. There are a lot of improvements to be made to the introduction course, primarily because I think I attempted to cover too much at once. The current deck of slides also fails to illustrate linearizability sufficiently.

I plan on providing a majorly retrofitted implementation of this presentation some time in the near future (the next loop of the introduction class) but in the mean time I have made the current deck of slides available at http://concurrencykit.org/presentations/lockfree_introduction/. For the curious, I used reveal.js to create the presentation. When viewing the presentation, please note the controls in the top right which indicate in which direction you should go. Use the arrow keys to navigate and prefer going down to going left/right.

If you’re interested in learning more about the goals of the course (to be decomposed into several talks), please read more. The relevant skillshare page is http://www.skillshare.com/Introduction-to-Lock-Free-Algorithms/592151380.


This talk introduces the attendee to non-blocking algorithm design and implementation. With multi-core processors being a commodity item, the ability to design and implement composable, scalable and resilient concurrent systems is becoming an increasingly (in)valuable skill. Lock-free synchronization allows concurrent systems to exude composibility, scalability, and resilience in ways impossible (in theory and in practice) via traditional lock-based synchronization methods. As lock-free algorithms receive a fair share of inappropriate hype, attendees will leave this course possessing the ability to determine when, where, and how to best utilize lock-free data structures and algorithms in real-world systems. The talk concludes with a plethora of valuable resources for the attendee to learn more about this exciting topic.

Topics include: blocking synchronization, atomic operations and the consensus problem, obstruction-freedom, wait-freedom, lock-freedom, memory models, the ABA problem, safe memory reclamation and the practical implications of non-blocking synchronization.

This entry was posted in Architecture. Bookmark the permalink.

Leave a comment