Compare-And-Swap (CAS) in Java

Compare-and-swap (CAS) is a single CPU instruction that updates a memory location only if it still contains the value you expect. In one indivisible step it says: "if the value is still 5, change it to 6; otherwise tell me it changed". If another thread got there first, the update fails, and the caller simply reads the new value and tries again. This "read, compute, CAS, retry" loop is how Java's atomic classes and many concurrent collections update data without locks. In this lesson, you will see CAS through compareAndSet, write your own CAS loop, and learn its limits.

How a CAS Loop Works

1. Read the current value.
2. Compute the new value from it.
3. CAS: set the new value only if the current value is still what was read.
4. If the CAS failed, another thread changed the value: go back to step 1.

Example: Writing a CAS Loop

Let's see an example that keeps the maximum mark seen by several threads, using a hand-written CAS loop, and counts how often a retry was needed.

import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.atomic.AtomicInteger;
 
public class CasLoop {
    static final AtomicInteger best = new AtomicInteger(0);
    static final AtomicInteger retries = new AtomicInteger(0);
 
    static void offer(int mark) {
        while (true) {
            int current = best.get();
            int next = Math.max(current, mark);
            if (best.compareAndSet(current, next)) {
                return;
            }
            retries.incrementAndGet();
        }
    }
 
    public static void main(String[] args) {
        try (ExecutorService pool = Executors.newFixedThreadPool(4)) {
            for (int t = 0; t < 4; t++) {
                int seed = t;
                pool.submit(() -> {
                    for (int i = 0; i < 100_000; i++) {
                        offer((i * 31 + seed * 7) % 100);
                    }
                });
            }
        }
        System.out.println("Best mark: " + best.get());
        System.out.println("Every offer counted (best is 99)? "
            + (best.get() == 99));
 
        AtomicInteger seat = new AtomicInteger(0);
        System.out.println("Navika books seat 0 -> 1: "
            + seat.compareAndSet(0, 1));
        System.out.println("Srihitha books seat 0 -> 1: "
            + seat.compareAndSet(0, 1));
    }
}

Best mark: 99
Every offer counted (best is 99)? true
Navika books seat 0 -> 1: true
Srihitha books seat 0 -> 1: false

Explanation: Each call to offer reads best, computes the larger value, and tries compareAndSet. If another thread changed best in between, the CAS fails, retries is increased, and the loop tries again with the fresh value, so no update is ever lost and no lock is taken. (How many retries happen depends on timing, so the program doesn't print that number.) In the seat example, the first CAS succeeds because the seat was still 0; the second fails because it is already 1. (updateAndGet and accumulateAndGet run exactly this kind of loop for you.)

CAS vs Locks

The ABA Problem

A CAS only checks that the value is equal to what was read. If another thread changed it from A to B and back to A, the CAS still succeeds, even though things changed in between. For numbers this rarely matters, but for linked data structures it can. AtomicStampedReference solves it by pairing the value with a version number that must also match.

Common Mistakes

Doing slow work or side effects inside a CAS loop. It may run several times; keep it short and pure.

Using CAS for updates that span several variables. Use a lock or one immutable object in an AtomicReference.

Assuming CAS is always faster than a lock. Under very heavy contention, constant retries can be slower.

Interview Corner

Practice

1. Easy: Use compareAndSet to let only the first of three threads "claim" a prize, and print who got it.
2. Harder: Write a lock-free stack (push and pop) using an AtomicReference to the top node and CAS loops.

Key Takeaways