Monday, July 11, 2016

John Cairns Presents - Smashing Atomics

If you're into Java and queues, here is a light intro talk by John Cairns. There's nothing new about it that you haven't already seen on other talks posted here (except for his Disruptor variant), but it's always nice to see how a SeqLock can work, and if you're a newbie to the area, this is not a bad place to start:

Btw, there are a few slides that mention RCU, but just replace that with Copy-On-Write because that's what is being talked about, not the RCU synchronization technique.

Also, the slide on "Lock Freedom" has a few incorrect statements so just ignore it.
Namely, the third statement that says "All threads will make progress in a finite time" is incorrect. Lock-Free methods do not give such a guarantee. To have all threads make progress in a finite number of steps we need to have Wait-Free, and there is no progress condition that gives guarantees about "time", they're all defined in terms of number of steps.
The fourth statement in the "Lock Freedom" slide is also incorrect. There are many lock-free data structures with some methods that are not linearizable. The most well known is Michael-Scott Queue (implemented in java.util.concurrent.ConcurrentLinkedQueue) which is not linearizable for iterations. Linearizability is a "Consistency Model" and Lock-Freedom is a "Progress Condition", and although there is some faint relationship between the two concepts, they are mostly orthogonal.

No comments:

Post a Comment