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().
Are you saying push() and pop() aren't lock-free because the wait on full/empty? Because that should just be seen as an optional feature - they could just as easily (or more easily) return an error on full/empty.
ReplyDeleteOr are they not lock-free in other cases?