并发原语：面试需要掌握到什么程度

为什么 LLD 会考并发

几乎每道 LLD 题最后都会被追问“如果多个线程同时调用呢”。还有一类题直接考并发：有界阻塞队列、限速执行器、哲学家就餐、多线程按顺序打印。这一章把需要的工具和思维方式过一遍，后面两章用它们解题。

三个核心问题

问题	含义	例子
原子性	一组操作要么全做，要么别人看不到中间状态	count++ 是读、改、写三步，两个线程并发会丢更新
可见性	一个线程的写，另一个线程何时能看到	一个线程把 stop 设为 true，另一个线程的循环可能一直看不到
有序性	编译器和 CPU 可能重排指令	双重检查锁的单例，没有 volatile 时可能拿到未初始化完的对象

在 Java 里，正确使用锁可以同时解决这三个问题：解锁前的写入，对随后获得同一把锁的线程可见（happens-before 关系）。volatile 只解决可见性和有序性，不保证复合操作的原子性。

Python 同学注意：GIL 不等于线程安全。x += 1 会编译成多条字节码，线程可能在中间被切换。Python 3.13 起还有可选的无 GIL 构建（free-threaded），多个线程真正并行执行字节码，靠 GIL “碰巧没出事”的代码会更快暴露问题。

工具箱

原语	用途	要点
互斥锁：synchronized、ReentrantLock	保护临界区	一次只有一个线程进入
读写锁 ReadWriteLock	读多写少	读操作必须真的只读（LRU 的 get 就不是）
条件变量：Condition、wait/notify	等待某个条件成立	持锁时等待，用 while 检查
信号量 Semaphore	限制同时访问的数量	计数 + 阻塞，适合资源池、并发上限
原子变量 / CAS	单变量无锁更新	适合计数器、标志位；多个变量要一致仍需锁；注意 ABA 问题
CountDownLatch / CyclicBarrier	等待一组线程到达某一点	Latch 一次性，Barrier 可重复使用
并发容器：ConcurrentHashMap、BlockingQueue	现成的线程安全结构	能用就用，但“先查再改”这类复合操作仍需注意

CAS 的 ABA 问题：线程读到值 A，准备 CAS 成 C；在此期间别的线程把它改成 B 又改回 A，CAS 照样成功，中间发生过的变化被忽略了。在无锁栈、无锁链表里，这会让一个已经被移除又重新入栈的节点被错误地当成“没变过”。解法是给值带上版本号（Java 的 AtomicStampedReference）。单纯的计数器不受影响。

条件变量的标准模板

这是并发题里出现频率最高的代码形状，要能闭着眼睛写出来：

lock.lock();
try {
    while (!conditionHolds()) {   // 必须是 while
        cond.await();             // 释放锁并睡眠；被唤醒后重新拿锁
    }
    doWork();                     // 此时条件成立且持有锁
    otherCond.signal();           // 通知等待另一个条件的线程
} finally {
    lock.unlock();
}

为什么是 while 而不是 if？两个原因：

1. 虚假唤醒：规范允许线程在没有被 signal 的情况下醒来。
2. 被抢先：线程 A 被唤醒后要重新抢锁，可能线程 B 先拿到锁并把条件又改掉了。A 拿到锁时条件未必还成立。

signal 还是 signalAll

• 所有等待者等的是同一个条件，且每次只有一个能继续时，signal 就够了，开销更小。
• 如果一个条件变量上混着等不同条件的线程（比如 Java 内置的 wait/notify 只有一个等待集合，生产者和消费者都在里面），notify 可能唤醒了错误的一方，真正能干活的线程却一直睡着，系统卡住。这时要么用 notifyAll，要么拆成两个条件变量。

死锁

死锁需要四个条件同时成立：互斥、持有并等待、不可抢占、循环等待。破坏任意一个就能避免，实践中最常用的是破坏循环等待：

• 固定加锁顺序：比如转账时总是先锁 id 小的账户。
• tryLock 加超时：拿不到就释放已持有的锁，退避后重试。退避时加随机抖动，否则容易变成活锁。
• 缩小锁的范围：持锁时不要调用外部代码（回调、IO、别的对象的同步方法）。

两个相关概念：活锁（线程都在动，但互相谦让，谁也推进不了）和饥饿（某个线程长期拿不到资源；公平锁能缓解，代价是吞吐下降）。

持锁期间别做的事

• 不要 sleep：其他线程全被你堵住了。
• 不要做网络或磁盘 IO。
• 不要调用不受你控制的回调。

正确的姿势是：锁里只做“读写共享状态”那一小段，把结果带到锁外再做耗时的事情。后面的限速执行器就有一个典型例子：在锁里算出要等多久，在锁外 sleep。

Java 虚拟线程：JDK 21–23 里，虚拟线程在 synchronized 块内阻塞时会被钉（pin）在载体线程上，载体线程被占满时程序会卡住，所以当时的建议是需要阻塞的临界区用 ReentrantLock。JDK 24（JEP 491）已经修复了这个问题。面试时能说出版本差异是加分项。

选型顺序

面试时遇到并发需求，按这个顺序考虑：

1. 能不能避免共享？每个线程独占状态，通过队列传消息。
2. 有没有现成的并发容器或 Executor？
3. 一把粗粒度的锁够不够？
4. 有了性能瓶颈的证据，才考虑细粒度锁、读写锁或无锁结构。

能清楚说出“先保证正确，用最简单的同步方式，再根据瓶颈优化”，比直接写出复杂的无锁代码更能让面试官放心。

去做题

Core Skills 的「并发」分组有 7 道能在线判题的多线程题，Python、Java、Go、C++ 都能提交。驱动会打乱线程的启动顺序，并在关键位置随机让出 CPU，同步没做对的代码很快就会出错：

• 按序执行、交替输出、零、偶、奇：用信号量或条件变量安排线程的先后。
• 造水分子：信号量加屏障，让线程按组通过。
• 哲学家就餐：固定加锁顺序，破坏循环等待。
• 有界阻塞队列：下一章的主题，单锁加两个条件变量。
• 读写锁：用一把锁和条件变量自己实现读者共享、写者独占。