Custom concurrent data structures

In this section, we will show how to design a concurrent data structure. The data structure we will use as a running example will be simple, but sufficient to demonstrate the general approach. You will be able to apply the same principles to more complex data structures.

Before we start, there is a disclaimer. Designing a concurrent data structure is hard, and, as a rule of the thumb, you should almost never do it. Even if you manage to implement a correct and efficient concurrent data structure, the cost of doing so is usually high.

There are several reasons why designing a concurrent data structure is hard. The first is achieving correctness: errors are much harder to notice, reproduce, or analyze due to inherent non-determinism. Then, operations must not slow down when more processors use the data structure. In other words, the data structure must be scalable. Finally, a concurrent data structure must be efficient in absolute terms, and it must not be much...