CAS Mechanism

Thread-safe implementations typically employ one of three approaches:

• Mutual exclusion synchronization: synchronized and ReentrantLock
• Non-blocking synchronization: CAS and AtomicXXXX
• Synchronization-free designs: thread-local storage, immutable objects

This article focuses on the Compare-And-Swap (CAS) mechanism.

What is CAS

CAS stands for Compare-And-Swap, a CPU atomic instruction that compares a memory value with an expected value and swaps it with a new value if they match. Modern processors implement this through platform-specific assembly instructions, while JVMs provide wrapper interfaces. Classes like AtomicInteger utilize these native implementations for lock-free concurrency.

The operation requires three parameters: an expected old value, a new value, and a memory location. During execution, CAS first verifies whether the current value matches the expected old value. If unchanged, the swap occurs; otherwise, the operation fails without modification.

This resembles conditional updates in SQL: UPDATE table SET id=3 WHERE id=2. Since single SQL statements execute atomically, only one thread succeeds when multiple threads attempt the same update concurrently.

CAS Implementation Example

Without CAS, synchronized blocks or locks are required for thread-safe variable modifications (AQS, used by Lock, also relies on CAS internally):

public class Counter {
    private int value = 0;
    
    public synchronized int increment() {
        return value++;
    }
}

Java provides AtomicInteger for lock-free concurrent updates:

public class Counter {
    private AtomicInteger value = new AtomicInteger(0);
    
    public int increment() {
        return value.addAndGet(1);
    }
}

CAS Limitations

CAS represents optimistic locking, while synchronized implements pessimistic locking. Generally, CAS offers better performance, but several issues exist:

ABA Problem

CAS checks whether values changed before updating. However, a value could change from A to B and back to A, passing the CAS check despite modification. The solution involves version tracking—appending a version number that increments with each update, transforming A→B→A into 1A→2B→3A.

Since Java 1.5, AtomicStampedReference addresses this by comparing both reference and stamp (version) before atomic updates.

Performance Overhead

Spinning CAS operations that repeatedly fail consume significant CPU cycles. Modern JVMs leverage processor pause instructions to improve efficiency by reducing pipeline stalls and memory order violations.

Unsafe Class Enalysis

The Unsafe class resides in sun.misc and provides low-level operations for direct memory access and resource management. While these capabilities enhance performance and enable底层 operations, they also introduce pointer-related risks. Unsafe grants Java memory manipulation abilities similar to C pointers, compromising Java's safety guarantees—usage requires extreme caution.

Unsafe methods are public but restricted; only trusted code and JDK internal classes can instantiate it directly.

Unsafe's capabilities span memory operations, CAS, class manipulation, object operations, thread scheduling, system information, memory barriers, and array operations.

Unsafe and CAS

Decompiled atomic integer methods reveal the implementation:

public final int getAndAddInt(Object target, long fieldOffset, int delta) {
    int current;
    do {
        current = getIntVolatile(target, fieldOffset);
    } while (!compareAndSwapInt(target, fieldOffset, current, current + delta));
    return current;
}

public final long getAndAddLong(Object target, long fieldOffset, long delta) {
    long current;
    do {
        current = getLongVolatile(target, fieldOffset);
    } while (!compareAndSwapLong(target, fieldOffset, current, current + delta));
    return current;
}

public final Object getAndSetObject(Object target, long fieldOffset, Object newValue) {
    Object current;
    do {
        current = getObjectVolatile(target, fieldOffset);
    } while (!compareAndSwapObject(target, fieldOffset, current, newValue));
    return current;
}

The implementation uses spin loops for CAS updates, retrying upon failure.

Unsafe supports only three native CAS operations:

public final native boolean compareAndSwapObject(Object target, long offset, Object expected, Object newValue);
public final native boolean compareAndSwapInt(Object target, long offset, int expected, int newValue);
public final native boolean compareAndSwapLong(Object target, long offset, long expected, long newValue);

Unsafe Implementation Details

The native compareAndSwapInt implementation delegates to platform-specific code:

// Linux x86 implementation
inline jint Atomic::cmpxchg(jint newValue, volatile jint* address, jint compareValue) {
    int mp = os::is_MP();
    __asm__ volatile(LOCK_IF_MP(%4) "cmpxchgl %1,(%3)"
                     : "=a"(newValue)
                     : "r"(newValue), "a"(compareValue), "r"(address), "r"(mp)
                     : "cc", "memory");
    return newValue;
}

On multi-processor systems, the lock prefix ensures cache coherence through cache locking instead of expensive bus locking.

Additional Unsafe Capabilities

Unsafe provides hardware-level operations for field offset retrieval and private field modification:

public native long staticFieldOffset(Field field);
public native int arrayBaseOffset(Class arrayClass);
public native int arrayIndexScale(Class arrayClass);
public native long allocateMemory(long bytes);
public native long reallocateMemory(long address, long bytes);
public native void freeMemory(long address);

AtomicInteger Deep Dive

Common API Methods

public final int get()                              // Returns current value
public final int getAndSet(int newValue)            // Gets value, then sets new value
public final int getAndIncrement()                  // Gets value, then increments
public final int getAndDecrement()                  // Gets value, then decrements
public final int getAndAdd(int delta)               // Gets value, then adds delta
public final void lazySet(int newValue)             // eventual set, may delay visibility

Comparison with Synchronized Counter

Traditional synchronized approach:

private volatile int counter = 0;

public synchronized void increment() {
    counter++;
}

public int getCount() {
    return counter;
}

AtomicInteger implementation:

private AtomicInteger counter = new AtomicInteger(0);

public void increment() {
    counter.incrementAndGet();
}

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

Internal Implementation

public class AtomicInteger extends Number implements Serializable {
    private static final Unsafe UNSAFE = Unsafe.getUnsafe();
    private static final long VALUE_OFFSET;
    
    static {
        try {
            VALUE_OFFSET = UNSAFE.objectFieldOffset(
                AtomicInteger.class.getDeclaredField("value"));
        } catch (Exception e) {
            throw new Error(e);
        }
    }
    
    private volatile int value;
    
    public final int get() {
        return value;
    }
    
    public final int getAndAdd(int delta) {
        return UNSAFE.getAndAddInt(this, VALUE_OFFSET, delta);
    }
    
    public final int incrementAndGet() {
        return UNSAFE.getAndAddInt(this, VALUE_OFFSET, 1) + 1;
    }
}

Two key mechanisms enable thread-safety:

• volatile: Ensures visibility across threads immediately after modificasion
• CAS: Guarantees atomicity during value updates

Complete Atomic Class Overview

JDK provides 12 atomic classses for various use cases.

Primitive Type Atomics

• AtomicBoolean: Boolean wrapper
• AtomicInteger: Integer wrapper
• AtomicLong: Long wrapper

These share similar APIs with AtomicInteger.

Array Atomics

• AtomicIntegerArray: Integer array elements
• AtomicLongArray: Long array elements
• AtomicReferenceArray: Reference array elements

Common methods include get(index) and compareAndSet(index, expected, update).

Example with AtomicIntegerArray:

public class ArrayDemo {
    public static void main(String[] args) throws InterruptedException {
        AtomicIntegerArray arr = new AtomicIntegerArray(new int[]{0, 0});
        System.out.println(arr);          // [0, 0]
        System.out.println(arr.getAndAdd(1, 2));  // 0
        System.out.println(arr);          // [0, 2]
    }
}

Reference Atomics

• AtomicReference: Generic reference wrapper
• AtomicStampedReference: Reference with version stamp for ABA prevention
• AtomicMarkableReference: Reference with boolean marker

AtomicReference example:

public class ReferenceDemo {
    public static void main(String[] args) {
        Person p1 = new Person(101);
        Person p2 = new Person(102);
        
        AtomicReference<Person> ref = new AtomicReference<>(p1);
        ref.compareAndSet(p1, p2);
        
        Person p3 = ref.get();
        System.out.println("p3: " + p3);
        System.out.println("p3 == p1: " + (p3 == p1));
    }
}

class Person {
    volatile long id;
    Person(long id) { this.id = id; }
    public String toString() { return "id:" + id; }
}

Output:

p3: id:102
p3 == p1: false

Note: Object.equals() defaults to reference comparison unless overridden.

Field Updater Atomics

• AtomicIntegerFieldUpdater: Updates int fields
• AtomicLongFieldUpdater: Updates long fields
• AtomicReferenceFieldUpdater: Updates reference fields

Field updaters are abstract and require newUpdater() with target class and field name. Fields must be volatile, instance-level (not static), and non-final.

public class FieldUpdaterDemo {
    public static void main(String[] args) {
        DataContainer data = new DataContainer();
        AtomicIntegerFieldUpdater<DataContainer> updater = 
            AtomicIntegerFieldUpdater.newUpdater(DataContainer.class, "publicField");
        
        System.out.println("Initial: " + updater.getAndAdd(data, 2));
    }
}

class DataContainer {
    public volatile int publicField = 3;
    protected volatile int protectedField = 4;
    private volatile int privateField = 5;
    public volatile static int staticField = 10;
}

Constraints: Only accessible fields from the calling context work; parent class fields are inaccessible; Integer/Long wrappers require AtomicReferenceFieldUpdater.

Solving ABA Problem with AtomicStampedReference

How It Works

AtomicStampedReference maintains a pair containing both object reference and version stamp:

public class AtomicStampedReference<V> {
    private static class Pair<T> {
        final T reference;
        final int stamp;
        private Pair(T reference, int stamp) {
            this.reference = reference;
            this.stamp = stamp;
        }
    }
    
    private volatile Pair<V> pair;
    
    public boolean compareAndSet(V expectedReference, V newReference,
                                  int expectedStamp, int newStamp) {
        Pair<V> current = pair;
        return expectedReference == current.reference &&
               expectedStamp == current.stamp &&
               ((newReference == current.reference &&
                 newStamp == current.stamp) ||
                casPair(current, Pair.of(newReference, newStamp)));
    }
}

The solution uses three principles:

• Version tracking
• New Pair objects for each update (no reference reuse)
• External stamp management

Practical Example

public class StampedReferenceDemo {
    private static AtomicStampedReference<Integer> stampedRef =
            new AtomicStampedReference<>(1, 0);
    
    public static void main(String[] args) throws InterruptedException {
        Thread mainThread = createMainThread();
        Thread interfererThread = createInterfererThread();
        
        mainThread.start();
        interfererThread.start();
    }
    
    private static Thread createMainThread() {
        return new Thread(() -> {
            System.out.println("Thread: " + Thread.currentThread().getName() + 
                ", initial value: " + stampedRef.getReference());
            int currentStamp = stampedRef.getStamp();
            
            try {
                Thread.sleep(1000);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
            
            boolean success = stampedRef.compareAndSet(1, 2, currentStamp, currentStamp + 1);
            System.out.println("Thread: " + Thread.currentThread().getName() + 
                ", CAS result: " + success);
        }, "MainThread");
    }
    
    private static Thread createInterfererThread() {
        return new Thread(() -> {
            Thread.yield();
            stampedRef.compareAndSet(1, 2, stampedRef.getStamp(), stampedRef.getStamp() + 1);
            System.out.println("Thread: " + Thread.currentThread().getName() + 
                ", after increment: " + stampedRef.getReference());
            stampedRef.compareAndSet(2, 1, stampedRef.getStamp(), stampedRef.getStamp() + 1);
            System.out.println("Thread: " + Thread.currentThread().getName() + 
                ", after decrement: " + stampedRef.getReference());
        }, "InterfererThread");
    }
}

Output:

Thread: MainThread, initial value: 1
Thread: InterfererThread, after increment: 2
Thread: InterfererThread, after decrement: 1
Thread: MainThread, CAS result: false

The main thread's CAS fails because the stamp changed even though the value returned to its original state.