Note that the linked paper predates the C++ / C11 memory model, which I would consider essential for anyone implementing lock-free algorithms in C or C++ today. It also long predates an understanding of the ABA problem[0].
back
2 comments
Eh? ABA problem was known since a long time ago. Google scholar[1] shows a paper titled "Correction of a Memory Management Method for Lock-Free Data Structures" in 1995, which in turn cites "ABA problem" mentioned in "System/370 Principles of Operation. IBM Corporation, 1983" (!!).
I stand corrected, thanks! I had the feeling that the ABA problem affected a lot of the earlier lock-free algorithms, but didn't know the understanding of it went that far back.
The C/C++ memory model is also inspired by the Java memory model which dates back to the mid 90s and was updated back in 2004.
Absolutely. The Java ecosystem deserves a huge amount of credit for putting lock-free programming on a theoretically sound basis, and it's informative how long it took to get it right.
But none of that had a serious effect on C and C++ practice until C++ started formalizing the memory model. Even today, we still have to deal with a lot of legacy code that uses pre-memory model primitives such as __sync_synchronize, __atomic_cmpxchg, InterlockedCompareExchange, etc. I'd like to see all that stuff go sooner rather than later. In my opinion, the original article is not helping, as it shows C code that does reads and writes through pointers, expecting them to behave as atomic operations.
The good thing is that those legacy operations can be now understood in term of the memory model.
I think that's only half-useful, at best. If all your access to atomics happened to be mediated by, say, __atomic_cmpxchg, then modeling that as (say) atomic_compare_exchange_strong would give you confidence in the implementation. The problem is that pre-memory model code is also likely to check the current state of the atomic through a raw pointer load instead of anything like atomic_load (which generally has no counterpart in pre-memory model synchronization libraries). So, analyzing that code through the lens of C11 tells you little more than that it's undefined behavior.
Like most undefined behavior, it can work in practice. Probably. Most of the time. If you stick to using older compilers.