Nonblocking Algorithms

When devising a concurrent data structure, we typically want to arrange for methods to be atomic—most often linearizable (Sec.  3.1.2 ). Most concurrent algorithms achieve atomicity by means of mutual exclusion, implemented using locks. Locks are blocking, however, in the formal sense of the word: whether implemented by spinning or rescheduling, they admit system states in which a thread is unable to make progress without the cooperation of one or more peers. This in turn leads to the problems of inopportune preemption and convoys, discussed in Sec.  7.5.2 . Locks—coarse-grain locks in particular—are also typically conservative: in the course of precluding unacceptable thread interleavings, they tend to preclude many acceptable interleavings as well.