Atomic Classes and CAS

This lesson covers the atomic classes in java.util.concurrent.atomic and the compare-and-set (CAS) operation they are built on. After it, a reader can write a lock-free counter or state machine, pick between AtomicLong and LongAdder, and explain the ABA problem. It uses the happens-before rules from Happens-Before and volatile: every atomic get has volatile read semantics and every set or successful CAS has volatile write semantics.

API or idea	Use
`AtomicInteger`, `AtomicLong`	Lock-free counters and sequence numbers
`AtomicReference<V>`	Lock-free replacement of an object reference
`compareAndSet(expected, new)`	Write only if the current value equals `expected`
`updateAndGet`, `accumulateAndGet`	CAS loop with a function
`LongAdder`	Counter split across cells for high contention
`AtomicIntegerFieldUpdater`	CAS on a `volatile int` field without a wrapper object
`AtomicStampedReference`	Reference plus an `int` stamp, against ABA

Compare-and-set

CAS is a single CPU instruction (lock cmpxchg on x86, cas or an ldaxr/stlxr pair on ARMv8) that does this atomically: if the memory location holds expected, store new and report success; otherwise change nothing and report failure. A thread whose CAS fails reads the new value and tries again. This retry pattern is a CAS loop.

Example 1: AtomicInteger counter

incrementAndGet makes the read-add-write of count++ one atomic step.

Java

import java.util.concurrent.atomic.AtomicInteger;

public class AtomicCounter {
    public static void main(String[] args) throws InterruptedException {
        AtomicInteger count = new AtomicInteger();
        Thread[] threads = new Thread[4];
        for (int t = 0; t < 4; t++) {
            threads[t] = new Thread(() -> {
                for (int i = 0; i < 100_000; i++) count.incrementAndGet();
            });
            threads[t].start();
        }
        for (Thread t : threads) t.join();
        System.out.println("count = " + count.get());
    }
}

Output

count = 400000

On x86 HotSpot compiles incrementAndGet to one lock xadd instruction, with no retry loop. AtomicLong has the same API for long. Other common methods: getAndIncrement, addAndGet, getAndSet, and compareAndSet.

Example 2: writing a CAS loop by hand

A CAS loop reads the current value, computes a new one, and retries if another thread changed the value in between. This example keeps the highest value ever seen.

Java

import java.util.concurrent.atomic.AtomicLong;

public class MaxTracker {
    private final AtomicLong max = new AtomicLong(Long.MIN_VALUE);

    void record(long value) {
        long current = max.get();
        while (value > current) {
            if (max.compareAndSet(current, value)) {
                return;                    // we won
            }
            current = max.get();           // lost the race: re-read and retry
        }
    }

    public static void main(String[] args) throws InterruptedException {
        MaxTracker tracker = new MaxTracker();
        Thread[] threads = new Thread[4];
        for (int t = 0; t < 4; t++) {
            int base = t * 1_000;
            threads[t] = new Thread(() -> {
                for (int i = 0; i < 1_000; i++) tracker.record(base + i);
            });
            threads[t].start();
        }
        for (Thread t : threads) t.join();
        System.out.println("max latency seen = " + tracker.max.get());
    }
}

Output

max latency seen = 3999

The loop exits early when the stored value is already larger, so most calls do no write at all. Each failed CAS means another thread made progress, which is the property that defines lock-free code (see the table at the end).

Example 3: updateAndGet and accumulateAndGet

Since Java 8 the atomic classes run the CAS loop for a function given as a lambda.

Java

import java.util.concurrent.atomic.AtomicLong;

public class FunctionalUpdates {
    public static void main(String[] args) {
        AtomicLong max = new AtomicLong(0);
        long[] samples = {120, 450, 90, 700, 300};
        for (long s : samples) {
            max.accumulateAndGet(s, Math::max);
        }
        System.out.println("max = " + max.get());

        AtomicLong budget = new AtomicLong(1_000);
        long left = budget.updateAndGet(v -> Math.max(0, v - 1_500)); // clamp at zero
        System.out.println("budget left = " + left);
    }
}

Output

max = 700
budget left = 0

The function may run more than once when the CAS fails, so it must be free of side effects. It should also be cheap: a slow function widens the window in which another thread can change the value and force a retry.

Example 4: AtomicReference for immutable state

AtomicReference<V> holds a reference with the same CAS operations. Paired with an immutable record, it updates several values together without a lock.

Java

import java.util.concurrent.atomic.AtomicReference;

public class PositionTracker {
    record Position(long qty, long notional) {
        Position fill(long q, long price) {
            return new Position(qty + q, notional + q * price);
        }
    }

    public static void main(String[] args) throws InterruptedException {
        AtomicReference<Position> pos = new AtomicReference<>(new Position(0, 0));
        Thread[] threads = new Thread[4];
        for (int t = 0; t < 4; t++) {
            threads[t] = new Thread(() -> {
                for (int i = 0; i < 1_000; i++) {
                    pos.updateAndGet(p -> p.fill(10, 100));
                }
            });
            threads[t].start();
        }
        for (Thread t : threads) t.join();
        Position p = pos.get();
        System.out.println("qty = " + p.qty() + ", notional = " + p.notional());
    }
}

Output

qty = 40000, notional = 4000000

qty and notional always change together because the whole record is replaced in one CAS. compareAndSet on AtomicReference compares references with ==, not equals. Each update allocates a new record, which is the cost of this pattern.

Example 5: LongAdder under contention

When many threads CAS the same variable, most attempts fail and the cache line holding it moves between cores on every write (Cache Coherence and False Sharing). LongAdder spreads updates across an array of cells, one per contending thread on average, and sum() adds them up.

Java

import java.util.concurrent.atomic.LongAdder;

public class RequestCounter {
    public static void main(String[] args) throws InterruptedException {
        LongAdder requests = new LongAdder();
        Thread[] threads = new Thread[8];
        for (int t = 0; t < 8; t++) {
            threads[t] = new Thread(() -> {
                for (int i = 0; i < 50_000; i++) requests.increment();
            });
            threads[t].start();
        }
        for (Thread t : threads) t.join();
        System.out.println("requests = " + requests.sum());
    }
}

Output

requests = 400000

	`AtomicLong`	`LongAdder`
Write under contention	Slows down, CAS retries	Scales, threads hit different cells
Read	One volatile read	Sums all cells
Exact read during updates	Yes	No, `sum()` is not an atomic snapshot
Supports CAS, `getAndIncrement`	Yes	No
Memory	One field	Grows up to about the number of CPUs

LongAdder fits metrics and statistics counters. Sequence numbers and IDs need AtomicLong, because each caller needs a unique value. LongAccumulator generalizes the idea to any associative function, such as Math::max.

Example 6: AtomicIntegerFieldUpdater

An AtomicInteger is a separate object with its own header. A class with millions of instances can instead keep a volatile int field and use a static field updater, which performs CAS on that field through reflection-checked access.

Java

import java.util.concurrent.atomic.AtomicIntegerFieldUpdater;

public class Connection {
    private static final int OPEN = 0, CLOSED = 1;

    private static final AtomicIntegerFieldUpdater<Connection> STATE =
            AtomicIntegerFieldUpdater.newUpdater(Connection.class, "state");

    private volatile int state = OPEN;   // must be volatile int
    private final String name;

    Connection(String name) { this.name = name; }

    boolean close() {
        if (STATE.compareAndSet(this, OPEN, CLOSED)) {
            System.out.println(name + " closed");
            return true;
        }
        return false;
    }

    public static void main(String[] args) throws InterruptedException {
        Connection c = new Connection("db-1");
        int[] wins = new int[4];
        Thread[] threads = new Thread[4];
        for (int t = 0; t < 4; t++) {
            int idx = t;
            threads[t] = new Thread(() -> wins[idx] = c.close() ? 1 : 0);
            threads[t].start();
        }
        for (Thread t : threads) t.join();
        System.out.println("successful closes = " + (wins[0] + wins[1] + wins[2] + wins[3]));
    }
}

Output

db-1 closed
successful closes = 1

Only one thread wins the CAS from OPEN to CLOSED, so cleanup runs exactly once. The field must be volatile and of type int (there are AtomicLongFieldUpdater and AtomicReferenceFieldUpdater for the others), or newUpdater throws. JDK classes such as BufferedInputStream use this pattern. VarHandle, Access Modes, and Fences shows the newer replacement.

Example 7: the ABA problem and AtomicStampedReference

ABA happens when a thread reads value A, another thread changes it to B and back to A, and the first thread's CAS succeeds because it sees A again, although the state behind A changed. The example simulates the interleaving in one thread so the output is fixed.

Java

import java.util.concurrent.atomic.AtomicReference;
import java.util.concurrent.atomic.AtomicStampedReference;

public class AbaDemo {
    public static void main(String[] args) {
        String a = "A", b = "B";

        AtomicReference<String> ref = new AtomicReference<>(a);
        String seen = ref.get();                 // thread 1 reads A
        ref.set(b);                              // thread 2: A -> B
        ref.set(a);                              // thread 2: B -> A
        boolean plain = ref.compareAndSet(seen, "C"); // thread 1 resumes
        System.out.println("plain CAS succeeded: " + plain);

        AtomicStampedReference<String> sref = new AtomicStampedReference<>(a, 0);
        int[] stampHolder = new int[1];
        String seenRef = sref.get(stampHolder);  // thread 1 reads A, stamp 0
        int seenStamp = stampHolder[0];
        sref.compareAndSet(a, b, 0, 1);          // thread 2: A -> B
        sref.compareAndSet(b, a, 1, 2);          // thread 2: B -> A
        boolean stamped = sref.compareAndSet(seenRef, "C", seenStamp, seenStamp + 1);
        System.out.println("stamped CAS succeeded: " + stamped + ", stamp now " + sref.getStamp());
    }
}

Output

plain CAS succeeded: true
stamped CAS succeeded: false, stamp now 2

In a lock-free stack, ABA can corrupt the list: thread 1 reads head A with next B, other threads pop A and B and push A back, and thread 1's CAS sets head to the removed B. The stamp, a version counter changed on every update, makes the second CAS fail. In Java, ABA on node reuse is rarer than in C because the garbage collector does not reuse a node's memory while any thread still holds a reference; it appears with object pools, interned values, and indices. AtomicMarkableReference is the variant with a boolean mark instead of an int.

Progress guarantees

Guarantee	Definition	Example
Blocking	A suspended thread can stop all others	`synchronized`, `ReentrantLock`
Obstruction-free	A thread finishes if it runs alone for long enough	Some software transactional memory designs
Lock-free	Some thread always finishes in a finite number of steps	CAS loops, `ConcurrentLinkedQueue`
Wait-free	Every thread finishes in a bounded number of steps	`getAndAdd` compiled to `lock xadd` on x86, `LongAdder.increment` is close

A CAS loop is lock-free but not wait-free: one thread can lose every race for a long time. Lock-free does not mean faster; under low contention a lock costs about the same as a CAS, and under heavy contention CAS loops waste work on retries.

Interview points

CAS writes only if the current value equals the expected one; a failed CAS means another thread made progress.
Atomic get and set have volatile semantics; compareAndSet is a volatile read and write together.
updateAndGet lambdas must be side-effect free because they may run several times.
LongAdder beats AtomicLong for write-heavy counters, but sum() is not an atomic snapshot and it has no CAS.
Field updaters avoid a wrapper object per instance; the field must be volatile and of the exact type.
ABA lets a CAS succeed on a recycled value; a stamp or version fixes it.
Lock-free guarantees system progress, wait-free guarantees per-thread progress.

Summary

AtomicInteger, AtomicLong, and AtomicReference provide lock-free read-modify-write.
AtomicReference plus an immutable record updates several values together.
AtomicReference.compareAndSet compares by identity.
AtomicStampedReference pairs a reference with an int stamp.
Contended CAS costs cache-line transfers and retries; LongAdder avoids them by striping.