> For the complete documentation index, see [llms.txt](https://isubasinghe.gitbook.io/isithas-wiki/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://isubasinghe.gitbook.io/isithas-wiki/computer_science/data_structures/lock_free_data_structures.md). # Lock-free data structures ## Basic idea Lock-free data structures coordinate threads with atomic operations instead of mutual exclusion. Correctness usually requires linearizability—a concurrent operation appears to take effect at one instant—while the progress condition determines whether the system or every individual thread is guaranteed to advance. ## Key facts * Obstruction-free: a thread completes if it eventually runs alone. * Lock-free: system-wide progress is guaranteed; individual starvation remains possible. * Wait-free: every operation finishes within a bounded number of its own steps. * Compare-and-swap conditionally performs $x\leftarrow n$ when the observed value still equals $o$. * The ABA problem occurs when a location changes $A\to B\to A$ and a CAS cannot detect the intervening change. * Safe reclamation techniques include hazard pointers, epochs, quiescent-state reclamation, and RCU. * A hazard pointer publishes nodes a thread may dereference; retired nodes are freed only after no hazard slot names them. * Epoch reclamation frees nodes once every participating thread has passed through a quiescent epoch after retirement. * RCU separates removal from reclamation and waits for a grace period in which all pre-existing readers have quiesced. * Reclamation must account for the memory model: publishing protection and validating reachability require appropriate ordering. ## Resources