Atomics and Concurrency

Summary

This is going to be a long post, but I hope you get value out of it. This wasn’t an easy topic to tackle but it was definitely worthwhile! Hopefully, you leave with a decent understanding of how memory ordering works and how to use atomics in conjunction with memory ordering to build a lock-free queue in C++. Note: If you want to actually compile the code and run it, make sure to do so with the TSan flag enabled for the CLang compiler. TSan is a reliable way of detecting data races in your code, instead of trying to repeatedly run the code in a loop hoping for a data race to occur. Imagine you have either some concurrent code operating on some shared data in memory. You have two threads or processes, one writing and one reading on some shared piece of state. The “safe” way of dealing with this is mutexes. However, mutexes tend to add overhead. Atomics are a more performant but much more complicated way of dealing with concurrent operations. Atomics This section is very simple. Atomics are simply operations or instructions that cannot be split by the compiler or the CPU or re-ordered in any way. The simplest possible example of an atomic in C++ is an atomic flag #include <atomic> std::atomic<bool> flag(false); int main() { flag.store(true); assert(flag.load() == true); } We define an atomic boolean, initialise it and then call store on it. This method sets the value on the flag. You can then load the flag from memory and assert its value. Operations With Atomics The operations you can perform with atomics are straightforward: You can store some value into them with a store() method. This is a write operation. You can load some value from them with a load() method. This is a read operation, You can do a Compare-and-Set(CAS) with them using a compare_exchange_weak() or compare_exchange_strong() method. This is a read-modify-write(RMW) operation. The important thing to remember is that each of these cannot be split into separate instructions. Note: There are more method...