一、引子

从这一个小节开始，我们要进入这一章的重中之重。

大题和小题的高频考点就是Cache。

之前我们学习了存储系统的一些优化策略，对于主存，我们可以用双端口RAM，还有多模块存储器这样的方式来提高主存的工作速度。但是无论主存的速度再怎么提高，相比于 CPU 的读写运算速度，依然速度差距是很大的。

所以如何解决这个问题，一个比较容易想到的方法是，我们可以设计更高速的存储单元，比如把 DRAM 芯片改成 SRAM 芯片。但是这又意味着我们的存储器价格会更高。

或者从另一个角度来讲，当你成本相同的情况下，容量肯定是需要下降的。

这个问题怎么解决？基于程序的局部性原理，我们可以再增加一个 Cache 层，用这样的方式来缓和CPU和主存之间的速度矛盾。

二、工作原理

来看一下 Cache 的工作原理。

先来看没有 Cache 的情况。假设这是大家的一个手机，你的手机可能是 128GB 或者 64GB 等等比较大的一个辅存。

你在你的储存空间上可以安装微信、王者荣耀各种各样的你喜欢用的软件或者游戏。

现在假设你的微信要启动，你启动微信的过程其实就是把微信相关的程序代码还有数据给它调入内存的一个过程。

比如微信里边可能会有一个模块是用来处理文字聊天的，还有一个模块用来处理视频聊天，还有一个模块的代码指令，专门用于实现你的朋友圈相关的功能。

当然了，除了你应用软件的这些代码指令之外，也会有一些相关的数据被调入内存。比如你的微信的聊天数据，还有朋友圈里一些图片之类的缓存数据，也需要放到内存里。

把这些数据调入内存之后，你的微信就可以正常的开始运行了。

微信运行的过程其实就是 CPU 从内存里一条一条地来取这些指令，执行指令的过程。

不过之前我们说过， CPU 速度是很快的，而内存（主存）它的速度很慢，所以快速的 CPU 每一次都从主存，从内存里边读取数据，这就会导致 CPU 的执行效率被内存的读写速度所拖累。

现在考虑这样的一个场景，假设现在你使用微信，正在和你的朋友或者和你的家人视频聊天，在你视频聊天的这一段时间内，是不是微信的这些数据当中，只有视频聊天相关的指令代码在这段时间内会被频繁地访问。

所以如果我们能够把视频聊天相关的代码把它复制一份，把它复制到一个更高速、读写速度更快的 Cache 当中，那么CPU就可以直接从 Cache 当中读取视频聊天相关的指令和数据。

而 Cache 的读写速度比内存快多了。这样CPU和内存之间的速度矛盾就会缓和。

之前我们给过一个截图，三星的内存条，它的读写速度大概是 37 GB 每秒，而 Cache 可以达到接近 1000 GB 每秒这样的一个读速度。写速度虽然比读速度要慢一些，但是也要比内存要快得多。

最右边这一溜表示的是 CPU访问主存的某一个存储单元和访问 Cache 的存储单元它所需要付出的一个时间代价大概是 61 纳秒，缩短到了1纳秒这样的一个量级。

所以 Cache 要比内存快得多，可以更好地配合高速的 CPU 工作。

这就是 Cache 的工作原理。

上面的图中，我们把 Cache 和 CPU 画成了两个框。

但事实上，现在的计算机通常将 Cache 高速缓冲存储器集成在CPU 内部，并且是用 SRAM 这种芯片来实现。

之前我们说过， SRAM 要比 DRAM 速度要快得多，但是成本也会更高。

另外 SRAM 的集成度会更低。这就意味着如果我们想要把 Cache 高速缓冲存储器塞进一个很小的手机里边，由于它的集成度很低，

所以在芯片的大小不能做的特别大的情况下，就注定了 Cache 的存储空间，就是存储容量不可能做得特别大。

这并不是有钱就能解决的事情，你得考虑到它的集成度，它的体积。

所以通常现在电脑上的CPU，比如英特尔 I5 系列的CPU，它的 Cache 的大小可能也就是 12 兆字节。

三、局部性原理

刚才我们说的视频聊天的场景，可能大家觉得会比较特殊，其他的程序运行也会存在我们刚才所描述的这么理想的场景吗？

就是在某一段时间内，CPU是否只会访问到某一部分的数据。

这个问题我们可以用程序的局部性原理来解释。

（1）空间局部性

来看这样的一段程序。程序A，我们传入了一个二维的数组， M 行 N 列。

这个程序里边，用了两层嵌套for 循环，一行一行地访问二维数组a里边的各个数据。

对于这个程序，它在运行的时候，我们需要把这个程序的代码翻译成二进制的机器指令。

另外像，数组还有各种各样的变量，这些数据我们也需要把它放到内存里边。

大家都应该学过 c 语言和数据结构，我们知道对于 c 语言里的二维数组，有 m 行、 n 列这样的二维数组。当我们把这些数据放入内存的时候，其实是一行一行来存储的。

所以我们看一下，内存里边0x400地址存储了 a0 数据， 0x404 这个位置存储了a0数据。

为什么这两个地址相差是4？因为我们每一个数组元素是一个 Int 类型，而一个 Int 类型刚好是 4 个字节。

具体的我在C语言数组栏目讲解过。

总之，从逻辑上看，这个数组它好像是一个二维的数组，但是我们放到内存里边的时候，这个数组会被展开成这种一维的形式来顺序的存储，一行一行的存。

现在结合我们程序的逻辑，要一行一行地访问二维数组。

不难得出这样的一个结论，假如现在我们访问了 a[0][0]元素，在接下来一段时间内，和a[0][0]数据相邻的其他元素是不是很有可能会紧接着被访问？

所以这就是所谓的空间局部性。就是最近的未来有可能要用到的信息，很有可能是在现在我们正在使用的这一个信息的存储空间周围的那些数据。

刚才我们看的是数组的数据，其实除了数据之外，指令的访问也存在空间局部性。

因为这些程序最终肯定是被翻译成一条一条的机器指令。这些机器指令在内存里边也是顺序存放的。因此，当我们访问某一条机器指令的时候，在不久的将来，与这条机器指令相邻的其他这些机器指令也有可能会紧接着被使用到。

这就是所谓的空间局部性。

（2）时间局部性

再来看时间局部性。

时间局部性指的是在最近的未来要使用到的信息，很有可能是现在我们正在使用的信息。

要理解时间局部性，最典型的例子就是程序里的循环结构。

比如这个加法sum+=a[i][j]，它所对应的指令可能是存放在内存里的某一个部分。如下：

当我们访问了这一条加法指令之后，由于有这种循环结构的存在，就意味着在未来很短的时间内，有可能会再次使用到加法所对应的指令。

（3）总结

这就是空间局部性和时间局部性。

空间局部性是因为我们的指令和数据在内存里边通常是顺序存储的，而我们访问这些指令和数据的时候，很多时候都是需要顺序的访问，所以这就导致了空间局部性。而时间局部性主要是因为我们程序里边会存在大量的循环结构，所以导致了时间局部性。

除了对指令的访问具有时间局部性之外，其实对某一些数据的访问也具有这种时间局部性。

比如对于变量i，变量j，变量sum，这些变量也因为循环结构的存在，很有可能在短时间内被重复地访问。

所以基于程序执行的局部性原理，我们不难想到这样的策略。

由于 CPU目前访问的这些主存地址，它的周围那些数据很有可能在不久的未来就被我们使用。另外，CPU当前访问的地址也有可能在未来被重复访问。

所以我们可以把目前访问的地址周围的一部分数据，先把它放到 Cache 当中，也就复制一份到 Cache 里边。

接下来 CPU 就可以直接从 Cache 里读取相应的数据。

比如当我们在访问数组的时候，如果此时 CPU 访问了a[0][0] 这个元素，我们完全可以制定一定的策略，把 a[0][0]之后的多个数组元素，把这些数据复制一份到 Cache 当中，这样接下来 CPU 想要再访问这些数据，是不是只需要去 Cache 里边找就可以了？

这样就可以大幅地提升 CPU 的运行速度。

所以局部性原理就是 Cache 能够有效工作的一个理论依据。

现在我们来把程序 A进行一个改造。程序A是对二维数组进行一行一行地访问，我们把 for 循环稍微改一改，把它改成一列一列地访问。就是程序B这种：（就是将两个for颠倒了一下）

对于程序 B来说，意味着它访问二维数组的顺序应该是这样的。

首先访问a[0][0]，接下来要访问的是a[1][0]，再往后应该要访问的是a[2][0]。

因为是一列一列地访问，也就意味着程序B这种执行方式，它的空间局部性要比程序A更差一些。

当程序A在访问某一个数组元素的时候，接下来它访问的肯定是与之相邻的其他元素，而程序B它是跳着来访问的，所以程序B的空间局部性会更差。

在实际当中，可能程序B它的实际运行时间要比程序A慢得多。因为程序 A可以很大概率直接从 Cache 当中找到它想要的数据。这是局部性原理。

四、性能分析

（1）方案一

接下来我们来看一下，增加了 Cache 之后，整个系统的运行效率可以提升多少。

还是以刚才微信的运行为例，整个微信它本来是有 1GB 这么大，但是现在我们把微信的其中某一小部分的代码和数据，放到 Cache 当中，把它复制了一份到 Cache 当中。

我们可以假设 CPU 对 Cache 的访问，就是进行一次读写只需要tc这么长的时间（脚标 c 指的就是Cache）。 CPU对内存的读或者写每一次访问需要tm 时间（m 指的是memory）。

现在 CPU 如果想要执行的是视频聊天相关的代码，这些代码就可以在 Cache 里边找到；或者 CPU想要读取朋友圈相关的数据，这些数据也可以在 Cache 当中找到。

所以对于CPU想要的数据，它如果能够直接在 Cache 里边找到，我们就称这种现象为 Cache 命中，与之对应的一个指标，就是所谓的命中率，就是CPU想要访问的信息，它已经在 Cache 当中的比例。

与命中率相对的是缺失率，就是没有命中的概率。

所以，如果我们能够知道访问Cache，访问主存分别需要花多长时间， Cache 命中的概率是多少，我们就可以计算出系统它的平均访问时间应该是多少。

首先，既然 Cache 更快，CPU 肯定优先会去 Cache 里边找数据。能够找到的概率是H这么多，从 Cache 当中读出数据，总共只需要花tc 这么长的时间。

另一种情况也有可能会发生，就是在 Cache 里边找不到数据的情况。比如此时 CPU要运行的是文字聊天相关的代码， CPU 先花了 tc 这么长的时间在 Cache 里边找，没找到。接下来 CPU 就会花 tm 这么长的时间去内存里边再去读数据。而这种情况发生的概率应该是 1-H 。

所以增加了 Cache 之后， CPU进行一次读写所需要的平均时间 t 就应该是这么长。

显然平均读写时间应该是大于 tc，但是又小于 tm 的。

大家需要注意理解刚才所说的过程。 CPU是先去 Cache 当中找，无论找得到还是找不到，都是要花 tc这么长的时间，如果没有命中没找到，CPU才会紧接着去主存里边找数据。

（2）方案二

有同学可能会说， CPU可不可以同时去 Cache 和内存里边找数据？

其实这种方案也是可以的。

<1> 比如此时 CPU想要找的是视频聊天相关的代码，它会同时去 Cache 和内存里边找。

但是当过了 tc 这么长的时间之后，它在 Cache 里边找到了，就是 Cache 命中了。这个时候它就可以立即停止在内存里的查找。

所以在 Cache 命中的情况下， CPU的访问时间同样只需要 tc 这么长的时间。这种情况发生的概率应该是H。

<2> 另一种情况，假设CPU此时要找的是文字聊天相关的代码，CPU 同时会去 Cache 和主存里边找，但是过了tc 这么长的时间之后，在 Cache 里边找不到。

既然Cache里边找不到，我们继续在内存找不就行了？但是由于左边和右边的查找是同时开始的，因此总共过了tm 这么长的时间之后，CPU 就可以直接从内存里找到相关的数据，而这种情况发生的概率是 1 - H 这么多。

所以和上面这种方式相比，下面这种方式，它的平均访问时间肯定要更短，效率会更高。

因为在 Cache 没有命中的情况下，我们所需要花费的时间更少，就是少了一个 tc 。

（3）考题

对于这种 Cache 储存系统也经常作为考题进行考察。

比如这个题，它告诉你 Cache 的速度是主存的 5 倍。

我们可以假设 Cache 的存取周期是t，主存的存取周期就应该是5t， Cache 的命中率是95%。问我们采用了 Cache 之后，存储器的性能提升了多少？

这个题目告诉我们，它采用的是 Cache 和主存同时被访问，也就是我们刚才说的第二种方案。

①来简单算一下 Cache 和主存同时被访问的情况。

当 Cache 命中的时候，我们的这次读写操作就只需要 t 这么长的时间，而如果 Cache 没有命中，我们这次读写操作就需要 5t 这么长的时间。

Cache 命中的概率是95%，没有命中的概率是5%。一相乘相加就可以得到一个平均的访问时间。

②没有引入Cache

对于系统来说，在没有引入 Cache 之前，我们每一次存或者取一个数据，肯定都得对主存进行访问，主存的访问一定是需要 5t 这么长的时间的。

而引入了 Cache 之后，我们的平均访问时间降到了 1. 2T。

所以引入了 Cache 之后，整个读写的性能变成了原来的 4. 17 倍，这个提升还是很明显的。

③先访问Cache再访问主存

再来看另一种情况，如果我们之前提到的第一种策略，就是先访问Cache，当 Cache 未命中的时候，再开始访问主存。

这种情况下， Cache 命中的时候，访问时间就应该是t，没有命中的时候，访问时间就应该是t再加上5t，也就是 6t 的时间。

所以平均访问时间我们可以相乘相加就可以得到，应该是 1. 25t，再和 5t 进行一个相除就可以得到，性能是提升为了以前的 4 倍，要比上面这种方式要更慢一些。

所以这种访问的策略不一样，平均访问时间的计算也会有一点点的区别，大家在做题的时候需要注意审题。

五、块

目前为止，我们已经大致了解了 Cache 的工作原理，并且通过题目，相信大家能够感受到引入 Cache 之后整个系统的性能提升。

但是对于Cache，我们依然还有很多需要解决的问题。

第一个问题，我们之前说过，基于局部性原理，我们其实可以把CPU目前访问的地址的周围部分数据先把它放到 Cache 当中。

那么我们如何界定所谓的周围的数据？

（1）主存

这个问题可以这么解决。我们可以把整个主存的存储空间进行一个分块，每一个块的大小是相同的。

比如一块是 1 k B，主存和 Cache 之间会以块为单位进行数据的交换。
比如此时我们访问了 a[0][0] 数组元素，由于整个主存被我们分为了这样一个一个的块，每个块大小是1KB。所以当我们访问数组元素的时候，我们可以通过地址信息来判断数组元素它从属于哪一个分块。

比如它的整个分块是这样的一个范围。

我们就可以把这一整块的数据全部放入到 Cache 当中，给它复制一份。

这就回答了刚才提出的问题。

我们是以块为单位进行数据的交换的。

整个主存会被分为大小相等的一个一个的块。为了方便管理， Cache 里的这些存储空间，也会被分为大小相等的一个一个的块。

来看我们这儿给出的例子。

假设整个主存总共是 4 兆字节， 4 兆字节应该是 2 的22 次方，这么多个字节。它被分为了 1 k B 1 k B 的大小。而 1K 应该是等于 2 的 10 次方。所以用 2 的 22次方除以 2 的 10 次方，我们就可以算出整个主存被分为了多少块，应该是 2 的 12 次方，也就是 4096 这么多个块。

所以我们可以给主存的各个块进行一个编号，从 0 开始一直到4095，每一块的大小是 1 kB。

如果主存它是按字节编址，是不是意味着主存它的地址空间应该包含 22 个比特位，因为总共有 4 兆个字节。

我们对主存分块之后，整个主存总共有 22 位的地址，我们可以把它拆分成两个部分。

前边的 12 位用来表示块号，因为 12 位刚好可以表示 0 到 4095 这个范围。

末尾的 10 位地址，我们可以用它来表示块内的地址，因为每一个块总共有 1K 个存储单元，刚好可以用 10 个比特位来表示。

对主存分块之后，主存的 22 位地址，可以把它看作是由块号和块内地址这样两个部分来组成的。

（2）Cache

现在再来看Cache，假设我们的Cache，它的存储空间只有 8KB这么多，我们把 Cache 分块之后，它总共只能被分为 8 个块，块号分别是 0- 7，每个块的大小同样是 1 kB。

所以对 Cache 和主存分块之后，接下来对这两个部分的数据进行交换，是不是就很方便了，可以一块一块地来交换。

（3）补充说明

1.术语

这个地方需要再聊这样的几个术语。

在操作系统当中，主存的这样的一个块也会被称为一个页，或者叫一个页面，或者一个页框。

大家在做题的时候，如果看到这样的描述，需要知道他说的其实就是主存的一个块。

另外，在很多教材当中，对于 Cache 的一个块，也会把它称为一个Cache行， Cache 的块号也会被称为行号。

我个人比较喜欢把 Cache 和主存的这两个术语进行一个统一，都把它们称作块还有块号，因为它们之间本来就有这种对应关系。

所以接下来的讲解当中，我们会用 Cache 块还有主存块或者内存块这样的方式来描述。

再次强调，主存和 Cache 之间是以块为单位进行数据交换的。

2.有待解决的问题

另一点需要补充的是， CPU优先会从 Cache 里边找数据，但是如果 Cache 当中找不到， CPU又会到主存里边找数据。

当 CPU 访问了主存的某一个存储单元之后，接下来一定会把存储单元所从属的这一整块立即调入到 Cache 当中。

注意这个过程只是把数据复制一份，并不会把主存里的这些数据给删除。

现在问题产生了，我们访问的这些主存块，它有可能被放到 Cache 的每一个位置。

<1> 主存块和 Cache 块它们之间的这种对应关系，我们应该如何记录？ CPU 又如何区分 Cache 里的数据和主存里的数据的一个对应关系？

这个问题就是我们下一小节会学习的 Cache 和主存的映射方式。

<2> 第二个问题，我们之前说过， Cache 的容量很小，而主存的容量一般要比 Cache 要大得多。这就意味着我们只可能把主存中的一小部分数据放到 Cache 当中。当 Cache 满了之后应该怎么办？

这个问题我们会在下下小节当中进行探讨。就是替换算法要解决的问题。

<3> 最后一个问题，我们主存里保存的数据，它是被复制了一份到 Cache 当中。

比如你用毁图秀秀 p 图的时候，你的图片数据有可能会被放到 Cache 当中。

图片的数据是被复制了一份到 Cache 里边。当我们进行 p 图的时候，其实 CPU 会优先更改的是 Cache 里边保存的数据。

而 Cache 里的数据，它只是一个数据副本，真正的数据母本是被保存在主存当中的。我们应该如何保证数据副本和数据母本它们之间的一致性？

这也是后面的小结会解决的问题，也就是 Cache 的写策略所要探讨的问题。

所以通过小结，希望给大家建立起一个关于 Cache 的全局观。接下来的几个小节当中，我们带着这些问题来寻找答案。

六、回顾

这个小节当中我们介绍了高速缓冲存储器 Cache 的一个基本工作原理，还有局部性原理，分为空间局部性和时间局部性。

正是因为程序局部性原理的存在，我们在引入了小容量的，但是高速的 Cache 之后，依然可以使整个系统的性能得到一个很明显的提升。

对于我们的性能提升了多少，这个问题大家一定需要注意审题，有这样的两种方式，第一种方式是先访问Cache， Cache 没有命中的情况下再去访问主存。第二种方式是同时对 Cache 和主存进行访问，如果 Cache 命中，会立即停止主存的访问，而如果 Cache 没有命中， CPU 会继续完成对主存的访问，所以第二种方式它的性能会更好一些。

最后我们还引入了几个很重要的概念，就是主存和Cache。它们都会被分块，每一个块的大小都是相同的。主存和 Cache 之间会以块为单位进行数据交换。

另外也需要注意主存块还有内存块它们的一个别名。

另一个方面，主存的存储空间被我们分块之后，主存的地址，我们可以在逻辑上把它看作是由主存块号和块内地址这样的两个部分来组成的。

这些内容如果大家之前学过操作系统，理解起来应该是很容易的。

这个小节的最后我们留下了一些关于 Cache 的问题，接下来的几个小节我们会逐一地解决这些问题。

以上就是这个小节的全部。