Author: David Stolp

Common Pitfalls in Writing Lock-Free Algorithms

Formally, a multi-threaded algorithm is considered to be lock-free if there is an upper bound on the total number of steps it must perform between successive completions of operations. The statement is simple, but its implications are deep – at every stage, a lock-free algorithm guarantees forward progress in some finite number of operations. Deadlock is impossible. The promise of a lock-free algorithm seems remarkable in theory. Concurrent threads can modify the same object, and even if...