What is compare-and-swap (CAS), and how do classes like AtomicInteger use it to update a value safely without locks?

## The problem CAS solves Suppose two threads both run `count++` on a shared `int`. `count++` is **not atomic** — it is really three steps: (1) read `count` into a register, (2) add 1, (3) write the result back. If thread A reads 5, then thread B reads 5, both compute 6, and both write 6 — one increment is **lost**. This is a *race condition* on a *read-modify-write* (RMW) operation. The classic fix is a **lock** (`synchronized`): only one thread at a time may run the three steps. That works but is *blocking* — a thread that holds the lock and gets descheduled forces every other thread to wait. ## What compare-and-swap is **Compare-and-swap (CAS)** — also called *compare-and-set* in Java — is a single operation the CPU performs **atomically** (indivisibly, as one uninterruptible unit). Conceptually it does: ``` CAS(memoryCell, expectedValue, newValue): if memoryCell == expectedValue: memoryCell = newValue return true // swap succeeded else: return false // someone else changed it; nothing written ``` The key point: the *compare* and the *swap* happen together as one indivisible step that no other thread can interleave with. Modern CPUs expose this as a machine instruction (e.g. `CMPXCHG` on x86, `LL/SC` load-linked/store-conditional on ARM). In Java it surfaces as `boolean compareAndSet(expected, newValue)` on the atomic classes. ## How AtomicInteger uses it (the retry loop) `AtomicInteger.incrementAndGet()` works like this: ```java int current; do { current = get(); // read the latest value int next = current + 1; // compute new value } while (!compareAndSet(current, next)); // try to swap; retry if it failed return next; ``` Walk through the race again. Thread A reads 5, thread B reads 5. Both want to write 6. Suppose B's CAS runs first: the cell is still 5, so `CAS(5, 6)` succeeds, cell becomes 6. Now A's `CAS(5, 6)` runs: the cell is **no longer 5** (it's 6), so A's CAS *returns false*. A loops, re-reads 6, computes 7, and `CAS(6, 7)` succeeds. No increment is lost, and **no lock was ever taken**. This is called **optimistic concurrency**: assume no conflict, do the work, and only redo it if the swap detects a conflict. ## Lock-free and non-blocking Because there is no lock, this style is **lock-free / non-blocking**: a thread that gets descheduled mid-loop cannot block others — the others' CAS attempts simply succeed. The system as a whole always makes progress (some thread always wins each round). Benefits: no deadlock, no lock-acquisition overhead, often better throughput than `synchronized` under low-to-moderate contention. ## The atomic class family - `AtomicInteger`, `AtomicLong` — atomic numeric counters with `incrementAndGet`, `getAndAdd`, `addAndGet`, `getAndSet`, `updateAndGet(IntUnaryOperator)`, `accumulateAndGet`. - `AtomicBoolean` — atomic flag. - `AtomicReference<V>` — atomic update of an object reference; the building block for lock-free data structures. - (`AtomicIntegerArray`/`AtomicReferenceArray` for element-wise atomicity.) `updateAndGet`/`accumulateAndGet` take a function and run the read-compute-CAS loop **for you**, so you express "apply this function atomically" without hand-writing the loop. ## Costs and caveats - **Spin under high contention.** If hundreds of threads hammer one counter, many CAS attempts fail and retry, wasting CPU. For very hot counters prefer `LongAdder`, which spreads updates across multiple cells. - **Only single-variable atomicity.** CAS atomically updates **one** cell. To update two related fields atomically you must put them behind a single `AtomicReference` (e.g. to an immutable holder object) or use a lock. - **The ABA problem.** CAS only checks that the value *equals* the expected value, not that it never changed. If it went A→B→A, a stale CAS(A, …) still succeeds even though the world moved. Mitigated with `AtomicStampedReference` (adds a version stamp). Numeric counters that only ever increase don't hit ABA in practice. - **Visibility.** Atomic-class reads/writes have the same memory-visibility guarantees as `volatile`, so updates are correctly published to other threads.