【计组 | Cache原理】讲透Cache的所有概念与题型方法

Cache

写在前面：高速缓存Cache一直408中的重点以及绝对的难点，前几天我在复习计组第三章的知识，Cache这一节把我困住了，我发现很多概念我都不记得了，一些综合性强的计算题根本无从下手，我深知Cache对于每个408的初学者来说，都是痛点、难点所在，因此花了一晚上狠狠学习Cache总结做了这个Cache“大观”，尝试用最精简且具有逻辑性的方式，只讲重难点和考点，给大家讲透Cache（我发现市面上很多课程讲解的都是比较零散且不好消化的，没有抓住主要矛盾），用最短的时间达到做出考研 408题目的要求。

为什么要使用Cache？

为了引出Cache这个高速缓存的妙用，我们先来认识一个概念—时间局部性。

所谓的时间局部性就是同一条指令在短时间内多次运行，比如循环结构，那么我们在循环体内重复更新的变量就是具有时间局部性的，而学过操作系统我们就知道程序是放在内存里运行的，由于时间局部性，程序运行时频繁访问的数据就集中在主存中的某几块区域内，于是我们只要把这几块区域的指令、数据全都复制到CPU的Cache里，这样CPU就可以先去Cache里看看有没有数据如果有直接取出，如果没有再取访存，提高了取数据的效率。由于命中率很高，平均访问是接近于Cache的访问时间的！！（小考点）

那么主存究竟是将数据复制到Cache内的呢？我们继续来看！

关于Cache的所有概念（重点）⭐

我们现在需要把主存中的部分高频访问内容复制到Cache中，最简单的思路就是把主存和Cache都划分出一个个的相同大小的区域，然后就可以直接把数据复制过去了对吧。实际上计算机也是这么做的。

**“块”**的概念：我刚刚说的大小相同的区域，在主存中叫作主存块，在Cache中叫作Cache块或Cache行（注意这两是一个东西，题目中给出块或者行都是OK的）。主存块的大小就等于Cache块的大小！！这是第一点需要我们铭记于心的，原理我刚刚已经说过了，就是方便交换数据。
Cache的数据结构模型（重点看，有个记忆能画出来是最好的）

从王道教材书这张图，我们可以看到Cache主要分为了tag标记位和存储数据两部分，数据部分是以“块”为单位与内存交换数据的，如果不够清晰，我们来看小林coding给出这张结构图：

我们可以清楚地看到每一个Cache行都分为了tag位和数据块，对应的主存也要划分成一个个一样大小的数据块，那么主存是怎么进行划分操作的呢？我们需要引出一个概念“主存地址”。
主存地址：将主存划分为多个主存块后，我们就需要一些数据位来标识块号，因此主存地址可以划分为两部分：高位地址（标识块号）+低位地址（块内地址）。请一定要记住这个划分它是我们后面做题的逻辑基点，同样的Cache以同样的划分方式：高位地址（标识块号）+低位地址（块内地址）。
有效位：Cache中除了拥有上述的主要部分tag+数据块，还有一些特别的东西，我们先从有效位开始介绍。
1. 工作原理：有效位用来标记对应的 Cache行中的数据是否是有效的，如果有效位是 0，无论Cache 中是否有数据，CPU 都会直接访问内存，重新加载数据。
2. 作用：有了这个有效位，我们想要淘汰一个主存块数据就很容易了，只需要把有效位置0，装入一个新的主存块的时候，再把有效位置为1即可。
CPU访问过程：我一开始的时候就说了，如果Cache中已经有了数据，我们就不要去访存了，但是如果在Cache中没有找到数据，我们就要去内存中读取并把数据块复制到Cache块中，这个过程也就是Cache的缺失处理。重点来了，到底是谁去完成这些判断、替换数据块工作的呢？为了保证速度当然只能由硬件来实现了，因此Cache对于程序员来说是透明的，所有过程都由硬件自动实现。硬件自动实现，硬件自动实现！！！重要的事情说三遍。

Cache和主存的映射方式（超级重点⭐⭐）

这一块请跟着我一起理解并记忆！！考察计算题！

我们一直再说交换数据，那么我们怎么把主存的数据块通过地址映射的方式，复制到Cache行中呢？先来了解一下三种映射方式：

1）三种映射方式

直接映射：每个主存块映射到Cache的特定行中，CPU访问某个特定行即可
全相联映射：主存块可以映射到Cache的任意行中，需要把Cache所有行都扫一遍
组相联映射：把Cache分成多个组，每个组又有多个行，主存块可以放到特定组的任意行中，访问的时候只需要看看那特定组的所有行

2）直接映射的理解

我们先来看这张图：
我们需要把主存块映射到特定的Cache行中，因此就需要一个转化的方式，我们把它提炼成一个公式：

cache 行号 = 主存块号 % Cache行数

我们来解释一下：假设我们一个主存块的大小为4B，给出一个主存地址x（还记得主存地址是什么吗，上面已经讲过高位标识块号低位为快内地址），我们就可以通过x/4去找到我们的主存块号（假设是从0标号的），我们也可以通过转成二进制然后通过右移操作（比如/4就是右移两位）来得到块号，再用块号去%Cache行数（同样的模运算也可以用二进制取后n位得到，等会会演示）。

Cache行数如果题目中没有给出，就是用Cache的总容量去 / cache块的大小（和主存块是一样大的）来得到。

好好理解一下这个公式，后面我会用综合性很强的计算题带着大家来做练习加深理解。
主存地址划分：

三部分组成：标记Tag+Cache行号（也有叫索引的）+块内地址（也有叫块内偏移的）

其中主存块号就是去除块内地址的部分，即标记+Cache行号。我们刚刚一直没有介绍tag位是用来干嘛的，只是引出了这个概念，实际上它是作为主存块和Cache块是否匹配的验证信息，如上图用一个比较器进行匹配的操作，同时还要去看有效位是否为1，不过这一块内容不是考察的重点，我们就算不太能理解也没有关系，能把各部分的位数计算出来就行了。
内存映射表：很多教材上都不讲这一点，所以对同学们造成了概念上的迷惑，到底什么是地址映射表？一句话，地址映射表就是Cache中除了装数据部分的大小，要用标记位+特殊位得到，等会看一道题。

3）全相联和组相联

理解了上面的直接映射后，这两种就好理解多了。

全相联映射：给每一个行都设置一个比较器，根据tag字段按内容访问Cache中的主存块，对于硬件开销比较大，但是能解决直接映射的冲突问题。

我们需要记住的是主存地址结构：标记+块内地址（最简单的一种，只有两部分）
组相联映射：组间采用直接映射，组内采用全相联映射。
1. Cache行数 = 组数 * 路数（每一组的大小是相等的，路数是指每一组有多少个Cache行，题目一般给出的也是k路组相联的信息，不要搞混了）
2. 地址结构：标记+组号+块内
3. 组号的计算方法和直接映射中Cache行号的计算思想是一样的，先求出主存块号，再对组数取模，后面直接来看例题就更清晰了。
4. 当路数为1时，就变成一块一组，也就退化成直接映射方式，当路数为Cache行数时，所有块都变成了一组，也就变成了全相联映射。