Lock-free Data Structures: Atomicity and Atomic Primitives

Peterson's Algorithm isn't lock-free, it's a blocking one.

It's a bad idea to treat these operations as constants. They get slower as traffic and contention increases. Different cache topologies will have different timing and different thread scheduling arrangements will also have different timings.

I find it helpful to think in terms of cache lines and cache coherence as that is the biggest factor in performance on cache coherent CPUs when you want to move a lot of data between cores.

A CAS is no worse than a store in that scenario because they both generate the same coherence traffic. One key difference is that the store can drain in the background while the CAS will pause processing.

Once you start thinking of the CPU as an asynchronous instruction processor it starts to get more interesting. For instance in Java if you use volatile, it will stall the CPU until the volatile write completes despite the fact that in most cases you don't actually care. But you can use Atomic* and lazySet or unsafe to make the store non-blocking while still getting the necessary protection against reordering.

What I am getting at is that thinking about a CPU in terms of instructions is the wrong way to go about it. Instructions have to actually execute somehow and that is where the rubber meets the road. A single core can simultaneously be performing several arithmetic operations, draining stores, fetching and pre-fetching cache lines, and several other things I probably haven't learned about. It's causing stalls in this process or introducing dependencies that prevents things from moving along quickly.

Doesn't it depend on the overlap and granularity of work? The concurrency mechanism should be treated as a failsafe on conflict, reducing the conflict in the algorithm should be the primary goal.