1 Cache¶

缓存是一种比内存更快的存储设备，它的出现就是为了解决读写内存数据耗时长的问题（处理器要从内存中直接读取数据都要花大概几百个时钟周期）。但缓存造假昂贵，因此缓存的容量一般很小，几十 KB~几十 MB 之间。

1.1 Cache 的写策略¶

WC（write-combining） 和UC（uncacheable） 。 这两种策略都是针对特殊的地址空间来使用的。

直写（write-through）：就是指在处理器对 Cache 写入的同时，将数据写入到内存中。
回写（write-back）：当处理器在改写了某个 Cache line 后，并不是马上把其写回内存。
WC（write-combining）：这种策略就是当一个Cache line 里的数据一个字一个字地都被改写完了之后，才将该Cache line写回到内存中。
UC（uncacheable）：是一部分特殊的内存，这种内存是不能缓存在Cache中的。

1.1.1 直写（write-through）¶

这种策略保证了在任何时刻，内存的数据和 Cache 中的数据都是同步的，这种方式简单、可靠。但由于处理器每次对Cache更新时都要对内存进行写操作，因此总线工作繁忙，内存的带宽被大大占用，因此运行速度会受到影响。假设一段程序在频繁地修改一个局部变量，尽管这个局部变量的生命周期很短，而且其他进程/线程也用不到它， CPU依然会频繁地在Cache和内存之间交换数据，造成不必要的带宽损失。

1.1.2 回写（write-back）¶

回写相对于直写而言是一种高效的方法。直写不仅浪费时间，而且有时是不必要的，比如上文提到的局部变量的例子。回写系统通过将 Cache line 的标志位字段添加一个 Dirty 标志位，当处理器在改写了某个 Cache line 后，并不是马上把其写回内存，而是将该 Cache line 的 Dirty 标志设置为 1。当处理器再次修改该 Cache line 并且写回到 Cache 中，查表发现该 Dirty 位已经为 1，则先将 Cache line 内容写回到内存中相应的位置，再将新数据写到 Cache 中。其实，回写策略在多核系统中会引起Cache 一致性的问题。设想有两个处理器核心都需要对某个内存块进行读写，其中一个核心已经修改了该数据块，并且写回到 Cache 中，设置了 Dirty 位；这时另外一个核心也完成了该内存块的修改，并且准备写入到 Cache 中，这时才发现该 Cache line 是“脏”的。

1.1.3 WC（write-combining）¶

write-combining策略是针对于具体设备内存（如显卡的RAM）的一种优化处理策略。对于这些设备来说，数据从Cache到内存转移的开销比直接访问相应的内存的开销还要高得多，所以应该尽量避免过多的数据转移。试想，如果一个Cache line里的字被改写了，处理器将其写回内存，紧接着又一个字被改写了，处理器又将该Cache line写回内存，这样就显得低效，符合这种情况的一个例子就是显示屏上水平相连的像素点数据。 writecombinin策略的引入就是为了解决这种问题，顾名思义，这种策略就是当一个Cache line里的数据一个字一个字地都被改写完了之后，才将该 Cache line 写回到内存中。

1.1.4 UC（uncacheable）¶

uncacheable 内存是一部分特殊的内存，比如 PCI 设备的 I/O 空间通过 MMIO 方式被映射成内存来访问。这种内存是不能缓存在 Cache 中的，因为设备驱动在修改这种内存时，总是期望这种改变能够尽快通过总线写回到设备内部，从而驱动设备做出相应的动作。如果放在 Cache 中，硬件就无法收到指令。

1.2 Cache 预取¶

所谓的 Cache 预取，也就是预测数据并取入到 Cache 中，是根据空间局部性和时间局部性，以及当前执行状态、历史执行过程、软件提示等信息，然后以一定的合理方法，在数据/指令被使用前取入 Cache。这样，当数据/指令需要被使用时，就能快速从 Cache 中加载到处理器内部进行运算和执行。 - 时间局部性：是指程序即将用到的指令/数据可能就是目前正在使用的指令/数据。因此，当前用到的指令/数据在使用完毕之后可以暂时存放在Cache中，可以在将来的时候再被处理器用到。一个简单的例子就是一个循环语句的指令，当循环终止的条件满足之前，处理器需要反复执行循环语句中的指令。
- 空间局部性：是指程序即将用到的指令/数据可能与目前正在使用的指令/数据在空间上相邻或者相近。因此，在处理器处理当前指令/数据时，可以从内存中把相邻区域的指令/数据读取到Cache中，这样，当处理器需要处理相邻内存区域的指令/数据时，可以直接从Cache中读取，节省访问内存的时间。一个简单的例子就是一个需要顺序处理的数组。

1.3 Cache 一致性¶

title: 产生缓存一致性问题的原因？
Cache一致性问题的根源是因为存在*多个处理器独占的Cache*， 而不是多个处理器。如果多个处理器共享Cache， 也就是说只有一级Cache， 所有处理器都共享它， 在每个指令周期内， 只有一个处理器核心能够通过这个Cache做内存读写操作， 那么就不会存在Cache一致性问题

1.3.1 一致性协议¶

解决 Cache 一致性问题的机制有两种： - 基于目录的协议（Directory-based protocol）：特点（中心节点统一管理）
- 总线窥探协议（Bus snooping protocol）：（重点）特点（监听通知广播） - Snarfing协议

1.3.1.1 基于目录的协议¶

基于目录协议的系统中，需要缓存在 Cache 的内存块被统一存储在一个目录表中，目录表统一管理所有的数据，协调一致性问题。该目录表类似于一个仲裁者，当处理器需要把一个数据从内存中加载到自己独占的 Cache 中时，需要向目录表提出申请；当一个内存块被某个处理器改变之后，目录表负责改变其状态，更新其他处理器的 Cache 中的备份，或者使其他处理器的 Cache 的备份无效。

1.3.1.2 总线窥探协议¶

总线窥探协议是在 1983 年被首先提出来，这个协议提出了一个窥探（snooping）的动作，即对于被处理器独占的 Cache 中的缓存的内容，该处理器负责监听总线，如果该内容被本处理器改变，则需要通过总线广播；反之，如果该内容状态被其他处理器改变，本处理器的 Cache 从总线收到了通知，则需要相应改变本地备份的状态。总线窥探协议衍生出著名的 MESI 协议，或者称为 Illinois Protocol。

1.3.2 MESI 协议¶

MESI 协议是 Cache line 四种状态的首字母的缩写，Cache 中缓存的每个 Cache Line 都必须是这四种状态中的一种。分别是: 1. 修改态（Modified） 2. 独占态（Exclusive） 3. 共享态（Shared） 4. 失效态（Invalid）

同一时刻 2 个缓存行缓存同一内存时缓存状态矩阵图
缓存状态迁移表

1.3.2.1 修改态¶

如果该Cache Line在多个Cache中都有备份，那么只有一个备份能处于这种状态，并且“dirty”标志位被置上。拥有修改态Cache Line的Cache需要在某个合适的时候把该Cache Line写回到内存中。但是在写回之前，任何处理器对该Cache Line在内存中相对应的内存块都不能进行读操作。 Cache Line被写回到内存中之后，其状态就由修改态变为共享态。

1.3.2.2 独占态¶

和修改状态一样，如果该 Cache Line 在多个 Cache 中都有备份，那么只有一个备份能处于这种状态，但是“dirty”标志位没有置上，因为它是和主内存内容保持一致的一份拷贝。如果产生一个读请求，它就可以在任何时候变成共享态。相应地，如果产生了一个写请求，它就可以在任何时候变成修改态。

1.3.2.3 共享态¶

意味着该 Cache Line 可能在多个 Cache 中都有备份，并且是相同的状态，它是和内存内容保持一致的一份拷贝，而且可以在任何时候都变成其他三种状态。

1.3.2.4 失效态¶

该 Cache Line 要么已经不在 Cache 中，要么它的内容已经过时。一旦某个 Cache Line 被标记为失效，那它就被当作从来没被加载到 Cache 中。

1.3.3 DPDK 保证缓存一致行的方法¶

原则：避免多个核访问同一个内存地址或者数据结构，每个核尽量都避免与其他核共享数据，从而减少因为错误的数据共享（cache line false sharing）导致的Cache一致性的开销。
方式 1：数据结构定义时，内存对齐缓存行大小（64Byte）；对于某些数据结构，给每个核都单独定义一份。
方式 2：对网络端口的访问时，不同的核使用不同网卡的发送队列/接收队列（也是内存中的一段内存结构），避免不同核使用同一个发送/接受队列。