- 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
Lockless Message-Passing
One of the most useful lockless data structures that I've come across is Keir Fraser's lockless ring buffer. You'll find this used in a lot of places in the Xen source code; for example, it's used to communicate between the front and back end of the paravirtualized ring buffers.
To understand how the lockless version works, it's worth revisiting how a normal ring buffer works. This fixed-sized memory blob acts as a circular queue. A producer puts things in at an insert point, and then a consumer takes them out. When the producer gets to the end, it goes back to the start.
With a concurrent ring buffer, the producer and consumer are in separate threads. Before inserting, the producer needs to make sure that space is available, which requires checking both the insert and remove pointers.
The first observation to make when creating a lockless version is to note that both the producer and consumer pointers only increase for most of their lifetime. The part when they wrap around is inconvenient, though, because they jump backward here, and a read at the wrong time could mean that you saw the empty space exactly opposite of where it really is.
There's a very simple way of eliminating this need to run backward: Make the counters free-running, so that they always increase, and then just use modulo arithmetic to find out where the values are inside the buffer. If you make the buffer size a power of two, you can simplify this design even more, by just masking off the low bits to give you the array index.
Once the counters are always increasing, this process becomes easier to do atomically. Subtracting the consumer pointer from the producer pointer always gives you the number of elements in the buffer. Subtracting this number from the array size always gives you the number of elements in the array.
In pseudocode, inserting works something like this:
while (producer - consumer == ring_size) { wait(); }
ring[(producer++) & (ring_size - 1)] = new_value;
Removing the value is similar:
while (producer - consumer == 0) { wait(); }
return ring[(consumer++) & (ring_size - 1)];
You don't actually need an atomic increment for either of these modifications to the counters, as long as the counters are of a type that can be written to memory in a single operation. Only one thread is ever incrementing either counter, so no two modifications can interfere with each other.
Keir's version is actually slightly more complex, including a pair of producer and consumer counters and allowing bidirectional communication. You can find a full explanation of how it works in Chapter 6 of my book The Definitive Guide to the Xen Hypervisor, which you can read online at InformIT.