Writing lock-free code

Since we have a very limited number of atomic operations, it is very hard to write lock-free code. For some common data structures, such as a double linked list, there is no lock-free implementation. Besides, it is very easy to make a mistake, and the main problem is that such code could work fine 99.9 percent of the time, which makes debugging enormously confusing.

Therefore, the best practice is to use standard implementations of such algorithms. A good place to start is by using concurrent collections from the System.Collections.Concurrent namespace that was introduced in the .NET Framework 4.0. We will review them in detail in Chapter 6, Using Concurrent Data Structures. However, now we will try to do not as advised and implement a lock-free stack and a lock-free queue from scratch.

The cornerstone of the lock-free code is the following pattern: read some data from the shared state, calculate a new value, and then write the new value back, but only if the shared...