Lock-Free Concurrency in Java: CAS Retry, Atomic Arrays, and the ABA Problem

This chapter explores advanced lock-free concurrency patterns in Java. We will examine the fundamental differences between volatile and atomic variables, build a custom lock-free retry loop (spin loop) using Compare-and-Set (CAS), and see how Java's atomic classes encapsulate these patterns under the hood. Finally, we will analyze the classic ABA Problem in lock-free algorithms and study how versioning/stamping resolves it.

1. Volatile vs. Atomic Variables: The Core Differences

When writing multi-threaded applications, developers often confuse the volatile keyword with atomic variables. While both are critical for thread safety, they solve fundamentally different problems.

Volatile: Visibility Guarantee

The volatile keyword ensures visibility. In modern multi-core processors, each CPU core has its own local cache (L1/L2/L3). When a thread reads or writes a variable, it may do so using its local cache instead of the main memory (RAM). This can lead to situations where updates made by one thread are invisible to another.

Declaring a variable as volatile forces all write operations to be flushed directly to the main RAM, and all read operations to be fetched directly from the main RAM.

Note: volatile does not guarantee atomicity. If multiple threads perform a compound read-modify-write operation (such as count++), volatile alone cannot prevent race conditions.

Atomic: Atomicity + Visibility

Atomic variables (such as AtomicInteger, AtomicLong, and AtomicReference) guarantee atomicity. An atomic operation is indivisible: it either executes completely or not at all. There is no intermediate state visible to other threads.

Furthermore, atomic variables are implicitly volatile. They use volatile fields under the hood, meaning you do not need to explicitly declare an atomic variable as volatile to get visibility guarantees.

2. The Need for CAS Retry: Moving Beyond Single-Winner Scenarios

In basic Compare-and-Set (CAS) operations, we often deal with "single-winner" scenarios. For example, in a seat-booking system, if two threads attempt to book the same seat simultaneously, only one thread should succeed (compareAndSet returns true), while the other thread fails (compareAndSet returns false) and is rejected.

However, many real-world scenarios require all threads to eventually succeed, just sequentially. Consider a Like Counter on a social media platform:

• If Thread 1 and Thread 2 both click "Like" at the same time, we cannot simply discard Thread 2's action.
• Both likes must be registered.
• If Thread 1 updates the counter first, Thread 2 must detect this change, recalculate its update based on the new value, and try again.

This pattern is known as a Lock-Free Retry Loop (or CAS Spin Loop). Instead of blocking threads using traditional locks, threads continuously attempt to update the value in a loop until they succeed.

3. Naive vs. Lock-Free Code: Building a Thread-Safe Like Counter

Let us build a LikeCounter class to demonstrate how to implement a lock-free retry loop using AtomicReference.

The Naive (Broken) Approach

First, let's look at a naive implementation that attempts to update an AtomicReference<Integer> without a retry loop.

// Naive implementation containing a critical race condition
public void naiveLike() {
    // Step 1: Read current value (Atomic)
    Integer current = totalCount.get(); 
    
    // Step 2: Compute new value
    Integer next = current + 1; 
    
    // Step 3: Set new value (Atomic)
    totalCount.set(next); 
}

Why this fails:

Although get() and set() are individually atomic, the compound operation (get, increment, set) is not atomic. If Thread 1 and Thread 2 both execute get() simultaneously when the count is 0, both will read 0, both will compute 1, and both will set the value to 1. One of the likes is lost.

The Lock-Free CAS Retry Loop Approach

To fix this without using synchronized blocks or locks, we use compareAndSet inside an infinite while(true) loop.

import java.util.concurrent.atomic.AtomicReference;

public class LikeCounter {
    // Using AtomicReference to hold our Integer count
    private final AtomicReference<Integer> totalCount = new AtomicReference<>(0);

    public void like() {
        while (true) {
            // Step 1: Capture the latest value of the counter
            Integer currentCount = totalCount.get();

            // Step 2: Calculate the desired new value
            Integer finalCount = currentCount + 1;

            // Step 3: Attempt to update using Compare-and-Set
            // Only updates if the value in memory is still equal to currentCount
            if (totalCount.compareAndSet(currentCount, finalCount)) {
                // Success! Exit the loop and return
                return; 
            }

            // Step 4: If compareAndSet returned false, another thread modified the value.
            // Print conflict message and retry the loop.
            System.out.println("[" + Thread.currentThread().getName() + "] Conflict detected! Retrying...");
        }
    }

    public Integer getTotalLikes() {
        return totalCount.get();
    }
}

Complete Multi-Threaded Test Harness

Below is the complete executable code demonstrating 10 concurrent threads, each performing 10 likes (expecting a final count of 100).

public class Demo3 {
    public static void main(String[] args) throws InterruptedException {
        LikeCounter likeCounter = new LikeCounter();
        int numThreads = 10;
        int likesPerThread = 10;
        Thread[] threads = new Thread[numThreads];

        // Create 10 threads, each calling like() 10 times
        for (int i = 0; i < numThreads; i++) {
            threads[i] = new Thread(() -> {
                for (int j = 0; j < likesPerThread; j++) {
                    likeCounter.like();
                }
            }, "Thread-" + (i + 1));
        }

        // Start all threads
        for (Thread t : threads) {
            t.start();
        }

        // Wait for all threads to finish execution
        for (Thread t : threads) {
            t.join();
        }

        System.out.println("----------------------------------------");
        System.out.println("Expected Likes: " + (numThreads * likesPerThread));
        System.out.println("Actual Total Likes: " + likeCounter.getTotalLikes());
        System.out.println("----------------------------------------");
    }
}

4. Optimizing the CAS Retry Loop

In our previous implementation, the variables currentCount and finalCount were declared inside the while(true) loop:

while (true) {
    Integer currentCount = totalCount.get();
    Integer finalCount = currentCount + 1;
    // ...
}

If a thread experiences high contention and retries many times, declaring these variables repeatedly inside the loop can put unnecessary pressure on the Java Garbage Collector (GC) due to frequent object allocation.

We can optimize this by declaring the reference variables outside the loop and reusing them:

public void optimizedLike() {
    Integer currentCount;
    Integer finalCount;
    
    while (true) {
        currentCount = totalCount.get();
        finalCount = currentCount + 1;
        
        if (totalCount.compareAndSet(currentCount, finalCount)) {
            return;
        }
        System.out.println("Conflict detected! Retrying...");
    }
}

5. AtomicReferenceArray: Thread-Safe Array Operations

Just as we have atomic variables for single references, Java provides AtomicReferenceArray to handle arrays of references in a thread-safe, lock-free manner.

In a standard array (Object[]), updating an index is not thread-safe. Multiple threads writing to the same index can cause data corruption or lost updates. AtomicReferenceArray ensures that operations on individual array indices are atomic.

Common Methods in AtomicReferenceArray<E>

• set(int i, E newValue): Atomically sets the element at index i to newValue.
• get(int i): Atomically gets the element at index i.
• compareAndSet(int i, E expect, E update): Atomically sets the element at index i to update if the current value at index i is equal to expect.

Code Example: Declaring and Using AtomicReferenceArray

import java.util.concurrent.atomic.AtomicReferenceArray;

public class AtomicArrayDemo {
    public static void main(String[] args) {
        // Create an Atomic Reference Array of size 5
        AtomicReferenceArray<String> seatArray = new AtomicReferenceArray<>(5);

        // Set initial values
        seatArray.set(0, "Empty");
        seatArray.set(1, "Empty");

        // Thread 1 tries to book Seat 0
        boolean success1 = seatArray.compareAndSet(0, "Empty", "User-Aditya");
        System.out.println("Booking Seat 0 for Aditya: " + success1); // true

        // Thread 2 tries to book Seat 0 while it is already booked
        boolean success2 = seatArray.compareAndSet(0, "Empty", "User-Rohit");
        System.out.println("Booking Seat 0 for Rohit: " + success2); // false
    }
}

Real-World Exercise: Multi-Seat Booking System

Using AtomicReferenceArray, you can design a seat booking system where multiple threads attempt to book seats across an array. If a thread fails to book index 0, it can iterate to index 1, index 2, etc., trying to find an available seat using compareAndSet(index, "Empty", "User_Name").

6. Under the Hood: How AtomicInteger Simplifies CAS

While writing custom CAS retry loops with AtomicReference is highly educational, Java provides specialized classes like AtomicInteger and AtomicLong that simplify these operations.

In our LikeCounter example, we used an AtomicReference<Integer> and wrote a 6-line retry loop. We can replace that entire logic with a single line using AtomicInteger and its built-in incrementAndGet() method.

Refactored Like Counter using AtomicInteger

import java.util.concurrent.atomic.AtomicInteger;

public class SimplifiedLikeCounter {
    // Initialize AtomicInteger to 0
    private final AtomicInteger totalCount = new AtomicInteger(0);

    public void like() {
        // Atomically increments the current value by 1 and returns the updated value
        totalCount.incrementAndGet(); 
    }

    public int getTotalLikes() {
        return totalCount.get();
    }
}

How does incrementAndGet() work internally?

It is important to understand that AtomicInteger does not use traditional OS-level locking. Under the hood, it implements the exact same CAS retry loop we wrote manually!

If you inspect the source code of Java's atomic classes (which delegate to Unsafe or VarHandle), you will find a loop structure equivalent to this:

// Conceptual internal implementation of incrementAndGet()
public final int incrementAndGet() {
    for (;;) {
        int current = get();
        int next = current + 1;
        if (compareAndSet(current, next)) {
            return next;
        }
    }
}

7. Compare-and-Swap (CAS) vs. Traditional Locking

The table below summarizes the key differences between lock-free CAS concurrency and traditional locking mechanisms (such as synchronized blocks or ReentrantLock).

8. The ABA Problem: The Hidden Flaw of Value-Only CAS

The ABA Problem is a classic anomaly that occurs in lock-free algorithms. It happens when a thread reads a memory location, gets preempted, and another thread changes that memory location from value A to B, and then back to A. When the original thread resumes, it performs a CAS operation, sees the value A, and assumes nothing has changed—even though the system state was modified in the interim.

Step-by-Step ABA Timeline

1. At $t=0$: Thread T1 reads the value A from memory.
2. At $t=1$: Thread T1 is context-switched (suspended) by the operating system.
3. At $t=2$: Thread T2 runs, changes the value from A to B.
4. At $t=3$: Thread T2 performs another operation, changing the value from B back to A.
5. At $t=4$: Thread T1 resumes. It executes compareAndSet(expected: A, new: X). Since the current value in memory is indeed A, the CAS operation succeeds!

When is ABA harmless?

In simple numeric counters (like our LikeCounter), the ABA problem is usually harmless. If a counter goes from 1 -> 2 -> 1, and a thread increments it to 2, the history of changes does not affect the correctness of the final count.

When is ABA dangerous?

The ABA problem is highly dangerous in node-based data structures (like lock-free Stacks, Queues, or Linked Lists) that reuse memory nodes.

If a node at address A is deleted, deallocated, and a new node is allocated at the exact same memory address A, a thread performing CAS might mistakenly assume it is the original node, leading to severe memory corruption or structural bugs.

9. Solving the ABA Problem: Versioning and Stamped References

To solve the ABA problem, we must track not just the value, but also the history of changes. We do this using Versioning (or Stamping).

Instead of storing just the value A, we store a pair: (Value, Version). Every time the value is updated, the version is incremented.

ABA Solution Timeline with Versioning

Now, when Thread T1 resumes at $t=4$, it attempts to execute a CAS expecting (A, Version 1). However, the memory contains (A, Version 3). The version mismatch is detected, the CAS fails, and T1 safely retries.

Java's Solution: AtomicStampedReference

In Java, this versioning pattern is implemented by the AtomicStampedReference class. It maintains an object reference along with an integer "stamp" (representing the version) that can be updated atomically.

import java.util.concurrent.atomic.AtomicStampedReference;

public class ABASolutionDemo {
    public static void main(String[] args) {
        String initialRef = "A";
        int initialStamp = 1;

        AtomicStampedReference<String> stampedRef = 
            new AtomicStampedReference<>(initialRef, initialStamp);

        // Thread 1 reads value and stamp
        int[] stampHolder = new int[1];
        String value = stampedRef.get(stampHolder);
        int originalStamp = stampHolder[0]; 

        System.out.println("Initial Value: " + value + " | Stamp: " + originalStamp); // A, 1

        // Thread 2 simulates ABA change
        // A -> B (Stamp increments to 2)
        stampedRef.compareAndSet("A", "B", 1, 2);
        // B -> A (Stamp increments to 3)
        stampedRef.compareAndSet("B", "A", 2, 3);

        // Thread 1 resumes and tries to update A -> X expecting original stamp 1
        boolean success = stampedRef.compareAndSet("A", "X", originalStamp, originalStamp + 1);

        System.out.println("CAS Success: " + success); // Prints false! ABA prevented.
        System.out.println("Current Value: " + stampedRef.getReference() + " | Stamp: " + stampedRef.getStamp());
    }
}

Summary and Key Takeaways

• Volatile vs. Atomic: volatile guarantees visibility by bypassing CPU caches to read/write directly to RAM. atomic variables guarantee both visibility and indivisible operations (atomicity).
• CAS Retry Loop: When multiple threads must all succeed in updating a shared variable, we wrap compareAndSet in a while(true) loop to continuously recalculate and retry updates until they succeed.
• GC Optimization: In high-contention retry loops, declare reference variables outside the loop to prevent excessive object allocation and reduce garbage collection overhead.
• Atomic Arrays: AtomicReferenceArray provides lock-free, thread-safe atomic operations on individual array indices using index-based CAS.
• Atomic Helper Classes: Specialized classes like AtomicInteger encapsulate the CAS retry loop internally, allowing you to replace complex spin-loop code with simple methods like incrementAndGet().
• Locking vs. CAS: Traditional locking is pessimistic and blocks threads, while CAS is optimistic, keeping threads active in user space and relying on hardware-level atomic instructions.
• The ABA Problem: A classic lock-free concurrency issue where a value changes from A -> B -> A, causing a standard CAS to mistakenly assume no changes occurred.
• ABA Prevention: Resolve the ABA problem using versioning or stamping. Java provides AtomicStampedReference to pair references with an integer version stamp, ensuring CAS fails if the value was modified and reverted in the interim.