- The Building Blocks
- Multiword Operations
- Lockless Message-Passing
- Hybrid Structures
- Pointers and Deletion
- Other Approaches
Like this article? We recommend
Like this article? We recommend
Like this article? We recommend
Multiword Operations
These basic operations work on single words—values that fit in a single register and can be accessed from memory with a single read or write. You can use them to implement multiword operations relatively easily.
Single-word operations are very convenient because you can typically interleave atomic writes with unsynchronized reads. For example, if you're using atomic operations to increment a counter, you can read the counter without an atomic operation, but you might get a slightly old value. If the counter is telling you the amount of data available to process, the fact that the value is old doesn't matter; you'll get the newer value the next time that you read it.
Multiword operations have to be a bit more careful. You cannot mix atomic and non-atomic operations. The simplest way of updating multiple words is to provide a free-running counter along with a data structure. The counter is a single word, so the CPU's atomic operations can control it. The lowest bit is regarded as an update flag, while the rest of the bits give the version.
When reading, you first read the version and then read the rest of the values, and then read the version again. If the new version ends in 1, or it isn't the same as the old version, you go back and try again.
When writing, you increment the version, modify the data structure, and then increment the version again. If you have a single writer and multiple readers, this process can be very fast indeed. You need two atomic instructions for a write and none for a read. If you have multiple writers, you need to do a compare-and-exchange operation when incrementing the version number, in order to make sure that another thread is not in the middle of modifying the number.
This is roughly equivalent to using a read-write lock, but with some important differences. The readers never block the writer, so you cannot modify the data structure in a way that will cause readers to break. In particular, you can't leave any dangling pointers in the middle, because the reader will get a segmentation fault when trying to follow them. However, you can use this approach to protect a large static-sized data structure.