How does Compare-And-Swap work?

• CAS operation – atomically: read the value at a memory address, compare it to an expected value, and if they match, write a new value. If they do not match, the operation fails and the caller retries.
• Hardware instruction – CMPXCHG on x86, LDREX/STREX on ARM. It is a single CPU instruction that cannot be interrupted by another thread.
• Lock-free – no thread is ever BLOCKED. If a CAS fails, the thread reads the new value and retries. Progress is always guaranteed globally (at least one thread succeeds per round).
• Spin loop – AtomicInteger.incrementAndGet() loops: read current, compute new, CAS. If CAS fails (another thread changed the value), repeat with the updated value.
• High contention – with 100 threads CAS-ing the same variable, most attempts fail on each round. The CPU spends cycles on retries rather than useful work.
• ABA problem – value changes A to B to A. CAS checks only the value, not whether it was modified. Fix: AtomicStampedReference pairs the value with a monotonically increasing stamp.

How does Compare-And-Swap work?

CAS is a single CPU instruction that performs three steps atomically: read the current value at a memory address, compare it to an expected value, and if they match, write a new value. If the current value does not match the expected value (meaning another thread changed it), the instruction returns false and the caller must retry.

// Pseudocode for CAS hardware instruction:
// boolean CAS(address, expected, newValue):
//     if memory[address] == expected:
//         memory[address] = newValue
//         return true
//     else:
//         return false   // another thread changed it

How does AtomicInteger use CAS?

package com.bank.concurrency;

import java.util.concurrent.atomic.AtomicInteger;

public class CASDemo {
    private static final AtomicInteger transactionCount = new AtomicInteger(0);

    public static void main(String[] args) throws InterruptedException {
        Runnable task = () -> {
            for (int i = 0; i < 100_000; i++) {
                transactionCount.incrementAndGet();
                // Internally:
                // do {
                //     int prev = get();            // volatile read
                //     int next = prev + 1;          // compute
                // } while (!compareAndSet(prev, next));  // CAS
            }
        };
        Thread t1 = new Thread(task, "Counter-1");
        Thread t2 = new Thread(task, "Counter-2");
        t1.start();
        t2.start();
        t1.join();
        t2.join();
        System.out.println("Count: " + transactionCount.get());  // always 200000
    }
}

Why does CAS spinning hurt under high contention?

With 100 threads all CAS-ing the same AtomicLong, each CAS round has only one winner. The other 99 threads read the new value and retry. On the next round, again only one wins. This means each increment takes roughly 50 attempts on average, wasting 99% of CAS operations.

// High contention scenario:
// 100 threads → AtomicLong.incrementAndGet()
// Round 1: Thread-1 CAS(99→100) succeeds. Threads 2-100: fail, retry.
// Round 2: Thread-2 CAS(100→101) succeeds. Threads 3-100: fail, retry.
// Each thread: ~50 retries on average = massive CPU waste!

What is the ABA problem?

The ABA problem occurs when a value changes from A to B and then back to A. A CAS operation that read A initially succeeds because the current value is still A, even though it was modified and restored. For simple counters this is harmless, but for pointer-based data structures like lock-free stacks, ABA can cause corruption.

package com.bank.concurrency;

import java.util.concurrent.atomic.AtomicStampedReference;

public class ABAFixDemo {
    public static void main(String[] args) {
        // AtomicStampedReference: CAS on BOTH value AND stamp
        AtomicStampedReference<String> ref =
                new AtomicStampedReference<>("SAV2001", 0);

        int[] stampHolder = new int[1];
        String current = ref.get(stampHolder);  // value="SAV2001", stamp=0

        // Another thread changes SAV2001 → CUR3001 → SAV2001 (ABA!)
        ref.compareAndSet("SAV2001", "CUR3001", 0, 1);  // stamp: 0→1
        ref.compareAndSet("CUR3001", "SAV2001", 1, 2);  // stamp: 1→2

        // Our CAS: expects stamp=0, but stamp is now 2 → FAILS (detects ABA!)
        boolean success = ref.compareAndSet("SAV2001", "FD4001", 0, 1);
        System.out.println("CAS success: " + success);  // false: stamp mismatch
    }
}

What are the fixes for high-contention CAS spinning?

Three strategies reduce contention:

• LongAdder – striped cells so each thread CAS-es its own cell with zero contention.
• Exponential backoff – after a failed CAS, sleep for a random duration that doubles with each retry, reducing the collision rate.
• Partitioned ranges – assign each thread a range of sequence numbers (Thread-1: 0-999, Thread-2: 1000-1999) so no CAS contention occurs at all.

How is CAS different from synchronized?

| Aspect | CAS (lock-free) | synchronized (blocking) |
|---|---|---|
| Blocking | Never | Yes (thread parks) |
| Context switch | None | Yes (park/unpark) |
| Low contention | Very fast (one CAS) | Fast (biased/thin lock) |
| High contention | CPU spinning (waste) | Thread parks (less CPU waste) |
| Deadlock possible? | No | Yes |
| Progress guarantee | Lock-free (global progress) | Blocking (no guarantee) |

What are common interview follow-up questions?

• Is CAS wait-free? No, it is lock-free. Lock-free guarantees that at least one thread makes progress in every round. Wait-free would guarantee that every thread makes progress in bounded steps. AtomicInteger.incrementAndGet() is lock-free but not wait-free.
• What CPU instruction implements CAS? CMPXCHG on x86 (with LOCK prefix for multi-core), LDREX/STREX on ARM, LL/SC on MIPS.