本节书摘来自异步社区《现代体系结构上的UNIX系统：内核程序员的对称多处理和缓存技术（修订版）》一书中的第2章，第2.1节，作者：【美】Curt Schimmel著，更多章节内容可以访问云栖社区“异步社区”公众号查看
第2章 高速缓存存储系统概述
高速缓存存储系统（cache memory system）是高速存储器，它能够利用引用的局部性来提高系统性能。本章解释了高速缓存的基本术语、规划和操作，阐述了高速缓存是如何配合主存储器运行的，以及高速缓存中的数据是如何定位的。本章还介绍了散列算法（hashing algorithm）、缺失处理（miss processing）、写策略（write policy）、替换策略（replacement policy）以及组相联（set associativity）。本章主要着眼于单处理器系统的高速缓存，多处理器高速缓存将在第三部分中进行介绍。到本章结束的时候，读者会对高速缓存的操作非常熟悉，可以在后面的章节中开始研究操作系统的问题了。
2.1 存储器层次结构
现代体系结构上的UNIX系统：内核程序员的对称多处理和缓存技术（修订版）
高速缓存是一种高速存储系统，它保存有主存储器很小的一个子集的内容。它的物理位置介于主存储器和CPU之间。因为它比主存储器速度快，所以如果频繁使用的指令和数据能够保存在高速缓存中供CPU存取，那么就有可能提高系统的性能。图2-1给出了包含高速缓存的一个计算机系统的逻辑框图。
高速缓存利用引用的局部性（locality of reference）来改善系统性能。引用局部性是大多数程序所表现出来的一种属性，在这些程序中，在一个特定的时间段内，程序指令和数据的一个相当小的子集被频繁地重复引用。如果能够把程序当前的局部引用保存在高速缓存中，那么程序就能执行得更快，因为高速缓存可以比主存储器更快地提供指令和数据。
高速缓存只是存储器层次结构（memory hierarchy）中的一个组成部分。这个存储结构的一端是磁盘存储器，它具有非常高的密度，很低的每位成本，而存取速度则（相对）较慢。另一端是CPU内的寄存器，在数量上只有几个，具有很高的每位成本，但是存取速度极快。随着我们从磁盘存储器过渡到寄存器，单位成本逐渐增加，存取速度逐渐加快，而密度却逐渐降低。
虚拟存储器调页系统（paging system）已经显示出只占系统中所有进程所使用的全部虚拟存储空间大小若干分之一的主存储器系统是怎样提供良好的整体性能的。引用的局部性通过只要求一个进程当前的工作集（working set）驻留内存使之成为可能，工作集是那些包含有进程当前局部引用位置的存储页面。进程地址空间的其他部分则可以保存在磁盘上，直到需要的时候再加载。
引用局部性延伸到了比工作集更细的粒度上。在一个进程工作集的页面内，肯定会有一组指令和变量在一段极短的时间内被一个程序频繁地重复引用。例如，考虑图2-2中计算矩阵a和b乘积的C代码小片段。假定a是一个m×r矩阵，而b是一个r×n矩阵，c的全部元素都初始化为0。
在这段代码执行的同时，它重复引用了3个循环内的指令、矩阵的元素以及循环计数器。这就是当这段代码在执行时程序的局部引用。由于矩阵包含的数据比寄存器能保存的数据多，因此如果没有高速缓存，CPU就不得不重复引用主存储器，从而将这部分程序的执行速度限制在了主存储器的存取时间上。
图2-2中有两种类型的局部性：时间的（temporal）和空间的（spatial）。时间局部性是程序有可能重复使用近期引用过的项的属性。例如，在执行最里面的一层循环期间，数组c的同一个元素会被引用两次，循环变量i、j和k也是如此。类似地，在所有三层循环中的指令也会被重复引用。所有这些引用都体现出了时间局部性。空间局部性是程序有可能重复使用前面附近引用过的项的属性。由于C语言中的数组都是按照行的顺序保存的，所以数组a和c都体现出了空间局部性，因为会在后面的迭代中访问到行中的下一个邻接元素。类似地，串行程序的执行表现出了高度的空间局部性。
主存储器系统速度的提高和成本的降低并不能跟上如今高速CPU的发展速度。如果CPU的速度和主存储器的存取时间远远不能平衡，这意味着存储器要比CPU执行指令以及加载和保存数据的能力慢得多，那么CPU就会受到存储器速度的限制。在这样的情况下，提高CPU的速度对于改善系统的整体性能来说几乎没有什么帮助，因为存储系统仍然是限制因素。虽然人们可以制造大规模的高速主存储器系统，它们的存取时间能够同CPU加载和保存数据的能力相媲美，但是这种存储系统对于高端大型机和超级计算机以外的系统来说往往太贵了。当今很多系统设计人员所采取的另一种选择是使用高速缓存。
通过利用细粒度的引用局部性，高速缓存能够弥补速度较慢的主存储系统和快速的CPU之间的鸿沟。在存储器层次结构中，每一级引用局部性的应用情况如图2-1所示。正如主存储器只保存了程序的一个子集（工作集）那样，寄存器保存了当前运算的操作数，高速缓存保存了正在工作的指令和变量集，在那之上形成了细粒度的局部引用。由于引用的局部性，高速缓存只需要拥有主存储器的很小一部分就能够发挥效用。由于它的规模相对较小，所以实际上可以使用比主存储器所采用的速度更快的存储设备，因为并不需要太多的高速缓存。于是，高速缓存的高速度与对引用局部性的利用相结合就能大幅提高系统性能，同时在经济上也很划算。
