Compare-And-Swap Principles and Volatile
Compare-And-Swap (CAS) is an optimistic locking technique that reads a value V from memory, compares it with an expected value A, and if they match, writes a new value B to memory. If they do not match, the operation is retried until it succeeds.
CAS is guaranteed to be atomic at the hardware level via the CPU instruction lock cmpxchg. In multi-core environments, the lock prefix locks the system bus, ensuring the compare-and-swap execution is uninterrupted by other cores.
For CAS to function correctly in a multithreaded environment, the shared variable must be declared with the volatile keyword. volatile ensures visibility, forcing threads to read the latest value from main memory rather than a CPU cache. While volatile alone cannot prevent instruction interleaving, combined with CAS, it achieves lock-free atomic updates.
CAS avoids the overhead of thread context switching and blocking associated with traditional mutexes like synchronized. However, under heavy contention, constant CAS failures and retries can degrade performance, making it best suited for scenarios with low contention and multiple CPU cores.
Lock-Free Withdrawal Example
import java.util.ArrayList;
import java.util.List;
import java.util.concurrent.atomic.AtomicInteger;
interface BankTransaction {
int getFunds();
void debit(int amount);
static void simulate(BankTransaction acct) {
List<Thread> threads = new ArrayList<>();
long startTime = System.nanoTime();
for (int i = 0; i < 1000; i++) {
threads.add(new Thread(() -> acct.debit(10)));
}
threads.forEach(Thread::start);
threads.forEach(t -> {
try { t.join(); } catch (InterruptedException e) { e.printStackTrace(); }
});
long endTime = System.nanoTime();
System.out.println(acct.getFunds() + " remaining, took " + (endTime - startTime) / 1_000_000 + " ms");
}
}
class UnprotectedAccount implements BankTransaction {
private int funds;
public UnprotectedAccount(int funds) { this.funds = funds; }
public int getFunds() { return funds; }
public void debit(int amount) { funds -= amount; }
}
class LockedAccount implements BankTransaction {
private int funds;
public LockedAccount(int funds) { this.funds = funds; }
public synchronized int getFunds() { return funds; }
public synchronized void debit(int amount) { funds -= amount; }
}
class LockFreeAccount implements BankTransaction {
private AtomicInteger funds;
public LockFreeAccount(int funds) { this.funds = new AtomicInteger(funds); }
public int getFunds() { return funds.get(); }
public void debit(int amount) {
while (true) {
int current = funds.get();
int updated = current - amount;
if (funds.compareAndSet(current, updated)) {
break;
}
}
}
}
public class CASDemo {
public static void main(String[] args) {
BankTransaction.simulate(new UnprotectedAccount(10000));
BankTransaction.simulate(new LockedAccount(10000));
BankTransaction.simulate(new LockFreeAccount(10000));
}
}Atomic API Categories
The java.util.concurrent.atomic package provides various atomic classes.
Atomic Integers and Custom Updates
Classes like AtomicInteger support standard atomic operations (incrementAndGet, getAndAdd). For custom logic, updateAndGet accepts a functional interface.
import java.util.concurrent.atomic.AtomicInteger;
import java.util.function.IntUnaryOperator;
public class CustomUpdater {
public static int modifyAndGet(AtomicInteger val, IntUnaryOperator op) {
while (true) {
int current = val.get();
int next = op.applyAsInt(current);
if (val.compareAndSet(current, next)) {
return next;
}
}
}
public static void main(String[] args) {
AtomicInteger num = new AtomicInteger(10);
System.out.println(modifyAndGet(num, x -> x * 3)); // Outputs 30
}
}Atomic References
For non-primitive types, AtomicReference provides CAS capabilities on object references.
import java.math.BigDecimal;
import java.util.concurrent.atomic.AtomicReference;
class DecimalAccount {
private AtomicReference<BigDecimal> balance;
public DecimalAccount(BigDecimal bal) { this.balance = new AtomicReference<>(bal); }
public BigDecimal getBalance() { return balance.get(); }
public void deduct(BigDecimal amt) {
while (true) {
BigDecimal curr = balance.get();
BigDecimal next = curr.subtract(amt);
if (balance.compareAndSet(curr, next)) break;
}
}
}The ABA Problem
CAS only checks if the expected value matches the current value. If a variable changes from A to B and back to A, CAS will not detect the intermediate modification. This is the ABA problem.
Versioned References
AtomicStampedReference resolves ABA by pairing the reference with an integer stamp (version number) that increments on each update.
import java.util.concurrent.atomic.AtomicStampedReference;
public class StampDemo {
static AtomicStampedReference<String> ref = new AtomicStampedReference<>("A", 0);
public static void main(String[] args) throws InterruptedException {
String prevRef = ref.getReference();
int prevStamp = ref.getStamp();
// Another thread modifies A -> B -> A, incrementing stamp
new Thread(() -> {
ref.compareAndSet("A", "B", ref.getStamp(), ref.getStamp() + 1);
ref.compareAndSet("B", "A", ref.getStamp(), ref.getStamp() + 1);
}).start();
Thread.sleep(100);
// Fails because the stamp no longer matches
System.out.println("Update successful? " + ref.compareAndSet(prevRef, "C", prevStamp, prevStamp + 1));
}
}Marked References
When only a boolean state change needs tracking (rather than a full version history), AtomicMarkableReference can be used.
Atomic Arrays
AtomicIntegerArray, AtomicLongArray, and AtomicReferenceArray provide thread-safe operations on array elements.
Field Updaters
AtomicIntegerFieldUpdater, AtomicLongFieldUpdater, and AtomicReferenceFieldUpdater allow atomic operations on specific volatile fields of a class without wrapping the entire class in an atomic container.
import java.util.concurrent.atomic.AtomicIntegerFieldUpdater;
class Player {
volatile int score;
}
public class FieldUpdaterDemo {
public static void main(String[] args) {
AtomicIntegerFieldUpdater<Player> updater =
AtomicIntegerFieldUpdater.newUpdater(Player.class, "score");
Player p = new Player();
updater.compareAndSet(p, 0, 100);
System.out.println(p.score);
}
}LongAdder Internals and Performance
Under high contention, AtomicLong suffers from frequent CAS retries. LongAdder addresses this by distributing updates across an array of Cell objects. Each thread updates a different cell, and the sum() method aggregates the base value and all cell values.
Internal Fields
base: Accumulates values when there is no contention.cells: Lazily initialized array of accumulation units.cellsBusy: Avolatile intflag (0 = unlocked, 1 = locked) used to guard cell array initialization and expansion.
CAS-Based Locking
The cellsBusy flag acts as a spinlock implemented via CAS.
import java.util.concurrent.atomic.AtomicInteger;
class SimpleSpinLock {
private AtomicInteger state = new AtomicInteger(0);
public void lock() {
while (!state.compareAndSet(0, 1)) {
// Spin and wait
}
}
public void unlock() {
state.set(0);
}
}Cache Line Pseudo-Sharing
CPU caches operate in 64-byte units called cache lines. If multiple Cell objects share the same cache line, an update to one cell by one core will invalidate the entire cache line for other cores, causing severe performance degradation. This is known as pseudo-sharing.
LongAdder's internal Cell class uses the @sun.misc.Contended annotation, which instructs the JVM to add padding (typically 128 bytes) around the object, ensuring each Cell resides on its own cache line.
Add and Sum Mechanics
The add(long x) method first attempts to CAS the base variable. If contention is detected (CAS fails), it selects a Cell based on the thread's probe value and attempts to CAS the cell's value. If the cell array does not exist or the chosen cell is null, it invokes longAccumulate to initialize or expand the array.
The sum() method is not atomic. It reads the base and iterates over the cells array, summing them up. Concurrent writes during the summation process will not be blocked but may not be reflected in the returned total.
Direct Unsafe Operations
sun.misc.Unsafe provides low-level memory and CAS operations. Because its singleton field theUnsafe is private, reflection is required to obtain an instance.
import sun.misc.Unsafe;
import java.lang.reflect.Field;
public class UnsafeAccess {
public static Unsafe getUnsafe() {
try {
Field f = Unsafe.class.getDeclaredField("theUnsafe");
f.setAccessible(true);
return (Unsafe) f.get(null);
} catch (Exception e) {
throw new RuntimeException(e);
}
}
}Custom Atomic Implementation
Using Unsafe, we can implement atomic protection on arbitrary object fields by calculating their memory offset.
import sun.misc.Unsafe;
abstract class Transaction {
abstract int getBalance();
abstract void withdraw(int amt);
}
class CustomAtomicCounter extends Transaction {
private volatile int balance;
private static final Unsafe UNSAFE;
private static final long BALANCE_OFFSET;
static {
UNSAFE = UnsafeAccess.getUnsafe();
try {
BALANCE_OFFSET = UNSAFE.objectFieldOffset(CustomAtomicCounter.class.getDeclaredField("balance"));
} catch (NoSuchFieldException e) {
throw new Error(e);
}
}
public CustomAtomicCounter(int initial) { this.balance = initial; }
public int getBalance() { return balance; }
public void withdraw(int amt) {
while (true) {
int curr = balance;
int next = curr - amt;
if (UNSAFE.compareAndSwapInt(this, BALANCE_OFFSET, curr, next)) {
return;
}
}
}
}