Skip to content

Lock-free

Sharing without locks: atomic operations, the algorithms built on them, and the memory rules that decide what one thread can see of another's writes.

All categories · How they connect

  • Atomic variable — A number or pointer whose reads, writes and increments each happen as one indivisible CPU operation, so threads can share it without a lock.
  • Compare-and-swap — Replace a value only if it still holds what you last read, in one atomic step; if another thread changed it first, read again and retry.
  • Lock-free — A progress guarantee for a shared data structure: however the threads are scheduled, some thread always completes an operation, and there is no lock to deadlock on.
    • Wait-free — Stronger than lock-free: every thread finishes its own operation in a bounded number of its own steps, whatever the other threads do.
  • Read-copy-update — Readers use shared data without any lock while a writer publishes a modified copy, and the old version is freed only after every reader that might still see it has finished.
  • Happens-before — The rule a memory model states for when one thread is guaranteed to see another thread's write: only when synchronization orders the write before the read.
  • Hazard pointers — Each thread publishes the pointers it is about to use, and memory is freed only when no thread has it published — safe memory reclamation for lock-free data structures.
  • Transactional memory — Running a block of memory reads and writes as a transaction that either commits atomically or rolls back and retries, instead of taking locks.
  • Concurrent data structures — Queues, maps, stacks and lists built to be used by many threads at once — with locks inside, lock-free algorithms, or both — so that their callers need no synchronization of their own.

Inside this category

flowchart LR
  n_atomic_variable["Atomic variable"]
  n_compare_and_swap["Compare-and-swap"]
  n_concurrent_data_structures["Concurrent data structures"]
  n_lock_free["Lock-free"]
  n_rcu["Read-copy-update"]
  n_wait_free["Wait-free"]
  n_concurrent_data_structures -->|uses| n_compare_and_swap
  n_lock_free -->|uses| n_atomic_variable
  n_lock_free -->|uses| n_compare_and_swap
  n_rcu -->|uses| n_atomic_variable
  n_wait_free -->|is a| n_lock_free