本节书摘来自异步社区《现代体系结构上的UNIX系统：内核程序员的对称多处理和缓存技术（修订版）》一书中的第2章，第2.2节，作者：【美】Curt Schimmel著，更多章节内容可以访问云栖社区“异步社区”公众号查看
2.2 高速缓存基本原理
因为几乎所有的程序都体现出了局部引用特性，所以在从PC（个人计算机）到超级计算机的各种系统上都能找到高速缓存。甚至在现今大多数微处理器芯片和内存管理单元（memory management unit，MMU）芯片上也可以找到集成的高速缓存。如果在微处理器或者MMU芯片上没有包含高速缓存，那么它一般会在主板（称为外部高速缓存）上。靠近CPU降低了CPU和高速缓存之间的存取时间。如果高速缓存位于一块独立的板卡上，从而必须通过总线来访问它，那么就会大幅增加时延（latency），从而带来系统性能上的相应损失。有些系统既使用片上高速缓存，也使用外部高速缓存。
高速缓存的大小从几个字节到数百KB都有，在大规模系统上甚至可能有1 MB以上的高速缓存。例如，今天的片上高速缓存一般介于4 KB到16 KB之间。外部高速缓存要大一些，介于128 KB到4 MB之间。随着时间的推移，高速缓存的规模正在逐步扩大。例如，Intel 80386没有片上高速缓存，80486有8 KB的高速缓存，而Pentium则有两块8 KB的高速缓存。外部高速缓存已经从MIPS R2000的64 KB增加到R4000的4 MB。
一般而言，高速缓存越大，性能提升就越多，因为有更大的一个存储子集被高速缓存起来供高速访问。正如随后的各章中将要看到的那样，高速缓存的规模并不能改变操作系统必须正确管理高速缓存的问题，而只能改变要使用的特定算法。高速缓存的性能将在2.11节里进一步讨论。
一个系统可以使用分离的指令高速缓存和数据高速缓存。这能够进一步提高系统的性能，因为CPU可以同时从指令高速缓存取得指令，而从数据高速缓存加载或者存储数据（参见2.10节）。正如第6章中将要看到的那样，可以使用多级高速缓存给存储器层次结构增加额外的层次（接下来的几章将集中介绍单级高速缓存）。
2.2.1 如何存取高速缓存
高速缓存的实现使得它们的存在对于用户程序来说基本上甚至完全地被忽略了。大多数实现的目标是隐藏高速缓存管理的全部细节，不论是硬件的还是操作系统的（在后面的章节中阐述），从而达到用户应用的可移植性。这一思路确保了无需修改程序，应用程序就可以移植到具有不同高速缓存组织、不同高速缓存规模的不同系统上，或者移植到没有高速缓存的系统上。这在当今的市场上是一个重要的好处。如此一来，程序可以像以前那样继续通过地址引用存储器。访问高速缓存不需要特殊的编码技术或者寻址模式。高速缓存可以通过控制高速缓存的硬件自动访问。一种称为物理高速缓存（physical cache）的高速缓存组织方式甚至对操作系统都是透明的。这就有可能给原本在设计上没有高速缓存的体系结构，例如IBM 370和IBM PC，增加高速缓存，同时仍然能够跟现有的系统软件保持兼容性（物理高速缓存将在第6章详细介绍）。
因为高速缓存只保存主存储器的一个子集，所以需要有几种方式来确定存储器的哪些部分当前驻留在高速缓存中。我们称存储器的那些部分被“缓存”了。这一点是通过将高速缓存中的数据用它们对应的主存储器地址进行标记（tagging）来做到的（对于指令高速缓存中的指令来说也是如此）。随后硬件就可以通过检查高速缓存中数据的标记来判断一个特定的内存位置是否被缓存了。这样，比如说当CPU请求一个它想要获取的主存储器地址时，这个地址就被发送给高速缓存，然后硬件就开始搜索高速缓存来寻找相应的数据（参见图2-3）。如果在高速缓存中找到了它，那么就称为一次缓存命中（cache hit）。如果没有找到相应的数据，那么就称为缓存缺失（cache miss）。缓存命中与缓存缺失的频率之比就称为命中率（hit ratio），它以引用命中的百分比或者命中发生的概率（90%的命中率和0.9的命中概率是等价的）来表示。命中率越高，系统的性能就越好。
如果发生了一次命中，那么数据被返回给CPU，就好像它是从主存储器中读取的一样。如果没有命中，那么就把地址传递给主存储系统，在那里访问寻址单元。在这种情况下，数据既返回给CPU也返回给高速缓存。在一次缺失之后数据被保存在高速缓存中，以便利用时间局部性。此时也可以把CPU读取的一段数据周围的数据都载入高速缓存，从而也利用空间局部性（正如后面将要讨论的那样，在高速缓存缺失期间载入的数据量取决于具体实现）。因为大多数程序都表现出了局部性，所以90% 或者更高的命中率并非罕见。
在高速缓存的设计中，要考虑的重要一点是用一个标记确定多少数据。如果独立地标记高速缓存中的每一个字节的话代价太大了。因此，来自主存储器的一个或者更多连续的字被组织到一起形成了一个高速缓存行（line）或者块（block），并且给每一行关联单个标记。所以一个完整的高速缓存行是由一个标记和一段数据组成的，但是高速缓存行的大小是指数据部分的字节数（一般并不包括标记的大小）。片上高速缓存行的典型大小范围是从16字节到32字节。因为行中数据部分的字节是从连续的存储器单元来的，所以标记只需要包括第一个字节的地址即可；其他字节的地址可以用它们在行内的位置来推算。
除了地址之外，一行的标记部分还包括控制信息（control information）。标记部分始终都要加上一位，作为有效位（valid bit），表明相关的高速缓存行是否投入使用以及是否包含有效的数据。仅当有效位被置为ON且标记吻合时，才能发生缓存命中。在系统复位或者启动期间初始化高速缓存的时候，所有的有效位都被清除，因此初始情况下所有的指令和数据都取自主存储器。
在标记中保存的另一个常见的标志是修改位（modified bit）。正如2.2.5节所讨论的那样，当CPU把数据保存到使用写回高速缓存机制（write-back caching）的一个高速缓存中的时候就会设置这个位。在标记中也可以出现其他依赖于具体实现的信息，比如键（key），它是第4章的主题。
在发生一次高速缓存缺失的时候，就从主存储器中读取填满整个高速缓存行所需要的字节数，然后加载到高速缓存中。因为反映整行状态的只有一个有效位，所以必须这样做。例如，如果高速缓存行的大小是两个字长，那么在一次高速缓存缺失时不可能只读取CPU所引用的那一个字。如果没有读取两个字，那么高速缓存行的一半就会包含无效的数据。一般说来，从主存储器中读取附加的字并不会影响性能，因为大多数现代的主存储系统的设计都能一次读取或者写入多个字。
有些实现选择使用非常长的高速缓存行（128~256字节或者更多）。这样做的优点是它减少了标记所需占用的存储器数量，因为一个标记现在能够覆盖更多的缓存行里数据部分的字节数。因此，为保存同等数量的数据，高速缓存所需的标记更少。长高速缓存行的缺点是，将整个行传入和传出主存储器所需要的时间开始明显变长。为了缓解这一问题，有些实现将一个高速缓存行划分成了多个子行（subline），每个子行都有它自己的有效位。于是每个子行都能独立地进行处理，就好像它是一个单独的高速缓存行一样，差别在于只有一个地址标记涵盖一行中所有的子行。这意味着所有的子行包含来自连续主存储器地址中的数据。每个子行的地址由它在整个高速缓存行中的位置和高速缓存行的标记就可以推算得到。幸运的是，子行的使用对于操作系统来说是透明的，所以它不需要成为随后讨论中的一个考虑因素。
2.2.2 虚拟地址还是物理地址
高速缓存可以设计成通过数据或者指令的虚拟地址或是物理地址来访问。类似地，缓存标记也可以被设计成连同其他信息一起，要么含有虚拟地址，要么含有物理地址。选择虚拟地址还是物理地址在设计硬件的时候就确定下来了，并且对高速缓存管理技术有很大的影响，而操作系统必须采用这些技术对用户程序隐藏高速缓存的存在。这些复杂的问题将是后续各章的讨论主题。对于本书剩下的内容来说，不需要考虑访问高速缓存时所采用的地址类型。采用其中任何一种地址类型对于下面介绍的主题都有相同的影响。接下来的几小节只是简单地称它们为“地址”。
2.2.3 搜索高速缓存
如果给定CPU想要的数据的地址，那么必须快速地搜索高速缓存来查找那个数据，因为高速缓存的全部目的就是要比主存储系统更快地返回数据。搜索技术还必须简单，以便高速硬件的实现既切合实际，又经济划算。比如说，线性搜索技术就不适用于高速缓存，因为除了最小的高速缓存之外，它们对于所有的高速缓存来说都太慢了。它们还难以在硬件上实现，因为它们需要一个状态机（state machine）或者定序器（sequencer）来保存搜索的当前状态。大多数高速缓存代之以使用一种简单的散列表（hash table）技术来进行搜索。
为了搜索一个高速缓存，来自CPU的地址经散列处理生成一个索引（index），这个索引指向高速缓存中的一个或者多个位置，如果相应的数据被缓存了，那么就会保存在这些位置上。和许多散列算法一样，不同的地址可能产生相同的索引值。于是必须用这些位置上的标记（它们包含着那些位置上正在高速缓存的数据的地址）和CPU所提供的地址进行比较。如果一个标记与来自CPU的地址相吻合，那么就发生一次命中；否则，就出现一次缺失。对于高速缓存来说，散列是一种很有用的技术，因为它将搜索限定在了包含一个或者多个位置的小集合中（除了在全相联的高速缓存中之外，这将在以后介绍。在全相联的高速缓存中不使用散列技术）。接下来，硬件会快速地并行搜索这些位置。对于大规模的高速缓存来说，这些技术格外重要，因为在这些高速缓存中只有足够的时间去搜索一小部分高速缓存。上述的所有活动都在硬件中执行，无需软件的介入。
2.2.4 替换策略
因为高速缓存比主存储器小，所以在高速缓存缺失操作期间载入新数据时缓存中的一些已有的数据必须被丢弃。要丢弃的数据是根据高速缓存的替换策略（replacement policy）来进行选择的（该策略与实现有关）。一旦被选中，那么高速缓存中要丢弃的数据就被新数据所替换。和数据相关联的标记也改成新数据的地址，从而在高速缓存中正确地标识它。
高速缓存所采用的替换策略往往相当简单。虽然在存储管理和虚拟存储调页系统中所看到的页面老化（page aging）和替换（replacement）技术从理论上说也可以应用于高速缓存，但是它们在硬件上实现起来过于复杂。它们经常需要大量的状态或者历史信息，而在高速缓存中使用的昂贵的高速存储器数量有限，没有充足的空间来保存这些状态和信息。典型的高速缓存替换策略有LRU（Least Recently Used，最近最少使用）、伪LRU（pseudo-LRU，一种LRU的近似）以及随机替换。这些策略将伴随本章后面讨论的不同高速缓存组织进行介绍。幸运的是，和前面讨论过的那些高速缓存访问的方面一样，替换策略对于软件来说也是透明的。
2.2.5 写策略
当CPU保存数据的时候，大多数实现都把数据直接保存到高速缓存中。将数据保存在高速缓存中有助于改善系统性能的原因有两个：第一，由于时间局部性，被保存的数据在写入之后会被频繁地重新读取，因此就提高了命中率；第二，在高速缓存中使用的速度更快的存储设备保存数据的速度要比主存储器快，这就解放了CPU，让它能够比其他可能的方式速度更快地开始下一次数据载入或者保存操作。写入高速缓存中的数据也可以同时写入主存储器。高速缓存的写策略（write policy）也叫做更新策略（update policy），表明了数据是怎样保存到高速缓存和主存储器中的。
要把数据保存到高速缓存中，必须搜索高速缓存，看看高速缓存内是否已经包含有和写入的地址相关的数据。此刻使用了与从高速缓存中读取数据时相同的搜索技术。先考虑在保存期间出现一次命中的情况。在这里，CPU写入的数据替换了高速缓存行内的老数据，以便利用时间局部性。
虽然高速缓存是用来自CPU的新数据更新的，但是该数据可以写入主存储器，也可以不写入主存储器，这取决于所采用的写入策略。两种可能的写入策略是写直通（write-through）和写回（write-back）（也叫做复制回，copy-back）。如果一个高速缓存正在使用写直通策略，那么来自CPU的数据既会写入高速缓存也会写入主存储器。写直通策略得名于存储器层次结构的组成（参见图2-1），它必须“直通”过高速缓存到达主存储器。MIPS R2000/R3000和Intel用于80486的82495DX外部高速缓存控制器都使用写直通高速缓存机制。写直通策略的效果是存储器始终保持在“最新”状态，这意味着在高速缓存中的数据和存在于主存储器内的数据副本完全相同（也叫做“保持缓存一致”）。这种策略的缺点是每次来自CPU的写入操作都需要有一个主存储器周期，这有可能会降低系统的速度。
另一种策略是写回（write-back）。此时来自CPU的数据还是按照以前那样被写入高速缓存，但是并不写入主存储器，直到在行替换或者操作系统明确要求写回主存储器期间才写入主存储器。这就消除了采用写直通高速缓存机制时，如果在某个地址的数据被高速缓存，同一个地址被写入若干次时所造成的额外的主存储器周期开销。写回策略的缺点是，主存储器中的内容相对于高速缓存而言变成了“过时的”或者说不一致的。为了重获一致性，往往需要操作系统的介入。
例如，考虑采用写回高速缓存的CPU在执行一个程序中i = i + 1这条语句时会发生什么情况（假定i的值以前没有被高速缓存过）。如果在执行这条语句之前，i在主存储器中的值为1，那么当CPU试图读取i的当前值的时候，它就不会在高速缓存中命中，并且要将值1载入到高速缓存中，然后返回给CPU（图2-4a）。接着，CPU给i的值加1，把i的值2写回。写入操作导致在高速缓存中发生一次命中，并且i在高速缓存中的值被更新为2。此刻写入操作完成时高速缓存中i拥有新值，但主存储器内仍然保持着i的旧值1（图2-4b）。在高速缓存内i的新值被认为相对于主存储器内的值被“修改”过了。
必须确保i在主存储器内的过时值不会被程序访问到，否则将会出现无法预测的结果。类似地，也必须确保多处理器系统上的其他进程不会使用过时的存储器内的值（这将在第三部分进行讨论）。只要i的新值保存在高速缓存内，那么程序就不会访问到i的过时值，因为程序总是可以在访问主存储器之前在高速缓存中命中。被修改的数据将保持被高速缓存，直到该行被替换为止。
在随后的缺失操作期间内的任何时刻，都可以替换写回高速缓存中的数据。被修改的数据不能被简单地丢弃，因为程序最终会在下一次引用时访问到在主存储器内的原来的过时值。因此，在替换之前，要替换的已被修改过的数据会由高速缓存硬件自动地写回到主存储器中。为了区分高速缓存中需要在替换时写回的已修改数据和不需要写回的未修改数据，在每个标记中加入了一个称为修改位（modified bit）的附加位。CPU写入数据的每一行的标记中都设置了修改位。只要在读缺失（read-miss）操作期间载入了数据，修改位就会被清除，因为数据仍然和主存储器保持同步。通过跟踪每一行的修改状态，高速缓存只需要在必要时写回高速缓存行，而无需像写直通高速缓存机制那样每次保存操作都要这样做。所以说，写回高速缓存机制的优点就是主存储器写入操作可能更少，总线操作可能更少，整体性能也就可能更好。缺点是操作系统需要好多次地把被修改的行写回存储器，以此来保持数据的完整性（在后面的章节中解释）。写回高速缓存机制实现起来也要比写直通高速缓存机制的成本更高。一般而言，写回机制的优点大于缺点，因此这项技术得以广泛使用。例如，Intel 486、Pentium的片上高速缓存和i860 XR、MIPS R4000、Motorola 88200和68040以及TI MicroSPARC和SuperSPARC（如果没有使用外部高速缓存的话）都使用写回高速缓存机制。
前面的讨论只考虑了保存来自CPU的数据期间在高速缓存里命中时情况。如果相反没有命中，那么采取的措施则取决于高速缓存是否支持写分配（write-allocate）。在使用写分配机制的时候，CPU保存的数据在发生高速缓存缺失的情况下始终会被写入高速缓存（也就是说，为数据分配高速缓存行），以便利用时间局部性和空间局部性的优点。要做到这一点，要执行与读缺失期间相同类型的处理。首先，替换策略选择一行要丢弃的数据，给保存新数据腾出空间。如果使用写回高速缓存机制，而且所选的要被替代的高速缓存行又被修改过，那么就必须把这一行写入到主存储器中。接着，从主存储器中读取与造成缺失的所有地址相关联的全部高速缓存行。之所以必须读取全部高速缓存行（或者子行），是因为正如2.2.1节所阐述的那样，只有一个有效位涵盖高速缓存行或者子行的状态。一旦读取了一行，那么CPU写入的数据就被插入到这一行中，并且设置这一行的高速缓存标记，以便反映出新数据的地址。如果使用了写回高速缓存机制，那么还要设置这一行的修改位。如果CPU写入数据的大小等于高速缓存行的大小（例如，把一个字保存在每行一个字的高速缓存中），那么就会跳过主存储器的读取操作，因为该行肯定要被CPU的数据所替换。MIPS R2000/R3000就是这种情况，它使用了4字节长的高速缓存行。使用写分配的其他处理器有MIPS R4000、Motorola 68040和88200、TI SuperSPARC以及Intel 80486（82495DX）的外部高速缓存。
有些高速缓存为了在硬件实现上更简单而放弃了写分配策略的局部好处。在不支持写分配策略的高速缓存中出现保存缺失的时候，数据被独自写入主存储器，而保持高速缓存的内容不变。Intel 80486和TI MicroSPARC就使用了这种技术。
在大多数情况下，写回高速缓存都使用写分配策略，但是写直通高速缓存则不然。这是由于硬件的成本问题：写分配会增加低成本的写直通方法的成本，因为在一次保存缺失期间必须读取一行再把这一行写入主存储器。写回高速缓存机制能够很好地配合写分配工作；另一方面，如果被写入的行尚未被CPU读取，那么就不会被高速缓存起来，从而导致所有这样的存储都被送往主存储器。但是，这也有例外。例如，Intel Pentium的外部高速缓存控制器（82434LX）能够配置成使用不带写分配的写回策略，MIPS R2000/R3000使用带有写分配的写直通策略。在MIPS芯片的案例中，硬件执行写分配很容易，因为每一个高速缓存行的大小只有4字节，从而不需要在发生保存缺失的情况下从存储器中读取一行。
其他的变化也是有可能的。例如，Motorola 88200上的高速缓存就使用了写回高速缓存机制，但是只要在高速缓存内发生了保存缺失时，就会更新存储器。这称为写一次（write-once），它允许高速缓存行即使刚发生对它的保存也能保持未修改状态，因为主存储器会被更新。幸运的是，对于操作系统来说，诸如这样的变化都是透明的。