第五章 - 层次化存储
约 13905 个字 预计阅读时间 46 分钟
引言
在实际执行计算机程序时，都遵循局部性原理 (principle of locality)。局部性原理表明，在任意一段时间内程序都指挥访问地址空间中相对较小的一部分内容。局部性有两种：
- 时间局部性 (temporal locality)：如果某个数据项被访问，那么在不久的将来它可能再次被访问。
- 空间局部性 (spatial locality)：如果某个数据项被访问，与它地址相邻的数据项可能很快也将被访问。
我们可以利用局部性原理来构建计算机的存储系统，称作存储层次结构 (memory hierarchy)。存储层次结构包括不同速度和容量的多级存储。存储速度越快，价格越昂贵，但容量越小。
上图是典型的层次化存储的基本结构。可见，速度越快的存储越靠近处理器；月满的存储成本越低，离处理器越远。这样做既能一相对低的价格提供大容量的存储，同时访问速度和最快的存储相当。
同样，数据也有相似的层次性：靠近处理器的那一层中的数据是那些较远层次中数据的子集，而所有的数据都被存在最远的那一层。
层次化存储可以有不同的层次组成，但是数据只能在两个相邻层次之间进行复制。我们每次只关注相邻的两个层次，在相邻两层之间进行信息交换的最小单元称作块 (block) 或行 (line)，如下图：
如果处理器所叙的数据在本层的存储中找到，称作命中 (hit)。如果没在本层存储中找到所需数据，称作失效 (miss)，将访问下一级存储。命中率 (hit rate) 指的是在访问本层存储时命中的次数占总次数的比例，通常作为存储层次结构的性能衡量指标之一。失效率 (miss rate) 指的是在访问本层存储时失效的次数占总次数的比例。
由于性能是引入层次化存储的主要原因，数据命中和失效的处理时间是非常重要的。命中时间 (hit time) 是访问本层存储的时间，包括判断访问命中或失效的时间。失效损失 (miss penalty) 指的是将相应的块从下层存储替换到上层存储中的时间，加上将数据块返回给处理器的时间。由于上层存储容量更小，并由速度更快的存储组成，命中时间也比下层存储的访问时间短，而访问下层存储的时间是失效损失的重要组成部分。
存储技术
在当今的层次化存储中有四种主要技术。主存采用动态随机访问存储 (Dynamic Random Access Memory, DRAM) 器件实现，靠近处理器的存储层次使用静态随机访问存储 (Static Random Access Memory, SRAM) 器件实现。DRAM 的访问速度慢于 SRAM，但它的没每比特成本也要低很多。两者的价格差主要源于 DRAM 的每比特占用面积远远小于 SRAM，因而 DRAM 能在等量的硅上实现更大的存储容量。第三种技术称作闪存 (flash memory)，这种非易失性存储一般作为个人移动设备的二级存储。第四种技术是磁盘 (magnatic disk)，用来实现服务器上最大也是最慢的存储层次。
SRAM 存储技术
SRAM 存储是一种存储阵列结构的简单集成电路，通常有一个读写端口。虽然读写操作的访问时间不同，但对于任意位置的数据，SRAM 的访问时间是固定的。SRAM 不需要刷新电路，所以访问时间可以和处理器的时钟周期接近。
过去，大多数个人电脑和服务器使用独立的 SRAM 芯片作为一级、二级甚至三级高速缓存 (cache)。如今由于摩尔定律，所有的高速缓存都被集成到处理器芯片上，因此独立的 SRAM 芯片不再流行。
DRAM 存储技术
在 SRAM 中，只要提供电源，数值会被一直保存。而在 DRAM 中，使用电容保存电荷的方式来存储数据。采用单个晶体管来访问存储的电荷，或读，或写。DRAM 的每个比特仅使用单个晶体管来存储数据，它比 SRAM 的密度更高，每比特价格更低廉。由于 DRAM 在单个晶体管上存储电荷，因此不能长久保持数据，必须进行周期性的刷新。与 SRAM 相比，这也是该结构被称作动态的原因。
DRAM 的内部结构如下图：
由图可见，其采用重合译码的方式，即先给出行地址，再给出列地址进行访问。这种行 (row) 结构有助于 DRAM 的刷新，也有助于改善性能。为提高性能，DRAM 中缓存了行数据以便重复访问。
为更好地优化与处理器的接口，DRAM 添加了时钟，因此被称作同步 DRAM (Synchronous DRAM, SDRAM)。SDRAM 的好处在于，使用始终消除了内存和处理器之间的同步问题。同步 DRAM 的速度优势来自于，进行突发传输 (burst transfer) 时无须指定额外地址位，而是通过时钟来突发传输后续数据。速度最快的结构称作双倍数据传输率 (Double Data Rate, DDR) SDRAM，这种结构在时钟的上升沿和下降沿都可以进行数据传输。因此，如果仅考虑时钟频率和数据尾款，使用该结构可以预期获得双倍的数据带宽。
要维持这样的高带宽，需要对 DRAM 的内部结构进行精心组织。现代 DRAM 以 bank 的方式来组织结构，即将 DRAM 划分为若干个 bank。DRAM 可以在内部组织对多个 bank 进行读或写，每个 bank 对应各自的行缓冲，而不仅仅是添加一个快速行缓冲。对多个 bank 发送一个地址允许同时对这些 bank 进行读或写，只需要一次访问时间，之后一轮转到方式对多个 bank 进行访问，就获得了若干倍的带宽。这种轮转的访问方式称作交叉地址访问 (address interleaving)。
服务器的存储通常都是集成在小电路板上售卖，这种结构被称作双列直插式内存模块 (Dual Inline Memory Modules, DIMM)。
闪存
闪存是一种电可擦除的可编程只读存储器 (Electrically Erasable Programmable Read-only Memory, EEPROM)。
与磁盘和 DRAM 不同，对于闪存这类 EEPROM 技术，闪存的写操作会对期间本身产生磨损。为应对这种限制，大多数闪存产品都包括一个控制器，用来将发生多次写的块重新映射到较少被写的块，从而使得写操作尽量分散。该技术被称作耗损均衡 (wear leveling)。具有孙浩俊亨的闪存控制器也能够通过重新映射，将生产制造中出现故障的存储单元屏蔽掉，从而改善产品的良率 (yield)。
磁盘
磁性硬盘由若干盘片组成，每个磁盘表面被分为若干的同心圆，称作磁道 (track)，每个盘面上通常有几万条磁道。每条磁道按序划分为上千个保存信息的扇区 (sector)，每个扇区的容量一般为 \(512 \sim 4096\) 字节。记录在磁介质上的内容依次为：扇区号、间隙、该扇区的信息（包括纠错码）、下一个扇区的扇区号等。
每个盘面都配有一个磁头，这些磁头互相连接并一起移动，每个磁头都可以读写每个盘面的每一条磁道。某磁头在给定点能够访问到的所有磁道集合称作柱面 (cylinder)。
操作系统通过三步完成对磁盘的数据访问。
第一步，将磁头定位在正确的磁道上方，这个操作称作寻道 (seek)，将磁头移动到所需刺刀上方是时间称作寻道时间 (seek time)。
第二步，当磁头到达正确的磁道后，我们需要等待所需扇区旋转到读写磁头下，这段时间称作旋转延时 (rotational latency)。平均旋转延时为磁盘旋转半周的时间，即
第三步，在磁头到达正确的扇区后，数据块 (block) 仍然需要一定的传输时间 (transfer time)。传输时间和扇区大小、旋转速度和磁道记录密度有关。
与闪存相同，磁盘也是非易失性存储，但是相较闪存没有写损耗问题。
cache 基础
我们从一个简单的高速缓存 (cache) 开始。我们假设处理器每次请求为一个字，且每个数据块由单个字组成。下图给出了这种简单 cache 在响应初始不在 cache 中的数据访问请求前后的情况：
具体来说，在响应请求前，该 cache 中包含了最近访问的数据集合 \(X_{1}, X_{2}, \cdots, X_{n - 1}\)，处理器请求的字 \(X_{n}\) 并不在 cache 中。这个请求会产生一次失效，字 \(X_{n}\) 从内存取到 cache 中。
在这个场景中，我们需要思考这样一个问题，即如何知道数据项是否存在于 cache 中？进一步来说，如果知道数据项存在于 cache 中，我们又该如何找到这个数据项？这两个答案是有关联的。如果每个字能够位于 cache 中的确定位置，只要它在 cache 中，那么找到它就是简单的。
在 cache 中为每个存储中的数据子进行位置分配的最简单方式，就是基于它在存储中的地址来分配 cache 中的位置，这种 cache 结构称作直接映射 (direct mapped)。直接映射 cache 中，存储地址和 cache 位置之间的典型映射关系通常非常简单，例如下述映射关系：
如果 cache 的块数是 \(2\) 的幂，则取模运算很简单，只需要取地址的低 \(N\) 位即可，其中 \(N = \log_{2} (\text{cache 的块数})\)。一个 8 个字的直接映射 cache 如下：
由于每个 cache 块中能够保存不同存储地址的内容，如何知道对应请求的数据字是够在 cache 中呢？这需要我们在 cache 中添加一组标签 (tag)，这些标签保存了所需的地址信息，这些信息用来确定请求字是否在 cache 中。标签中只需要保存地址的高位部分，这部分地址不会用来作为 cache 的索引。例如在上图中，只需要使用 5 位地址中的高 2 位作为标签，低 3 位作为地址的索引字段来选择数据块。
同时，还需要一种方法能够判断 cache 中的数据块中是否保存有效信息。最常用的方法就是添加有效位 (valid bit)，用来表示该表项中是否保存有效的数据。一般置 \(0\) 表示对应数据块不能使用，置 \(1\) 表示可以使用。
cache 访问
我们对 cache 访问的讨论从下面这个示例开始，这是对一个大小为 8 个数据块的空 cache 进行 9 次存储访问的操作序列：
我们看一看第一次访问前后 cache 的变化：
在整个过程中，许多 cache 中的内容也会发生覆写，完整的操作序列执行结束后，cache 应该如下：
接下来我们讨论 cache 的容量。我们设定如下条件：
- \(64\) 位地址
- 直接映射 cache
- cache 中有 \(2^{n}\) 个数据块，因此索引字段为 \(n\) 位
- 单个数据块大小为 \(2^{m}\) 个单字，即 \(2^{m + 2}\) 字节，因此在单个数据块中使用 \(m\) 位来索引单字，再使用地址的最低 \(2\) 位来索引字节
于是，标签字段的大小为：
该 cache 的总容量为：
由于单个数据块的大小为 \(2^{m}\) 个单字，每个单字有 \(2^{5} = 32\) 位，并使用 \(1\) 位来表示有效位，因此以上 cache 的容量大小为：
假设 \(64\) 位的存储地址，对于直接映射 cache，如果数据大小为 \(16 \mathrm{KiB}\)，每个数据块为 \(4\) 字大小，求该 cache 的容量。
数据大小 \(16 \mathrm{KiB}\) 为 \(2^{12}\) 个字。单个数据块大小为 \(2^{2}\) 字，则共有 \(2^{10}\) 个数据块。代入公式有
\[2^{10} \times (2^{2} \times 32 + (64 - 10 - 2 - 2) + 1) = 2^{10} \times 179 = 179 \mathrm{Kib}\]
除了会计算 cache 的容量，我们还需要会计算地址的映射。我们看如下例题：
假设 cache 有 \(64\) 个数据块，每个数据块的大小为 \(16\) 字节。对于字节地址 \(1200\)，会映射到哪个基本块？
\[\text{块地址} = \left\lfloor \frac{\text{字节地址}}{\text{每块中的字节数}} \right\rfloor\]题目中即为 \(\frac{1200}{16} = 75\)。再根据公式
\[\text{cache 块号} = (\text{块地址}) \mod (\text{cache 中的数据块数量})\]题目中即为 \(75 \mod 64 = 11\)。事实上，从 \(1200\) 到 \(1215\) 的字节地址都映射到这个块号。
容量更大的块可以通过挖掘空间局部性来降低失效率，因此随着块大小的增长，失效率通常都在下降。但如果单个快大小占 cache 容量的比例增加到一定程度，失效率最终会随之上升，这是因为 cache 中可存放的块数变少了。这一关系如下图：
增大快容量时，另一个更严重的问题是失效损失。失效损失是从下一级存储获得数据块并加载到 cache 的时间，分为两部分：访问命中的时间和数据的传输时间。容易知道，数据的传输之间将随着数据块容量的增大而增大，而且这会消解数据块容量增大待来的失效率改善的手艺。最终的结果是，失效损失增大引起的性能下降超过了失效率降低带来的手艺，cache 的性能也随之下降。当然，如果能设计出高效的传输大数据快的存储，就可以增大数据块的容量，并得到更大的性能改善。
处理 cache 失效
在考虑真是系统的 cache 之前，我们先来讨论一下控制单元如何处理 cache 失效。控制单元必须能够检测到失效，然后通过从下一级存储中取得所需的数据来处理失效。
cache 的失效处理需要两部分协同工作：一部分是处理器的控制单元；另一部分是单独的控制器，用来初始化内存访问和重填 cache。cache 的失效处理会引发流水线的停顿，这与例外或者中断处理不同，后者需要保存所有寄存器的状态，而 cache 失效将会停顿整个处理器流水线来等待下一级内存返回数据。
我们先回顾如何处理指令失效。如果一条指令访问引发了失效，那么指令寄存器的内容将被置为无效。我们可以用相同的方法处理数据失效。为了将正确的指令写入 cache 中，必须能够对下一级存储发出读操作。由于程序计数器 (PC) 是在执行的第一个时钟周期递增，引发指令 cache 失效的指令地址就等于程序计数器的数值减 \(4\)。一旦确定了地址，就需要知道主存进行读操作。等待内存响应，然后将含有所需指令的字写入指令 cache 中。
一旦发生指令 cache 失效，可以定义如下处理步骤：
- 将 PC 的原始值（当前 PC 减 \(4\)）发送到内存；
- 对主存进行读操作，等待贮存完成本次访问；
- 写 cache 表项，将从内存获得的数据写入到该表项的数据部分，将地址的高位（来自 ALU）写入标签字段，并将有效位置为有效；
- 重启指令执行，这将会重新取指，本次取指将在指令 cache 中命中。
以上叙述的是指令 cache 失效的情况。数据访问的 cache 控制本质上是相同的，一旦失效，简单地暂停处理器，直到内存返回数据。
处理写操作
写操作有一些不同。例如对于存储指令，只把数据写入数据 cache 而不改变主存。完成写入操作后，主存中的数据将和 cache 中的数据不同。这种情况称作 cache 和主存不一致 (inconsistent)。保持 cache 和主存一致的最简单方法是，总是将数据写回内存和 cache。这样的写策略称作写穿透或写直达 (write-through)。
写操作的另一个关键点是写失效的处理。我们先从主存中取来对应数据块中的数据，之后将其写入 cache 中，覆盖引发失效的数据块中的数据。同时，也会使用完整地址将数据写回主存。
虽然上述设计方案能够简单地处理写操作，但是其性能不佳。在写穿透策略中，每次写操作都会引起写主存操作，这种写操作的延时很长。
解决这个问题的方法之一是使用写缓冲 (write buffer)。写缓冲中保存着等待写回主存的数据。数据写入 cache 的同时也写入写缓冲中，之后处理器继续执行。当写入主存的操作完成后，写缓冲中的表项将被释放。如果写缓冲满了，处理器必须停顿流水线直到写缓冲中出现空闲表项。
然而即使采用写缓冲策略，当写操作成簇 (burst) 发生时，也会发生停顿。为减少这样的停顿发生，处理器通常会增多写缓冲的表项数。
相对于写穿透或者写直达策略，另一种写策略称作写返回 (write-back)。基于写返回策略，当发生写操作时，新值只被写入 cache 中，被改写的数据块在替换出 cache 时才被写到下一级存储，写返回策略能够改善性能，但是其具体实现相对复杂。
cache 的性能评估和改进
在本节中，我们先讨论评估和分析 cache 性能的方法，然后再介绍两种不同的改善 cache 性能的技术。第一项技术主要关注通过减少两个不同的内存块争夺同一缓存位置的发生概率来降低失效率。第二项技术是通过添加额外的一个存储层次来减少失效代价，即多级缓存 (multievel catching) 技术。
评估和分析 cache 性能
CPU 时间可被分成 CPU 用于执行程序的时间和 CPU 用来等待访存的时间。通常我们假设 cache 命中的访问时间只是正常 CPU 执行时间的一部分。因此
假设等待存储访问的时钟周期数主要来自于 cache 失效。具体来说，等待存储访问的时钟周期数可以被定义为，读操作带来的停顿周期数加上写操作带来的停顿周期数，即
读操作带来的停顿周期数可以有每个程序的读操作次数、读操作失效率和读操作的失效代价来定义，即
写操作则复杂一些。对于写穿透策略，有两个停顿的来源：一个是写失效。通常在连续写之前需要将数据块取回；另一个是写缓冲停顿，通常在写缓冲满时进行写操作会引发该停顿。因此，写操作带来的停顿周期数等于下面两部分的总和：
由于写缓冲停顿主要依赖于写操作的密集度，而不只是它的频度，故难以给出一个简单的计算此类停顿的公式。但一般地，如果系统中有一个容量合理的写缓冲，同时主存接受写请求的速度能够大于程序的平均写速度，写缓冲引起的停顿将会很少而几乎可以忽略。
写返回策略也会额外增加停顿，主要来源于当数据块被替换并需要将其写回到主存时。
在大多数写穿透 cache 的结构中，读和写的失效代价是相同的，都是讲数据块从内存取至 cache 所花的时间。假设写缓冲停顿是可以忽略不计的，就可以使用失效率和失效代价来同时刻画读操作和写操作：
该公式也可以记作
除了失效率外，命中时间也是影响 cache 性能的重要因素。为了表明不论命中还是失效访问数据存储的时间都会影响性能，设计者采用平均存储访问时间 (Average Memory Access Time, AMAT) 作为指标来衡量不同的 cache 设计，定义如下：
使用更为灵活的替换策略
到目前为止，我们在将数据块写入 cache 时，采用的是一种最简单的定位策略，即一个数据块在 cache 中只有一个对应位置。正如之前提到的，这种策略称作直接映射，因为它将主存中的任意数据块地址直接映射到上层存储的一个准确位置。但是，定位策略显然不止直接映射一种。接下来我们将讨论不同的定位策略，以降低 cache 失效率。
第一种策略称作全相联 (fully associative)，即主存中的某个数据块和 cache 中的任意表项都可能有关联，数据块可以存放在 cache 的任意位置。在全相联 cache 中查找给定的数据块，所有的表项都必须进行比对，因为数据块可以存放在任意位置。为此，每个 cache 表项都需要一个比较器进行并行比较，这显然增加了硬件开销，使得全相联策略只能用于那些小容量的 cache。
介于直接映射和全相联之间的组织结构称作组相联 (set associative)。在一个组相联 cache 中，没一个数据块可以存放的位置数量是固定的。每个数据块有 \(n\) 个位置可放的组相联 cache 称作 \(n\) 路组相联 cache。在一个 \(n\) 路组相联 cache 中，包含有若干组 (set)，每一组包含有 \(n\) 个数据块。主存中的每个数据块通过索引位映射到 cache 中对应的组，数据块可以存放在该组中的任意位置。因此，组相联 cache 将直接映射和全相联结合起来：某个数据块直接映射到某一组，之后组中所有数据块都需要与之进行命中比对。
下图就展示了三种组织结构的区别：
在直接映射 cache 中，贮存数据块的位置为
在组相联 cache 中，包含主存块的组号为
由于数据块可以放置在该组内的任意位置，组内所有元素的所有标签都必须被检查。在全相联 cache 中，数据块可以放置在任意位置，cache 中所有数据块的所有标签都要被检查。
提高相连度的好处是通常可以降低失效率，正如下面的例子所示。主要的问题在于可能会增加命中时间。
在 cache 中查找数据块
接下来我们考虑如何在组相联 cache 中找到所需的数据块。正如在直接映射 cache 中，组相联 cache 中的没一个数据块都包括一个确定其地址的标签。在同一组内的每个 cache 块的标签都需要比较，判断是否与处理器访问的数据块地址匹配。下图给出了组相联 cache 中地址的三个组成部分：
其中，索引位用来选择访问数据所在的组，标签为用来在所在组内比较并选出数据块，block offset 用来在数据块内找到所需的数据。考虑到数据访问的速度，被选中组内的所有数据块的标签是并行比较的。
如果 cache 容量保持不变，增加相联度可以增加每组内数据块的数量，这也增加了需要并行比较的数据块数量。因此，任何一个存储层次，在直接映射、组相联和全相联映射结构之间进行选择，都需要在失效代价与相联度之间进行权衡。
选择替换的数据块
当组相联 cache 中出现失效，所需的数据块将替换组中的某一个数据块，这需要我们对替换哪一个数据块做出选择。
最常用的策略是最近最少使用 (Least Recently Used, LRU)，即替换最长时间未被使用的数据块。LRU 替换策略可以通过跟踪某个数据块相对于同组内其它数据块的使用时间来实现。例如对于两路组相联 cache 来说，只需要用 1 位记录最近访问的是哪一块。但是当相连度增大时，LRU 的实现将变得困难。
使用多级 cache 减少失效代价
我们也可以使用多级 cache 来减少失效代价。以二级 cache 为例，当一级 cache 失效后，先访问二级 cache。如果二级 cache 中命中，一级 cache 的失效代价就是二级 cache 的访问时间，这相较主存的访问时间就少得多。如果二级 cache 也失效，此时才需要访问主存，这也意味着此时的失效代价增大了。
此时我们会考察二级 cache 的局部失效率 (local miss rate)，即所有在二级 cache 上失效的访问数在二级 cache 的所有访问数上的占比。由于一级 cache 对存储访问进行了过滤，因此二级 cache 的局部失效率会比全局失效率要高。
对于一级和二级 cache，设计考虑是明显不同的。一级 cache 应当更关注命中时间的最小化以提高工作频率或关注流水级数的减少，二级 cache 则应当更关注失效率来降低长访存延迟带来的失效代价。可见，相比于单独一个 cache 来说，其他 cache 层次的存在会改变其最佳策略的选择。
更进一步地，多级 cache (multievel cache) 中，高级 cache 往往使用较小的数据块容量，以配合较小的 cache 容量，从而降低失效代价。相对地，低级 cache 更关注降低失效率，而访问时间就没那么关键，故会采用更大的容量和更高的相联度。
通过分块进行软件优化
由于存储层次对程序性能具有非常重要的影响，许多软件优化技术通过重用 cache 中的数据来提高处理器性能，荣国改善程序的时间局部性来降低失效率。
处理数组时，如果能将数组元素按照访问顺序存放在存储器中，则能够获得性能上的好处。但是，假设同时处理多个数组，一些数组按行访问，一些数组按列访问，此时无论是采用按行存储（行优先）还是按列存储（列优先）的策略存储数组都不能解决问题。
因此，分块 (blocked) 算法针对子矩阵 (submatrice) 或者数据块来进行操作，而不针对数组中完整的一行或一列机型操作。其目标为，在替换之前对已在 cache 中的数据进行尽可能多的访问，即提高程序的时间局部性以减少 cache 失效。
分块思想也可以用于协助寄存器分配。通过采用规模较小的数据块，可以把数据块保存在寄存器中，这样可以降低程序访问存储的次数，提高程序的性能。
虚拟存储
基本概念
通过前面的讨论，我们知道了 cache 如何对程序中最近访问的代码和数据提供快速访问。同样，主存可以为通常由磁盘实现的辅助存储充当 cache，这种技术称作虚拟存储 (virtual memory)。虚拟存储的动机主要有二：
- 允许在多个程序之间高效安全地共享内存
- 消除小而受限的主存容量对程序设计造成的影响
为了允许多个虚拟机共享内存，必须保护虚拟机免受其它虚拟机影响，确保程序只读写分配给它的那部分主存。主存只需存储众多虚拟机中活跃的部分，就像 cache 只存放一个程序的活跃部分一样。因此，局部性原理支持虚拟存储和 cache，虚拟存储允许我们高效地共享处理器一级主存。
在编译虚拟机时，无法知道哪些虚拟机将与其它虚拟机共享存储。事实上，共享存储的虚拟机在运行时会动态变化。由于这种动态的交互作用，我们希望将每个程序都编译到它自己的地址空间中，即只有这个程序能访问的一系列存储位置。虚拟存储实现了将程序地址空间转换为物理地址 (physical address)，这种地址转换处理加强了各个程序地址空间之间的保护 (protection)。
此外，虚拟内存允许单用户程序使用超出内存容量的内存，这使得程序员不必面对诸如需要将程序分段执行的困境。虚拟内存自动管理由主存和辅助存储所代表的两级存储层次结构。
虽然虚拟存储和 cache 的工作原理相同，但术语上有一定区别。虚拟存储块称作页 (page)，虚拟存储失效称作缺页失效 (page fault)。在虚拟存储中，处理器产生一个虚拟地址 (virtual address)，该地址通过软硬件转换为一个物理地址，物理地址再直接访问主存。
下图显示了分页的虚拟存储被映射到主存中的过程：
这个过程称作地址映射 (address mapping) 或地址转换 (address translation)。
虚拟内存还通过重定位 (relocation) 简化了执行时程序的载入。在用地址访问存储之前，重定位将程序使用的虚拟地址映射到不同的物理地址。重定位允许将程序载入主存中的任何位置。此外，现今所有的虚拟存储系统都将程序重定位成一组固定大小的块（页），从而不需要寻找连续内存块来放置程序；相反，操作系统只需要在主存中找到足够数量的页。
在虚拟存储中，地址被划分为虚拟页号 (virtual page number) 和页内偏移 (page offset)。下图显示了虚拟页号到物理页号 (physical page number) 的转换：
物理页号构成物理地址的高位部分；页内偏移不变，其构成物理地址的低位部分；页内偏移的位数决定页的大小。虚拟地址可寻址的页数与物理地址可寻址的页数可以不同，拥有比物理页更多数量的虚拟页是一个没有容量限制的虚拟存储的基础。
缺页失效的高成本是许多设计选择虚拟存储系统的原因。这种巨大的失效代价导致了设计虚拟存储系统时的几个关键决策：
- 页应该足够大以分摊长访问时间。
- 能降低缺页失效率的组织结构很有吸引力，如允许存储中的页以全相联方式放置。
- 缺页失效可以由软件处理，因为与磁盘访问时间相比，这样的开销将很小。
- 写穿透策略对于虚拟存储不合适，因为写入时间过长。故虚拟存储系统采用写返回策略。
页的存放和查找
由于缺页失效的代价非常高，设计人员通过优化页的放置来降低缺页失效频率。因此，我们一般选择全相联方式，并使用先进而灵活的替换策略来降低缺页失效率，并简化全相联方式下页的放置。
全相联映射的困难在于项的定位，全部进行检索是不切实际的。在虚拟存储系统中，我们使用一个索引主存的表来定位页，这个结构称作页表 (page table)，被存放在主存中。页表使用虚拟地址中的页号作为索引，找到相应的物理页号。每个程序都有自己的页表，它将程序的虚拟地址空间映射到主存。为了表明页表在内存中的未知，硬件包含一个指向页表首地址的寄存器，称作页表寄存器 (page table register)。
下图说明了如何使用页表寄存器、虚拟地址和被指向的页表来说明硬件如何形成物理地址：
可见，正如在 cache 中所做的那样，每个页表项中使用 1 位有效位。如果该位为无效，则该页就不在主存中，发生一次缺页失效。如果该位为有效，则该页在内存中，并且该项包含物理页号。
由于页表包含了每个可能的虚拟也的映射，因此不需要标签。在 cache 术语中，索引是用来访问页表的，这里由整个块地址，即虚拟页号组成。
缺页失效
如果虚拟页的有效位为无效，则会发生缺页失效，控制权通过例外机制移交给操作系统。一旦操作系统的到控制，它必须在存储层次结构的下一级中找到该页，并确定将请求的页放在主存中的什么未知。
虚拟地址本身并不会立即告诉我们该页在辅助存储中的位置，因此，在虚拟存储系统中，我们必须跟踪记录虚拟地址空间的每一页在辅助存储中的位置。
由于我们无法提前获知存储器中的某一页什么时候将被替换出去，因此操作系统通常会在创建进程时为所有页面在闪存或磁盘上创建空间。这个空间称作交换区 (swap space)。同时，操作系统也会用出具结构来记录每个虚拟页在磁盘上的存储位置。下图就展示了一个保存了物理页号或辅助存储器地址的单个表的结构：
操作系统还会用数据结构跟踪记录使用每个物理地址的是哪些进程和哪些虚拟地址。发生缺页失效时，如果内存中的所有页都正在使用，则操作系统必须选择一页进行替换。被替换的页将被写到辅助存储器中的交换区。
支持大虚拟地址空间的虚拟存储
直接存储页表所需的空间往往是庞大而不可接受的，因此我们提出了一系列技术以减少页表所需的存储空间。具体如下：
- 最简单的级数是保留界限寄存器，限制给定进程的页表大小。如果虚拟页号大于界限寄存器的值，那么表项将被添加到页表中。这种技术允许页表随着进程消耗空间的增多而增长。因此，只有当进程使用了许多虚拟页时，页表才会变得很大。这种技术要求地址空间只向一个方向扩展。
- 大多数语言都需要两个大小可扩展的区域：一个区域容纳栈，另一个区域容纳堆。因此我们划分页表使其既可以从最高地址向下增长，也可以从最低地址向上增长。这意味着需要两个单独的页表和两个单独的界限寄存器。这种方案的主要缺点是：当地址空间以稀疏方式而不是连续方式被访问时，其不能很好地工作。
- 另一种减小页表容量的方法是对虚拟地址应用哈希函数，以使页表容量等于主存中物理页的数量。这种结构称作反向页表 (inverted page table)。
- 为减少页表占用的实际主存，大多数现代系统还允许将页表再分页。
-
多级页表也可以用来减少页表存储的总量。下图是 RISC-V 为减少地址转换占用的内存所采用的解决方案。
关于写
访问 cache 和主存的时间相差几十到几百个时钟周期，如果采用写穿透策略，则需要一个写缓冲区向处理器隐藏写操作的延迟。在虚拟存储系统中，写入存储层次结构的下一级可能需要数百万个处理器时钟周期；因此如果创建一个写缓冲区，允许系统采用写穿透的方式以对磁盘进行写的方法是完全不可行的。相对应地，虚拟存储系统必须使用写返回策略，对内存中的页进行单独的写操作，并当页被从主存中替换出时，将其复制到辅助存储。
加快地址转换
由于页表存储在主存中，因此程序每个访存请求至少需要两次访存：第一次访存获得物理地址，第二次访存获得数据。提高访问性能的关键在于页表的访问局部性。
因此，现代处理器包含一个特殊的 cache 以追踪记录最近使用过的地址转换。这个特殊的地址转换 cache 通常被称作快表 (translation-lookaside buffer, TLB)，或地址转换 cache。其结构如下图：
由图可知，TLB 中的每个标签项保存虚拟页号的一部分，每个数据项保存一个物理页号。因为每次引用都访问 TLB 而不是页表，所以 TLB 需要包括其它状态位，例如脏位和引用位。TLB 也适用于多级页表，只需从最后一级页表中载入物理地址和保护标签即可。
每次引用时，在 TLB 中查找虚拟页号。如果命中，则使用物理页号来形成地址，相应的引用位被置位。如果处理器要执行写操作，那么脏位也会被置位。如果 TLB 发生失效，我们必须确定是缺页失效还是只是 TLB 失效。如果该页在内存中，TLB 失效表明缺少该地址转换，在这种情况下，处理器可以将最后一级页表中的地址转换加载到 TLB 中，并重新访问来处理失效。如果该页不在内存中，那么 TLB 失效意味着真正的缺页失效，此时处理器调用操作系统的例外处理。
TLB 失效可以通过硬件或软件处理。两种方法几乎没有性能差异。在修改 TLB 表项时，我们通常使用写返回策略。这是因为我们期望 TLB 的失效率很低。
TLB 中相联度的设置非常多样。一些系统使用小的全相联 TLB，因为全相联映射的失效率较低；同时由于 TLB 很小，全相联映射的成本也不是太高。此时用硬件实现 LRU 方案的成本太高，且 TLB 失效比缺页失效更频繁，因此一般采用开销较低的随机选择替换表项。
其它一些系统使用容量大的 TLB，此时其相联度就较小。
集成虚拟存储、TLB 和 cache
虚拟存储和 cache 系统就像一个层次结构一样共同工作，除非数据在主存中，否则其不可能在 cache 中出现。操作系统帮助管理该层次结构，当它决定将某一页移到磁盘上去时，就在 cache 中将该页的内容刷新。同时操作系统修改页表和 TLB，而后尝试访问该页上的数据都将发生缺页。
在最好的情况下，虚拟地址由 TLB 进行转换，然后被送到 cache，找到相应的数据，取回并发给处理器。在最坏的情况下，访问在存储层次结构的三个部件中都发生失效：TLB、页表和 cache。下表汇总了 TLB、虚拟存储系统和 cache 中时间的可能组合。
虚拟存储中的保护
虚拟存储最重要的功能就是允许多个进程共享一个主存，同时为这些进程和操作系统提供内存保护。保护机制必须确保：尽管多个进程共享相同的主存，但无论有意或无意，一个恶意进程不能写另一个用户进程或操作系统的地址空间。TLB 中的写访问位可以防止一个页被写入。
处理 TLB 失效和缺页失效
当 TLB 中没有表项能与虚拟地址匹配时，将发生 TLB 失效。此时有两种可能：
- 页在内存中，只需创建缺少的 TLB 表项。
- 页不在内存中，需要将控制转移给操作系统来处理缺页失效。
处理 TLB 失效或缺页失效需要使用例外机制来中断活跃进程，将控制转移到操作系统，然后再恢复执行被中断的进程。缺页将在主存访问时钟周期的某一时刻被发现，为了在缺页失效处理结束后重启指令，必须保存导致缺页失效的指令的程序计数器。此时管理态例外程序计数器 (supervisor exception program counter, SPEC) 用于保存该值。
此外，TLB 失效或缺页失效例外必须在访存发生的同一个时钟周期的末尾被判定，这样下一个时钟周期将开始进行例外处理而不是继续正常的指令执行。
一旦操作系统知道引起缺页失效的虚拟地址，其必须完成以下三个步骤：
- 使用虚拟地址找到对应的页表表项，并在辅助存储中找到引用页的位置。
- 选择要替换的物理页：如果所选页是脏的，则必须先将其写入辅助内存，然后才能将新的虚拟页写到此物理页中。
- 启动读操作，将被访问的页从磁盘上去回到所选择的物理页的位置上。
当然，最后一步通常将花费数百万个处理器时钟周期。因此操作系统通常会选择另一个进程在处理器中执行直到磁盘访问结束。由于操作系统已经保存了当前进程的状态，所以它可以方便地将处理器的控制权交给另一个进程。
当从辅助存储器读页完成后，操作系统可以恢复最初导致缺页失效的进程的状态并执行从例外返回的指令。该指令将处理器从内核态重置为用户态，同时也恢复程序计数器的值。然后用户进程重新执行引发缺页失效的指令，成功访问锁清秋的页面并继续执行。
数据访问引起的缺页失效例外很难处理，是由于以下三个特征：
- 它们发生在指令的中间，与指令缺页失效不同。
- 在例外处理结束之前无法完成指令。
- 例外处理结束后，指令必须重新启动，并且必须恢复例外发生前的状态，而没有额外的影响。
因此，使指令可重新启动 (restartable)，这样例外被处理之后，指令也能继续执行。这在类似 RISC-V 的体系结构中相对容易实现。因为每条指令只写一个数据项，并且这个写操作发生在指令周期的末尾，所以我们可以简单地阻止指令完成（不执行写操作）并在开始处重新启动指令。
存储层次结构的一般框架
接下来，我们将讨论关于存储层次结构如何动作的一些选项，以及它们如何决定其行为。我们通过适用于存储层次结构两层之间的四个问题来研究这些策略。
块可以被放在何处
在较高存储层次结构中，块的放置可以使用一系列方案，从直接映射到组相联，再到全相联。每种方案中组的数量和每组中快得数量不同，如下表：
增加相联度的好处时通常会降低失效率，这来自于减少竞争同一位置而产生的失效。但潜在的缺点是增加了代价和访问时间。具体的性能改进如下图：
可以看到，随着 cache 容量的增加，相联度的提高对性能改进作用较小，这是因为大容量 cache 的总失效率较低，因此改善失效率的机会减少，并且由相联度引起的失效率的绝对改进明显减少。
如何找到块
根据前文的介绍，我们可以将找到块的方案总结为下表：
在存储层次结构中，直接映射、组相联和全相联映射的选择取决于失效代价与相联度实现代价之间的权衡，包括时间和额外硬件开销。在片上包含二级 cache 允许实现更高的相联度，这是因为命中时间不再关键，设计者也不必依靠标准 SRAM 芯片来构建模块。除非容量很小，否则 cache 不适用全相联映射方式，其中比较器的成本并不是压倒性的，而绝对失效率的改进才是最明显的。
在虚拟存储系统中，页表是一张独立的映射表，其用于索引内存。除了表本身需要的存储空间外，使用索引表还会引起额外的存储访问。使用全相联映射和额外的页表有以下几个原因：
- 全相联有助于规避较高的失效代价
- 全相联允许软件使用复杂度的替换策略以降低失效率
- 全相联容易索引，不需要额外的硬件，也不需要进行查找
因此，虚拟存储系统通常使用全相联。
组相联映射通常用于 cache 和 TLB，访问时包括索引和组内查找。一些系统使用直接映射 cache，这是因为访问时间短并且实现简单。访问时间短是因为查找时不需要进行比较。
总的来说，设计选择取决于具体的实现细节，例如 cache 是否集成在片上，实现 cache 的级数以及 cache 的访问时间对处理器周期时间的重要性。
当 cache 发生失效时替换哪一块
当相联的 cache 发生失效时，我们必须决定要替换哪个块。在全相联的 cache 中，所有的块都是替换掉候选者。如果 cache 是组相联的，则必须在一组的块中进行选择。
在组相联或全相联的 cache 中有两种主要的替换策略：
- 随机：随机选择候选块，可能使用一些硬件辅助实现
- 最近最少使用：被替换的块是最久没有被使用过的块
实际上，在相联度不低（如二路到四路）的层次结构中实现 LRU 的代价太高，这是因为追踪记录使用信息的代价很高。即使对于四路组相联，LRU 通常也是近似实现的。
对于较大的相联度，LRU 是近似的或使用随机替换策略。在 cache 中，替换算法由硬件实现，这意味着方案应该易于实现。随机替换算法用硬件很容易实现，对于两路组相联 cache，随机替换的失效率比 LRU 替换策略的失效率高约 \(1.1\) 倍。随着 cache 容量变大，两种替换策略的失效率下降，并且绝对差异也变小。
在虚拟存储中，LRU 的一些形式都是近似的，因为当失效代价很大时，失效率的微小降低都很重要。由于失效代价很高且相对不频繁发生，主要由软件来近似这项信息的做法是可行的。
写操作如何处理
任何存储层次结构的一个关键特性是如何处理写操作。我们已经看到两种基本方式：
- 写穿透：信息将写入 cache 中的块和存储层次结构中较低层的块（对 cache 而言是主存）。
- 写返回：信息仅写入 cache 中的块。修改后的块只有在它被替换时才会写入层次结构中的较低层。虚拟存储系统总是采用写返回策略。
两种方式有其各自的优势。写穿透的优势在于：
- 失效比较简单，代价也比较小，这是因为不需要将块写回到存储层次结构中的较低层。
- 写穿透比写返回更容易实现，尽管实际上写穿透 cache 仍然需要写缓冲区。
写返回的优势在于：
- 处理器可以按 cache 而不是内存能接受的速率写单个的字。
- 块内的多次写操作只需对存储层次结构中的较低层进行一次写操作。
- 当写回块时，由于写一整个块，系统可以有效地利用高带宽传输。
在虚拟存储系统中，只有写返回策略才是实用的，这是因为写到存储层次结构较低层的延迟很大。尽管允许存储器的物理和逻辑宽度更宽，并对 DRAM 采用突发模式，处理器产生写操作的速率通常还是超过存储系统可以处理它们的速率。因此，现在最低一级的 cache 通常采用写回策略。
一种理解存储层次结构的直观模型
在本节中，我们将介绍一种模型，以便我们洞察存储层次结构中引起失效的原因，以及存储层次结构中的变化对失效的影响。我们将用 cache 来解释这些想法，尽管这些想法对其它层次也直接适用。在此模型中，所有失效都被分为以下三类：
- 强制失效：对没有在 cache 中出现过的块进行第一次访问时产生的失效，也称作冷启动失效。
- 容量失效：cache 无法包含程序执行期间所需的所有块而引起的失效。当某些块被替换出去，随后再被调入时，将发生容量失效。
- 冲突失效：在组相联或者直接映射 cache 中，很多块为了竞争同一个组导致的失效。冲突失效是直接映射或组相联 cache 中的失效，而在相同大小的全相联 cache 中不存在。这种失效也称作碰撞失效 (collision miss)。
改变 cache 设计中的一些方面可以直接影响这些失效的原因，总结如下表：
由于冲突失效来自对同一 cache 块的争用，因此提高相联度可减少冲突失效。但是提高相联度会延长访问时间，从而降低整体性能。
简单地增大 cache 容量可以减少容量失效。但在增大 cache 的同时，我们也必须注意访问时间的增长，这可能导致整体性能的降低。实际上，多年来二级 cache 容量一直在稳步增长，一级 cache 也在增大，但是增速较慢。
由于强制失效是对块的第一次访问时产生的，因此对 cache 系统来说，减少强制失效次数的主要方法是增加块大小。由于程序将由较少的 cache 块组成，因此这将减少对程序每一块都要访问一次时的总访问次数。故块容量增加太多可能对性能产生负面影响，因为失效代价会增加。