Lock Free Concurrency: Compare and Swap, Atomic Variables, and Volatile

Two Ways to Handle Concurrency

When multiple threads need to work with shared data at the same time, you have two fundamentally different approaches available to you in Java. This is a classic interview question: in how many ways can you achieve thread safety?

The first approach is lock based concurrency. You use mechanisms like synchronized, ReentrantLock, ReadWriteLock, StampedLock, and so on. These tools force threads to take turns. One thread grabs the lock, does its work, and releases the lock. Every other thread just waits outside the door.

The second approach is lock free concurrency. No thread is ever blocked waiting for another. Instead, threads use a clever hardware level trick to update shared data safely without ever sitting idle. This is what AtomicInteger, AtomicBoolean, AtomicReference, and friends are built on.

Understanding both approaches deeply, knowing when to use each, and knowing the tradeoffs is exactly what distinguishes a senior Java developer from someone who just learned the synchronized keyword.

---

The Problem With Locks

Before you can appreciate lock free concurrency, you need to understand what is actually painful about locks.

Imagine a shared counter. Ten threads all want to increment it. With a synchronized method, only one thread can be inside that method at a time. Thread one enters, reads the value, adds one, writes it back, exits. Thread two can now enter. Thread three is still waiting.

This blocking has real costs:

Thread context switching is expensive. When a thread cannot acquire a lock, the operating system parks it and switches to another thread. That switch costs time. On a busy system with many threads fighting over the same lock, you can spend more CPU time switching between threads than actually doing work.

Priority inversion can occur. A high priority thread might be stuck waiting because a low priority thread holds a lock and got preempted before releasing it.

Deadlocks are possible. Thread A holds lock 1 and wants lock 2. Thread B holds lock 2 and wants lock 1. Neither ever moves.

Starvation. One thread keeps losing the race to acquire the lock and never makes progress.

Lock free concurrency sidesteps all of these problems. But how?

---

Optimistic Locking: The Inspiration

Before jumping to the CPU level, consider a pattern you might already know from databases: optimistic locking.

In a database, you have a row with a row_version column. When thread one reads a row, it notes the current row_version, say it is 1. When thread two also reads that row, it also notes row_version is 1.

Now thread one wants to update the row. It runs:

UPDATE users SET name = 'Raj K' WHERE id = 123 AND row_version = 1

Because the row version is still 1, this succeeds. The database also increments row_version to 2.

Now thread two tries its update:

UPDATE users SET name = 'Ravi' WHERE id = 123 AND row_version = 1

But the row version is now 2, not 1. This update affects zero rows. Thread two knows it lost the race and tries again, reading the fresh data from the start.

Nobody blocked. Nobody waited at a lock. Both threads ran freely and the one whose update was stale simply retried.

This is the spirit of lock free concurrency. Compare and Swap is the CPU level version of exactly this idea.

---

Compare and Swap: The Core Idea

Compare and Swap, abbreviated CAS, is a single CPU instruction available on modern processors. Java exposes it through its Atomic classes.

Here is the idea in plain English: you want to update a value in memory. Before you write the new value, you first check whether the current value in memory still matches what you expected. If yes, you write the new value. If no, the update fails because someone else changed it first.

The critical part: the check and the write happen atomically, as a single uninterruptible CPU operation. The hardware guarantees that no other thread can sneak in between the check and the write.

Think of it like a vault with a combination that you set yourself. You say to the vault: "If the combination is still 1234, change it to 5678." The vault checks and changes in one locked mechanical motion. Nothing can interrupt that motion from outside.

In pseudocode, CAS looks like this:

boolean compareAndSwap(memoryAddress, expectedValue, newValue) {
    if (currentValueAt(memoryAddress) == expectedValue) {
        setValueAt(memoryAddress, newValue)
        return true   // success
    } else {
        return false  // someone else changed it, try again
    }
}

When CAS returns false, you loop back, read the current value fresh from memory, compute your new value again, and try CAS once more. This loop is sometimes called a spin loop or CAS loop.

---

Hardware Support for CAS

CAS is not Java magic. It is a real CPU instruction. On x86 processors the instruction is called CMPXCHG (compare and exchange). On ARM it is a pair of instructions called LDREX and STREX (load exclusive and store exclusive).

The CPU marks a memory location as being "monitored" during the read. If any other core writes to that location before your store instruction runs, your store fails and you know you need to retry.

Because this happens at the hardware level, there is no operating system involvement. No thread is ever parked. No context switch happens. The failing thread just loops back and tries again immediately. This is dramatically faster than acquiring a mutex when contention is low.

Inside the JDK, CAS is reached through low-level internal APIs (jdk.internal.misc.Unsafe, and VarHandles since Java 9), which the JIT compiles down to that single CPU instruction. You do not call these yourself. The java.util.concurrent.atomic package wraps them in safe, clean classes that you actually use.

---

AtomicInteger: The Workhorse

AtomicInteger is the most commonly used atomic class. It represents an integer value that can be updated safely from multiple threads without synchronization.

Here is a demonstration of the problem it solves:

public class UnsafeCounter {
    private int counter = 0;

    // NOT thread safe
    public void increment() {
        counter++;   // read, add, write: three steps, not one
    }

    public int get() {
        return counter;
    }
}

You might run this from two threads, each calling increment() 200 times, and expect a final value of 400. But you will often get something like 387 or 392 because the read/add/write sequence is not atomic. Two threads can read the same value, both add one to it, and both write back the same incremented value, effectively losing one increment.

Now the thread safe version using AtomicInteger:

import java.util.concurrent.atomic.AtomicInteger;

public class SafeCounter {
    // AtomicInteger wraps an int and uses CAS internally
    private AtomicInteger counter = new AtomicInteger(0);

    public void increment() {
        counter.incrementAndGet();  // atomic: no data race possible
    }

    public int get() {
        return counter.get();
    }
}

Run this from two threads each calling increment() 200 times and you will always get exactly 400.

Key AtomicInteger Methods

AtomicInteger ai = new AtomicInteger(0);

// Get current value
int value = ai.get();

// Set a new value
ai.set(42);

// Increment by one and return the new value
int newVal = ai.incrementAndGet();   // like ++i

// Increment by one and return the old value
int oldVal = ai.getAndIncrement();   // like i++

// Add a specific amount and return new value
int result = ai.addAndGet(5);

// The raw CAS operation: if current == 10, set to 20, return success flag
boolean success = ai.compareAndSet(10, 20);

The compareAndSet method is the direct exposure of the CAS instruction. You say: "if the current value is 10, change it to 20." It returns true if the swap happened and false if it did not.

How incrementAndGet Works Internally

Let us look inside incrementAndGet to see the CAS loop:

// Simplified version of what AtomicInteger does internally
public int incrementAndGet() {
    while (true) {
        int expectedValue = this.value;     // read current value from memory
        int newValue = expectedValue + 1;   // compute desired new value

        // Try to atomically swap expectedValue for newValue
        if (compareAndSwap(this.value, expectedValue, newValue)) {
            return newValue;   // CAS succeeded, we are done
        }
        // CAS failed: another thread changed the value between our read and swap
        // Loop back and try again with the fresh value
    }
}

Thread one reads value 0 and computes new value 1. Thread two reads value 0 and computes new value 1. Thread one successfully CAS swaps 0 to 1. Returns 1. Thread two tries to CAS swap 0 to 1, but memory now holds 1, not 0. CAS fails. Thread two loops back, reads 1, computes 2, CAS swaps 1 to 2. Returns 2.

The final result is 2, which is correct.

Note that the value field inside AtomicInteger is declared volatile. This guarantees every thread sees the latest written value. More on volatile shortly.

---

AtomicBoolean: Safe Flags

AtomicBoolean solves the problem of a shared boolean flag that multiple threads need to read and write safely.

A classic use case is a "shutdown requested" flag:

import java.util.concurrent.atomic.AtomicBoolean;

public class ServiceManager {
    private final AtomicBoolean shutdownRequested = new AtomicBoolean(false);

    public void requestShutdown() {
        shutdownRequested.set(true);
    }

    public boolean isShutdownRequested() {
        return shutdownRequested.get();
    }

    public void runLoop() {
        while (!shutdownRequested.get()) {
            // do work
        }
        System.out.println("Shutting down cleanly");
    }
}

Another critical use case is one time initialization. Suppose you want exactly one thread to initialize a resource even if fifty threads all check and try to initialize simultaneously:

private final AtomicBoolean initialized = new AtomicBoolean(false);

public void initializeOnce() {
    // compareAndSet returns true only for the one thread that
    // successfully changes false to true
    if (initialized.compareAndSet(false, true)) {
        // Only ONE thread ever enters here
        performExpensiveInitialization();
    }
}

This is elegant. Fifty threads all call initializeOnce(). All fifty hit compareAndSet(false, true). But only one wins: the one that atomically flips false to true first. The other 49 see false returned and skip the initialization entirely. No lock needed.

---

AtomicReference: Safe Object References

AtomicReference<T> does for object references what AtomicInteger does for ints. It lets you atomically update a reference to an object.

import java.util.concurrent.atomic.AtomicReference;

public class UserCache {
    private final AtomicReference<String> currentUser = new AtomicReference<>("guest");

    public void login(String username) {
        // Atomically replace "guest" with the actual username
        currentUser.compareAndSet("guest", username);
    }

    public String getCurrentUser() {
        return currentUser.get();
    }

    public void logout() {
        // Atomically replace current user with "guest"
        String user = currentUser.get();
        currentUser.compareAndSet(user, "guest");
    }
}

AtomicReference is also commonly used to build lock free data structures. Instead of locking a linked list to add a node, you CAS the head pointer from the old head to a new node that points to the old head. If another thread changed the head between your read and your CAS, you retry.

---

The ABA Problem

There is a subtle pitfall with CAS on references called the ABA problem. This is a genuine interview question.

Imagine a memory location holds value A. Thread one reads A and is about to CAS it to C. Before thread one runs its CAS, thread two changes the value from A to B, then back to A again.

Thread one runs its CAS. It sees A in memory. It expected A. The CAS succeeds. Thread one is happy.

But thread one is wrong to be happy. The state of the system may have changed in a meaningful way even though the raw value looks the same. For example, in a lock free stack, if the top node is removed and then a new node with the same memory address is pushed, a CAS checking the pointer address alone would not notice that the stack changed entirely.

Solution: use AtomicStampedReference.

AtomicStampedReference<T> pairs the reference with an integer stamp (typically a version number). Every update increments the stamp. Now CAS checks both the reference and the stamp. Even if the reference returns to A, the stamp will be different (A with stamp 2 is not equal to A with stamp 1), so the ABA problem is detected and the CAS fails correctly.

import java.util.concurrent.atomic.AtomicStampedReference;

AtomicStampedReference<String> ref = new AtomicStampedReference<>("A", 0);

int[] stampHolder = new int[1];
String current = ref.get(stampHolder);   // reads value AND stamp
int currentStamp = stampHolder[0];

// Only succeeds if both value AND stamp match
boolean success = ref.compareAndSet(current, "C", currentStamp, currentStamp + 1);

---

The volatile Keyword: Visibility, Not Atomicity

Now for a keyword that is frequently misunderstood and regularly appears in interviews: volatile.

First, understand what problem volatile solves. To run fast, the JIT compiler may keep a variable in a CPU register, and the compiler and CPU may reorder reads and writes. Without any rule forcing it, nothing guarantees when (or whether) a write by one thread becomes visible to another thread.

This means thread one might update a variable, but thread two keeps seeing the old value. Thread two is seeing stale data. This is a visibility problem.

volatile solves exactly this problem. The Java Memory Model guarantees that a write to a volatile field happens-before every later read of that field: every read sees the most recent write, and writes made before the volatile write cannot be reordered after it. (A simple mental model: volatile reads and writes are never served from a stale private copy.)

public class StopFlag {
    // Without volatile, the worker thread might never see this change
    // because it may keep reading a stale copy
    private volatile boolean stopped = false;

    public void stop() {
        stopped = true;   // visible to every thread that reads it afterwards
    }

    public void run() {
        while (!stopped) {   // always sees the latest write
            doWork();
        }
    }
}

Without volatile, the JIT is allowed to keep stopped in a register for the worker thread. The worker might spin forever even after the main thread sets stopped = true.

volatile Does NOT Give You Atomicity

This is the critical interview point. Repeat it clearly: volatile provides visibility, not atomicity.

Consider this:

private volatile int counter = 0;

// Called from multiple threads
public void increment() {
    counter++;   // STILL NOT THREAD SAFE even with volatile
}

The counter++ operation is three steps: read the value, add one, write the value back. Even with volatile, two threads can both read the same value (both read 5), both compute 6, and both write 6 back. You lost an increment. The result is 6 when it should be 7.

volatile guarantees that each read sees the latest write. It does not guarantee that the entire read/increment/write sequence is uninterruptible. That guarantee requires either AtomicInteger (CAS) or synchronized.

---

volatile vs synchronized vs Atomic: When to Use Each

Concern	volatile	synchronized	Atomic classes
Visibility (thread sees fresh value)	Yes	Yes	Yes
Atomicity (read/modify/write)	No	Yes	Yes
Blocks other threads	No	Yes	No
Performance	Very fast	Moderate	Fast
Deadlock possible	No	Yes	No

Use volatile when:

• You have a simple flag that one thread writes and other threads read.
• You never need compound operations like read/increment/write.
• You want to publish a reference to a safely constructed object to other threads.
• Example: volatile boolean shutdownRequested

Use synchronized when:

• You need to execute a block of multiple statements atomically.
• You need to wait on a condition (using wait/notify).
• The work inside the lock is substantial enough that the overhead does not matter.
• Example: a method that reads a value, makes a decision based on it, and writes a new value.

Use Atomic classes when:

• You need single variable atomicity without the overhead of a lock.
• High throughput is critical and you cannot afford thread blocking.
• You are implementing lock free algorithms or data structures.
• Example: a counter shared across threads, a one time flag, a versioned reference.

---

volatile Inside AtomicInteger

If you look at the source of AtomicInteger, the internal value field is declared volatile:

public class AtomicInteger extends Number {
    private volatile int value;   // volatile guarantees fresh reads for CAS
    
    // ...
}

This is intentional. The CAS loop reads the current value at the start of each iteration, and that read must see the latest value written by any thread.

So volatile and CAS work together here. volatile handles the visibility concern. CAS handles the atomicity concern. Together they make AtomicInteger both correct and lock free.

---

Concurrent Collections: A Brief Note

The same lock free principles power the concurrent collections in java.util.concurrent. ConcurrentHashMap, for example, uses CAS for its internal bucket head pointer updates. When adding an entry to an empty bucket, it CAS swaps the bucket head from null to the new node. No lock is needed for that operation at all. Locks are only acquired for more complex scenarios.

You will notice that ConcurrentHashMap has dramatically better throughput than a Collections.synchronizedMap wrapper under high concurrency, precisely because it uses lock free CAS wherever possible and only falls back to fine grained locks when necessary.

---

Common Mistakes and Pitfalls

Pitfall 1: Thinking volatile makes operations atomic.

private volatile int count = 0;
count++;   // Still a data race! Use AtomicInteger.

Pitfall 2: Using AtomicInteger for multi variable invariants.

AtomicInteger x = new AtomicInteger(0);
AtomicInteger y = new AtomicInteger(0);
// These two increments are individually atomic but NOT together atomic
x.incrementAndGet();
y.incrementAndGet();
// Another thread could see x=1, y=0, which may be invalid
// Use synchronized if both must change together

Pitfall 3: Forgetting to loop on CAS failure. If you call compareAndSet and it returns false, that means your update was rejected. You must read the value again, recompute, and try again. Not looping is a silent bug where you silently lose updates.

Pitfall 4: Ignoring the ABA problem in pointer based structures. If you are building lock free data structures with AtomicReference, always consider whether ABA could affect your algorithm. When in doubt, use AtomicStampedReference.

---

Check yourself

1. What is the difference between pessimistic and optimistic concurrency?
2. What does Compare-and-Swap do, and what happens when it fails?
3. Why does counter++ lose updates, and how does AtomicInteger.incrementAndGet() avoid it?
4. How does AtomicBoolean.compareAndSet(false, true) give you run-once initialization?
5. What is the ABA problem, and what fixes it?
6. What does volatile guarantee, and what does it not guarantee?
7. When would you choose volatile, synchronized, or an Atomic class?

Answers

1. Pessimistic: take a lock before touching shared data (synchronized, locks). Optimistic: work without a lock and check before committing that nobody changed the data (CAS).
2. Atomically: if the value in memory equals the expected value, write the new value and return true; otherwise return false, and the caller re-reads and retries.
3. counter++ is read-add-write, so two threads can read the same value. incrementAndGet retries a CAS until it succeeds, so no increment is lost.
4. Only one thread can flip false to true; every other thread gets false and skips the initialization.
5. A value changes A to B and back to A, so a CAS that only compares values wrongly succeeds. AtomicStampedReference adds a version stamp that must also match.
6. Visibility (a write is seen by later reads) and ordering. Not atomicity: count++ on a volatile is still unsafe.
7. volatile for a simple flag written by one thread; synchronized for multi-step updates or waiting on conditions; Atomic classes for single-variable counters/flags without blocking.