705-高速缓存的工作原理
# 705-高速缓存的工作原理
因为 CPU 的速度和内存的速度差距越来越大， 那计算机整体系统的性能，就受到了巨大的影响， 而高速缓存技术的出现，则挽救了这个局面。那在这一节， 我们就来看一看高速缓存是如何工作的
就是计算机的存储层次结构， 高速缓存，也就是 Cache 对于 CPU 和主存之间， 相比于主存，它的容量要小的多
但是速度也快很多， 但是为什么在 CPU 和主存之间，增加这么一个速度很快，但是容量很小的存储部件， 就可以提升这个计算机系统的性能呢？这就要得益于计算机中运行程序的一个特点， 这个特点被称为程序的局部性原理。 我们通过一个例子来进行说明
这是一段很常见的程序， 有两层循环，对一个二位数组进行累加， 如果 sum 这个变量是保存在内存中的，那它所在的这个存储单元，就会不断的被访问， 这就称为时间局部性， 这些对循环变量进行判断和对循环变量进行递增的指令，也都会被反复执行， 而另一点叫作空间局部性，指的是正在被访问的存储器单元附近的那些数据，也很快会被访问到。 那么就来看这个数组，它在内存当中，是连续存放的， 从 a00，a01，a02，这样一个接一个的存放下去， 那么在这段循环访问它的时候，访问了 a00 之后，很快就会访问 a01，然后很快会访问 a02， 这样的特征，就被称为空间局部性， 那 Cache 就是利用了程序的局部性原理，而设计出来的
首先，我们来看 Cache 对空间局部性的利用， 当 CPU 要访问主存时，实际上是把地址发给了 Cache， 最开始，Cache 里面是没有数据的，所以 Cache 会把地址再发给主存，然后从主存中取得对应的数据， 但 Cache 并不会只取回 CPU 当前需要的那个数据， 而是会把与这个数据，位置相邻的主存单元里的数据，一并取回来， 这些数据就称为一个数据块， 那么 Cache 会从主存里，取回这么一个数据块，存放在自己内部，然后再选出 CPU 需要的那个数据送出去， 那过一会儿，CPU 很可能就会需要刚才那个数据附近的其它数据， 那这时候，这些数据已经再 Cache 当中了，就可以很快的返回， 从而提升了访存的性能。
第二种情况，是 Cache 对时间局部性的利用， 那因为这个数据块暂时会保存在 Cache 当中，那 CPU 如果要再次用到刚才用过的那个存储单元，那 Cache 也可以很快的提供这个单元的数据， 这就是 Cache 对程序局部性的利用
我们要注意，这些操作都是由硬件完成的， 对于软件编程人员来说，他编写的程序代码当中，只是访问了主存当中的某个地址， 而并不知道这个地址对应的存储单元，到底是放在主存当中，还是在 Cache 当中
如果这个不太好理解的话，那我来打个比方， 我们可以把主存看作一个图书馆，里面可能有几千万册的藏书， 那 CPU 就像一个来借书的人，那他给出了一个书号，希望借到这本书，那可能要花几个小时，才能找到这本书，拿出来交给借书的人。 那过一会儿，借书的人把这本书还了以后，管理员又把它放回到仓库当中去，再过一会儿，这个人又要借这本书， 那管理人员又要花几个小时，从仓库里再找到这本书，拿出来， 后来管理员发现，这样的工作实在是太低效了， 于是就在这个仓库的外面，借阅的柜台旁边，准备了一个柜子，把刚才借过的书，暂时先存放在这个柜子里， 有些书在很短的时间内，会被多次借阅， 所以这本书放在这个临时柜子里的时候，经常就会被借阅到， 那管理员就可以很快的把这本书交给借阅的人，而不用去大库里面，花几个小时去寻找。 于此同时，管理员还发现了另一个现象，那就是有一个人来借了一本明朝的故事， 然后过一会儿，就会再来借清朝的故事，在过一会儿，可能又来借宋朝的故事， 而这些书，在仓库里面，都是紧挨着排放的， 所以他干脆这么做，当要从仓库里取出一本书的时候， 就把和这个书在同一层书架上的所有的书，都一次性拿出来， 这样并不会比取一本书多花多少时间， 而对于借书的人来说，他并不会知道管理员做了这件事情， 对他来说，还是给出了一个书号，然后过一会儿得到这本书， 他只会发现，借书的速度变快了，这个类比差不多就是 Cache 所做的事情
# Cache 的访问过程
那我们再来整理一下 Cache 的访问过程， 那现在 CPU 发出度请求，都是直接发给 Cache 了， 然后 Cache 这个硬件的部件，会检查这个数据，是否在 Cache 当中， 如果是，就称为 Cache 命中，然后从 Cache 当中取出对应的数据，返回给 CPU 就可以了
但是如果这个数不在 Cache 中，我们就称为 Cache 失效， 那这时候，就要由 Cache 这个部件，向主存发起读请求， 这个过程 CPU 是不知情的，它仍然是在等待 Cache 返回数据， 那 Cache 向主存发出读请求之后，就会等待主存将数据返回， 这个过程会很长，那么当包含这个数据的一整个数据块返回之后，Cache 就会更新自己内部的内容，并将 CPU 需要的那个数据返回给 CPU，这样就完成了一次 Cache 读的操作。
# Cache 组织结构示例
那么 Cache 这个部件内部是如何组织的呢？ Cache 主要组成部分是一块 SRAM，当然还有配套的一些控制逻辑电路， 那这个 SRAM 的组织形式，像这个表格，它会分为很多行， 那么在这个示例的结构当中，一共有 16 行， 每一行当中有一个比特，是有效位，还有若干个比特是标签， 然后其它的位置，都是用来存放从内存取回来的数据块。在这个例子当中，一个数据块是 16 个字节
那么还是通过一个例子，来看一看这个 Cache 是如何运行的， 我们就用这个表格来代表 Cache，假设现在这个 Cache 里面全是空的， 有效位为 0，代表它对应的这一行没有数据， 那么现在来执行这四条指令
第一步，我们要访问 2011H 这个内存地址， 并取出对应的字节，放在 AL 寄存器当中去，那 CPU 就会把这个地址发给 Cache， 那因为现在 Cache 全是空的，所以显然没有命中，那 Cache 就会向内存发起一次读操作的请求。
但我们要注意，因为 Cache 一次要从内存中读出一个数据块，而现在这个 Cache 的结构，一个数据块是 16 个字节，所以它发出的地址，都是 16 个字节对齐的， 所以这时，Cache 向主存发出的地址，是 2010H， 这个地址是 16 个字节对齐的， 而且从它开始的 16 个字节的这个数据块当中，包含了 2011H 这个地址单元， 当 Cache 把这个数据块读回来之后，会分配到表项 1 中
那么在这个表项当中， 这个字节就是 2010 所对应的数据，这个字节就是 2011 所对应的数据， 所以 Cache 会将这个字节返回给 CPU
但是 Cache 为什么要把这个数据块，放在了表项 1 当中呢？ 我们详细来看一看， CPU 在执行这条指令的时候，Cache 收到的地址，实际上是 2011H
那因为现在一个数据块当中，包括 16 个字节，那最后的这个 16 进制数（peterjxl 注：就是 2011H 中的最后一个数，1H，表明我们要的是第 1 个字节），正好用来指令这 16 个字节当中的哪一个字节，是当前所需的，
因此，我们取回的这个数据块，要放在哪一个表项当中，就要靠前面的一个地址来决定（peterjxl 注：也就是 2011H 这个数，去掉最后一个 1，然后取最低位的那个数，这里是 1H）。 那么在现在的 Cache 设计当中，一般来说，都是用剩下的这些地址当中， 最低的那几位，来决定到底把这个数据块放在哪一个 Cache 行中。
那我们现在由 16 个表项，所以也需要 4 位的地址来决定， 那因此，现在剩下的最低的 4 位地址，就正好是这个 16 进制数了， 这个数是 1，所以 Cache 就决定把这个数据块放在表项 1 的 Cache 行里， 那现在还剩下 8 位的地址，我们也必须记录下来， 不然以后就搞不清楚，这个 Cache 行里存放的数据，到底是对应哪一个地址的， 所以剩下的地址，不管有多少，都要存放在标签这个域当中。 当然，在把数据块取回之后，还需要把这个有效位置为 1， 那这样，我们通过这个表格，就可以明确的知道，当前的这个数据块，是从 2010 这个地址读出来的，那在这个 Cache 行中的第一个字节，就是 CPU 现在做需要的那个字节了。 那把这个字节取出来，交给 CPU，这条指令对应的读操作就完成了。
peterjxl 小结，2011H 每一个的用处
倒数第一个 1，就是表明我们要的是哪个字节（因为 CPU 是从字节对齐的方式取一个数据块的）
倒数第二个 1，表明放在哪个表项中
倒数第三和第四个数：放到标签里。
所以要看 2011H 这个字节的位置，要这样看：看 标签为 20H + 表项位置 + 最后一个字节的位置 = 2011H
# 第二条指令
然后我们再来看第二条指令，这条指令要读取 4011H 这个地址， 那这次我们就来看一看，Cache 在收到这个地址后，会做哪些操作。 开始收到 4011 这个地址后，首先应该找到这个地址对应的 Cache 行在哪里， 那它会用这一部分的地址来索引行，所以找到的还是表项 1， 然后检查有效位，是 1，代表这一行当中的数据是有效的。 但这并不能说明它所需要的数据就在这一行里面。接下来还需要比较标签位， 那把地址当中的高位 40H 和这个标签位进行比较，结果发现不相等， 那就说明这行当中的数据不是 4011 对应的那个数据块， 因此 Cache 还是需要向储存放出访存请求
那发出的访存地址应该是什么呢？你先考虑一下。 那还有一点要注意的，就是等会取回的这个数据块，也还是需要放在这个表项 1 当中， 所以会覆盖现在 Cache 当中的这个数据块，而且等会还会把这个标签位也改成 40H。 那假设现在 Cache 已经把对应的数据块从储存当中读回来了， 并且完成了对这个 Cache 行的替换操作， 那之后 Cache 就可以根据地址当中的最低四位找到对应的字节， 那现在还是第一个字节， 把这个字节 B1H 返回给 CPU，就完成了这条指令的读操作了。
# 第三条指令
然后我们再来看第三条指令，那请先想一想访问这个地址的时候，Cache 会 去检查哪一个表项，又会进行什么样的操作呢？请先思考一下， 然后我会快速地给出结果，就不再详细地解释了。 其实这一次会访问表项 3，然后不命中，然后读取内存地址 3730 的数据块，并填到表项 3 中，然后返回其中第二个字节 C2H，这样就完成了第三条指令。
# 第四条指令
然后我们再来看第四条指令， 这条指令的地址是 401F，那么 Cache 会首先找到对应的行， 因为这部分地址是 1，所以索引到的还是表项 1 ，然后查看有效位，确定这一行的数据是有效的。 下一步是比较标签，那么都是 40，所以标签也是匹配的， 这样就可以确认这个地址对应的数据就在这个 Cache 行当中，那我们就称为 Cache 命中， 最后再根据地址的最低几位，找到对应的字节， 那这个 BFH 就是 CPU 需要的这个数据了， 把这个数据返回之后，这条指令也就完成了。
那现在我们就了解了 Cache 读操作的几种典型的情况，
一种是没有命中，而且对应的表项是空的时候；
第二是没有命中，但是对应的表项已经被占用的情况
还有就是命中了的情况
那看完了读，我们再来看一看写的情况。 当 CPU 要写一个数据的时候，也会先送到 Cache， 那这时也会有命中和失效两种情况。 如果 Cache 命中，我们可以采用一种叫写穿透的策略，把这个数据写入 Cache 中命中的那一行的同时，也写入主存当中对应的单元， 那这样就保证了 Cache 中的数据和主存中的数据始终是一致的。
但是因为访问主存比较慢，这样的操作效率是比较低的， 所以我们还可以用另一种策略叫做写返回， 那这时只需要把数据写到 Cache 当中，而不写回主存， 只有当这个数据块被替换的时候，才把数据写回主存。 那这样做的性能显然会好一些， 因为有可能会对同一个单元连续进行多次的写， 那这样只用将最后一次写的结果在替换时，写回主存就可以了，大大减少了访问主存的次数。 但是要完成这样的功能，Cache 这个部件就会变得复杂得多
那同样地，在 Cache 失效的时候，也有两种写策略，
一种叫做“写不分配”，因为 Cache 失效，所以要写的那个存储单元不在 Cache 当中， 写不分配的策略就是直接将这个数据写到对应的主存单元里；
而另一种策略叫“写分配”，那就是先将这个数据所在的数据块读到 Cache 里以后，再将数据写到 Cache 里。
那写不分配的策略实现起来是很简单的，但是性能并不太好， 而写分配的策略，虽然第一次写的时候操作复杂一些， 还是要将这个块读到 Cache 里以后再写入，看起来比写不分配要慢一点， 但是根据局部性的原理， 现在写过的这个数据块过一会很可能会被使用，所以提前把它分配到 Cache 当中后，会让后续的访存性能大大提升。
因此在现代的 Cache 设计当中，写穿透和写不分配这两种比较简单的策略往往是配套使用的， 用于那些对性能要求不高，但是希望设计比较简单的系统； 而大多数希望性能比较好的 Cache，都会采用写返回和写分配这一套组合的策略。
那除此之外，在对 Cache 进行写的过程中，如何去查找分配和替换 Cache 中的表项，都是和刚才介绍过的读操作的情形是一样的，就不再重复描述了。
高速缓存的基本原理并不复杂， 现在我们就可以构造出能够正常工作的高速缓存了。 但是如果希望高速缓存能够高效地工作，真正提升计算机的性能， 就还需要解决很多的细节问题， 之后，我们一一探索。
