4. 无锁编程与原子操作

在并发编程中，锁通过互斥保证临界区安全，但锁本身会带来阻塞、上下文切换、优先级反转等问题。无锁编程试图用硬件提供的原子指令替代互斥锁，让多个线程在不阻塞彼此的前提下安全地修改共享数据。理解无锁编程，需要从最基础的 CAS 指令出发，逐步理解原子变量、内存屏障，最终落到无锁队列的实现与适用边界上。

一、CAS 原理：无锁的基石

CAS（Compare-And-Swap，比较并交换）是一条由 CPU 直接支持的原子指令，其语义可以概括为：给定内存地址 V、期望值 A 和新值 B，当且仅当 V 当前的值等于 A 时，才把 V 更新为 B，并返回成功；否则不做任何修改，返回失败。整个“比较—判断—写入”过程在硬件层面不可分割，因此不会出现两个线程同时通过比较的竞态。

CAS 的典型使用模式是“读取—计算—CAS 重试”循环。线程先读取共享变量的当前值，基于它计算新值，然后尝试 CAS；如果失败，说明期间有其他线程修改过该变量，于是重新读取、重新计算、再次 CAS，直到成功。这个循环被称为自旋重试。它的正确性依赖于一个关键前提：计算新值的过程本身不产生副作用，否则重试会导致副作用被重复执行。

CAS 存在两个经典问题。其一是 ABA 问题：线程读取到值 A，期间另一个线程把 A 改成 B 又改回 A，第一个线程的 CAS 仍会成功，但它无法感知中间发生过变化。解决方式通常是引入版本号或标记位，把“值 + 版本”作为一个整体进行 CAS。其二是自旋开销：在高竞争场景下，大量线程反复 CAS 失败会持续占用 CPU。因此 CAS 更适合竞争不激烈、临界区极短的场景。

二、原子变量：CAS 的工程封装

直接手写 CAS 循环既繁琐又容易出错，工程中通常使用语言或库提供的原子变量。以 Java 为例，AtomicInteger、AtomicLong、AtomicReference 等类封装了 CAS 操作，并提供 compareAndSet、getAndIncrement、updateAndGet 等方法。其中 getAndIncrement 本质上就是“读取—加一—CAS 重试”的循环封装。

原子变量并非只提供单个变量的原子操作。通过 AtomicReference 可以把多个字段打包成一个不可变对象，再对这个对象引用做 CAS，从而实现对多个字段的原子更新。这种“不可变对象 + CAS”的组合，是无锁数据结构中非常常见的技巧。

// 示例：用 AtomicReference 原子更新“余额+版本号”
class Account {
    static class State {
        final long balance;
        final long version;
        State(long balance, long version) {
            this.balance = balance;
            this.version = version;
        }
    }
    private final AtomicReference<State> ref =
        new AtomicReference<>(new State(1000, 0));

    boolean withdraw(long amount) {
        while (true) {
            State cur = ref.get();
            if (cur.balance < amount) return false;
            State next = new State(cur.balance - amount, cur.version + 1);
            if (ref.compareAndSet(cur, next)) return true;
        }
    }
}

这段示例中，版本号字段使每次更新都产生新的 State 对象，即使余额恰好回到原值，引用也不同，从而规避了 ABA 问题。需要注意的是，示例中的初始余额 1000 和扣减金额均为教学假设值，实际使用时由业务决定。

三、内存屏障：让可见性与顺序可控

CAS 和原子变量解决的是“操作不可分割”，但并发正确性还依赖另外两件事：可见性和有序性。现代 CPU 和编译器为了性能，会对指令重排序，并让写操作先停留在写缓冲区。一个线程的写入，另一个线程未必立刻看到。内存屏障（Memory Barrier/Fence）就是用来约束重排序和强制刷新可见性的指令。

常见的内存屏障语义包括：LoadLoad 屏障保证前面的读先于后面的读完成；StoreStore 屏障保证前面的写先于后面的写对其他处理器可见；LoadStore 和 StoreLoad 则分别约束读后写、写后读的顺序。在 Java 中，volatile 写操作会插入 StoreLoad 屏障，volatile 读会插入 LoadLoad/LoadStore 屏障，从而建立 happens-before 关系。C++ 则通过 std::atomic 的 memory_order 参数（relaxed、acquire、release、acq_rel、seq_cst）让开发者按需选择屏障强度。

理解内存屏障的关键在于：原子性不等于可见性。一个用 relaxed 语义的原子操作虽然不会撕裂，但可能被重排序，导致其他线程看到不一致的状态。因此无锁数据结构中，发布数据通常使用 release 语义，读取数据使用 acquire 语义，形成“写—读”配对。

四、无锁队列的实现要点

无锁队列是无锁编程最典型的落地场景。以基于单链表的 Michael-Scott 队列为例，它维护 head 和 tail 两个原子引用，并引入一个 dummy 节点：head 指向 dummy，tail 指向最后一个节点。入队时，线程先读取 tail，构造新节点，用 CAS 把 tail.next 从 null 改为新节点；成功后，再用 CAS 把 tail 推进到新节点。如果第二步 CAS 失败，说明其他线程已经推进过 tail，当前线程可以重试或直接返回。

出队时，线程读取 head 和 head.next。如果 next 为 null，说明队列为空；否则用 CAS 把 head 从旧节点改为 next，成功后返回旧 head 的数据。这里 dummy 节点的作用是让 head 始终指向一个“已出队”的哨兵节点，从而简化边界处理。

实现无锁队列时，有几个容易出错的点。第一，节点数据的写入必须发生在指针发布之前，否则其他线程可能通过 next 指针访问到尚未初始化完成的数据，这正是需要 release/acquire 屏障配对的原因。第二，tail 的推进允许滞后，即 tail 不一定总是指向真正的尾节点，这不会破坏正确性，但会影响性能。第三，节点回收不能简单 free，因为其他线程可能仍持有该节点的引用，通常需要结合引用计数、Hazard Pointer 或 epoch-based reclamation 等安全回收机制。

五、适用场景与边界

无锁队列适合以下场景：生产者或消费者数量较多、临界区极短、对延迟敏感、不能接受线程阻塞。例如高吞吐日志采集、网络包转发、任务分发等。它的优势在于没有锁竞争导致的线程挂起，最坏情况下的延迟更可控。

但无锁并不总是更快。当竞争非常激烈时，大量线程反复 CAS 失败会浪费 CPU；当临界区较长或需要维护复杂不变量时，无锁实现的复杂度会急剧上升，正确性难以验证。此外，无锁队列通常只保证单个操作的原子性，不提供跨多个操作的强一致语义。因此在实际工程中，应优先使用经过充分验证的库实现，而不是自行手写；只有在性能剖析明确显示锁是瓶颈，且团队具备相应验证能力时，才考虑自研无锁结构。