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.

Java exposes this through a class called sun.misc.Unsafe which has a native compareAndSwapInt method implemented in C++. You do not call Unsafe yourself. The java.util.concurrent.atomic package wraps it 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 ensures every CAS read goes to main memory, not a CPU cache. 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. Modern CPUs do not read and write directly to RAM for every operation. They have multiple layers of cache: L1, L2, and L3. L1 cache is tiny but blazingly fast. Reading from L1 is perhaps 100 times faster than reading from RAM.

When a thread runs on a CPU core, it reads variables into that core's cache and works with the cached copy. It may write updates back to the cache before eventually flushing them to main memory. There is no guarantee about when this flush happens.

This means thread one might update a variable, but thread two, running on a different core, is still reading the old cached value. Thread two is seeing stale data. This is a visibility problem.

volatile solves exactly this problem. When you mark a field volatile, every read of that field goes directly to main memory and every write goes directly to main memory, bypassing the CPU cache.

public class StopFlag {
    // Without volatile, the worker thread might never see this change
    // because it keeps reading from its own CPU cache
    private volatile boolean stopped = false;

    public void stop() {
        stopped = true;   // writes directly to main memory
    }

    public void run() {
        while (!stopped) {   // reads directly from main memory every iteration
            doWork();
        }
    }
}

Without volatile, the JVM and CPU are allowed to cache stopped in the worker thread's local register. The worker might spin forever even after the main thread sets stopped = true, because the worker never looks at main memory again.

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 go to main memory, 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 both reads come from main memory. 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. That read must always come from main memory, not a stale CPU cache, so that when CAS checks whether the memory still matches the expected value, it is comparing against the real current state.

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.

---

Interview Questions: Complete List

Q: In how many ways can you achieve thread safety in Java?

There are two approaches. Lock based concurrency uses tools like synchronized, ReentrantLock, and ReadWriteLock. Lock free concurrency uses atomic classes backed by the CAS CPU instruction, like AtomicInteger, AtomicBoolean, and AtomicReference.

Q: What is Compare and Swap and how does it work?

CAS is a single atomic CPU instruction. It takes three arguments: a memory address, an expected value, and a new value. If the value at the memory address equals the expected value, it atomically replaces it with the new value and returns true. If not, it leaves memory unchanged and returns false. The check and swap happen as one uninterruptible unit at the hardware level.

Q: What is the difference between volatile and synchronized?

volatile ensures visibility: reads and writes go directly to main memory, not the CPU cache. It does not ensure atomicity, so compound operations like counter++ are still unsafe with volatile alone.

synchronized ensures both visibility and atomicity. Only one thread can execute a synchronized block at a time, so no two threads can interleave their operations.

Q: What is the difference between volatile and Atomic classes?

volatile is about visibility only. AtomicInteger and friends combine visibility (the internal field is volatile) with atomicity via CAS. Use volatile for simple single read or write operations. Use Atomic classes when you need compound operations like increment, compare and swap, or get and set to be atomic.

Q: Can you increment a volatile int safely from multiple threads?

No. volatile int counter; counter++ is not thread safe because the increment is three operations: read, add, write. Another thread can interleave between any two of these steps. Use AtomicInteger.incrementAndGet() instead.

Q: What is the ABA problem?

ABA occurs when a CAS sees the expected value in memory and succeeds, but the value was changed away from that expected value and then changed back between the time of your read and your CAS. The CAS does not detect that a change happened. In some algorithms, this silent change can corrupt state. The solution is AtomicStampedReference, which pairs the value with a version stamp so even if the value reverts, the stamp difference reveals the intermediate change.

Q: Why is lock free concurrency sometimes faster than synchronized?

Because no thread ever blocks. With a lock, a thread that cannot acquire the lock is descheduled by the OS and a context switch happens. Context switches are expensive. In a CAS based algorithm, a thread that fails a CAS simply loops and retries immediately, without any OS involvement. Under low to moderate contention, this is dramatically faster.

Q: When would synchronized be better than AtomicInteger?

When you need to execute multiple operations as a single atomic unit, you cannot use AtomicInteger alone. For example, if you need to increment two different counters together and guarantee that no thread ever sees them in an inconsistent state (one incremented, the other not yet), you need a lock over both increments. AtomicInteger can only make each individual operation atomic, not groups of operations together.

Q: What does volatile guarantee about instruction reordering?

volatile also establishes a happens before relationship. A write to a volatile variable happens before every subsequent read of that same variable. This means the JVM and CPU cannot reorder instructions across a volatile read or write. This is how you can safely use a volatile boolean flag to signal that construction of an object is complete, because the volatile write ensures all the object initialization instructions ran before the flag was set.

---

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.

---

Summary

Lock free concurrency through Compare and Swap is one of the most powerful tools in modern Java development. Here is the complete picture:

• There are two approaches to thread safety: lock based and lock free.
• CAS is a hardware instruction that atomically checks and updates a memory location.
• AtomicInteger, AtomicBoolean, and AtomicReference expose CAS through a safe Java API.
• The CAS loop reads a value, computes an update, tries to CAS swap, and retries if it fails.
• The ABA problem can silently corrupt CAS logic when a value changes and then reverts. Use AtomicStampedReference to add a version stamp.
• volatile solves the visibility problem: reads and writes go to main memory, not CPU cache.
• volatile does NOT provide atomicity. Compound operations like ++ are still unsafe.
• Inside AtomicInteger, the value field is volatile so that the CAS loop always reads fresh data.
• Use volatile for simple flags and publications. Use Atomic classes for single variable compound operations. Use synchronized when you need multiple variables to change together atomically.

Lock free algorithms shine in high contention, high throughput scenarios. They eliminate context switching, deadlocks, and priority inversion entirely. Understanding when to reach for a CAS based tool versus a lock, and being precise about what volatile does and does not guarantee, is the mark of a developer who truly understands concurrent programming in Java.