How do Compare-And-Swap (CAS) algorithms and lock-free data structures work?

Short answer

CAS uses an atomic processor instruction to compare a memory location with an expected value and replace it with a new value if they match. If the operation fails, the thread retries without acquiring a lock.

Explanation

Traditional locks put a thread to sleep when there is contention, at the cost of an expensive context switch. Atomic variables (such as Java's AtomicInteger or C++'s std::atomic) use a lightweight retry loop (CAS Loop): the thread reads the current value, calculates a new value, and runs CAS. If another thread changed the value at the same instant, the instruction fails, so the thread retries and reads the updated value, providing high throughput.

Code example

// Concept of a lock-free atomic CAS loop:
do {
  current = value.get();
  next = current + 1;
} while (!value.compareAndSet(current, next));

Common mistakes

• CAS algorithms are vulnerable to the ABA problem: a value changes from A to B and then back to A, so a thread does not detect that the contents changed.

Follow-up questions

• What is the memory visibility problem, and what do the volatile keyword and memory barriers do?

Sources

• Compare-and-swap - Wikipedia