第7章 多核系统（并行的挑战） Multicore Systems
一、导读
1.1 本章学习目标
理解多核处理器架构的演进历程及其对操作系统设计的影响
掌握缓存一致性（Cache Coherence）问题的本质和主要解决方案
深入理解 MESI 协议及其变体的工作原理
理解内存模型（Memory Model）的概念，掌握内存屏障（Memory Barrier）的作用
了解 NUMA（Non-Uniform Memory Access）架构的特性及其对性能的影响
掌握多核环境下的同步机制和锁竞争问题
理解无锁编程（Lock-Free Programming）的基本思想和常见数据结构
了解多核系统的性能扩展性挑战和优化策略
1.2 为什么本章如此重要
多核处理器的普及是 21 世纪计算领域最重要的架构变革之一。自 2005 年前后，由于功耗和散热的物理限制，单核处理器的频率提升遭遇瓶颈（"频率墙"），处理器厂商转向在单个芯片上集成多个处理核心。从最初的双核发展到如今的数十核甚至上百核，多核架构已成为所有计算平台——从智能手机到超级计算机——的标准配置。
多核架构对操作系统的设计提出了全新的挑战。在单核系统中，并发是通过时间片切换实现的——任何时刻只有一个线程在执行，切换点是确定的（时钟中断）。在多核系统中，多个线程真正同时执行在不同的核心上，竞争和同步问题变得更加复杂和微妙。数据竞争（Data Race）不再只是理论上的可能性，而是在实际运行中频繁出现的现实问题。
从性能的角度来看，多核系统的性能扩展并非简单的线性关系。Amdahl 定律指出，程序中串行部分的比例决定了并行加速的理论上限。Gustafson 定律则从另一个角度说明，随着问题规模的增大，并行部分的比例可能增加。理解这些定律对于合理评估多核系统的性能潜力至关重要。
从软件生态的角度来看，多核时代的到来迫使整个软件行业重新思考编程模型。传统的单线程编程模型无法利用多核的计算能力，开发者需要采用多线程、多进程或异步编程模型来编写并行程序。操作系统作为软件栈的基础层，必须提供高效的原语和支持机制来帮助上层软件充分利用多核架构。
1.3 核心问题引导
为什么单核处理器的频率提升遇到了瓶颈？多核架构是如何解决这一问题的？
什么是缓存一致性问题？为什么多核系统中每个核心需要独立的缓存？
MESI 协议如何维护多个核心之间的缓存一致性？它的状态转换规则是什么？
什么是内存模型？为什么不同处理器架构的内存模型不同？
内存屏障的作用是什么？在什么场景下需要使用内存屏障？
NUMA 架构与 UMA 架构有什么区别？NUMA 对程序性能有什么影响？
多核系统中的锁竞争为什么比单核系统更严重？有哪些缓解策略？
无锁编程的基本思想是什么？它真的能完全替代基于锁的编程吗？
二、核心概念详解
2.1 多核架构与缓存层次
多核处理器在单个芯片（Die）上集成了多个处理核心（Core），每个核心拥有独立的执行单元、寄存器和缓存。多核架构的出现是半导体技术发展和功耗限制共同作用的结果。
单核处理器的性能提升传统上依赖于频率提升和微架构改进。然而，根据动态功耗公式 P = C V^2 f（C 为电容，V 为电压，f 为频率），频率的提升导致功耗呈超线性增长。当频率超过一定阈值后，散热问题变得不可解决（"频率墙"）。同时，晶体管密度的持续增长（摩尔定律）使得在芯片上集成更多核心成为可能。因此，处理器厂商从"更大、更快的单核"转向"更多、更小的多核"。
现代多核处理器的缓存层次结构通常为三级。L1 Cache 是每个核心私有的高速缓存，通常分为指令缓存（L1i）和数据缓存（L1d），大小约为 32-64KB，访问延迟约 3-4 个 CPU 周期。L2 Cache 也是每个核心私有的，大小约为 256KB-1MB，访问延迟约 10-12 个周期。L3 Cache（Last Level Cache, LLC）被所有核心共享，大小通常为几 MB 到几十 MB，访问延迟约 30-40 个周期。
缓存层次的设计基于局部性原理——大部分内存访问集中在最近访问过的数据附近。L1 Cache 提供最快的访问速度但容量最小，L3 Cache 容量较大但速度较慢，主存（DRAM）容量最大但速度最慢。这种层次化结构在成本和性能之间取得了良好的平衡。
多核架构带来了缓存一致性问题。由于每个核心都有自己的 L1 和 L2 缓存，当多个核心读写同一内存位置时，各核心缓存中的副本可能不一致。例如，核心 A 将变量 x 的值从 1 修改为 2，但如果核心 B 的缓存中仍然保存着 x 的旧值 1，B 读到的就是错误的结果。缓存一致性协议通过核心之间的通信来确保所有核心看到的内存值是一致的。
2.2 缓存一致性协议
缓存一致性协议（Cache Coherence Protocol）确保在多核系统中，无论哪个核心读取某个内存位置，都能获得该位置最新的值。一致性协议需要维护两个属性：写传播（Write Propagation）——一个核心对内存的写操作必须传播到其他核心的缓存中；事务串行化（Transaction Serialization）——多个核心对同一位置的写操作必须按某种顺序串行化。
MESI 协议是最经典的缓存一致性协议，由 Intel 在其处理器中广泛使用。MESI 为每个缓存行（Cache Line，通常为 64 字节）定义了四种状态。
Modified（M，已修改）：缓存行已被当前核心修改，与内存中的值不一致。该核心拥有此缓存行的唯一有效副本。当该缓存行被替换时，需要将修改后的值写回内存（Write-Back）。
Exclusive（E，独占）：缓存行与内存中的值一致，且只有当前核心的缓存中包含此缓存行。核心可以在不通知其他核心的情况下直接修改此缓存行（状态变为 M）。
Shared（S，共享）：缓存行与内存中的值一致，且可能被多个核心的缓存同时包含。核心不能直接修改共享状态的缓存行——修改前必须先通知其他核心使其失效。
Invalid（I，无效）：缓存行无效，不能被使用。当核心需要访问此缓存行时，必须从内存或其他核心的缓存中获取。
MESI 协议的状态转换由核心之间的嗅探（Snooping）消息驱动。每个核心通过共享总线或目录（Directory）监听其他核心的缓存操作。当核心 A 要写入一个处于 S 状态的缓存行时，它广播一个"读独占"（Read For Ownership, RFO）消息，其他核心将自己的副本置为 I 状态，A 的缓存行状态变为 M。
MESI 协议的变体包括 MESIF（增加了 Forward 状态用于优化数据转发）和 MOESI（增加了 Owned 状态允许脏数据共享，AMD 处理器使用）。这些变体在保持一致性的同时优化了特定的性能场景。
2.3 内存模型与内存屏障
内存模型（Memory Model）定义了多处理器系统中内存操作的可见性顺序。它规定了当一个核心写入内存位置后，其他核心在什么条件下能够看到这次写入。
在单核系统中，内存操作的顺序与程序顺序一致——编译器优化和 CPU 乱序执行不会影响程序的语义，因为只有一个执行流。但在多核系统中，编译器和 CPU 的优化可能改变内存操作的可见顺序，导致其他核心观察到不一致的结果。
编译器的重排序（Compiler Reordering）：编译器为了优化性能，可能调整不依赖的内存操作的执行顺序。例如，a = 1; b = 2; 可能被优化为 b = 2; a = 1;。在单核中这不影响结果，但在多核中，如果另一个核心在 a 和 b 的写入之间读取它们，可能看到 a 仍为旧值而 b 已为新值的不一致状态。
CPU 的重排序（CPU Reordering）：现代 CPU 采用乱序执行（Out-of-Order Execution）来提高指令级并行度。不同架构的重排序规则不同。x86 采用强内存模型（TSO, Total Store Ordering），只允许写后读的重排序。ARM 和 RISC-V 采用弱内存模型，允许更广泛的重排序，提供了更大的优化空间但增加了编程复杂性。
内存屏障（Memory Barrier / Fence）是强制内存操作顺序的指令。Load Barrier 确保屏障之前的所有读操作在屏障之后的读操作之前完成。Store Barrier 确保屏障之前的所有写操作在屏障之后的写操作之前完成。Full Barrier 同时保证读和写的顺序。
在编程实践中，内存屏障通常通过高级同步原语间接使用。互斥锁（Mutex）的获取操作包含 Acquire 语义（相当于 Load Barrier），确保锁之后的读写不会被重排到锁获取之前。释放操作包含 Release 语义（相当于 Store Barrier），确保锁之前的读写不会被重排到锁释放之后。原子操作（Atomic Operations）也隐含了适当的内存屏障。
2.4 NUMA 架构
NUMA（Non-Uniform Memory Access，非统一内存访问）架构是多核系统中内存组织的一种方式。在传统的 UMA（Uniform Memory Access）架构中，所有核心访问任何内存位置的延迟相同。而在 NUMA 架构中，内存被划分为多个节点（Node），每个节点与一组核心关联，核心访问本地节点内存的延迟远低于访问远程节点内存的延迟。
NUMA 架构的产生源于物理布局的限制。当核心数量增加到一定程度时，所有核心共享一个统一的内存总线成为性能瓶颈——总线的带宽和延迟无法满足大量核心的并发访问需求。NUMA 通过将内存分散到多个节点，每个节点有自己的内存控制器，从而增加了总体的内存带宽。
在典型的 NUMA 系统中（如 AMD EPYC 和 Intel Xeon 服务器处理器），每个 CPU 封装（Socket）或 CCD（Core Complex Die）构成一个 NUMA 节点。本地内存访问延迟约为 80-100ns，远程内存访问延迟可能高达 140-200ns，性能差距可达 40-100%。
NUMA 对程序性能有显著影响。如果进程的数据分配在远程 NUMA 节点上，每次内存访问都需要跨节点传输，增加了延迟并占用了节点间的互连带宽（如 Intel 的 UPI 或 AMD 的 Infinity Fabric）。在极端情况下，NUMA 节点间的互连可能成为瓶颈，导致性能反而低于 UMA 架构。
NUMA 感知的优化策略包括以下几种。线程亲和性（Thread Affinity）将线程绑定到特定的核心或 NUMA 节点上，避免线程迁移导致的缓存失效和远程内存访问。本地内存分配（Local Memory Allocation）确保进程的内存从其执行所在的 NUMA 节点分配。Linux 提供了 numactl 工具和 mbind()、set_mempolicy() 等系统调用来控制 NUMA 内存策略。首次接触分配（First-Touch Policy）是 Linux 的默认策略——内存由首次访问它的核心所在节点分配。
三、深入分析与讨论
3.1 锁竞争与可扩展性
在多核系统中，锁（Lock）是保护共享数据的基本同步机制。然而，随着核心数量的增加，锁竞争（Lock Contention）成为系统可扩展性的主要瓶颈。
当多个核心上的线程竞争同一把锁时，只有一个线程能获得锁并执行临界区代码，其他线程必须等待。等待的线程消耗了 CPU 周期（自旋锁的情况）或涉及上下文切换（互斥锁的情况），这些都是纯粹的性能浪费。更严重的是，锁竞争导致并行执行退化为串行执行，使得增加核心数量无法带来性能提升。
锁竞争的性能影响可以通过几个指标来衡量。吞吐量（Throughput）——单位时间内完成的操作数，锁竞争导致吞吐量随核心数增加而趋于饱和。延迟（Latency）——单个操作的完成时间，锁竞争增加了等待时间。可扩展性（Scalability）——性能随核心数增长的比例，理想情况下应为线性增长，但锁竞争导致亚线性甚至零增长。
缓解锁竞争的策略包括以下几种。细粒度锁（Fine-Grained Lock）用多个小锁替代一个大锁，减少同时竞争同一把锁的线程数。例如，哈希表的每个桶使用独立的锁，而不是整个表使用一把锁。读写锁（Read-Write Lock）允许多个读者并发访问但写者独占，在读多写少的场景中显著提高并发度。锁分离（Lock Splitting）将不同功能的锁分开——如 Java 的 ConcurrentHashMap 将 size 操作的锁与 put/get 操作的锁分离。锁合并（Lock Coalescing）在单线程执行路径上合并多个锁操作，减少锁的获取和释放次数。
3.2 无锁编程与并发数据结构
无锁编程（Lock-Free Programming）试图完全消除锁的使用，通过原子操作和内存屏障来实现线程安全。无锁算法保证在任意时刻至少有一个线程能够取得进展，即使其他线程被暂停或延迟。
原子操作（Atomic Operation）是无锁编程的基础。CAS（Compare-And-Swap）是最重要的原子操作——它将内存位置的值与预期值比较，如果相等则更新为新值，否则不做修改。CAS 操作是不可中断的，在硬件层面由 CPU 保证原子性。基于 CAS 可以构建各种无锁数据结构。
无锁栈的实现：使用 CAS 操作来更新栈顶指针。压栈时，将新节点的 next 指向当前栈顶，然后用 CAS 将栈顶指针从旧值更新为新节点。如果 CAS 失败（说明其他线程修改了栈顶），则重试。弹栈类似，用 CAS 将栈顶指针更新为栈顶的 next。
无锁队列的实现更为复杂，通常需要解决 ABA 问题——线程 A 读取值 X，线程 B 将 X 改为 Y 再改回 X，线程 A 的 CAS 成功但实际上中间状态被忽略了。解决方法包括使用版本号（Stamped Reference）或 Hazard Pointer。
然而，无锁编程并非银弹。无锁算法的设计和验证极其复杂，容易出现微妙的 Bug。CAS 的重试循环在高竞争场景下可能消耗大量 CPU 周期。此外，无锁算法通常需要处理内存回收问题——如何安全地释放被其他线程引用的节点。因此，在实践中，细粒度锁和读写锁往往是更好的选择，无锁编程更适合特定的高性能场景。
四、实践案例
4.1 Linux 内核的多核优化
Linux 内核经过数十年的多核优化，积累了丰富的多核编程经验。
内核的锁机制经历了从大内核锁（Big Kernel Lock, BKL）到细粒度锁的演进。早期的 Linux 使用一把全局的 BKL 保护内核数据结构，这严重限制了多核扩展性。从 Linux 2.6 开始，BKL 被逐步替换为细粒度的自旋锁和互斥锁。到 Linux 2.6.39，BKL 被完全移除。
Per-CPU 变量是 Linux 内核中避免锁竞争的重要技术。对于不需要在核心之间共享的数据，为每个 CPU 核心创建独立的副本。例如，每个核心的调度运行队列、统计计数器等都是 per-CPU 变量。访问 per-CPU 变量不需要任何锁，因为每个核心只访问自己的副本。当需要汇总所有核心的数据时（如统计总 CPU 使用率），遍历所有核心的副本并求和。
RCU（Read-Copy-Update）是 Linux 内核中一种革命性的同步机制，由 Paul McKenney 设计。RCU 的核心思想是：读操作不加锁，直接访问数据；写操作创建数据的副本，修改副本后用原子操作将指针切换到新副本。旧副本在所有读者完成访问后（经过一个"宽限期" Grace Period）才被释放。RCU 在读多写少的场景中性能极佳，被广泛应用于内核的路由表、进程列表等数据结构。
4.2 多核性能分析与调优
使用性能分析工具可以识别多核程序中的性能瓶颈。
Linux 的 perf 工具提供了全面的性能分析功能。perf stat 可以统计程序的硬件事件（如缓存未命中、分支预测失败、指令周期数）。perf record 和 perf report 可以进行采样分析，定位热点函数。perf c2c（Cache to Cache）专门用于分析多核间的缓存行竞争——它可以识别哪些缓存行在核心之间频繁传递（False Sharing 或 True Sharing），帮助开发者优化数据结构布局。
False Sharing 是多核编程中的常见陷阱。当两个线程在不同的核心上运行，但修改位于同一缓存行的不同变量时，缓存一致性协议会频繁地在核心之间传递该缓存行，导致性能急剧下降。解决方法是在数据结构中插入填充（Padding），确保不同线程访问的变量位于不同的缓存行。
NUMA 性能分析可以使用 numastat 命令查看每个进程的 NUMA 内存分布。如果发现大量内存分配在远程节点上，可以通过 numactl --interleave=all 启用交叉分配策略，或使用 numactl --membind 将内存绑定到特定节点。
五、常见误区与注意事项
误区：核心数越多性能越好。 由于 Amdahl 定律的限制、锁竞争和同步开销，程序的性能不会随核心数线性增长。通常当核心数超过一定阈值后，性能增益急剧下降。
误区：无锁编程总是比有锁编程更快。 无锁编程在低竞争场景中可能更快，但在高竞争场景中，CAS 重试循环可能消耗大量 CPU 周期。选择锁策略应根据实际竞争程度来决定。
误区：多线程程序天然能利用多核。 如果程序中存在全局锁或串行瓶颈，多线程程序可能仍然只有一个核心在工作。需要使用性能分析工具识别并消除瓶颈。
注意事项：警惕 False Sharing。 在多线程程序中，确保不同线程频繁访问的变量不在同一缓存行中。使用 alignas(64) 或手动填充来对齐数据结构。
注意事项：内存分配器的多核扩展性很重要。 传统的 malloc() 实现可能使用全局锁，在高并发场景中成为瓶颈。使用 per-CPU 缓存的分配器（如 jemalloc、tcmalloc）可以显著提高多核扩展性。
六、本章小结
本章深入探讨了多核系统的架构特性和编程挑战。多核架构是频率提升遭遇物理瓶颈后的必然选择，每个核心拥有独立的缓存层次，带来了缓存一致性问题。MESI 协议通过缓存行状态管理和嗅探消息来维护一致性。内存模型定义了多核环境中内存操作的可见性顺序，内存屏障用于防止编译器和 CPU 的重排序破坏并发正确性。NUMA 架构通过分布式内存控制器增加了内存带宽，但引入了非均匀的访问延迟，需要 NUMA 感知的优化策略。锁竞争是多核系统可扩展性的主要瓶颈，细粒度锁、读写锁和 RCU 等机制可以缓解竞争。无锁编程通过原子操作消除了锁的使用，但设计复杂且适用场景有限。Linux 内核的 per-CPU 变量、RCU 和细粒度锁机制为多核编程提供了优秀的实践范例。
七、思考题与练习
画出 MESI 协议的完整状态转换图，标注每个转换的触发条件。分析以下场景中的状态变化：核心 A 读取变量 x，核心 B 也读取 x，核心 A 写入 x，核心 B 再次读取 x。
解释 Amdahl 定律和 Gustafson 定律。如果一个程序有 10% 的串行代码，在 8 核系统上的理论最大加速比是多少？如果核心数增加到 64 呢？
什么是 False Sharing？设计一个实验来验证 False Sharing 对性能的影响。如何通过数据结构布局来消除 False Sharing？
研究 Linux 的 RCU 机制。它的基本工作原理是什么？与读写锁相比有什么优势？"宽限期"是如何确定的？
分析一个 NUMA 系统的内存访问模式。使用 numactl --hardware 查看系统的 NUMA 拓扑，使用 numastat 分析进程的内存分布。
实现一个基于 CAS 的无锁栈。分析在什么情况下 CAS 会失败？重试循环的最大迭代次数是否有上界？
比较 x86 的 TSO 内存模型和 ARM 的弱内存模型。为什么 ARM 选择弱内存模型？这对跨平台并发程序的编写有什么影响？
研究 Google 的 tcmalloc 或 Facebook 的 jemalloc 内存分配器。它们是如何实现 per-CPU 缓存来避免锁竞争的？与传统的 glibc malloc 相比有什么优势？