Sunday, October 19, 2014

Tony Van Eerd on "Lock-Free by Example"

One of the talks on CppCon 2014 was given by Tony Van Eerd on the subject of lock-free queues.

The title of the talk is a bit misleading because although the techniques he describes are the ones used on lock-free algorithms and data structures, the queue shown on the presentation is not actually lock-free for either pop() or push().

The interesting thing about his talk is that he focuses on the thought process needed to arrive at a lock-free queue. Most papers and talks just give us the "end result" with the algorithm as it should be, but they don't explain why it has to be the way it is. His talk goes into the common pitfalls of designing a lock-free queue, which makes it particularly instructive for people new to the field.

There was one statement that caught my attention, that lock-free algorithms need to maintain invariants at all times. This is sooooo true!
The main reason why designing lock-free (and wait-free) data structures is hard, is due to the fact that the invariants must hold at every step of the way, for every method of the data structure, and every shared (atomic) variable. The more methods you have on a lock-free data structure, the more complex the problem becomes. The more variables are shared among those methods, the greater the complexity and possible interleavings, and higher number of states, where each one must still uphold all the invariants.
Designing data structures with locks is much easier because, the code within a lock()/unlock() can temporarily break invariants without worry, as long as the invariants are restored before the call to unlock().

Sunday, October 12, 2014

Concurrency Track of Eurosys 2014

Eurosys 2014 had a Concurrency Track and they recorded the videos for the four presentations.
Here is the link to the recording: