Lock-free Programming

Lock-free programming is hard. We will not spend a lot of time discussing lock-free programming in this course, but instead, we will provide an example of how a very simple lock-free data structure could be implemented. Some concepts you might have heard of, such as compare-and-swap (CAS) and the ABA problem, will not be further discussed in this course.

Example: A lock-free queue

Here, we are going to see an example of a lock-free queue, which is a relatively simple but useful lock-free data structure. Lock-free queues can be used for one-way communication with threads that cannot use locks to synchronize access to shared data.

Its implementation is straightforward because of the limited requirements: it only supports one reader thread and one writer thread. The capacity of the queue is also fixed and cannot change during runtime.

A lock-free queue is an example of a component that might be used in environments where exceptions are typically abandoned. The queue that follows is therefore designed without exceptions, which makes the API differ from other examples in this course.

The class template LockFreeQueue<T> has the following public interface:

• push(): Adds an element to the queue and returns true on success. This function must only be called by the (one and only) writer thread. To avoid unnecessary copying when the client provides an rvalue, push() overloads on const T& and T&&. This technique was also used in the BoundedBuffer class presented earlier in this chapter.

• pop(): Returns a std::optional<T> with the front element of the queue unless the queue is empty. This function must only be called by the (one and only) reader thread.

• size(): Returns the current size of the queue. This function can be called by both threads concurrently.

The following is the complete implementation of the queue: