Chapter 2. Lock-Free Concurrency

In Chapter 1, Traditional Concurrency, we reviewed thread synchronization with locking and how to use locks effectively. However, there will be still performance overhead related to locking. The best way to avoid such issues is by not using locks at all whenever possible. Algorithms that do not use locking are referred to as lock-free algorithms.

Lock-free algorithms in turn are of different types. One of the most important types is wait-free algorithms. These algorithms not only evade the use of locks, but also are guaranteed to not wait for any events from other threads. This is a best-case scenario but unfortunately, it is a rare situation when we can avoid waiting for the other threads at all. Usually, a real concurrent program tries to be as close as possible to wait-free, and this is what every developer should try to achieve.

There is one more category of algorithms that do not use OS-level thread blocking but use spin locks. This allows...