凌云的博客

存储器层次结构

分类：os| 发布时间：2026-08-09 16:16:00

概述

存储器系统是一个具有不同容量、成本和访问时间的存储设备的层次结构。 CPU 寄存器保存着最常用的数据。 靠近 CPU 的小的、快速的高速缓存存储器作为一部分存储在相对慢速的主存储器（main memory, 简称主存）中的数据和指令的缓冲区域。 主存暂时存放存储在容量较大的、慢速磁盘上的数据, 而这些磁盘常常又作为存储在通过网络连接的其他机器上的磁盘或磁带上的数据的缓冲区域。

存储器层次结构是可行的, 这是因为你与下一个更低层次的存储设备相比来说, 一个编写良好的程序倾向于更频繁地访问某一个层次上的存储设备。 所以, 下一层的存储设备可以更慢速一点, 也因此可以更大, 每个位更便宜。 整体效果是一个大的存储器池, 其成本与层次结构底层最便宜的存储设备相当, 但是却以接近于层次结构顶部存储设备的高速率向程序提供数据。

如果你的程序需要的数据是存储在 CPU 寄存器中, 那么指令在执行期间, 在零个周期内就能访问到她们。 如果存储在高速缓存中, 需要 1~30 个周期。 如果存储在主存中, 需要 50~200 个周期。 而如果存储在磁盘上, 需要大约几千万个周期！

如果你理解了系统是佮将数据在存储器层次结构中上上下下移动的, 那么你就可以编写你的应用程序, 使得它们的数据项存储在层次结构中较高的地方, 在那里 CPU 能更快地访问到它们。

这个思想围绕着计算机程序的一个称为局部性的基本属性。 具有良好局部性的程序倾向于一次又一次地访问相同的数据项集合, 或是倾向于访问邻近的数据项集合。 具有良好局部性的程序比局部性差的程序更多得倾向于从存储器层次结构中较高层次处访问数据项, 因此运行得更快。

存储技术

随机访问存储器

随机访问存储器(Random-Access Mmory, RAM)分为两类：静态的和动态的。 静态 RAM(SRAM) 比动态 RAM(DRAM) 更快, 但也贵得多。 SRAM 用来作为高速缓存存储器, 既可以在 CPU 芯片上, 可以在其他地方。 DRAM 用来作为主存以及图形系统中帧缓冲区。

1、 静态 RAM

SRAM 将每个位存储在一个双稳态的存储器单元里。 每个单元是用一个六晶体管电路来实现的。 这个电路有这样一个属性, 它可以无限期地保持在两个不同的电压配置或状态之一。 其他任何状态都是不稳定的——从不稳定状态开始, 电路会迅速地转移到两个稳定状态中的一个。

2、 动态 RAM

DRAM 将每个位存储为对一个电容的充电。 这个电容非常小, 通常只有大约 30 豪微微法拉——30×10^-15 法拉。 DRAM 存储可以制造得非常密集——每个单元由一个电容和一个访问晶体管组成。 但是, 与 SRAM 不同, DRAM 存储单元对于干扰非常敏感。 当电容的电压被扰乱后, 它就永远不会恢复了。

很多原因会导致漏电, 使得 DRAM 单元在 10~100 毫秒时间内失去电荷。 存储器系统必须周期性地通过读出, 然后重新写来刷新存储器的每一位。 有些系统也可以使用纠错码, 其中计算机的字会被多编码几位（例如, 32 位的字可能用 38 位来编码）, 这样一来, 电路可以发现并纠正一个字中任何单个的错误位。

下图总结了 SRAM 和 DRAM 的存储器特性。

	每位晶体管数	相对访问时间	持续的？	敏感的？	相对花费	应用
SRAM	6	1×	是	否	100×	高速缓存存储器
DRAM	1	10×	否	是	1×	主存, 帧缓冲区

图 1 DRAM 和 SRAM 存储器的特性

3、传统的 DRAM

DRAM 芯片中的单元（位）被分成 d 个超单元(supercell), 每个超单元都由 w 个 DRAM 单元组成。 一个 d×w 的 DRAM 总共存储了 dw 位信息。 超单元被组织成一个 r 行 c 列 的长方形阵列, 这里 rc=d。

下图展示了一个 16×8 的 DRAM 的芯片的组织, 有 d=16 个超单元, 每个超单元由 w=8 位, r=4 行, c=4列。 信息通过称为引脚(pin) 的外部连接器流入和流出芯片。 每个引脚携带一个1位的信号。

每个 DRAM 芯片被连接到某个称为存储器控制器的电路, 这个电路可以一次传送 w 位到每个 DRAM 芯片或一次从每个 DRAM 芯片传出 w 位。 为了读出超单元 (i, j) 的内容, 存储控制器将行地址 i 发送到 DRAM, 然后是列地址 j。 DRAM 把超单元 (i, j) 的内容发回给控制器作为相应。 行地址 i 称为 RAS(Row Access Strobe, 行访问选通脉冲)请求。 列地址 j 称为 CAS(Column Access Strobe, 列访问选通脉冲)请求。

4、存储器模块

DRAM 芯片包装在存储器模块中, 它是插到主板的扩展槽上的。 常见的包装包括 168 个引脚的双列直插存储器模块 (Dual Inline Memory Module, DIMM), 它以 64 位为块传送数据到存储器控制器和从存储器控制器传出数据, 还包括 72 个引脚的单列直插存储器模块 (Single Inline Memory Module, SIMM), 它以 32 位为块传送数据。

图 3 展示了一个存储器模块的基本思想。 示例模块用 8 个 64Mbit 的 8M×8 的 DRAM 芯片, 总共存储 64MB (兆字节), 这 8 个芯片编号为 0~7。 每个超单元存储主存的一个字节, 而用响应超单元地址为 (i, j) 的 8 个超单元来表示主存中字节地址 A 处的 64 位双字。 在下图示例中, DRAM 0 存储第一个 (低位) 字节, DRAM 1 存储下一个字节, 依此类推。

要取出存储器地址 A 处的一个 64 位双字, 存储控制器将 A 转换成一个超单元地址 (i, j), 并将它发送给存储器模块, 然后存储器模块将 i 和 j 广播到每个 DRAM。 作为响应, 每个 DRAM 输出它的 (i, j) 超单元的 8 位内容。 模块中的电路收集这些输出, 并把它们合并成一个 64 位双字, 再返回给存储控制器。

5、增强的 DRAM

以下都是基于传统的 DRAM 单元, 并进行了一些优化, 改进了访问基本 DRAM 单元的速度。

• 块页模块 DRAM (Fast Page Mode DRAM, FPM DRAM)。 传统额 DRAM 将超单元的一整行拷贝到它的内部行缓冲区中, 使用一个, 然后丢弃剩余的。 FPM DRAM 允许对同一行连续地访问可以直接从行缓冲区得到服务, 从而改进了这一点。 例如, 要从一个传统的 DRAM 的行 i 中读四个超单元, 存储控制器必须发送四个 RAS/CAS 请求, 即使是行地址 i 在每个情况中都是一样的。 要从一个 FPM DRAM 的同一行中读取超单元, 存储控制器发送第一个 RAS/CAS 请求, 后面跟三个 CAS 请求。 初始的 RAS/CAS 请求将行 i 拷贝到行缓冲区, 并返回 CAS 寻址的那个超单元。 接下来三个超单元直接从行缓冲区获得, 因此比初始的超单元更快。
• 扩展数据输出 DRAM (Extended Data Out DRAM, EDO DRAM)。 FPM DRAM 的一个增强的形式, 它允许单独的 CAS 信号在时间上靠的更紧密一点。
• 同步 DRAM (Synchronous DRAM SDRAM)。 就它们与存储控制器通信使用一组显式的控制信号来说, 常规的、FPM 和 EDO DRAM 都是异步的。 SDRAM 用与驱动存储控制器相同的外部时钟信号的上升沿来代替许多这样的控制信号。最终效果就是 SDRAM 能够比那些异步的存储器更快地输出超单元的内容。
• 双倍数据速率同步 DRAM (Doubl Data-rate Synchronous DRAM, DDR SDRAM)。 DDR SDRAM 是对 SDRAM 的一种增强, 它通过使用两个时钟信号沿作为控制信号, 从而使 DRAM 的速度翻倍。 不同类型的 DDR SDRAM 是用提高有效带宽的很小的预取缓冲区的大小来划分的：DDR(2位)、DDR2(4位)和DDR3(8位)。
• 视频 RAM (Video RAM, VRAM)。 它用在图形系统的帧缓冲区中。 VRAM 的思想与 FPM DRAM 类型。 两个主要的区别是：1) VRAM 的输出是通过一次对内部缓冲区的整个内容进行移位得到的; 2) VRAM 允许对存储器并行地读和写。 因此, 系统可以在写下一次更新的新值(写) 的同时, 用帧缓冲区的像素刷屏幕(读)。

6、非易失性存储器

如果断电, DRAM 和 SRAM 会丢失它们的信息, 从这个意义上说, 它们是易失的(volatile)。 另一方面, 非易失性存储器(nonvolatile memory) 即使是在关电后, 也仍然保存着它们的信息。 现在有很多种非易失性存储器。 由于历史原因, 虽然 ROM 中有的类型既可以读也可以写, 但是它们整体上都称为只读存储器(Read-Only Memory, ROM)。 ROM 是以它们能够被重编程(写)的次数和对它们进行重编程所用的机制来区分的。

PROM (Programmable ROM, 可编程ROM) 只能被编程一次。 PROM 的每个存储器单元有一种熔丝(fuse), 它只能用高电流熔断一次。

可擦写可编程 ROM(Erasable Programmable ROM, EPROM) 有一个透明的石英窗口, 允许光到达存储单元。 紫外线光照射过窗口, EPROM 单元就被清除为0。 对 EFROM 编程是通过使用一种把 1 写人 EPROM 的特殊设备来完成的。 EPROM 能够被擦除和重编程的次数的数量级可以达到 1000 次。 电子可擦除 PROM (Electrically Erasable PROM, EEPROM) 类似于 EPROM, 但是它不需要一个物理上独立的编程设备, 因此可以直接在印制电路卡上统扁程。 EEPROM 能够被编程的次数的数量级可以达到10⁵ 次。

闪存(flash memory) 是一类非易失性存储器, 基于EEPROM, 它已经成为了一种重要的存储技术。 闪存到处都是, 为大量的电子设备提供快速而持久的非易失性存储, 包括数码相机、手机、音乐播放器、PDA 和笔记本、台式机以及服务器计算机系统。

存储在 ROM 设备中的程序通常为固件(firmware)。 当一个计算机系统通电以后, 它会运行存储在 ROM 中的固件。 一些系统在固件中提供了少量基本的输入和输出函数——例如, PC 的BIOS (基本输人/输出系统) 例程。 复杂的设备, 像图形卡和磁盘驱动控制器, 也依赖固件翻译来自 CPU 的 I/O(输人/输出) 请求。

7、访问主存

数据流通过称为总线(bus) 的共享电子电路在处理器和 DRAM 主存之间来来回回。 每次 CPU 和主存之间的数据传送都是通过一系列步骤来完成的, 这些步骤称为总线事务(bus transaction)。 读事务(read transaction) 从主存传送数据到 CPU。 写事务(write transaction) 从 CPU 传送数据到主存。

下图展示了一个示例计算机系统的配置。 主要部件是 CPU 芯片、我们称为 I/O 桥(IO bridge)的芯片组(其中包括存储控制器), 以及组成主存的 DRAM 存储器模块。 这些部件由一对总线连接起来, 其中一条总线是系统总线(system bus), 它连接 CPU 和 I/O 桥, 另一条总线是存储器总线(memory bus), 它连接 I/O 桥和主存。

IO 桥将系统总线的电子信号翻译成存储器总线的电子信号。 IO 桥也将系统总线和存储器总线连接到 I/O 总线,像磁盘和图形卡这样的 I/O 设备共享 I/O 总线。

磁盘存储

磁盘是由盘片构成的。 每个盘片有两面或者成为表面(surface), 表面覆盖着磁性记录材料。 盘片中央有一个可以旋转的主轴, 它使得盘片以固定的旋转速率旋转, 通常是 5400~15000 转每分钟。 磁盘通常包含一个或多个这样的盘片, 并封装在一个密封的容器中。

1、磁盘构造

下图展示了一个典型的磁盘表面的结构。 每个表面是由一组称为磁道(track) 的同心圆组成的。 每个磁道被划分为一组扇区(sector)。 每个扇区包含相等数量的数据位(通常是 512 字节), 这些数据编码在扇区的磁性材料中。 扇区之间由一些间隙(gap) 分隔开, 这些间隙中不存储数据位。 间隙存储用来标识扇区的格式化位。

磁盘是由一个或多个叠放在一起的盘片组成的, 它们被封装在一个密封的包装里, 如下图所示。 整个装置通常称为磁盘驱动器, 我们通常称为磁盘。

图 6磁盘构造-多个盘片的视图

磁盘的制造商通常用术语柱面(cylinder) 来描述多个盘片驱动器的构造, 这里, 柱面是所有盘片表面上到主轴中心的距离相等的磁道的集合。 例如, 如果一个驱动器有三个盘片和六个面, 每个表面上的磁道的编号都是一致的, 那么柱面 k 就是六个磁道 k 的集合。

2、磁盘容量

一个磁盘上可以记录的最大位数称为它的最大容量, 或者简称为容量。 磁盘容量是由以下技术因素决定的：

• 记录密度(recording density) (位/英寸): 磁道一英寸的段中可以放入的位数。
• 磁道密度(track density) (道/英寸): 从盘片中心出发半径上一英寸的段内可以有的磁道数。
• 面密度(areal density) (位/平方英寸): 记录密度与磁道密度的乘积。

最初的磁盘, 是在密度很低的时代设计的, 将每个磁道分为数据相同的扇区, 扇区的数目是由最靠内的磁道能记录的扇区数决定的。 为了保持每个磁道有固定的扇区数, 越往外的磁道扇区隔得越开。 在面密度相对比较低的时候, 这种方法还算合理。 不过, 随着面密度的提供, 扇区之间的间隙(那里没有存储数据位) 变得不可接受地大。 因此, 现代大容量磁盘使用一种称为多区记录(multiple zone recording) 的技术, 在这种技术中, 柱面的集合被分割成不相交的子集合, 称为记录区(recording zone)。 每个区包含一组连续的柱面。 一个区内的每个柱面中的每条磁道都有相同数量的扇区, 这个扇区的数量是由该区中最里面的磁道所能包含的扇区数确定的。

下面的公式给出了一个磁盘的容量：

$$\text{磁盘容量}=\frac{\text{字节数}}{\text{扇区}}\times \frac{\text{平均扇区数}}{\text{磁道}}\times \frac{\text{磁道数}}{\text{表面}}\times \frac{\text{表面数}}{\text{盘片}}\times \frac{\text{盘片数}}{\text{磁盘}}$$

例如, 假设我们有一个磁盘, 有 5 个盘片, 每个扇区 512 个字节, 每个面 20000 条磁道, 每条磁道平均 300 个扇区。 那么这个磁盘的容量是:

$$\text{磁盘容量}=\frac{\text{512 字节}}{\text{扇区}}\times \frac{\text{300 扇区}}{\text{磁道}}\times \frac{\text{20 000 磁道}}{\text{表面}}\times \frac{\text{2 表面}}{\text{盘片}}\times \frac{\text{5 盘片}}{\text{磁盘}}=\text{30 720 000 000 字节}=\text{30.72 GB}$$

3、磁盘操作

磁盘用读/写头(read/write head) 来卖写存储在磁性表面的位, 而读写头连接到一个传动臂(actuator arm)一端。 通过沿着半径轴前后移动这个传动臂, 驱动器可以将读/写头定位在盘面上的任何磁道上。 这样的机械运动称为寻道(seek)。 一旦读/写头定位到了期望的磁道上, 那么当磁道上的每个位 通过它的下面时, 读/写头可以感知到这个位的值(读该位), 也可以修改这个位的值(写该位)。 有多个盘片的磁盘针对每个盘面都有一个独立的读/写头。 读/写头垂直排列, 一致行动。 在任何时刻, 所有的读/写头都位于同一个柱面上。

磁盘以扇区大小的块来读写数据。 对扇区的访问时间(accesstime)有三个主要的部分: 寻道时间(seektime)、旋转时间(rotational latency) 和传送时间(transfer time):

• 寻道时间: 为了读取某个目标扇区的内容, 传动臂首先将读/写头定位到包含目标扇区的磁道上。 移动传动臂所需的时间称为寻道时间。 寻道时间 T_seek 依赖于读/写头以前的位置和传动臂在盘面上移动的速度。 现代驱动器中平均寻道时间 T_{avg seek} 是通过对几千次对随机扇区的寻道求平均值来测量的, 通常为 3~9 ms。 一次寻道的最大时间 T_{max seek} 可以高达 20ms。
• 旋转时间: 一旦读/写头定位到了期望的磁道, 驱动器等待目标扇区的第一个位旋转到读/写头下。 这个步骤的性能依赖于当读/写头到达目标扇区时盘面的位置和磁盘的旋转速度。 在最坏的情况下, 读/写头刚刚错过了目标扇区, 必须等待磁盘转一整圈。 因此, 最大旋转延迟, (以秒为单位)是 $${\text{T}}_{\text{max rotation}}=\frac{1}{\text{RPM}}\times \frac{\text{60 secs}}{\text{1 min}}$$ 平均旋转时间 T_{avg rotation} 是 T_{max rotation} 的一半。
• 传送时间: 当目标扇区的第一个位位于读/写头下时, 驱动器就可以开始读或者写该扇区的内容了。 一个扇区的传送时间依赖于旋转速度和每条磁道的扇区数目。 因此, 我们可以粗略地估计一个扇区以秒为单位的平均传送时间如下 $${\text{T}}_{\text{avg transfer}}=\frac{1}{\text{RPM}}\times \frac{1}{\text{(平均扇区数/磁道)}}\times \frac{\text{60 secs}}{\text{1 min}}$$

从磁盘读取数据的整体时间为:

T_access=T_{avg seek}+T_{avg rotation}+T_{avg transfer}

4、逻辑磁盘块

现代磁盘构造复杂, 有多个盘面, 这些盘面上有不同的记录区。 为了对操作系统隐藏这样的复杂性, 现代磁盘将它们的构造呈现为一个简单的视图, 一个 B 个扇区大小的逻辑块的序列, 编号为 0, 1, ..., B-1。 磁盘中有一个小的硬件/固件设备, 成为磁盘控制器, 维护着逻辑块号和实际(物理) 磁盘扇区之间的映射关系。

当操作系统想要执行一个 I/O 操作时, 例如读一个磁盘扇区到数据主存, 操作系统会发送一个命令到磁盘控制器, 让它读某个逻辑块号。 控制器上的固件执行一个快速表查找, 将一个逻辑块号翻译成一个 (盘面, 磁道, 扇区) 的三元组, 这个三元组唯一地标识了对应的物理扇区。

5、连接到 I/O 设备

像图形卡、监视器、鼠标、键盘和磁盘这样的 输入/输出 设备, 都是通过 I/O 总线, 例如 Intel 的外围设备互联(Peripheral Component Interconnect, PCI) 总线连接到 CPU 和主存的。 系统总线和存储器总线是与 CPU 相关的, 与它们不同, 诸如 PCI 这样的 I/O 总线设计成与底层 CPU 无关。 下图展示了一个典型的 I/O 总线结构, 它连接了 CPU、主存和 I/O 设备。

虽然 I/O 总线比系统总线和存储器总线慢, 但是它可以容纳种类繁多的第三方 I/O 设备。

6、访问磁盘

图 8 总结了当 CPU 从磁盘读数据时发生的步骤。

CPU 使用一种称为存储器映射 I/O 的技术向 I/O 设备发出命令(见图 8)。 在使用存储器映射 I/O 的系统中, 地址空间中有一块地址是为与 I/O 设备通信保留的。 每个这样的地址称为一个 I/O 端口(I/O port)。 当一个设备连接到总线时, 它与一个或多个端口相关联。

固态硬盘

固态硬盘(Solid State Disk, SSD) 是一种基于闪存的存储技术, 在某些情况下是传统旋转磁盘的极有吸引力的替代产品。 图 9 展示了它的基本思想。 SSD 插到 I/O 总线上标准硬盘插槽(通常是USB或SATA)中, 行为就和其他硬盘一样, 处理来自 CPU 的读写逻辑磁盘块的请求。 一个 SSD 包由一个或多个闪存芯片和闪存翻译层(flashtranslation layer) 组成, 闪存芯片替代传统旋转磁盘中的 机械驱动器, 而闪存翻译层是一个硬件/固件设备, 扮演与磁盘控制器相同的角色, 将对逻辑块的请求翻译成对底层物理设备的访问。

局部性

一个编写良好的计算机程序常常具有良好的局部性(locality)。 也就是说, 它们倾向于引用邻近于其他最近引用过的数据项的数据项, 或者最近引用过的数据项本身。 这种倾向性, 被称为局部性原理。

局部性通常有两种不同的形式: 时间局部性(temporal locality) 和空间局部性(spatial locality)。 在一个具有良好时间局部性的程序中, 被引用过一次的存储器位置很可能在不远的将来再被多次引用。 在一个具有良好空间局部性的程序中, 如果一个存储器位置被引用了一次, 那么程序很可能在不远的将来引用附近一个存储器位置。

对程序数据引用的局部性

考虑下图 10 中的简单函数, 它对一个向量的元素求和。 这个程序有良好的局部性吗？ 为了回答这个问题, 我们来看看每个变量的引用模式。 这个例子中, 变量 sum 在每次循环迭代中被引用了一次, 因此, 对于 sum 来说, 有好的时间局部性。 另一方面, 因为 sum 是标量, 对于 sum 来说, 没有空间局部性。

int sumvec(int v[N])
{
    int i, sum = 0;

    for (i = 0; i < N; i++)
        sum += v[i];
    return sum;
}

图 10 一个具有良好局部性的程序

正如我们在图 11 中看到的, 向量 v 的元素是被顺序读取的, 一个接一个, 按照它们存储在存储器中的顺序(为了方便, 我们假设数组是从地址 0 开始的)。 因此, 对于变量 v, 函数有很好的空间局部性, 但是时间局部性很差, 因为每个向量元素只被访问了一次。 因为对于循环体中的每个变了, 这个函数要么有好的空间局部性, 要么有好的时间局部性, 所以我们可以断定 sumvec 函数有良好的局部性。

地址	0	4	8	12	16	20	24	28
内容	v0	v1	v2	v3	v4	v5	v6	v7
访问顺序	1	2	3	4	5	6	7	8

图 11 向量 v 的引用模式(N=8)

像 sumvec 这样顺序访问一个向量每个元素的函数, 具有步长为 1 的引用模式。 有时我们称步长为 1 的引用模式为顺序引用模式。 一个连续向量中, 每隔 k 个元素进行访问, 就被称为步长为 k 的引用模式。 步长为 1 的引用模式是程序中空间局部性常见和重要的来源。 一般而言, 随着步长的增加, 空间局部性下降。

取指令的局部性

因为程序指令是存放在存储器中的, CPU 必须取出(读出) 这些指令, 所以我们也能评价一个程序关于取指令的局部性。 例如, 图 10 中 for 循环体里的指令是按照连续的存储器顺序执行的, 因此循环有良好的空间局部性。 因为循环体会被执行多次, 所以它也有很好的时间局部性。

代码区别于程序数据的一个重要属性是在运行时它是不能被修改的。 当程序正在执行时, CPU 只从存储器中读出它的指令。 CPU 决不会重写或修改这些指令。

局部性小结

• 重复引用一个变量的程序具有良好的时间局部性。
• 对于具有步长为 k 的引用模式的程序, 步长越小, 空间局部性越好。 具有步长为 1 的引用模式的程序有很好的空间局部性。 在存储器中以大步长跳来跳去的程序空间局部性会很差。
• 对于取指令来说, 循环有好的时间和空间局部性。 循环体越小, 循环迭代次数越多, 局部性越好。

存储器层次结构

• 存储技术: 不同存储技术的访问时间差异很大。 速度较快的技术每字节的成本要比速度较慢的技术高, 而且容量小。 CPU 和主存之间的速度差距在增大。
• 计算机软件: 一个编写良好的程序倾向于展示出良好的局部性。

计算中一个喜人的巧合是, 硬件和软件的这些基本属性互相补充得很完美。 它们这种相互补充的性质使人想到一种组织存储器系统的方法, 称为存储器层次结构, 所有的现代计算机系统中都使用了这种方法。 图 12 展示了一个典型的存储器层次结构。

存储层次结构中的缓存

一般而言, 高速缓存(cache, 读作“cash”) 是一个小而快速的存储设备, 它作为存储在存储设更大、也更慢的设备中的数据对象的缓冲区域。 使用高速缓存的过程称为缓存(caching, 读作"cashing")。

存储器层次结构的中心思想是, 对于每个 k, 位于 k 层的更快更小的存诸设备作为位于 k+1 层的更大更慢的存储设备的缓存。 换句话说, 层次结构中的每一层都缓存来自较低一层的数据对象。 例如, 本地磁盘作为通过网络从远程磁盘取出的文件(例如Web页面) 的缓存, 主存作为本地磁盘上数据的缓存, 依此类推直到最小的缓存一CPU寄存器集合。

图 13 展示了存储器层次结构中缓存的一般性概念。 第 k+1 层的存储器被划分成连续的数据对象片(chunk), 称为块(block)。 每个块都有一个唯一的地址或名字, 使之区别于其他的块。 块可以是固定大小的(通常是这样的), 也可以是可变大小的(如存储在Web服务器上的远程HTML文件)。 例如, 图 13 中第 k+1 层存储器被划分成 16 个大小固定的块, 编号为 0~15。

类似地, 第k层的存储器被划分, +1层的块的大小一成较少的块的集合, 每个块的大小与k在图6-24中, 第k第k1层块的一个子集的拷贝。例如, 样。在任何时刻, 第k层的缓存包含层的缓存有4个块的空间, 当前包含块 4、9、14 和 3 的拷贝。

1、缓存命中

当程序需要第 k+1 层的某个数据, 它首先在当前存储在第 k 层的一个块中查找 d。 如果 d 刚好缓存在第 k 层中, 那么就是我们所说的缓存命中(cache hit)。 该程序直接从第 k 层读取 d , 根据存储器层次结构的性质, 这要比从第 k+1 层读取 d 更快。

2、缓存不命中

另一方面, 如果第 k 层中没有缓存数据对象 d, 那么就是我们所说的缓存不命中(cache miss)。 当发生缓存不命中时, 第 k 层的缓存从第 k+1 层缓存中取出包含 d 的那个块, 如果第 k 层的缓存已经满了的话, 可能就会覆盖现存的一个块。

覆盖一个现存的块的过程称为替换(replacing) 或驱逐(evicting) 这个块。 被驱逐的这个块有时也称为牺块(victim block)。 决定该替换哪个块是由缓存的替换策略(replacement policy) 来控制的。 例如, 一个具有随机替换策略的缓存会随机选择一个牺牲一块。 一个具有最近最少被使用(LRU)替换策略的缓存会选择那个最后被访问的时间距现在最远的块。

3、缓存不命中的种类

一个空的缓存有时称为冷缓存(cold cache), 此类不命中称为强制性不命中或冷不命中(cold miss)。 冷不命中不重要, 因为它们通常是短暂的事件, 不会反复访问存储器使得缓存暖身(warmed up) 之后的稳定状态中出现。

只要发生了不命中, 第 k 层的缓存就必须执行某个放置策略, 确定把它从第 k+1 层中取出的块放在哪里。 最灵活的替换策略是允许来自第 k+1 层的任何块放在第 k 层的任何块中。 对于存储层次结构中高层的缓存(靠近 CPU), 它们是用硬件来实现的, 而且速度是最优的, 这个策略实现起来通常很昂贵, 因为随机地放置块, 定位起来代价很高。

因此, 硬件缓存通常使用的是更严格的放置策略, 这个策略将第 k+1 层的某个块限制放置在第 k 层块的一个小的子集中(有时只是一个块)。

这种限制性的放置策略会引起一种不命中, 称为冲突不命中(conflict miss), 在这种情况下, 缓存足够大, 能够保存被引用的数据对象, 但是因为这些对象会映射到同一个缓存块, 缓存会一直不命中。

程序通常是按照一系列阶段(如循环)来运行的, 每个阶段访问缓存块的某个相对稳定不变的集合。例如, 一个嵌套的循环可能会反复地访问同一个数组的元素。 这个块的集合称为这个阶段的工作集(working set)。 当工作集的大小超过缓存的大小时, 缓存会经历容量不命中(capacity miss)。 换句话说, 缓存就是太小了, 不能处理这个工作集。

4、缓存管理

正如我们提到过的, 存储器层次结构的本质是, 每一层存储设备都是较低一层的缓存。 在每一层上, 某种形式的逻辑必须管理缓存。

例如, 编译器管理寄存器文件, 缓存层次结构的最高层。它决定当发生不命中时何时发射加载, 以及确定哪个寄存器来存放数据。 L1、L2 和 L3 层的缓存完全是由内置在缓存中的硬件逻辑来管理的。 在一个有虚拟存储器的系统中, DRAM 主存作为存储在磁盘上的数据块的缓存, 是由操作系统软件和 CPU 上的地址翻译硬件共同管理的。

存储器层次结构概念小结

概括来说, 基于缓存的存储器层次结构行之有效, 是因为较慢的存储设备比较快的存储设备更便宜, 还因为程序往往展示局部性:

• 利用时间局部性: 由于时间局部性, 同一数据对象可能会被多次使用。 一旦一个数据对象在第一次不命中时被拷贝到缓存中, 我们就会期待后续对该目标有一系列的访问命中。 因为缓存比低一层的存储设备更快, 对后面的命中的服务会比最开始的不命中快很多。
• 利用空间局部性: 块通常包含多个数据对象。 由于空间局部性, 我们会期望后面对该块中其他对象的访问能够补偿不命中后拷贝该块的花费。

现在系统中到处都使用了缓存。如下图所示：

类型	缓存什么	被缓存在何处	延迟(周期数)	由谁管理
CPU寄存器	4字节或8字节	芯片上的CPU寄存器	0	编译器
TLB	地址翻译	芯片上的TLB	0	硬件MMU
L1高速缓存	64字节块	芯片上的L1高速缓存	1	硬件
L2高速缓存	64字节块	芯片上/下的L2高速缓存	10	硬件
L3高速缓存	64字节块	芯片上/下的L3高速缓存	30	硬件
虚拟存储器	4KB页	主存	100	硬件+OS
缓冲区缓存	部分文件	主存	100	OS
磁盘缓存	磁盘扇区	磁盘控制器	100 000	控制器固件
网络缓存	部分文件	本地磁盘	10 000 000	AFS/NFS 客户
浏览器缓存	Web 页	本地磁盘	10 000 000	Web 浏览器
Web 缓存	Web 页	远程服务器磁盘	1 000 000 000	Web 代理服务器

图 14 缓存在现代计算机系统中无处不在

高速缓存存储器

早期计算机系统的存储器层次结构只有三层: CPU 寄存器、DRAM 主存储器和磁盘存储。 不过, 由于 CPU 和主存之间逐渐增大的差距, 系统设计者被迫在 CPU 寄存器文件和主存之间插入了一个小的 SRAM 高速缓存存储器, 称为 L1高速缓存(一级缓存), 如图 15 所示。 L1 高速缓存的访问速度几乎和寄存器一样快, 典型地是 2~4 个时钟周期。

随着 CPU 和主存之间的性能差距不断增大, 系统设计者在 L1 高速缓存和主存之间又插入了一个更大的高速缓存, 称为 L2 高速缓存, 可以在大约 10 个时钟周期内访问到它。 有些现代系统还包括有一个更大的高速缓存, 称为 L3 高速缓存, 在存储器层次结构中, 它位于 L2 高速缓存和主存之间, 可以在 30 或者 40 个周期内访问到它。

通用的高速缓存存储器结构

考虑一个计算机系统, 其中每个存储器地址有 m 位, 形成 M=2^m 个不同的地址。 如图 6-27a 所示, 这样一个机器的高速缓存被组织成一个有 S=2^s 个高速缓存组的数组。 每个组包含 E 个高速缓存行。 每个行是由一个 B=2^b 字节的数据块组成一个, 一个有效位指明这个行是否包含有意义的信息, 还有 t=m-(b+s) 个标记位, 它们唯一地标识存储在这个高速缓存行中的块。

高速缓存的结构可以用元组 (S, E, B, m) 来描述。 高速缓存的大小（或容量）C 指的是所有块的大小的和。 标记位和有效位不包括在内。因此, C=S×E×B。

基本参数
参数	描述
S=2s	组数
E	每个组的行数
B=2b	块大小(字节)
m=log2(M)	(主存)物理地址位数

衍生出来的量
参数	描述
M=2m	存储器的最大数量
s=log2(S)	组索引位数量
b=log2(B)	块偏移位数量
t=m-(s+b)	标记位数量
C=B×E×S	不包括像有效位和标记位这样开销的高速缓存大小(字节)

直接映射高速缓存

根据 E (每个组的高速缓存行数) 高速缓存被划分为不同的类。 每个组只有一行 (E=1) 的高速缓存称为直接映射高速缓存。

高速缓存确定一个请求是否命中, 然后抽取出被请求的字的过程, 分为三步: 1) 组选择, 2) 行匹配, 3) 字抽取。

1、直接映射高速缓存中的组选择

在这一步中, 高速缓存从 w 的地址中间抽取出 s 个组索引位。 这些位被解释成一个对应于一个组号的无符号整数。 换句话来说, 如果我们把高速缓存看成是一个关于组的一维数组, 那么这些组索引位就是一个到这个数组的索引。 图 18 展示了直接映射高速缓存的组选择是如何工作的。 这个例子中, 组索引位 00001₂ 被解释为一个选择组 1 的整数索引。

2、直接映射高速缓存中的行匹配

既然在上一步中我们已经选择了某个组 i, 接下来的一步就要确定是否有字 w 的一个拷贝存储在组 i 包含的一个高速缓存行中。 在直接映射高速缓存中这很容易, 而且很快, 这是因为每个组只有一行。 当且仅当设置了有效位, 而且高速缓存行中的标记与 w 的地址中的标记相匹配时, 这一行中包含 w 的一个拷贝。

图 19 展示了直接映射高速缓存中行匹配时如何工作的。 在这个例子中, 选中的组中只有一个高速缓存行。 这个行的有效位设置了, 所以我们知道标记和块中的位是有意义的。 因为这个高速缓存行中的标记位与地址中的标记位相匹配, 所以我们知道我们想要的那个字的一个拷贝确实存储在这个行中。 换句话说, 我们得到一个缓存命中。 另一方面, 如果有效位没有设置, 或者标记不相匹配, 那么我们就得到一个缓存不命中。

3、直接映射高速缓存中的字选择

一旦命中, 我们知道 w 就在这个块中的某个地方。 最后一步确定所需要的字在块中是从哪里开始的。 如图 19 所示, 块偏移位提供了所需要的字的第一个字节的偏移。 就像我们把高速缓存看成一个行的数组一样, 我们把块看成一个字节的数组, 而字节偏移是得到这个数组的一个索引。 在这个示例中, 块偏移位是 100₂, 它表明 w 的拷贝是从块中的字节 4 开始的 (我们假设字长为 4 字节)。

4、直接映射高速缓存中不命中时的行替换

如果缓存不命中, 那么它需要从存储器层次结构中的下一层取出被请求的块, 然后将新的块存储在组索引位指示的组中的一个高速缓存行中。 一般而言, 如果组中都是有效高速缓存行了, 那么必须要驱逐出一个现存的行。 对于直接映射高速缓存来说, 每个组只包含有一行, 替换策略非常简单: 用新取出的行替换当前的行。

为什么用中间的位来做索引?
你也许会奇怪, 为什么高速缓存用中间的位来作为组索引, 而不是用高位。 为什么用中间的位更好, 是有很好的原因的。 图 20 说明了原因。 如果高位用做索引, 那么一些连续的存储器块就会映射到相同的高速缓存块。例如, 在图中, 头四个块映射到第一个高速缓存组, 第二个四个块映射到第二个组, 依此类推。 如果一个程序有良好的空间局部性, 顺序扫描一个数据的元素, 那么在任何时刻, 高速缓存都只保存着一个块大小的数组内容。 这样对高速缓存的使用效率很低。 相比较而言, 以中间位作为索引, 相邻的块总是映射到不同的高速缓存行。 在这种情况下, 高速缓存能够存放整个大小为 C 的数组片, 这里 C 是高速缓存的大小。

组相联高速缓存

直接映射高速缓存中冲突不命中造成的问题是源于每个组只有一行 (或者, 按照我们的术语来描述就是 E=1) 这个限制。 组相联高速缓存 (se associative cache) 放松了这条限制, 所以每个组都保存有多于一个的高速缓存行。 一个 1<E<C/B 的高速缓存通常称为 E 路组相联高速缓存。 图 21 展示了一个 2 路组相联高速缓存的结构。

1、组相联高速缓存中的组选择

它的组选择与直接映射高速缓存的组选择一样, 组索引标识组。 图 22 总结了这个原理。

2、组相联高速缓存中的行匹配和字选择

组相联高速缓存中的行匹配比直接映射高速缓存中的更复杂, 因为它必须检查多个行的标记位和有效位, 以确定所请求的字是否在集合中。 一个传统的存储器是一个值的数组, 以地址作为输入, 并返回存储在那个地址的值。 另一方面, 一个相联的存储器是一个 (key, value) 对的数组, 以 key 为输入, 返回与输入的 key 相匹配的 (key, value) 对中的 value 值。 因此, 我们可以把组相联高速缓存中的每个组都看成一个小的相联存储器, key 是标记和有效位, 而 value 就是块的内容。

图 23 展示了相联高速缓存中行匹配的基本思想。 这里的一个重要思想就是组中的任何一行都可以包含任何映射到这个组的存储器块。 所以高速缓存必须搜索组中的每一行, 寻找一个有效的行, 其标记与地址中的标记相匹配。 如果高速缓存找到了这样一行, 那么我们就命中, 块偏移从这个块中选择一个字, 和前面一样。

3、组相联高速缓存中不命中时的行替换

如果CPU请求的字不在组的任何一行中, 那么就是缓存不命中, 高速缓存必须从存储器中取出包含这个字的块。 不过, 一旦高速缓存取出了这个块, 该替换哪个行呢? 当然, 如果有一个空行, 那它就是个很好的候选。 但是如果该组中没有空行, 那么我们必须从中选择一个非空的行, 希望CPU不会很快引用这个被替换的行。

最简单的替换策略是随机选择要替换的行。 其他更复杂的策略利用了局部性原理, 以使在比较近的将来引用被替换的行的概率最小。 例如, 最不常使用(Least-Frequently-Used, LFU)策略会替换在过去某个时间窗口内引用次数最少的那一行。 最近最少使用(Least-Recently-Used, LRU)策略会替换最后一次访问时间最久远的那一行。 所有这些策略都需要额外的时间和硬件。 但是, 越往存储器层次结构下面走, 远离CPU, 一次不命中的开销就会更加昂贵, 用更好的替换策略使得 不命中最少也变得更加值得了。

全相联高速缓存

一个全相联高速缓存(fully associative cache) 是由一个包含所有高速缓存行的组(即 E=C/B) 组成的。 图 24 给出了基本结构。

1、全相联高速缓存中的组选择

全相联高速缓存中的组选择非常简单, 因为只有一个组, 图 25 做了个小结。 注意地址中没有组索引位, 地址被划分成了一个标记和一个块偏移。

2、全相联高速缓存中的行匹配和字选择

全相联高速缓存中的行匹配和字选择与组相联高速缓存中的是一样的, 如图 26 所示。 它们之间的区别主要是个规模大小的问题。 因为高速缓存电路必须并行地搜索许多相匹配的标记, 构造一个又大又快的相联高速缓存很困难, 而且很昂贵。 因此, 全相联高速缓存只适合做小的高速缓存, 例如虚拟存储器系统中的翻译备用缓冲器(TLB),它缓存页表项。

有关写的问题

正如我们看到的, 高速缓存关于读的操作非常简单。 首先, 在高速缓存中查找所需字 w 的拷贝。 如果命中, 立即返回字 w 给 CPU。 如果不命中, 从存储器层次结构中较低层中取出包含字 w 的块, 将这个块存储到某个高速缓存行中(可能会驱逐一个有效的行), 然后返回字 w。

写的情况就要复杂一些了。 假设我们要写一个已经缓存了的字 w 写命中(writehit)。 在高速缓存更新了它的 w 的拷贝之后, 怎么更新 w 在层次结构中紧接着低一层中的拷贝呢? 最简单的方法, 称为直写(write-through), 就是立即将 w 的高速缓存块写回到紧接着的低一层中。 虽然简单, 但是直写的缺点是每次写都会引起总线流量。 另一种方法, 称为写回(write-back), 尽可能地推迟存储器更新, 只有当替换算法要驱逐更新过的块时, 才把它写到紧接着的低一层中。 由于局部性, 写回能显著地减少总线流量, 但是它的缺点是增加了复杂性。 高速缓存必须为每个高速缓存行维护一个额外的修改位(dirty bit), 表明这个高速缓存块是否被修改过。

另一个问题是如何处理写不命中。 一种方法称为写分配(write-allocate), 加载相应的低一层中的块到高速缓存中, 然后更新这个高速缓存块。 写分配试图利用写的空间局部性, 但是缺点是每次不命中都会导致一个块从低一层传送到高速缓存。 另一种方法, 称为非写分配(not-write-allocate), 避开高速缓存, 直接把这个字写到低一层中。 直写高速缓存通常是非写分配的。 写回高速缓存通常是写分配的。

高速缓存参数的性能影响

有许多指标来衡量高速缓存的性能:

• 不命中率(missrate)。 在一个程序执行或程序的一部分执行期间, 存储器引用不命中的比率。 它是这样计算的: 不命中数量/引用数量。
• 命中率(hitrate)。 命中的存储器引用比率。 它等于 1-不命中率。
• 命中时间(hit time)。从 高速缓存传送一个字到 CPU 所需的时间, 包括组选择、行确认和字选择的时间。 对于L1高速缓存来说, 命中时间的数量级是几个时钟周期。
• 不命中处罚(miss penalty)。 由于不命中所需要的额外的时间。 L1 不命中需要从 L2 得到服务的处罚, 典型地是数 10 个周期;从 L3 得到服务的处罚, 40个周期;从主存得到的服务的处罚, 100个周期。

1、高速缓存大小的影响

一方面, 较大的高速缓存可能会提高命中率。 另一方面, 使大存储器运行得更快总是要难一些的。 结果, 较大的高速缓存可能会增加命中时间。 对于芯片上的 L1 高速缓存来说这一点尤为重要, 因为它的命中时间必须短。

2、块大小的影响

大的块有利有弊。 一方面, 较大的块能利用程序中可能存在的空间局部性, 帮助提高命中率。 不过, 对于给定的高速缓存大小, 块越大就意味着高速缓存行数越少, 这会损害时间局部性比空间局部性更好的程序中的命中率。 较大的块对不命中处罚也有负面影响, 因为块越大, 传送时间就越长。 现代系统通常会折中, 使高速缓存块包含 32~64 个字节。

3、相联度的影响

这里的问题是参数 E 的选择的影响, E 是每个组中高速缓存行数。 较高的相联度(也就是 E 的值较大) 的优点是降低了高速缓存由于冲突不命中出现抖动的可能性。 不过, 较高的相联度会造成较高的成本。 较高的相联度实现起来很昂贵, 而且很难使之速度变快。 每一行需要更多的标记位, 每一行需要额外的 LRU 状态位和额外的控制逻辑。 较高的相联度会增加命中时间, 因为复杂性增加了, 另外, 还会增加不命中处罚, 因为选择牺牲行(victim line) 的复杂性也增加了。 相联度的选择最终变成了命中时间和不命中处罚之间的折中。 传统上, 努力争取时钟频率的高性能系统会为 L1 高速缓存选择较低的相联度(这里的不命中处罚只是几个周期), 而在不命中处罚比较高的较低层上使用比较小的相联度。例如, Intel Core i7 系统中, L1 和 L2 高速缓存是 8 路组相联的, 而 L3 高速缓存是 16 路组相联的。

4、写策略的影响

直写高速缓存比较容易实现, 而且能使用独立于高速缓存的写缓冲区(write buffer), 用来更新存储器。 此外, 读不命中开销没这么大, 因为它们不会触发存储器写。 另一方面, 写回高速缓存引起的传送比较少, 它允许更多的到存储器的带宽用于执行 DMA 的 IO 设备。 此外, 越往层次结构下面走, 传送时间增加, 减少传送的数量就变得更加重要。 一般而言, 高速缓存越往下层, 越可能使用写回而不是直写。

编写高速缓存友好的代码

局部性比较好的程序更容易有较低的不命中率, 而不命中率较低的程序往往比不命中率较高的程序运行得更快。 因此, 从具有良好局部性的意义上来说, 好的程序员总是应该试着去编写高速缓存友好(cache fiendly) 的代码。 下面就是我们用来确保代码高速缓存友好的基本方法:

然我们已经明白了高速缓存存储器是如何工作的了, 我们就能更加精确一些了。

• 让最常见的情况运行得快。 程序通常把大部分时间都花在少量的核心函数上, 而这些函数通常把大部分时间都花在了少量循环上。 所以要把注意力集中在核心函数中的循环上, 而忽略其他部分。
• 在每个循环内部缓存不命中数量最小。 在其他条件(例如加载和存储的总次数)相同的情况下, 不命中率较低的循环运行得更快。
  • 对局部变量的反复引用是好的, 因为编译器能够将它们缓存在寄存器文件中(时间局部性)。
  • 步长为 1 的引用模式是好的, 因为存储器层次结构中所有层次上的缓存都是将数据存储为连续的块(空间局部性)。

小结

基本存储技术包括随机存储器(RAM)、非易失性存储器(ROM)和磁盘。 RAM 有两种基本类型。 静态 RAM(SRAM)快一些, 但是也贵一些, 它既可以用做CPU芯片上的高速缓存, 也可以用做芯片下的高速缓存。 动态RAM(DRAM)慢一些, 也便宜一些, 用做主存和图形帧缓冲区。 非易失性存储器, 也称为只读存储器(ROM), 即使是在关电的时候, 也能保持它们的信息, 它们用来存储固件。 旋转磁盘是机械的非易失性存储设备, 以每个位很低的成本保存大量的数据, 但是访问时间比 DRAM 更长。 固态硬盘(SSD)基于非易失性的闪存, 越来越变成旋转磁盘对某些应用的具有吸引力的替代产品。

一般而言, 较快的存储技术每个位的价格会更高, 而且容量较小。 这些技术的价格和性能属性正在以显著不同的速度变化着。 特别地, DRAM 和磁盘访问时间远远大于 CPU 周期时间。 系统通过将存储器组织成存储设备的层次结构来弥补这些差异, 在这个层次结构中, 较小、较快的设备在顶部, 较大、较慢的设备在底部。 因为编写良好的程序有好的局部性, 大多数数据都可以从较高层得到服务, 结果就是存储系统能以较高层的速度运行, 但却有较低层的成本和容量。

程序员可以通过编写有良好空间和时间局部性的程序来显著地改进程序的运行时间。 利用基于 SRAM 的高速缓存存储器特别重要。 主要从高速缓存取数据的程序能比主要从存储器取数据的程序运行得快得多。