Lock-Free Concurrency in Java | Atomic Variables & CAS Explained

This chapter explores the mechanics of lock-free concurrency in Java. We will analyze why traditional locking mechanisms introduce performance overhead, how atomic variables (AtomicInteger, AtomicLong, AtomicBoolean, and AtomicReference) eliminate race conditions without using locks, and how the Compare-And-Swap (CAS) operation coordinates thread safety at the hardware and electrical level.

1. The Problem of Non-Atomic Operations

To understand why we need lock-free concurrency, we must first examine how a simple, seemingly harmless operation fails in a multi-threaded environment.

Consider a basic Counter class where a shared variable count is incremented by multiple threads:

class Counter {
    int count = 0;

    public void increment() {
        count++;
    }
}

If we spin up two threads ($T_1$ and $T_2$), where each thread calls the increment() method $10,000$ times, the mathematically expected value of count at the end is $20,000$. However, when run in practice, the final value is almost always significantly less than $20,000$ (e.g., $13,241$ or $15,890$). This discrepancy is caused by a race condition.

Why count++ is Not Safe

At the high-level language level, count++ looks like a single operation. At the machine level, however, it is a non-atomic operation consisting of three distinct steps:

          Memory (count = 0)
                 |
                 | 1. Read value (0)
                 v
          Thread CPU Register
                 |
                 | 2. Increment value (0 + 1 = 1)
                 v
          Thread CPU Register (1)
                 |
                 | 3. Write value back (count = 1)
                 v
          Memory (count = 1)

1. Read: The thread reads the current value of count from main memory into its local CPU register.
2. Modify: The thread increments the value by $1$ inside the register.
3. Write: The thread writes the updated value back to main memory.

The Race Condition Interleaving

Because these three steps are non-atomic, a thread can be context-switched out at any point during execution. If $T_1$ and $T_2$ run concurrently, they can interleave as follows:

Even though two increments occurred, the final value in memory is $1$ instead of $2$. This loss of updates is the core symptom of a race condition.

2. The Traditional Solution & Its Overhead

To prevent interleaving, we traditionally isolate the critical section using locks. This ensures that only one thread can execute the read-modify-write sequence at a time.

The Locking Approach

We can achieve mutual exclusion by using the synchronized keyword or explicit locks like ReentrantLock:

class SynchronizedCounter {
    private int count = 0;

    // Using monitor lock
    public synchronized void increment() {
        count++;
    }
}

The Cost of Locking

While locks guarantee correctness, they introduce significant performance overhead:

• Thread Blocking & Context Switching: When a thread fails to acquire a lock, the Operating System puts it into a blocked/waiting state. This requires a context switch from user space to kernel space, which is highly expensive in terms of CPU cycles.
• Priority Inversion: A low-priority thread holding a lock can block a high-priority thread from executing.
• Deadlocks: Poorly managed locking sequences can cause threads to wait on each other indefinitely, freezing the application.
• Resource Contention: As the number of threads increases, threads spend more time waiting for locks than doing actual work, severely limiting scalability.

This brings us to the need for Lock-Free Concurrency: achieving thread safety and data consistency without blocking threads.

3. Core Mental Model: What is Lock-Free Concurrency?

Lock-free concurrency allows multiple threads to access shared resources without the overhead of blocking or waiting. Instead of preventing other threads from entering a critical section, lock-free algorithms allow all threads to proceed, using atomic hardware instructions to detect and resolve conflicts.

The "All-or-Nothing" Principle of Atomicity

An operation is atomic if it appears to occur instantaneously to the rest of the system. It follows an All-or-Nothing execution model:

• The operation either completes entirely or does not execute at all.
• No other thread can observe the operation in a partially completed state.
• The thread executing the operation cannot be context-switched out mid-execution.

Note: In Java, basic assignments to reference variables and primitive variables (except long and double on older 32-bit JVMs) are atomic. For example, int x = 4; is atomic. However, compound operations like x++ or x = x + 1 are not.

Lock-Free vs. Locking Workflows

Instead of blocking Thread 2, the lock-free approach lets it continuously attempt the update until it succeeds, eliminating kernel-level context switches.

4. AtomicInteger in Action

Java provides a suite of lock-free utility classes in the java.util.concurrent.atomic package. The most widely used class is AtomicInteger.

Refactoring the Counter with AtomicInteger

Let's rewrite our multi-threaded counter to use AtomicInteger instead of primitive int and locks:

import java.util.concurrent.atomic.AtomicInteger;

class AtomicCounter {
    // Initialize atomic integer with 0
    private final AtomicInteger count = new AtomicInteger(0);

    public void increment() {
        // Atomically increments the current value by 1
        count.incrementAndGet();
    }

    public int getCount() {
        return count.get();
    }
}

Complete Executable Demonstration

Below is a complete test harness demonstrating how AtomicInteger resolves race conditions under heavy thread contention:

public class AtomicDemo {
    public static void main(String[] args) {
        AtomicCounter counter = new AtomicCounter();

        // Thread 1: Increments 10,000 times
        Thread t1 = new Thread(() -> {
            for (int i = 0; i < 10000; i++) {
                counter.increment();
            }
        });

        // Thread 2: Increments 10,000 times
        Thread t2 = new Thread(() -> {
            for (int i = 0; i < 10000; i++) {
                counter.increment();
            }
        });

        t1.start();
        t2.start();

        // Wait for both threads to finish execution
        try {
            t1.join();
            t2.join();
        } catch (InterruptedException e) {
            Thread.currentThread().interrupt();
        }

        // Output will always be exactly 20000
        System.out.println("Final Count: " + counter.getCount());
    }
}

Regardless of how many times you run this code, the output will always be exactly 20000. The execution is completely lock-free, meaning no threads were blocked or put to sleep by the OS during the increment operations.

5. Core Methods of AtomicInteger

The AtomicInteger class provides several atomic methods that map directly to common arithmetic and assignment operations.

6. AtomicLong and AtomicBoolean

In addition to AtomicInteger, Java provides AtomicLong and AtomicBoolean to handle other primitive types.

1. AtomicLong

AtomicLong is identical in behavior to AtomicInteger but is backed by a 64-bit long value.

Real-World Use Case: Unique ID Generation

In distributed systems or database engines, generating unique, sequential transaction or session IDs across multiple threads is a common requirement. AtomicLong is perfect for this because it is highly performant and prevents duplicate IDs without locking:

import java.util.concurrent.atomic.AtomicLong;

public class IdGenerator {
    private final AtomicLong currentId = new AtomicLong(1000); // Start IDs from 1000

    public long nextId() {
        return currentId.incrementAndGet();
    }
}

2. AtomicBoolean

AtomicBoolean provides an atomic boolean flag that can be safely read and updated by multiple threads.

Real-World Use Case: Shared State Flags

In producer-consumer workflows or thread shutdown sequences, threads often poll a shared flag to determine if they should stop processing.

import java.util.concurrent.atomic.AtomicBoolean;

public class WorkerService implements Runnable {
    private final AtomicBoolean isRunning = new AtomicBoolean(true);

    public void stop() {
        isRunning.set(false); // Safe, visible write to all threads
    }

    @Override
    public void run() {
        while (isRunning.get()) {
            // Perform background processing task
        }
        System.out.println("Worker stopped cleanly.");
    }
}

Memory Visibility Guarantee: When using atomic variables, you do not need to declare them as volatile. The internal value field of all atomic classes is already marked as volatile, ensuring that any write to an atomic variable is immediately visible to all other threads.

7. The Limits of Atomicity: Compound Operations Pitfall

A common developer mistake is assuming that because individual operations on an atomic variable are thread-safe, combining multiple atomic operations is also thread-safe. This is false.

The "Check-Then-Act" Bug

Consider the following code snippet which attempts to increment a counter only if its value is greater than $4$:

// WARNING: This code contains a race condition!
if (count.get() > 4) { 
    count.incrementAndGet(); 
}

Even though get() and incrementAndGet() are individually atomic, the compound operation of checking and then acting is not atomic.

If $T_1$ and $T_2$ execute this block simultaneously when count is $5$, both will pass the check and both will increment the counter, resulting in two increments instead of one coordinated action. To make compound operations thread-safe, you must either use traditional locking or use the Compare-And-Swap (CAS) pattern.

8. AtomicReference & The Double Seat Booking Problem

Just as we protect primitive types, we often need to protect object references in a multi-threaded environment. This is where AtomicReference is used.

Real-Life Analogy: Movie Ticket Booking

Imagine a movie theater with a single premium seat. The seat can either be "empty" or booked by a specific person (e.g., "Aditya" or "Rohit"). If two customers try to book the seat at the exact same time, only one should succeed, and the other should receive a failure message.

Naive (Broken) Implementation

Let's look at a naive implementation of this booking system:

class NaiveSeatBooking {
    // Shared reference pointing to the seat status
    String seat = "empty";

    public boolean bookSeat(String personName) {
        // Check if the seat is empty
        if (seat.equals("empty")) {
            // Act: Assign the seat to the person
            seat = personName; 
            return true; // Booking successful
        }
        return false; // Seat already taken
    }
}

The Double-Booking Bug

If Thread 1 ($T_1$ for Aditya) and Thread 2 ($T_2$ for Rohit) call bookSeat() concurrently, they can both execute the check seat.equals("empty") simultaneously. Both find it to be true, and both proceed to assign their names to the seat.

Depending on which thread writes last (even by a fraction of a nanosecond), one name will overwrite the other. However, both threads will receive a return value of true. Both Aditya and Rohit will believe they successfully booked the seat, leading to a critical double-booking bug in production.

9. Solving Double Booking with Compare-And-Swap (CAS)

To solve the double-booking problem without using slow synchronized locks, we can use AtomicReference and its core lock-free operation: compareAndSet().

Refactored Code using AtomicReference

import java.util.concurrent.atomic.AtomicReference;

class SafeSeatBooking {
    // Wrap the seat reference inside an AtomicReference
    private final AtomicReference<String> seat = new AtomicReference<>("empty");

    public boolean bookSeat(String personName) {
        // 1. Read the current value
        String currentStatus = seat.get();

        // 2. If the seat is already booked, fail immediately
        if (currentStatus.equals("empty") == false) {
            return false;
        }

        // 3. Attempt an atomic Compare-And-Swap (CAS)
        // Expect: "empty", New Value: personName
        return seat.compareAndSet("empty", personName);
    }
}

Complete Executable Flow Demonstration

Here is a complete program showing how two threads compete for the seat, with Java guaranteeing that only one thread succeeds:

public class BookingDemo {
    public static void main(String[] args) throws InterruptedException {
        SafeSeatBooking bookingSystem = new SafeSeatBooking();

        // Thread 1: Aditya tries to book
        Thread t1 = new Thread(() -> {
            boolean success = bookingSystem.bookSeat("Aditya");
            System.out.println("Aditya Booking Status: " + (success ? "SUCCESS" : "FAILED"));
        });

        // Thread 2: Rohit tries to book
        Thread t2 = new Thread(() -> {
            boolean success = bookingSystem.bookSeat("Rohit");
            System.out.println("Rohit Booking Status: " + (success ? "SUCCESS" : "FAILED"));
        });

        t1.start();
        t2.start();

        t1.join();
        t2.join();

        // Verify who actually got the seat
        // The output will show one SUCCESS, one FAILED, and the seat assigned to the winner.
    }
}

How compareAndSet Works Here

The method seat.compareAndSet("empty", personName) performs the check and the assignment as a single, atomic step:

1. It looks at the current value inside seat.
2. If the current value is exactly "empty", it updates it to personName and returns true.
3. If the current value is anything else (e.g., another thread already booked it), it leaves the value untouched and returns false.

10. Deep Dive: How CAS Works Under the Hood

How does Java guarantee that compareAndSet is atomic without using locks? How does it handle parallel execution on multi-core CPUs?

The answer lies in a hardware-level coordination mechanism called Compare-And-Swap (CAS).

1. The CPU Instruction Level (Assembly)

At the Java level, compareAndSet() calls native methods that compile down to a single, atomic assembly instruction supported directly by modern CPU architectures.

On x86/x64 processors, this instruction is:

LOCK CMPXCHG <destination>, <source>

• CMPXCHG (Compare and Exchange) compares the value in a register with a memory location. If they are equal, it loads the source value into the destination.
• The LOCK prefix is a hardware signal. When a CPU core executes an instruction with a LOCK prefix, it asserts a physical signal on the system bus or locks the cache line containing the memory address. This prevents any other CPU core from reading or writing to that memory location until the instruction completes.

2. The Memory Controller & Physical/Electrical Level

Even if two threads run on completely different CPU cores (true parallel execution) and execute compareAndSet at the exact same physical instant, the hardware prevents simultaneous access.

The Physical Limit of Electrical Signals

1. The Memory Controller as a Gatekeeper: The memory controller is a physical, silicon-based electronic device. It processes incoming memory read/write requests sequentially.
2. The Picosecond Difference: Even if two CPU cores send electrical signals at what seems to be the exact same time, there is always a tiny physical difference (measured in picoseconds) due to:
   • Microscopic differences in wire lengths on the motherboard.
   • Minor variations in silicon temperature and resistance.
   • The speed of light travel time across the chip.
3. Flip-Flop States: At the transistor level, memory cells and logical gates (flip-flops) are binary. A flip-flop gate is either open or closed; it cannot be half-open or process two electrical signals simultaneously. One signal will always arrive first and trigger the gate, causing the second signal to be rejected or processed next.

Real-World Analogy: The Buzzer Game

Think of a game show with two contestants and two physical buzzers connected to a central console.

Even if both contestants slam their buzzers at what looks like the exact same millisecond, the central console's electronic circuit will only register one winner. The electrical signal from one buzzer will reach the logic gate first—even if by a fraction of a nanosecond—due to a shorter wire or a faster button press. Once that signal registers, the circuit instantly disables the other input.

This is exactly how the memory controller handles concurrent CAS requests from multiple CPU cores.

11. Summary and Key Takeaways

• Non-Atomic Operations: Common operations like count++ are compound operations (Read-Modify-Write) that are vulnerable to race conditions when accessed by multiple threads.
• The Cost of Locks: Traditional locking (synchronized, ReentrantLock) guarantees thread safety but introduces heavy performance overhead due to thread blocking, context switching, and resource contention.
• Lock-Free Concurrency: Lock-free concurrency uses atomic variables to perform thread-safe operations without blocking threads, allowing high throughput and low latency.
• Atomic Variables: Java's java.util.concurrent.atomic package provides classes like AtomicInteger, AtomicLong, and AtomicBoolean which use volatile memory semantics and hardware-level atomic operations.
• The Compound Operation Trap: Combining multiple atomic operations (e.g., if (atomic.get() == x) { atomic.set(y); }) is not atomic. It must be executed using a single CAS operation.
• Compare-And-Swap (CAS): CAS is the foundation of lock-free programming. It checks if a memory location contains an expected value, and if so, updates it to a new value in a single, atomic step.
• Hardware-Level Coordination: Under the hood, CAS relies on CPU instructions like LOCK CMPXCHG on x86 architectures.
• Physical Serialization: At the electrical level, the memory controller and physical logic gates (flip-flops) ensure that even simultaneous parallel requests are processed sequentially, guaranteeing that only one thread wins a CAS race.