Also, if the telephone exchange "is not defective, it can always make the connection"[This quote needs a citation] (see nonblocking minimal spanning switch).
In contrast, global data structures protected by mutual exclusion cannot safely be accessed in an interrupt handler, as the preempted thread may be the one holding the lock.
A lock-free data structure increases the amount of time spent in parallel execution rather than serial execution, improving performance on a multi-core processor, because access to the shared data structure does not need to be serialized to stay coherent.
[4] With few exceptions, non-blocking algorithms use atomic read-modify-write primitives that the hardware must provide, the most notable of which is compare and swap (CAS).
However, the emerging field of software transactional memory promises standard abstractions for writing efficient non-blocking code.
[5][6] Much research has also been done in providing basic data structures such as stacks, queues, sets, and hash tables.
[10][11][12][13] Non-blocking algorithms generally involve a series of read, read-modify-write, and write instructions in a carefully designed order.
Even when they don't, many modern CPUs often re-arrange such operations (they have a "weak consistency model"), unless a memory barrier is used to tell the CPU not to reorder.
It was shown in the 1980s[16] that all algorithms can be implemented wait-free, and many transformations from serial code, called universal constructions, have been demonstrated.
For example, it has been shown[17] that the widely available atomic conditional primitives, CAS and LL/SC, cannot provide starvation-free implementations of many common data structures without memory costs growing linearly in the number of threads.
Typically, the amount of store logically required is a word, but physically CAS operations on the same cache line will collide, and LL/SC operations in the same exclusive reservation granule will collide, so the amount of store physically required[citation needed] is greater.
However, in 2011 Kogan and Petrank[18] presented a wait-free queue building on the CAS primitive, generally available on common hardware.
A subsequent paper by Timnat and Petrank[21] provided an automatic mechanism for generating wait-free data structures from lock-free ones.
Under reasonable assumptions, Alistarh, Censor-Hillel, and Shavit showed that lock-free algorithms are practically wait-free.