# Cache 基本原理

# Cache 简介

在计算机系统中，CPU 的速度远远高于内存的速度，为了解决内存速度低下的问题，CPU 内部会放置一些 SRAM 用做 Cache（缓存），来提高 CPU 访问程序和数据的速度。可以说 Cache 是连接 CPU 和内存的桥梁。如下图所示：

Cache 具有时间局部性和空间局部性：

时间局部性：如果某个数据被访问，那么它很可能被再次访问。比如循环，循环体代码被 CPU 重复的执行，直到循环结束。如果将循环体代码放在 Cache 中，那么只是第一次访问这些代码需要耗费些时间，以后这些代码每次都能被 CPU 快速的访问，从而提高了访问速度。

空间局部性：如果某个数据被访问，那么与它相邻的数据可能很快被访问。比如数组，如果一次将数组中的多个元素从内存复制到 Cache 中，那么只是初次访问这个数组需要一些时间，之后再次访问时，速度就很快了。

# Cache 的层次化管理

现代的处理器都采用多级的 Cache 组织形式，来达到性能和功能的最优。

单核处理器大都采用下图所示的 Cache 结构：

单核处理器通常包含两级 Cache：L1 Cache 和 L2 Cache。在 L1 中，指令和数据使用各自的 Cache，分别叫做指令 Cache（ICache）、数据 Cache（DCache）；在 L2 中，指令和数据共用一套 Cache。通常 L1 空间为几十 KB，L2 空间为几百 KB。

当内核需要访问程序或者数据时，会先从 L1 中去取，如果没有，L1 从 L2 中将数据导入，如果还是没有，则 L2 从内存中将数据导入。

L1 通常和CPU内核同频率以保证访问速度，L2 通常会降频使用以降低功耗。

多核处理器大都采用下图所示的Cache结构：

在多核处理器中，一般每个内核独享自己的 L1 和 L2，所有的内核会共用一个大容量的 L3。

# Cache 的工作方式

整个 Cache 空间被分成 N 个 line，每个 line 通常是 32Byte 或者 64Byte 等，Cache line 是 Cache 和内存交换数据的最小单位，每个 Cache line 基本结构如下图所示：

block 中存储的是内存在 Cache 缓存的数据，tag 中存储的是该 Cache line 对应的内存块地址，valid 表示该 Cache line 中的数据是否有效。

假设处理器只有一级 Cache，当 CPU 访问一个数据时，首先会在 Cache 中寻找，第一次肯定找不到，于是就发生 Cache miss，这时内存中的数据被导入到一个 Cache line 的 block 中，并将地址写到相应的 tag 位置，同时将 valid 置 1。当下一次 CPU 继续访问这个数据时，处理器根据地址在 Cache 中找到对应的 Cache line，发现 valid 标志为 1 并且 tag 标志也匹配，就直接从 Cache 中访问这个数据，这个过程叫 Cache hit。

当 Cache hit 时，CPU 直接从 Cache 中访问数据，时间通常为几个周期，当 Cache miss 时，数据需要从内存中导入，时间通常是几十、几百个周期。

Cache 提供了两种写策略：

# Write through（写通方式）

Write through 策略是指每次 CPU 修改了 Cache 内容时，Cache 立即更新内存中的内容。如下图所示：

在上面的例子中，CPU 读入变量 x，它的值为 3，不久后 CPU 将 x 改为 5，CPU 修改的是 Cache 中的数据，当 Cache 采用 Write through 策略时，Cache 控制器将 x 的值更新到内存中。

# Write back（写回方式）

Write back 策略是指 CPU 修改 Cache 的内容后，Cache 并不会立即更新内存中的内容，而是等到 Cache line 因为某种原因需要从 Cache 中移除时，Cache 才更新内存中的数据。例如，Cache 的 line0 已经存储了 line0 的数据，CPU 想修改地址在内存 line0 中的变量，它实际修改的是 Cache line0 中的数据，当 CPU 访问内存 line4 时，这块数据也需要使用 Cache line0，这时 Cache 控制器会先将 Cache line0 的内容更新到内存的 line0，然后再将 Cache line0 作为内存 line4 的缓存。内存 line0 在很长时间内存储的都不是最新的数据，不过这并不影响程序的正确性。如下图所示：

Write through 由于有大量的访问内存的操作，效率较低，大多数处理器都使用 Write back 策略。

Cache 通过增加一个新的 dirty 标志来标明这行数据是否被修改。dirty 标志为 1 表示 Cache 内容被修改，当该 Cache line 被移除时，数据需要被更新到内存；dirty 标志为 0（称为 clean）表示 Cache 的内容和内存的内容一致。如下图所示：

指令 Cache 不会被修改，不需要 dirty 标志，数据 Cache 需要 dirty 标志。