Lock-free concurrent data structures

As mentioned in the previous sections, lock-based data structures have some drawbacks. Among them, the reduction in performance is caused by the need to check the synchronization structures and the possibility of introducing problems such as deadlocking. A possible solution to this problem is to use lock-free concurrent data structures.

Unlike lock-based functions, where one thread can block another, and both might wait for some condition before making progress, a lock-free state ensures progress is made by at least one of the threads. We say that algorithms and data structures using data synchronization primitives are blocking. That is, a thread is suspended until another thread acts. That means the thread can’t progress until the block is removed (typically unlocking a mutex). Our interest lies in data structures and algorithms that don’t use blocking functions. We call some of them lock-free, although we should make a distinction...