lockfree

Lock-free is a property of concurrent algorithms and data structures that allows multiple threads to operate without using mutual-exclusion locks. In a lock-free design, the system guarantees that some thread makes progress in a finite number of steps, even if other threads are delayed or fail. This contrasts with lock-based synchronization, where a thread holding a lock can prevent progress for others.

Lock-free is a form of non-blocking synchronization. It is related to, but distinct from, wait-free and obstruction-free progress guarantees. The term is often used in conjunction with atomic primitives such as compare-and-swap, load-linked/store-conditional, and fetch-and-add, which provide the atomicity needed to build non-blocking algorithms.

Common lock-free data structures include stacks, queues, and linked lists implemented with pointer manipulation and atomic updates. Notable examples include the Michael-Scott queue and the Treiber stack. Designing correct lock-free structures requires attention to issues such as the ABA problem and memory reclamation, since nodes may be reused while other threads still hold references. Techniques such as hazard pointers and epoch-based reclamation address these concerns.

Advantages of lock-free approaches include resilience to thread delays, bounded pause times, and reduced risk of priority inversion. Disadvantages include greater implementation complexity, potential performance variability under contention, and subtle correctness pitfalls. They are often favored in real-time and high-concurrency environments, where predictable latency is important.

See also: non-blocking synchronization, wait-free, concurrent data structure, memory reclamation.