Lock-free Programming is Hard
Lock-free programming has this magical aura around it. If you’ve ever heard of lock-free programming, you’ve probably seen those neat little Compare-And-Swap (CAS) loops that seem to solve everything. I found a bug in a CAS loop that had been sitting quietly in CMU’s 15-418 Parallel Computer Architecture lecture slide for years. The “Simple” Example Here’s what the example in lecture slide looked like: // atomic compare and swap int atomicCAS(int* addr, int compare, int val) { int old = *addr; *addr = (old == compare) ? val : old; return old; } // build atomic max using CAS void atomic_max(int* addr, int x) { int old = *addr; int new = max(old, x); while (atomicCAS(addr, old, new) != old) { old = *addr; new = max(old, x); } } The idea is: ...