关于CPU Cache

CPU-Cache

从主存访问数据有很高的延迟成本(大约 100 到 300 个时钟周期)，因此处理器核心使用本地高速缓存来将数据保存在需要的硬件线程附近。从缓存访问数据的成本要低得多(大约 3 到 40 个时钟周期)，这取决于所访问的缓存。

由图可知，一般是三级缓存：L3->L2->L1速度依次递减

  1. L1 Cache最接近CPU, 容量最小（如32K、64K等）、速度最高，每个核上都有一个L1 Cache（准确地说是两个L1 Cache, 一个存数据 L1d Cache, 一个存指令 L1i Cache）
  2. L2 Cache容量更大（如256K）、速度更低, 一般情况下，每个核上都有一个独立的L2 Cache。
  3. L3 Cache最接近内存，容量最大（如12MB），速度最低，同一个CPU插槽之间的核共享一个L3 Cache。

CPU从内存读取数据到CPU Cache的过程中，是一小块一小块来读取数据的，而不是按照单个元素来读取数据的。

这样一小块一小块的数据，在CPU Cache里面，叫做Cache Line，Cache line是高速缓存系统的最小交换单位

在我们日常使用的 Intel 服务器或者 PC 里，Cache Line 的大小通常是 64 字节

MESI协议

MESI协议规定Cache line必须处于这四种状态中：

  1. M（修改, Modified）: 当前CPU cache拥有最新数据（拥有最新的cache line），其他CPU拥有失效数据（cache line的状态是invalid），虽然当前CPU中的数据和主存是不一致的，但是以当前CPU的数据为准。
  2. E（专有, Exclusive）: 只有当前CPU中有数据，其他CPU中没有改数据，当前CPU的数据和主存中的数据是一致的。
  3. S（共享, Shared）: 当前CPU和其他CPU中都有共同数据，并且和主存中的数据一致。
  4. I（无效, Invalid）: 当前CPU中的数据失效，数据应该从主存中获取，其他CPU中可能有数据也可能无数据，当前CPU中的数据和主存被认为是不一致的。

MESI是一种写失效（Write Invalidate）协议

  1. 当一个CPU写入数据时
  2. 在这个CPU核心写入Cache之后，它会去广播一个“失效”请求告诉所有其他的CPU核心。
  3. 其他的CPU核心，只是去判断自己是否也有一个“失效”版本的Cache line，然后把这个也标记成失效

相对的，也有一种写广播（Write Broadcast）协议：一个写入请求广播到所有的CPU核心，同时更新各个核心里的Cache line

写失效只需要告诉其他的CPU核心，哪一个地址失效了

但是写广播还需要把对应的数据传输给其他CPU核心，而写广播需要占用更多的总线带宽

总线嗅探机制

即Snoopy 协议，帮助实现MESI协议，这种协议更像是一种数据通知技术，CPU和内存通过总线（BUS）互通消息。

CPU感知其他CPU的行为（比如读、写某个缓存行）就是是通过嗅探（Snoop）其他CPU发出的请求消息完成的。

CPU Cache 通过这个协议可以识别其它Cache上的数据状态。有时CPU也需要针对总线中的某些请求消息进行响应，如果有数据共享的话，可以通过广播机制将共享数据的状态通知给其它 CPU Cache。这个协议要求每个 CPU Cache 都可以窥探数据事件的通知并做出相应的反应。

缓存的一致性

每个内核都有自己所需的cache line的副本，取值运算都在副本中进行。这就是为什么多线程应用中内存的变化会造成性能噩梦。

当并行的多个线程正在访问相同的数据值，甚至是相邻的数据值时，它们将访问同一cache line上的数据。

为了提高写的性能，主流的 CPU采用的是 Write Back 的策略：写操作先在 cache 上，然后再 flush 到内存上

如果某个核心上的一个线程对其cache line的副本进行了更改，那么根据总线MESI协议，同一cache line的所有其他副本都必须标记为失效。当线程尝试对dirty cache line进行读写访问时，需要放弃此次cache line访问，转而向主存访问(大约 100 到 300 个时钟周期)来获得cache line的新副本，以保证数据的一致性。

也许在一个 2 核处理器上这不是什么大问题，但是如果一个 32 核处理器在同一cache line上同时运行 32 个线程来访问和改变数据，那会发生什么？处理器到处理器的通信延迟更大。应用程序将会在主存中周转，性能将会大幅下降。

可见性

从性能角度考虑，没有必要在修改后就立即flush修改的值——如果多次修改后才使用，那么只需要最后一次同步即可，在这之前的同步都是性能浪费。因此，可见性的定义要弱一些，只需要保证：当一个线程修改了线程共享变量的值，其它线程在使用前，能够得到最新的修改值。

可见性可以认为是最弱的“一致性”（弱一致），只保证用户见到的数据是一致的，但不保证任意时刻，存储的数据都是一致的（强一致）。

各种高级语言（包括Java）的多线程内存模型中，在线程栈内自己维护一份缓存是常见的优化措施，但显然在CPU级别的缓存一致性问题面前，一切都失效了。

伪共享问题

缓存一致性会带来另一个问题，不同的处理器拥有完全或部分分离的缓存。

当一个处理器改变了属于它自己缓存中的一个值，其它处理器就再也无法使用它自己原来的值，因为其对应的内存位置将被刷新(invalidate)到所有缓存。而且由于缓存操作是以缓存行而不是字节为粒度，所有缓存中整个缓存行将被刷新！

举个例子

  1. 如果线程A要对变量a进行操作，于是以64bit的大小将a和其附近的所有变量都装入cache line
  2. 此时B要对b进行操作，于是也以64bit的大小将b和其附近的所有变量都装入cache line
  3. 如果a紧邻b，根据局部性原理，这两个变量共享共享了缓存行
  4. 线程A对a进行修改后，将a写回主存，那么B的缓存行就失效了（B：我还没操作呢，怎么就失效了）
  5. B就只能乖乖从主存再加载数据，大大影响了性能，这就出现了伪共享问题

常见的解决思路就是：以空间换时间，让不同线程操作的不相干变量加载到不同缓存行，避免相互影响

1
2
3
4
5
public class FalseSharingPadding {
    protected long p1, p2, p3, p4, p5, p6, p7;
    protected volatile long value = 0L;
    protected long p9, p10, p11, p12, p13, p14, p15;
}

变量 value 前后分别填充了 7 个 long 类型的变量。

这样不论在什么情况下，都可以保证在多线程访问 value 变量时，value 与其他不相关的变量处于不同的 Cache Line

MESI协议的优化

严格遵循 MESI 协议的 CPU 会有啥问题？

严格遵守 MESI 协议的 CPU ，如果某一个核需要写一块缓存行时，它需要通知所有的同伴：我要写这块缓存了，如果你们谁有这块缓存的副本，请把它置成 Invalid 状态。Invalid 状态意味着该缓存失效，如果其他 CPU 再访问这一缓存区时，就会从主存中加载正确的值。

如果缓存状态是 Exclusive 和 Modified，那么不需要通知其他核。但是在 Share 状态下，如果一个核想独占缓存进行修改，就需要先给所有 Share 状态的同伴发出 Invalid 消息，等所有同伴确认并回复它“Invalid acknowledgement”以后（后文简称为ACK），它才能把这块缓存的状态更改为 Modified，也就说，只能在核心收到ACK后，才会对该缓存行进行写入操作，这是保持多核信息同步的必然要求。

这个过程相较于直接在核内缓存里修改是非常漫长的。这也就会导致某个核请求独占时间比较长。

写缓冲

CPU 的设计者为每个核都添加了一个名为 store buffer 的结构，store buffer 是硬件实现的缓冲区，它的读写速度比缓存的速度更快，所有面向缓存的写操作都会先经过 store buffer。

由于中文经常将 cache 和 buffer 都翻译成缓冲，或者缓存，所以我想强调一下 cache 和 buffer 的区别。

  1. cache：存储的信息是副本。cache 的数据即使丢失了，也可以从内存中找到原始数据（不考虑脏数据的情况），cache 存在的意义是加速查找。
  2. buffer：类似于一个蓄水池，没有副本，一旦丢失就彻底丢失了，它会收集多次写操作，然后在合适的时机进行提交。

在这样的结构里，如果 CPU 的某个核再要对一个变量进行赋值，它就不必等待其他核心的ACK，而是直接把新的值放入 store buffer

由 store buffer去做核间同步，并将新的值刷入到 cache 中去

而且每个核的 store buffer 都是私有的，其他核不可见

失效队列

当一个 CPU 向同伴发出 Invalid 消息的时候，它的同伴要先把自己的缓存置为 Invalid，然后再发出ACK，这个顺序是严格固定的

但是从“把缓存行置为 Invalid”到“发出ACK”的过程其实是比较漫长的，并且由于 store buffer 的存在提升了写入速度

那么收取ACK的速度相比起来就慢了，这就带来了速度的不匹配，很容易导致 store buffer 的操作还没有收到ACK并更新到cache里，容量就被撑爆了，从而失去了加速的作用。

为了解决这个问题，CPU 设计者又引入了“invalid queue”，也就是失效队列。加入了这个结构后，收到 Invalid 消息的 CPU会立即向 CPU0发送ACK，但其实这个核心并没有有把自己的 cache 由 Share 置为 Invalid，而是把这个失效的消息放到一个队列中，等到空闲的时候再去处理失效消息，这个队列就是 invalid queue

重排序

编译器、底层硬件（CPU等）出于“优化”的目的，按照某种规则将指令重新排序（尽管有时候看起来像乱序）

优化排序（乱序优化）

处理器层面的乱序优化节省了大量等待时间，提高了处理器的性能。

所谓“乱序”只是被叫做“乱序”，实际上也遵循着一定规则：只要两个指令之间不存在数据依赖，就可以对这两个指令乱序。不必关心数据的精准性

简而言之：只要不影响程序单线程、顺序执行的结果，就可以对两个指令重排序。

不进行乱序优化时，处理器的指令执行过程如下：

  1. 指令获取。
  2. 如果输入的运算对象是可以获取的（比如已经存在于寄存器中），这条指令会被发送到功能单元。如果运算对象在当前的时间片中是不可获取的（通常需要从主内存获取），处理器会开始等待直到它们是可以获取的。
  3. 指令在功能单元中被执行
  4. 功能单元将运算结果写回寄存器

乱序优化下的执行过程如下：

  1. 指令获取。
  2. 指令被发送到一个指令序列（也称执行缓冲区或者保留站）中。
  3. 指令将在序列中等待，直到它的数据运算对象是可以获取的。然后，指令被允许在先进入的旧指令之前离开序列缓冲区。（此处表现为乱序）
  4. 指令被分配给功能单元并执行。
  5. 将结果放到一个序列中。
  6. 仅当所有该指令之前的指令都将他们的结果写入寄存器后，这条指令的结果才会被写入寄存器中。

总结：使用指令序列实现乱序执行，先执行可获取运算对象的指令。再使用序列让结果按顺序写入寄存器，重新整理乱序结果。

当然，为了实现乱序优化，还需要很多技术的支持，如寄存器重命名、分枝预测等，但大致了解到这里就足够

编译器编译时的优化

JVM自己维护的内存模型中也有可见性问题，使用volatile做标记，就解决了JVM层面的可见性问题。编译器产生的重排序也采用了同样的思路

编译器为什么要重排序呢？和处理器乱序执行的目的是一样的：与其等待阻塞指令（如等待缓存刷入）完成，不如先去执行其他指令。与处理器乱序执行相比，编译器重排序能够完成更大范围、效果更好的乱序优化。

幸运的是，编译器层面的重排序，自然可以由编译器控制。使用volatile做标记，就可以禁用编译器层面的重排序。

由于放宽MESI协议导致的乱序问题

假定一种场景

  1. Core0先更新缓存中的v1，再更新缓存中的v2（位于两个缓存行，这样淘汰缓存行时不会一起写回内存）。
  2. Core0读取v1（使用LRU淘汰缓存），然后长时间并未读取v2
  3. Core0的缓存满，此时将最久未使用的v2写回内存。
  4. Core1的缓存中本来存有v1，现在将v2加载入缓存

由于写缓冲和失效队列的存在，Core1中v1的更新操作可能还存放于失效队列中，尽管“更新v1”早于“更新v2”发生，但Core1只看到了v2的最新值，却看不到v1的最新值。

这就是放款MESI导致的乱序问题，万事不能尽善尽美，解决了一个问题一定会引发另一个问题

内存屏障（Memory Barrier）

如何解决放宽MESI协议导致的乱序问题：在Core0修改了数据v后，让Core1在使用v前，能得到v最新的修改值

  1. Core0修改v1后，发送一个信号，将Core1缓存的v1标记为失效，并将修改值写回内存。
  2. Core0可能会多次修改v1，每次修改都只发送一个信号（发信号时会锁住缓存间的总线），Core1缓存的v1保持着失效标记。
  3. Core1使用v1前，发现缓存中的v1已经失效了，得知v1已经被修改了，于是重新从其他缓存或内存中加载v1。

内存屏障是硬件之上、操作系统或JVM之下，对并发作出的最后一层支持。

再向下是是硬件提供的支持；向上是操作系统或JVM对内存屏障作出的各种封装。内存屏障是一种标准，各厂商可能采用不同的实现。

通过volatile，可以解决编译器层面的可见性与重排序问题。而内存屏障则解决了硬件层面的可见性与重排序问题。

标准

  1. Store：将处理器缓存的数据flush到内存中。
  2. Load：将内存的数据拷贝到处理器的缓存中。
屏障类型 指令示例 说明
LoadLoad Load1;LoadLoad;Load2 该屏障确保Load1数据装载先于Load2及其之后所有的装载操作
StoreStore Store1;StoreStore;Store2 该屏障确保Store1刷新数据到内存先于Store2及其之后所有的内存刷新操作，即保证对其他处理器可见
LoadStore Load1;LoadStore;Store2 该屏障确保Load1数据装载先于Store2及其之后所有的内存刷新操作
StoreLoad Store1;StoreLoad;Load2 该屏障确保Store1刷新数据到内存先于Load2及其之后所有的装载操作。StoreLoad会使该屏障之前的所有内存访问指令(存储指令和访问指令)完成之后,才执行该屏障之后的内存访问指令

StoreLoad同时具备其他三个屏障的效果，因此也称之为全能屏障（mfence），但是相对其他屏障，该屏障的开销相对昂贵。

x86架构的实现

除了mfence，不同的CPU架构对内存屏障的实现方式与实现程都度非常不一样。

相对来说，Intel CPU的强内存模型比DEC Alpha的弱复杂内存模型（缓存不仅分层了，还分区了）更简单。

x86架构是在多线程编程中最常见的，下面讨论x86架构中内存屏障的实现。

不过不管是哪种方案，内存屏障的实现都要针对乱序执行的过程来设计，前文已经有写过。

内存屏障可以通过使用类似MESI协议的思路实现。

Store Barrier

sfence指令实现了Store Barrier，相当于StoreStore Barriers

强制所有在sfence指令之前的store指令，都在该sfence指令执行之前被执行，发送缓存失效信号，并把store buffer中的数据刷新到CPU的L1 Cache中，所有在sfence指令之后的store指令，都在该sfence指令执行之后被执行。禁止对sfence指令前后store指令的重排序跨越sfence指令

所有Store Barrier之前发生的内存更新都是可见的。

前文说的乱序优化说基于寄存器和内存，而在内存屏障的标准中，讨论的是缓存与内存间的相干性，实际上，这同样适用于寄存器与缓存、甚至寄存器与内存间等多级缓存之间。x86架构使用了MESI协议的一个变种，由协议保证三层缓存与内存间的相关性，则内存屏障只需要保证store buffer（可以认为是寄存器与L1 Cache间的一层缓存）与L1 Cache间的相干性。

Load Barrier

lfence指令实现了Load Barrier，相当于LoadLoad Barriers

强制所有在lfence指令之后的load指令，都在该lfence指令执行之后被执行，并且一直等到load buffer被该CPU读完才能执行之后的load指令（发现缓存失效后发起的刷入）。禁止对lfence指令前后load指令的重排序跨越lfence指令。

配合Store Barrier，使所有Store Barrier之前发生的内存更新，对Load Barrier之后的load操作都是可见的。

这里的“可见”，指修改值可见（内存可见性）且操作结果可见（禁用重排序）

Full Barrier

mfence指令实现了Full Barrier，相当于StoreLoad Barriers。

mfence指令综合了sfence指令与lfence指令的作用

强制所有在mfence指令之前的store/load指令，都在该mfence指令执行之前被执行；

所有在mfence指令之后的store/load指令，都在该mfence指令执行之后被执行。

禁止对mfence指令前后store/load指令的重排序跨越mfence指令，使所有Full Barrier之前发生的操作，对所有Full Barrier之后的操作都是可见的。

volatile如何解决内存可见性与处理器重排序问题

既然有了内存屏障，是不是就不需要volatile了？当然不是，还有三个问题：

  1. 并不是所有的硬件架构都提供了相同的一致性保证，JVM需要volatile统一语义
  2. 可见性问题不仅仅局限于CPU缓存内，JVM自己维护的内存模型中也有可见性问题。使用volatile做标记，可以解决JVM层面的可见性问题。
  3. 如果不考虑真重排序，MESI确实解决了CPU缓存层面的可见性问题；然而，真重排序也会导致可见性问题。

在编译器层面，仅将volatile作为标记使用，取消编译层面的缓存和重排序。

如果硬件架构本身已经保证了内存可见性（单核处理器、一致性足够的内存模型等），那么volatile就是一个空标记，不会插入内存屏障

如果不保证，以x86架构为例，JVM对volatile变量的处理如下：

  1. 在写volatile变量v之后，插入一个sfence。这样，sfence之前的所有store（包括写）不会被重排序到sfence之后，sfence之后的所有store不会被重排序到sfence之前，禁用跨sfence的store重排序；sfence之前修改的值都会被立刻写回缓存，并标记其他CPU中的缓存失效。
  2. 在读volatile变量v之前，插入一个lfence。这样，lfence之后的load（包括读v）不会被重排序到lfence之前，lfence之前的load不会被重排序到lfence之后，禁用跨lfence的load重排序；且lfence之后，会首先刷新掉无效缓存，从而得到最新的修改值，与sfence配合保证内存可见性。
  3. 在另外一些平台上，JVM使用mfence代替sfence与lfence，实现更强的语义。

CAS

在x86架构上，CAS被翻译为”lock cmpxchg“。cmpxchg是CAS的汇编指令。

在CPU架构中依靠lock信号保证可见性并禁止重排序。

lock前缀是一个特殊的信号，执行过程如下：

  1. 对总线和缓存上锁。
  2. 强制所有lock信号之前的指令，都在此之前被执行，并同步相关缓存。
  3. 执行lock后的指令（如cmpxchg）。
  4. 释放对总线和缓存上的锁。
  5. 强制所有lock信号之后的指令，都在此之后被执行，并同步相关缓存。

因此，lock信号虽然不是内存屏障，但具有mfence的语义

#计算机组成原理
关于CPU Cache
http://example.com/post/关于CPU-Cache.html
作者
SamuelZhou
发布于
2022年12月6日
许可协议