无锁编程核心

CAS 和原子类是 Java 无锁编程的基石，理解其原理和使用场景是面试必考内容。

CAS 原理 ⭐⭐⭐⭐⭐

什么是 CAS

CAS（Compare-And-Swap） 是一种乐观锁机制，实现无锁并发控制。

三个操作数：

• V（内存地址）：要更新的变量

• E（预期值）：期望的旧值

• N（新值）：要设置的新值

执行逻辑：

// 伪代码
boolean compareAndSwap(V, E, N) {
    if (V == E) {
        V = N;
        return true;
    }
    return false;
}

CAS 底层实现

硬件层面：

// Java 层面
public final boolean compareAndSet(int expect, int update) {
    return unsafe.compareAndSwapInt(this, valueOffset, expect, update);
}

// 底层调用 CPU 指令
// x86: LOCK CMPXCHG
// ARM: LDREX/STREX

内存屏障：

CAS 操作具有 volatile 读写的内存语义
- 读操作：LoadLoad + LoadStore 屏障
- 写操作：StoreStore + StoreLoad 屏障

CAS 使用示例

线程安全的计数器：

public class CASCounter {
    private AtomicInteger count = new AtomicInteger(0);

    public void increment() {
        int oldValue;
        int newValue;
        do {
            oldValue = count.get();
            newValue = oldValue + 1;
        } while (!count.compareAndSet(oldValue, newValue));
    }

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

自旋锁实现：

public class SpinLock {
    private AtomicReference<Thread> owner = new AtomicReference<>();

    public void lock() {
        Thread current = Thread.currentThread();
        // 自旋等待，直到 CAS 成功
        while (!owner.compareAndSet(null, current)) {
            // 自旋
        }
    }

    public void unlock() {
        Thread current = Thread.currentThread();
        owner.compareAndSet(current, null);
    }
}

CAS vs 锁

特性	CAS	synchronized/Lock
阻塞	非阻塞（自旋）	阻塞（等待队列）
上下文切换	无	有
适用场景	低竞争、操作简单	高竞争、复杂操作
性能	高（低竞争时）	低（需加锁）
公平性	不公平	可配置
问题	ABA、自旋开销	死锁、性能差

---

ABA 问题 ⭐⭐⭐⭐⭐

问题描述

场景：线程 T1 读取值 A，准备 CAS 更新；线程 T2 将 A 改为 B，再改回 A；T1 的 CAS 成功，但中间状态已改变。

// 栈的 ABA 问题
class Stack {
    AtomicReference<Node> top = new AtomicReference<>();

    void push(int value) {
        Node newNode = new Node(value);
        Node oldTop;
        do {
            oldTop = top.get();
            newNode.next = oldTop;
        } while (!top.compareAndSet(oldTop, newNode));
    }

    Node pop() {
        Node oldTop;
        Node newTop;
        do {
            oldTop = top.get();
            if (oldTop == null) return null;
            newTop = oldTop.next;
        } while (!top.compareAndSet(oldTop, newTop));
        return oldTop;
    }
}

// ABA 问题场景
// 线程1：读取 top = A
// 线程2：pop(A) → pop(B) → push(A)
// 线程1：CAS(A, B) 成功，但 A 已经是新对象！

危害：

• 栈结构被破坏

• 内存泄漏

• 数据不一致

解决方案

1. 版本号（AtomicStampedReference）

// 带版本号的引用
AtomicStampedReference<Integer> asr = new AtomicStampedReference<>(100, 0);

// 线程1：读取值和版本号
int[] stamp = new int[1];
Integer value = asr.get(stamp);
int version = stamp[0];

// 线程2：修改值，版本号+1
asr.compareAndSet(100, 200, 0, 1);
asr.compareAndSet(200, 100, 1, 2);

// 线程1：CAS 失败，因为版本号不匹配
asr.compareAndSet(value, 200, version, version + 1); // false

完整示例：

public class ABADemo {
    static AtomicStampedReference<Integer> asr =
        new AtomicStampedReference<>(100, 0);

    public static void main(String[] args) {
        // 线程1：读取初始值
        new Thread(() -> {
            int[] stamp = new int[1];
            Integer value = asr.get(stamp);
            System.out.println("Thread1 读取: value=" + value + ", stamp=" + stamp[0]);

            try {
                Thread.sleep(1000); // 模拟延迟
            } catch (InterruptedException e) {}

            // 尝试 CAS
            boolean success = asr.compareAndSet(value, 200, stamp[0], stamp[0] + 1);
            System.out.println("Thread1 CAS: " + success); // false
        }).start();

        // 线程2：制造 ABA
        new Thread(() -> {
            int[] stamp = new int[1];
            Integer value = asr.get(stamp);

            // A -> B
            asr.compareAndSet(value, 200, stamp[0], stamp[0] + 1);
            System.out.println("Thread2 修改为 200");

            value = asr.get(stamp);
            // B -> A
            asr.compareAndSet(value, 100, stamp[0], stamp[0] + 1);
            System.out.println("Thread2 修改回 100");
        }).start();
    }
}

2. 标记位（AtomicMarkableReference）

// 只关心是否被修改过，不关心修改次数
AtomicMarkableReference<Integer> amr = new AtomicMarkableReference<>(100, false);

// 检查是否被标记
boolean[] marked = new boolean[1];
Integer value = amr.get(marked);

if (!marked[0]) {
    amr.compareAndSet(value, 200, false, true);
}

---

Atomic 原子类 ⭐⭐⭐⭐⭐

基本类型原子类

AtomicInteger / AtomicLong / AtomicBoolean

AtomicInteger ai = new AtomicInteger(0);

// 常用方法
int get();                          // 获取当前值
void set(int newValue);             // 设置新值
int getAndSet(int newValue);        // 获取旧值并设置新值
int getAndIncrement();              // i++
int incrementAndGet();              // ++i
int getAndAdd(int delta);           // i += delta
int addAndGet(int delta);           // i += delta，返回新值
boolean compareAndSet(int expect, int update);  // CAS

// 示例
ai.incrementAndGet();               // 线程安全的 i++
ai.compareAndSet(10, 20);           // 如果当前值是 10，则改为 20

性能对比：

// synchronized 方式
public synchronized void increment() {
    count++;
}

// AtomicInteger 方式
public void increment() {
    count.incrementAndGet();  // 更快，无锁
}

数组类型原子类

AtomicIntegerArray / AtomicLongArray / AtomicReferenceArray

AtomicIntegerArray array = new AtomicIntegerArray(10);

// 原子操作数组元素
array.set(0, 100);
array.getAndIncrement(0);           // array[0]++
array.compareAndSet(0, 100, 200);   // 如果 array[0]==100，改为 200

// 批量操作示例
public class ParallelSum {
    static AtomicIntegerArray arr = new AtomicIntegerArray(1000);

    public static void main(String[] args) {
        // 多线程并发写入
        for (int i = 0; i < 10; i++) {
            new Thread(() -> {
                for (int j = 0; j < 100; j++) {
                    arr.incrementAndGet(j);
                }
            }).start();
        }
    }
}

引用类型原子类

AtomicReference

public class User {
    private String name;
    private int age;
}

AtomicReference<User> userRef = new AtomicReference<>();

// 原子更新引用
User oldUser = userRef.get();
User newUser = new User("Alice", 25);
userRef.compareAndSet(oldUser, newUser);

// 实战：单例模式
public class Singleton {
    private static AtomicReference<Singleton> instance = new AtomicReference<>();

    public static Singleton getInstance() {
        while (true) {
            Singleton current = instance.get();
            if (current != null) {
                return current;
            }
            current = new Singleton();
            if (instance.compareAndSet(null, current)) {
                return current;
            }
        }
    }
}

字段更新器

AtomicIntegerFieldUpdater / AtomicLongFieldUpdater / AtomicReferenceFieldUpdater

public class User {
    volatile int age;  // 必须是 volatile

    static AtomicIntegerFieldUpdater<User> ageUpdater =
        AtomicIntegerFieldUpdater.newUpdater(User.class, "age");

    public void increaseAge() {
        ageUpdater.incrementAndGet(this);
    }
}

// 优势：节省内存
// 如果有 100 万个 User 对象
// 使用 AtomicInteger：每个对象额外 16 字节（对象头）
// 使用 FieldUpdater：共享一个 Updater 对象

累加器（JDK 8+）

LongAdder / DoubleAdder

// LongAdder 比 AtomicLong 更快
LongAdder adder = new LongAdder();

// 多线程累加
adder.increment();      // +1
adder.add(10);          // +10
long sum = adder.sum(); // 获取总和

// 原理：分段累加，减少竞争
// AtomicLong: 所有线程竞争一个变量
// LongAdder:  每个线程有自己的累加槽，最后汇总

性能对比：

// 高并发场景（64 线程，每线程累加 1000 万次）
AtomicLong:  耗时 3000ms
LongAdder:   耗时 500ms   // 6倍提升！

---

无锁队列 ⭐⭐⭐⭐

ConcurrentLinkedQueue

特点：

• 基于 CAS 的无锁队列

• FIFO 顺序

• 线程安全

• 适合高并发场景

实现原理：

public class ConcurrentLinkedQueue<E> {
    private static class Node<E> {
        volatile E item;
        volatile Node<E> next;
    }

    private transient volatile Node<E> head;
    private transient volatile Node<E> tail;

    // 入队：CAS 更新 tail
    public boolean offer(E e) {
        Node<E> newNode = new Node<>(e);
        for (Node<E> t = tail, p = t;;) {
            Node<E> q = p.next;
            if (q == null) {
                // p 是尾节点，尝试 CAS
                if (p.casNext(null, newNode)) {
                    // CAS 成功，更新 tail（允许滞后）
                    if (p != t) {
                        casTail(t, newNode);
                    }
                    return true;
                }
            } else {
                // p 不是尾节点，继续找
                p = (p != t && t != (t = tail)) ? t : q;
            }
        }
    }

    // 出队：CAS 更新 head
    public E poll() {
        restartFromHead:
        for (;;) {
            for (Node<E> h = head, p = h, q;;) {
                E item = p.item;
                if (item != null && p.casItem(item, null)) {
                    // CAS 成功取出元素
                    if (p != h) {
                        updateHead(h, (q = p.next) != null ? q : p);
                    }
                    return item;
                } else if ((q = p.next) == null) {
                    updateHead(h, p);
                    return null;
                } else if (p == q) {
                    continue restartFromHead;
                } else {
                    p = q;
                }
            }
        }
    }
}

使用示例：

ConcurrentLinkedQueue<Integer> queue = new ConcurrentLinkedQueue<>();

// 生产者
new Thread(() -> {
    for (int i = 0; i < 1000; i++) {
        queue.offer(i);
    }
}).start();

// 消费者
new Thread(() -> {
    while (true) {
        Integer value = queue.poll();
        if (value != null) {
            System.out.println(value);
        }
    }
}).start();

ConcurrentLinkedDeque

双端队列，支持头尾两端操作：

ConcurrentLinkedDeque<Integer> deque = new ConcurrentLinkedDeque<>();

deque.offerFirst(1);   // 头部插入
deque.offerLast(2);    // 尾部插入
deque.pollFirst();     // 头部取出
deque.pollLast();      // 尾部取出

队列对比

队列	阻塞	有界	实现	性能
ConcurrentLinkedQueue	❌ 非阻塞	❌ 无界	CAS 无锁	高
ArrayBlockingQueue	✅ 阻塞	✅ 有界	ReentrantLock	中
LinkedBlockingQueue	✅ 阻塞	✅ 可选	分段锁	中
LinkedTransferQueue	✅ 阻塞	❌ 无界	CAS 无锁	高

---

面试要点 ⭐⭐⭐⭐⭐

Q1: CAS 是什么？如何实现？

• CAS = Compare-And-Swap，比较并交换

• 三个操作数：内存地址 V、预期值 E、新值 N

• 底层调用 CPU 指令（x86: LOCK CMPXCHG）

• 具有 volatile 读写的内存语义

Q2: CAS 有什么问题？

• ABA 问题：值从 A 改为 B 再改回 A，中间状态丢失

• 自旋开销：高竞争时，大量线程自旋消耗 CPU

• 只能保证一个变量：需要多个变量原子操作时无能为力

Q3: 如何解决 ABA 问题？

• 使用 AtomicStampedReference：增加版本号

• 使用 AtomicMarkableReference：增加标记位

• 不可变对象：每次修改都创建新对象

Q4: AtomicInteger 和 synchronized 的区别？

• AtomicInteger 基于 CAS，非阻塞，性能更高

• synchronized 基于互斥锁，阻塞等待，有上下文切换

• AtomicInteger 适合简单计数，synchronized 适合复杂临界区

Q5: LongAdder 为什么比 AtomicLong 快？

• AtomicLong：所有线程竞争一个变量，CAS 冲突严重

• LongAdder：分段累加，每个线程有自己的槽位，最后汇总

• 高并发下，LongAdder 性能提升 5-10 倍

Q6: ConcurrentLinkedQueue 的实现原理？

• 基于单向链表，使用 CAS 更新 head 和 tail

• 允许 tail 滞后（延迟更新），减少 CAS 次数

• 入队和出队都是无锁的，适合高并发

Q7: 什么时候使用 CAS，什么时候使用锁？

• CAS 适用：低竞争、操作简单（计数、状态标志）

• 锁适用：高竞争、复杂操作、需要公平性

Q8: volatile 和 AtomicInteger 的区别？

• volatile 只保证可见性和有序性，不保证原子性

• AtomicInteger 保证原子性（基于 CAS）

• volatile int i; i++ 不是线程安全的

• AtomicInteger i; i.incrementAndGet() 线程安全

---

参考资料

1. 书籍推荐：《Java 并发编程的艺术》、《Java 并发编程实战》

2. 论文：《Practical lock-freedom》- Keir Fraser

3. 源码：java.util.concurrent.atomic 包