并发编程- CPU 缓存模型

2022-10-15

10 min read

c/cpp , techs

本文（备忘）以程序员的角度来理解 CPU 的缓存机制。存储分层是因为 CPU 的执行速度要远快于主存的访问速度，利用程序的局部性原理，将短期内频繁使用的数据放在容量较小但访问较快的缓存里可以减少 CPU 与主存交互的次数，从而提升性能

对 CPU 结构有一定了解的编码人员一般知道当代 CPU 在缓存上的分层：L1、L2、L3 和物理内存。但真实的 CPU 架构要比这复杂，例如 CPU 和 Cache 之间还有 Store Buffer，CPU 架构图可参考这里。下图展示了不同存储结构的访问延迟

CPU 缓存

CPU 缓存（Cache）是大部分编码人员知晓的 CPU 缓存结构，当代 CPU 缓存行（Cache line）一般有固定的大小（16~256Bytes），所以缓存系统与主存同步时以固定大小的块为单位。CPU 读写（Load/Store）行为直接与 Cache 进行交互而不是主存，Cache 系统将负责不同核心之间的缓存、核心中的缓存和主存的数据同步

缓存的数量有限，特别是 L1 Cache，一般只有数千字节。随着计算的进行，那些计算所需但不存在于缓存中的数据（Cache miss）会被载入缓存中，短期内不被需要的缓存可能会被踢出缓存系统。造成 Cache miss 的原因有多种，例如缓存容量不足（capacity miss）、缓存地址冲突（associativity miss）、只读缓存（write miss）和 communication miss 等。communication miss 会在下文解释。细节请参考 Memory Barriers¹ 第 1 节

缓存一致性

多核心 CPU 中不同 Core 可能会同时读写主存中相同位置的数据，如果不同核心的缓存不进行任何同步操作，那么多线程代码在读写相同数据的时候会造成数据不一致的问题。为了保证数据的一致性（Cache-Coherence），不同 Core 之间的缓存会使用消息进行通信（上图中的 Communication Structure 用于不同 Core 缓存之间的通信）。缓存同步示例如下：

假设 Core A 将要写变量 ItemD，那么它在写之前需要发送消息给其他 Cores，其他 Cores 将 ItemD 对应的缓存行卸载后（并反馈消息给 Core A），Core A 才能写 ItemD。其他 Cores 在卸载缓存行后，后续的执行期间发现需要读取 ItemD，此时就触发了 Cache miss。此类 Cache miss 被称为 communication miss

不同 Cores 之间的缓存同步消息可以类比分布式系统中相关的概念。不同计算机结构，缓存同步耗时是不同的，比较常见的系统架构有 SMP、NUMA 等，细节可以参考这里。多 Socket 系统应尽量减少不同 Socket CPU 的缓存同步，这个过程比同一个颗 CPU 上不同 Core 之间的缓存同步要更耗时

MESI

为实现不同 Cores 中缓存数据的一致性，CPU 引入了缓存一致性协议。真实的缓存一致性协议十分复杂，对于编码人员而言，理解简化后的 MESI 协议即可

MESI 状态位

使用 MESI 协议的 Cache 系统，每个缓存行有两个标志位，可以表示当前缓存行的 4 种状态：

M (modified)，当前缓存行在其他 Cores 没有副本，且当前 Core 已经修改过缓存行中的数据，但还没有同步到主存中
E (exclusive)，当前缓存行在其他 Cores 中没有副本，且缓存行中的数据没有被修改过，即缓存中的数据与主存中的数据一致
S (Shared)，当前缓存行在其他 Cores 中有副本，且所有副本内容相同
I (Invalid)，当前缓存行中没有有效的数据

MESI 消息机制

为了实现数据一致性，不同 Cores 使用消息进行通信以实现缓存数据的同步。使用 MESI 协议的缓存之间使用 MESI 协议消息进行通信

假设同一个 CPU 上的不同 Cores 使用同一条总线进行通信，那么任何一个 Core 在读取数据时会先发起 Read Msg。如果其他核心缓存中已经载入了对应的数据，那么当前核心就可以直接从其他核心缓存中载入对应数据，这个过程避免了内存访问，提升了效率。其他比较典型的 MESI 消息有：Read Response、Invalidate Acknowledge、Read Invalidate 等。细节请参考 Memory Barriers¹ 第 2.2 节

不同核心缓存之间的同步会改变缓存行的 MESI 状态

存储缓冲

存储缓冲（Store Buffer）比 L1 Cache 更接近 CPU 的执行单元²。使用 Store Buffer 是为了减少缓存同步造成的性能损失。按照上文的介绍，一个 Core 如果想修改数据，需要先发消息通知其他缓存，其他缓存反馈后当前 Core 才能执行改动操作。消息的发送与反馈需要时间，如果没有其他机制，这个时间里当前 Core 会被阻塞

为了减少 Core 等待的时间，硬件工程师给每个 Core 新增了 Store Buffer 机制。Core 的写操作会先操作 Store Buffer 中可用的单元，待缓存行同步完成后再将修改写进缓存行中。如此，Core 在等待其他 Cache 反馈的同时可以执行其他操作

Store forwarding：CPU 读取数据时会同时访问缓存行与 Store Buffer，以获取最新的数据

Store Buffer 并不是只用于写操作，Store Buffer 中一般包含最新的数据，所以读的时候不查询 Store Buffer 将造成数据的丢失

内存屏障

void foo() { a = 1; b = 1; } // thread 1
void bar() { while(b == 0) continue; assert(a == 1); } // thread 2

Store Buffer 的存在会造成缓存数据更新的延迟。以上面代码片段为例，假设 a、b 位于不同的缓存行，那么 bar 中的 assert 就有可能失败。对于线程 1（Core A 上执行），假设 b 对应的缓存行已经被载入到 Core A 中，而 a 对应的缓存行不在，foo 中对 a 的更新写进了 Store Buffer 而对 b 的更新则直接写进了缓存行；线程 2（Core B 上执行）中，bar 读到 b 所在的缓存且得到最新数据，而 Core A/B 中与 a 相关的缓存行都未更新，从而造成 assert 的失败

The memory barrier will cause the CPU to flush its store buffer before applying each subsequent store to its variable’s cache line.

如上内存屏障（Memory Barrier）的定义，内存屏障（下面代码片段中的 smp_mb 函数将触发 CPU 内存屏障相关机制）将在 Cache 的读操作前刷新 Store Buffer 中的数据到 Cache 中（或者保证 Store Buffer 刷新到 Cache 的有序性，例如给需要刷新的 Store Buffer 标记优先级），以保证不同 Core 之间的数据有序性。这个硬件机制对应着 C++ 多线程内存序（Memory Order）里的 Happen-Before。其他与内存序相关的概念有乱序执行

void foo() { a = 1; smp_mb(); b = 1; } // thread 1
void bar() { while(b == 0) continue; assert(a == 1); } // thread 2

失效队列

内存屏障的存在会迫使 Core 刷新 Store Buffer 中的数据，这个刷新过过程会触发不同 Core 之间的通信。如果其他 Core 负载过重，那么这个反馈过程可能比较耗时，当前 Core 的刷新耗时操作也会被延长

Store Buffer 与 Cache 之间的刷新在有些场景下不需要其他 Core 进行耗时的校验。例如被标记为 S 的缓存行，当前 CPU 在可以在发送 Invalid 消息并获得其他 Core 的即时反馈后可直修改对应缓存。其他 CPU 可以把接收到的消息先放到失效队列里（Invalidate Queue），后续读写缓存前先处理队列中相关消息即可完成缓存之间的同步，而且也不会阻塞其他 Core 的操作

真实的 Invalidate Queues 机制要比上面介绍的复杂，细节请参考其他资料

再探内存屏障

Invalidate Queues 的存在有可能会打破上文介绍的数据有序性，这是因为 Core 并不会实时处理其 Invalidate Queue。实时处理 Invalidate Queue 将打断当前 Core 的流水线与多发射流程，造成性能损害，而且队列里的消息也不一定对当前操作有影响

内存屏障的另一个功能是促使 Core 执行 Invalidate Queue 中相关的消息，以更新相关缓存。如此便可以保证不同 Cores 之间的数据有序性。示例代码如下，下面代码在读写缓存时都使用 smp_mb 函数。第一个 smp 促使 Store Buffer 与缓存的同步，第二个 smp 促使 Core 处理 Invalidate Queue 中的相关消息

void foo() { a = 1; smp_mb(); b = 1; } // thread 1
void bar() { while(b == 0) continue; smp_mb(); assert(a == 1); } // thread 2

读/写屏障

如上文介绍，Mem Barrier 有两个功能：①刷新 Store Buffer ②处理 Invalidate Queue。这两个功能在不同的 CPU 架构中的实现方式不同，有些 CPU 使用一个条命令同时完成①和②；有些 CPU 分别提供了对应于①的 Write Barrier 和对应于②的 Read Barrier，如此可以减少不必要的额外操作，以进一步提升性能。示例代码如下，smp_wmb 和 smp_rmb 分别对应着①和②

void foo() { a = 1; smp_wmb(); b = 1; } // thread 1
void bar() { while(b == 0) continue; smp_rmb(); assert(a == 1); } // thread 2

此类硬件机制可对应 C++ 内存序中的 release/acquire

不同 CPU 体系

由上文可知，不同 Cores 之间实时同步缓存将影响多线程场景下 CPU 的性能。为了提升性能，不同 CPU 架构使用了不同方式放松了缓存的实时同步

顺序一致性

Ensuring sequential consistency is quite expensive and none of todays processor architectures provide a fully sequentially consistent memory model

顺序一致性（Sequential consistency）是最严格的缓存同步约束。顺序一致性条件下，无论如何，下面两个线程执行后，r1 和 r2 不可能同时为 0。因为顺序一致性成本太高，所以当代 CPU 在实现缓存结构时都放松了顺序一致性

\[Initially: \mathrm{X}=0, \mathrm{Y}=0\\ Thread 1: Thread 2:\\ \begin{array}{ll} X=1 & Y=1 \\ r 1=Y & r 2=X \end{array} \]

弱一致性

典型的 CPU 架构如 x86、ARM 和 Power 都放宽了顺序一致性约束。x86 缓存结构与上文介绍类似，不同 Core 之间的缓存同步不是实时的，ARM 和 Power 缓存模型比 x86 更宽松。这两类 CPU 的缓存结构可以类比于传统集中式服务和分布式服务。集中式服务中大部分资源相邻，不同模块之间交互快捷方便，适合耦合较紧密的业务；分布式服务中各资源分布更松散，相互之间隔离做的比较好，在执行没有相关性的业务时更高效。细节请参考 Memory Models for C/C++ Programmers²

在编码中利用缓存

理解并利用 CPU 缓存机制可以提升软件性能，测试示例见下节内容。下面列出一些多线程适用的原则

尽量使用 Padding 将不相干的数据分散在不同的缓存行中。C++17 后可以考虑使用 std::hardware_destructive_interference_size，如果编译器没有定义这个变量，可以考虑使用 char padding[256]。具体使用方法见下面测试代码
1. 对于频繁修改的数据，将锁和被锁保护的数据分离在不同的缓存行，其他线程的锁操作不会影响当前线程对数据的访问
2. 对于竞争不频繁的数据，将锁与被锁保护的数据放在相同的缓存行，减少缓存行的同步次数
尽量使用基于任务的线程模型，将数据拆分给不同的线程，避免不同线程之间的数据共享
注意 direct-mapped caches 对多线程代码的影响。很多缓存系统使用内存地址来映射内存块，假设某段代码中每次内存跳转的首地址都是内存页的首地址（比如链表的遍历），那么内存总是会被映射到缓存系统中固定的缓存行中，每次访问都会触发 Cache miss。这大大降低了系统效率，解决这类问题的一种方法是避免内存访问中出现固定模式

测试代码

测试所用代码: 参考。下面测试代码中每个线程都只执行计数操作（counter），为了避免数据的不一致，需要使用锁保护变量，或者直接使用原子变量

DistributedCounterMtx/DistributedCounterOneAtomic，所有线程访问同一个锁或者同一个原子变量
DistributedCounterMultMtx/DistributedCounterMultiAtomic，使用锁数组或者原子变量数组，不同线程访问不同变量
DistributedCounterMultMtxPadding/DistributedCounterMultiAtomicPadding，使用锁数组或者原子变量数组，不同线程访问不同的变量。与 2 不同之处在于使用 padding 将不同变量分隔在不同的缓存行中

测试结果

下面两项测试分别在不同的 PC 和操作系统下完成。以第一个测试为例，含有 Padding 的原子数组执行速度最快（12s），比使用一个全局锁要快一个数量级

Intel(R) Xeon(R) CPU E5-2630L v4 @ 1.80GHz 10C20T 64GB 2133 && Ubuntu g++ 11.3 (-O2)

DistributedCounterMtx: 157, get(): 949999981
DistributedCounterMultMtx: 53, get(): 949999981
DistributedCounterMultMtxPadding: 19, get(): 949999981
DistributedCounterOneAtomic: 42, get(): 949999981
DistributedCounterMultiAtomic: 21, get(): 949999981
DistributedCounterMultiAtomicPadding: 12, get(): 949999981

阿里云 ARM 计算服务器，Ampere Altra / AltraMax @ 2.8G 16 vCPU 32 GiB && Ubuntu g++ 9.3 (-O2)

DistributedCounterMtx: 93, get(): 949999981
DistributedCounterMultMtx: 36, get(): 949999981
DistributedCounterMultMtxPadding: 31, get(): 949999981
DistributedCounterOneAtomic: 43, get(): 949999981
DistributedCounterMultiAtomic: 38, get(): 949999981
DistributedCounterMultiAtomicPadding: 8, get(): 949999981

Intel(R) Core(TM) i7-8750H CPU @ 2.20GHz 6C12T 16GB 2667 && Win10 Visual Studio 2022 Release

DistributedCounterMtx: 44, get(): 949999981
DistributedCounterMultMtx: 17, get(): 949999981
DistributedCounterMultMtxPadding: 7, get(): 949999981
DistributedCounterOneAtomic: 24, get(): 949999981
DistributedCounterMultiAtomic: 11, get(): 949999981
DistributedCounterMultiAtomicPadding: 3, get(): 949999981

MacBook Air Apple M2 @8C8T 16GB && Apple clang version 15.0.0 (-O2)

DistributedCounterMtx: 22, get(): 949999981
DistributedCounterMultMtx: 5, get(): 949999981
DistributedCounterMultMtxPadding: 4, get(): 949999981
DistributedCounterOneAtomic: 32, get(): 949999981
DistributedCounterMultiAtomic: 14, get(): 949999981
DistributedCounterMultiAtomicPadding: 3, get(): 949999981

锁（Mutex）

对性能要求不高的场景，或者性能不是关键因素的场景，锁（mutex）是比较好的手段，无论使用还是理解都比上面介绍的机制简单。网络上对 Linux 锁的介绍文章比较多（细节可以参考这里或者这），本文不再重复。本文只描述锁的实现和上文内容的联系。下面代码片段是 linux mutex 结构体

struct mutex {
    atomic_long_t owner;  // 指向锁持有者的 task struct 结构
    spinlock_t wait_lock; // 自旋锁，用于wait_list链表的保护操作
    struct list_head wait_list; // 链表，用于管理所有在该互斥锁上睡眠的 task
		// 省略部分内容 ...
};

// 参考：https://ithelp.ithome.com.tw/m/articles/10213633
typedef struct spinlock {
    struct raw_spinlock rlock;
} spinlock_t;
// 省略部分内容 ...
typedef struct {
    volatile int counter;
} atomic_t;

mutex 成员主要是一些原子和普通变量，为实现内存同步与互斥依旧依赖内存屏障。以 mutex_lock 函数为例，其内部使用的子方法__mutex_fastpath_lock 实现如下。LOCK_PREFIX 就是上文介绍的 smp_mb 相关机制。为了性能，mutex_lock 混用了其他方法，不过这些方法也隐含内存屏障

static inline void __mutex_fastpath_lock(atomic_t *v,
                                         void (*fail_fn)(atomic_t *)) {
    asm_volatile_goto(LOCK_PREFIX "   decl %0\n"
                                  "   jns %l[exit]\n"
                      : : "m"(v->counter)
                      : "memory", "cc"
                      : exit);
    fail_fn(v);
exit:
    return;
}

McKenney, Paul E. “Memory barriers: a hardware view for software hackers.” Linux Technology Center, IBM Beaverton (2010).APA ↩︎
Pöter, Manuel, and Jesper Larsson Träff. “Memory models for C/C++ programmers.” arXiv preprint arXiv:1803.04432 (2018). ↩︎