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 ...