Skip to content

Compare-and-swap

Category: Lock-free · Status: stub · Lessons: chapter 02, Shared state

One line: 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.

Also called: CAS, compare-exchange, compare-and-set.

How it connects

flowchart LR
  n_aba_problem["ABA problem"]
  n_compare_and_swap["Compare-and-swap"]
  n_concurrent_data_structures["Concurrent data structures"]
  n_lock_free["Lock-free"]
  n_toctou["Time of check to time of use"]
  n_compare_and_swap -->|can cause| n_aba_problem
  n_compare_and_swap -->|prevents| n_toctou
  n_concurrent_data_structures -->|uses| n_compare_and_swap
  n_lock_free -->|uses| n_compare_and_swap
  classDef center stroke-width:3px
  class n_compare_and_swap center
  classDef outside stroke-dasharray: 4 3
  class n_aba_problem,n_concurrent_data_structures,n_lock_free,n_toctou outside

In each language
Rust compare_exchange ↗, and compare_exchange_weak ↗, which may fail spuriously even when the comparison succeeds
Go CompareAndSwap ↗ on the typed values, returning whether it swapped
C atomic_compare_exchange_strong and atomic_compare_exchange_weak ↗; the weak forms may fail spuriously
C++ compare_exchange_strong and compare_exchange_weak ↗; the weak one may fail spuriously
Java AtomicInteger.compareAndSet ↗ and its siblings in java.util.concurrent.atomic
C# Interlocked.CompareExchange ↗ compares two values and, if they are equal, replaces one as an atomic operation
JavaScript Atomics.compareExchange ↗ on a shared typed array
Swift Atomic.compareExchange(expected:desired:ordering:) ↗

Where to read more