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 the creation of quite efficient code in situations when the code inside the lock has to run very fast. Such algorithms can be called lock-free in various sources, but strictly speaking they are not as they do not guarantee that the algorithm will be progressing, since it is possible it gets blocked in various situations. We will discuss such situations later in Chapter 10, Troubleshooting Parallel Programs.