The number of commodity
PCs being manufactured with the capability to run more than one process at a time, either through multiple processors (
SMP), multiple cores on one processor (
CMP), or
multiple functional units, is rising, and will continue to rise as the
CPU industry reaches the limit on the amount of power a single CPU can pack.
In recognition of this fact, much research has been turned toward solving the problem of efficiently and easily writing multi-threaded code. Traditional lock-based synchronization, while easy in theory, is difficult to efficiently implement in practice. It is prone to various and sundry problems, including deadlock, starvation, priority inversion, and lock convoying. Avoiding these problems in a reasonably complex system while still keeping the locking fine-grained enough to be efficient is somewhere between non-trivial and impossible, depending on the complexity of the system.
Non-blocking synchronization is the name given to a class of algorithms that implement synchronization without the use of mutual exclusion (locks). These algorithms typically use atomic primitives in the architecture, such as compare-and-swap (CAS) or load-locked/store-conditional. For example, a typical use of CAS is to read a value from an address, perform a multi-step computation on the value, and (atomically) CAS the new value back to the address, conditional on the old value still being there. If the CAS succeeds, it appears as though the entire operation were performed atomically.
There are three subclasses of non-blocking synchronization: wait-freedom, lock-freedom, and obstruction-freedom, in order of strength. Wait-freedom guarantees that every thread makes progress in a bounded number of steps. Lock-freedom guarantees that some thread makes progress in a bounded number of steps. Obstruction-freedom guarantees that some thread makes progress in a bounded number of steps if it runs in isolation (i.e., if all other running threads are suspended).
While ad-hoc non-blocking implementations of various data structures exist, most current research is directed towards developing generalized non-blocking synchronization methods, i.e. replacing locks entirely, using non-blocking techniques.
M. Herlihy, V. Luchangco and M. Moir. "Obstruction-Free Synchronization: Double-Ended Queues as an Example." 23rd International Conference on Distributed Computing Systems, 2003, p.522.