约 8 分钟3 张卡

锁与无锁

锁与无锁算法都用于协调多个线程对共享状态的访问。本文从加锁等待和 CAS 重试的成本入手，再介绍降低竞争与测量性能的方法。最后区分无锁算法的进度保证，并解释独立变量为何仍会发生缓存竞争。

CAS 是比较当前值并尝试更新的原子操作。

1. 面试核心

先记住这几条，再读正文

锁的等待关系。 锁通过互斥保护临界区，等待者依赖持有者释放。
CAS 重试成本。 CAS 失败后，线程需要重新读取状态并计算新值，竞争越强或计算越贵，重试成本越高。卡 · 锁的竞争成本
进展保证。 在执行前提满足时，lock-free 保证系统整体有操作完成，wait-free 还保证每个操作的自身步数有界。卡 · 无锁算法的进度保证
减少共享更新。 分片让不同任务更新不同状态，批处理把多次更新合并执行。两者都能减少共享位置的竞争频率，但需要明确合并与读取语义。
伪共享。 不同线程更新各自变量时，若变量位于同一缓存行，仍会因伪共享产生缓存竞争。卡 · 伪共享与缓存行竞争

2. 锁的竞争成本

必会卡 · 为什么无锁方案在高竞争下可能比锁更慢

锁通过互斥让共享状态在同一时刻只由一个线程修改。受锁保护的代码称为临界区，其他线程要等持有者释放锁后才能进入。

lock.lock();
try {
    updateState();
} finally {
    lock.unlock();
}

示例把一次状态变更放在锁内。finally 确保正常与异常路径都释放锁。

低竞争时，线程可以通过很短的路径取得锁。竞争持续时，等待者会自旋或挂起：自旋指持续尝试，挂起则暂时停止执行，等待被唤醒。不同实现会采用不同的等待策略。

这会带来以下竞争成本：

获取和释放锁需要执行原子操作，协调多个线程对锁状态的访问。
多个 CPU 核心修改共享状态时，需要协调缓存中的副本，产生缓存行迁移。缓存行是 CPU 缓存传输与一致性维护的基本单位。
等待者排队、挂起和被唤醒时，会增加调度与上下文切换的开销。

锁可以在一个临界区内完成多字段、多步骤更新，维持业务约束。它还能配合条件队列，让线程在资源未就绪时等待，等条件满足后再继续。

3. 无锁更新的重试成本

CAS 更新通过检测共享状态是否改变，判断本次计算能否提交。若其他线程先完成更新，当前线程就放弃本次结果，读取新状态后重试。

while (true) {
    State current = state.get();
    State next = current.advance();
    if (state.compareAndSet(current, next)) {
        return;
    }
}

本例要求 State 不可变，advance() 无副作用。这样，即使 CAS 失败并丢弃 next，也只浪费一次计算。线程重新读取状态后，就能安全地计算下一次更新。

竞争越密集，多个线程争夺同一缓存行的次数越多，失败计算也越多。如果 advance() 很昂贵，大量 CPU 时间就会花在最终作废的结果上。因此，无锁算法的成本需要按成功操作衡量，同时观察重试次数。

完整的数据结构还要分析节点何时可以移除、回收或复用，以及其他线程是否仍在访问它。Java 堆对象由 GC 管理回收，但节点复用仍需要遵守算法约束。

ABA 和更新函数的副作用限制见 CAS。

4. 两类方案的常见错误

选择方案时，除了运行成本，还要考虑正确性和审查难度。下表列出两类实现需要处理的主要风险。

方案	需要处理的风险
锁	锁顺序、持锁 I/O、忘记释放、等待超时
无锁算法	失败重试、局部饥饿、ABA、重复副作用

锁顺序错误会引出死锁，持锁 I/O 则会让其他线程一起等待。锁还可能造成优先级反转：高优先级线程等待低优先级线程释放锁，后者却迟迟得不到执行机会。

无锁算法中的反复重试会拖延单个线程；更新函数若带有外部副作用，失败重试还会重复执行它。因此，审查无锁结构时，需要推导各种线程交错下的状态变化。

业务需要更新多个字段时，短临界区更容易表达和审查一致性约束。需要复杂并发结构时，优先使用 JUC 的成熟组件，避免重复实现无锁链表等底层算法。

5. 降低竞争的方法

降低竞争可以先从减少共享入手，让线程更少争用同一份状态。选择锁或 CAS 之前，可以考虑以下减少争用的方法：

把计数分到多个单元，定期聚合，减少所有线程同时更新一个计数器的次数。
按 key 分配状态所有权，让同一份数据由固定的线程或任务负责修改。
批量合并更新后再提交，让多次业务操作共用一次同步。
发布不可变快照，让读者直接读取快照，减少读写争锁。
使用成熟并发容器管理单项操作，复用它们已经实现的并发算法。

这些方法仍要满足业务一致性要求。例如，分片统计需要聚合多个单元，读取方应接受聚合期间各单元仍在变化的结果。若业务要求一个时刻的精确总量，就需要更强的协调。

6. 竞争曲线基准

必会卡 · 为什么无锁方案在高竞争下可能比锁更慢

同一种算法在低竞争和高竞争下会表现不同，因此要比较性能随竞争变化的曲线。线程数至少覆盖 1、2、CPU 核心数和超额订阅。超额订阅指可运行线程数超过可用核心数，线程需要轮流使用 CPU。

设计基准时，应比较以下负载条件与性能指标：

改变读写比例和临界区长度，比较不同业务计算量下的表现。
分别使用均匀 key 和热点 key，观察集中争用的影响。
记录成功操作吞吐和 p95/p99 延迟，避免把失败重试误当作业务进展。
记录 CAS 失败数、锁等待和 park 时长，解释时间消耗在哪里。
对照 CPU、上下文切换和对象分配率，检查重试或阻塞带来的额外成本。

JMH 是 JVM 的微基准测试工具，用于测量局部代码的性能。JFR 和 async-profiler 是运行时分析工具，可以帮助解释测量结果。只测单线程，只能看到低竞争开销，无法回答并发度提高后的扩展性。

具体采集方法见锁竞争。

7. 无锁算法的进度保证

必会卡 · lock-free 和 wait-free 分别保证什么？

无锁算法的进度保证回答的是：线程持续获得执行机会时，哪些操作一定能完成。它需要分析完整算法，包括每次尝试所做的计算。下表区分三种进度保证：

性质	保证范围
obstruction-free	一个操作独自执行足够久时可以完成
lock-free	并发执行中，系统整体持续有操作完成
wait-free	每个操作在自身有界步数内完成

lock-free 保证系统整体持续有操作完成，但某个线程仍可反复失败而饥饿。wait-free 进一步约束每个操作的自身步数，让单个操作也有完成保证。这里的步数上界要在算法规定的执行前提下理解，例如底层原子操作能够完成。

这些性质描述算法的执行步数，而非现实时间的延迟上限。线程长时间得不到调度时，即使算法满足 wait-free，也要等获得 CPU 才能继续。

单次 CAS 的原子性无法替代完整算法的进度证明。若循环中还要等待锁，或执行没有完成边界的工作，就需要重新分析进度性质。