There are two types of non-blocking thread synchronization algorithms – lock-free, and wait-free. Their meaning is often confused. In lock-free systems, while any particular computation may be blocked for some period of time, all CPUs are able to continue performing other computations. To put it differently, while a given thread might be blocked by other threads in a lock-free system, all CPUs can continue doing other useful work without stalls. Lock-free algorithms increase the overall throughput of a system by occassionally increasing the latency of a particular transaction. Most high-end database systems are based on lock-free algorithms, to varying degrees.
By contrast, wait-free algorithms ensure that in addition to all CPUs continuing to do useful work, no computation can ever be[Read more...]