前言
下面是《深入理解计算机系统》第六章节的一段话
对系统的研究中，我们依赖于一个简单的计算机系统模型， CPU 执行指令，而存储器系统为 CPU 存放指令和数据 。 在简单模型中，存储器系统是一个线性 的字节数组，而 CPU 能够在一个常数时间内访问每个存储器位置。虽然迄今为止这都是一个有效的模型，但是它没有反映现代系统实际工作的方式 。
存储器系统(memory system)是一个具有不同容量、成本和访问时间的存储设备的层次结构。 CPU 寄存器保存着最常用的数据。靠近 CPU 的小的、快速的高速缓存存储器 (cache memory)作为一部分存储在相对慢速的主存储器(main memory) 中数据和指令的缓冲区域。 主存缓存存储在容量较大的、慢速磁盘上的数据，而这些磁盘常常又作为存储在通过网络连接的其他机器的磁盘或磁带上的数据的缓冲区域 。
存储器层次结构是可行的，这是因为与下一个更低层次的存储设备相比来说，一个编写良好的程序倾向于更频繁地访问某一个层次上的存储设备。所以，下一层的存储设备可以更慢速一点，也因此可以更大，每个比特位更便宜。整体效果是一个大的存储器池，其成本与层次结构底层最便宜的存储设备相当，但是却以接近于层次结构顶部存储设备的高速率向程序提供数据。
作为一个程序员，你需要理解存储器层次结构，因为它对应用程序的性能有着巨大的影响 。 如果你的程序需要的数据是存储在 CPU 寄存器中的，那么在指令的执行期间，在 0 个周期内就能访问到它们。如果存储在高速缓存中，需要 4~7 5 个周期 。 如果存储在主存中，需要上百个周期。而如果存储在磁盘上，需要大约几千万个周期！
存储技术
随机访问存储器
随机访问存储器 (Random-Acces s Memory, RAM)分为两类：静态的和动态的。静态 RAM(SRAM) 比动态 RAM(DRAM) 更快，但也贵得多。 SRAM 用来作为高速缓存存储器，既可以在 CPU 芯片上，也可以在片下 。 DRAM 用来作为主存以及图形系统的帧缓冲区。典型地，一个桌面系统的 SRAM 不会超过几兆字节，但是 DRAM 却有几百或几千兆字节 。
SRAM将每个位存储在一个双稳态的 (bistable) 存储器单元里。每个单元是用一个六晶体管电路来实现的。这个电路有这样一个属性，它可以无限期地保持在两个不同的电压配置 (configuration)或状态 (state) 之一。其他任何状态都是不稳定的从不稳定状态开始，电路会迅速地转移到两个稳定状态中的一个。
由千 SRAM 存储器单元的双稳态特性，只要有电，它就会永远地保持它的值。即使有干扰（例如电子噪音）来扰乱电压，当干扰消除时，电路就会恢复到稳定值。
DRAM每个位用一个电容 + 一个晶体管存储。电容有电荷表示 1，无电荷表示 0；
电容很小，容易漏电；
一般 10～100 毫秒内就可能丢失电荷；
所以必须周期性地 读出再写回，也就是刷新；
对光、电噪声比较敏感；
优点是结构简单、密度高、成本低，适合做主存。
有些系统还会给 DRAM 加 纠错码 ECC，比如 64 位数据用 72 位存储，这样可以发现并纠正单比特错误。
传统的DRAM
DRAM 芯片中的位被组织成超单元 supercell。每个超单元包含 w 位，共有 d 个超单元，所以总容量是 d×w 位。这些超单元排成 r 行 c 列的二维阵列，满足 rc = d。访问时采用行列复用：
- 内存控制器先发送 行地址 i，称为 RAS；
- DRAM 把第 i 行复制到内部 行缓冲区；
- 再发送 列地址 j，称为 CAS；
- 从行缓冲区中取出第 j 个超单元的数据返回。
内存模块DIMM
多个 DRAM 芯片会封装成 内存模块，插到主板上。常见的是 DIMM，一次以 64 位为单位与内存控制器交换数据。
例如一个模块用 8 个 8M×8 的 DRAM 芯片，每个芯片提供 8 位，合起来就是 64 位。访问某个主存地址时，内存控制器把地址转换成行列地址，广播给所有芯片，每个芯片返回自己的 8 位，最后拼成一个 64 位字。
增强的DRAM
为了弥补传统 DRAM 速度慢的问题，出现了多种改进：
FPM DRAM：同一行连续访问时，行缓冲区可以复用，后续访问只需 CAS，不用每次都发 RAS；
EDO DRAM：在 FPM 基础上进一步缩短 CAS 之间的间隔；
SDRAM：和系统时钟同步，比异步 DRAM 更快；
DDR SDRAM：在时钟上升沿和下降沿都传输数据，使有效带宽翻倍；DDR、DDR2、DDR3 等通过增大预取缓冲区继续提升带宽；
VRAM：用于图形帧缓冲区，支持并行读写，适合一边刷新屏幕一边写入新像素。
非易失性存储器
SRAM 和 DRAM 都是 易失性存储器，断电后数据会丢失。非易失性存储器即使断电也能保存数据。
常见类型：
PROM：只能编程一次；
EPROM：可用紫外线擦除，再重新编程；
EEPROM：可用电信号擦除和编程，能在电路板上直接改写；
Flash：基于 EEPROM 发展而来，广泛用于 U 盘、SSD、手机存储等；
存储在 ROM 中的程序常称为 固件 firmware，比如 PC 的 BIOS。
访问主存
数据流通过称为总线 (bus) 的共享电子电路在处理器和 DRAM 主存之间来来回回 。 每次 CPU 和主存之间的数据传送都是通过一系列步骤来完成的，这些步骤称为总线事务 (bus transaction) 。读事务(read transaction)从主存传送数据到 CPU。写事务(write trans-action)从 CPU 传送数据到主存 。
总线是一组并行的导线，能携带地址、 数据和控制信号 。 取决于总线的设计，数据和地址信号可以共享同一组导线，也可以使用不同的。同时，两个以上的设备也能共享同一总线 。 控制线携带的信号会同步事务， 并标识出 当前正在被执行的事务的类型。
现在有一个命令：movq A,%rax
地址A的内容被加载到寄存器%rax中。CPU芯片上称为总线接口的电路在总线上发起读事务。
读事务是由三个步骤组成的。首先， CPU 将地址 A 放到系统总线上。 I/0 桥将信号传递到内存总线。 接下来，主存感觉到内存总线上的地址信号，从内存总线读地址，从 DRAM 取出数据字，并将数据写到内存总线 。 I/0 桥将内存总线信号翻译成系统总线信号，然后沿着系统总线传递。最后， CPU 感觉到系统总线上的数据，从总线上读数据，并将数据复制到寄存器 %rax。
反过来，CPU执行这样一个存储操作：movq %rax A
这里，寄存器%rax 的内容被写到地址 A, CPU 发起写事务。同样，有三个基本步骤。首先， CPU 将地址放到系统总线上。内存从内存总线读出地址，并等待数据到达 。接下来， CPU 将 %rax 中的数据字复制到系统总线 。最后，主存从内存总线读出数据字，并且将这些位存储到 DRAM 中 。
内存映射IO
CPU 向 I/O 设备发命令时，使用一种叫内存映射 I/O 的技术。
普通内存地址用来访问 RAM，但地址空间里有一部分地址被保留给 I/O 设备。这些地址叫 I/O 端口。当一个设备接到总线上时，它会被映射到一个或多个端口。
比如磁盘控制器被映射到地址 0xa0。CPU 想读磁盘时，可以连续执行三次存储指令：
- 写入一个命令字，告诉磁盘“开始读”，并附带参数，比如读完后是否中断 CPU；
- 写入要读的逻辑块号；
- 写入数据要存放的主存地址。
CPU 发完命令后，不会一直等着磁盘读完。因为磁盘访问可能要十几毫秒，而 1GHz 的 CPU 在这期间可以执行上千万条指令。所以 CPU 会继续做别的事。
DMA ：磁盘控制器直接把数据写到内存
磁盘控制器收到读命令后，会把逻辑块号翻译成物理扇区地址，然后读出扇区内容。
关键点是：数据不是先交给 CPU，再由 CPU 写进内存；而是由磁盘控制器直接写到主存。这个过程叫DMA，直接内存访问。
DMA 的好处很明显：CPU 不用参与数据搬运，可以继续执行其他指令，效率更高。
中断：数据到达后通知 CPU
当 DMA 传送完成，磁盘扇区的数据已经安全放进主存后，磁盘控制器会向 CPU 发送一个中断信号。
CPU 收到中断后，会暂停当前工作，跳转到操作系统的一段中断处理程序。这个程序记录“I/O 已完成”，然后恢复 CPU 之前被中断的地方。
所以整个读磁盘过程可以概括成：
CPU 发命令 → 磁盘控制器翻译逻辑块 → DMA 传数据到内存 → 中断通知 CPU。
固态硬盘SSD
SSD 是基于闪存的存储设备，通常通过 SATA、USB 等接口接入 I/O 总线，对外表现得像普通磁盘一样，可以接收 CPU 发出的逻辑块读写请求。
一个 SSD 主要由两部分组成：
| 组成部分 | 作用 |
|---|---|
| 闪存芯片 | 替代传统磁盘中的机械盘片，用于存储数据 |
| 闪存翻译层 FTL | 类似磁盘控制器，把逻辑块地址映射到物理闪存块和页 |
闪存的读写机制
闪存内部结构是分层的：
页：最小读写单位，通常为 512B～4KB。
块：由多个页组成，通常为 32～128 页，大小约 16KB～512KB。
擦除单位是块：只有整个块被擦除后，才能重新写入其中的页。
写限制：一个块擦除后，其中每个页可以写一次；再次修改需要先擦除整个块。
磨损问题：闪存块有写入寿命，大约 10 万次重复写入后可能磨损失效。
因此，SSD 写入比读取复杂，尤其是随机写：
擦除块耗时较长，通常在毫秒级，远高于页访问时间。
如果要修改某个已有数据的页，必须把该块中仍然有效的数据复制到新块，再擦除旧块，最后写入新数据。这会导致额外的内部写操作，称为写放大。
FTL 会通过磨损均衡等机制，把擦写操作尽量均匀分布到不同块上，从而延长 SSD 寿命。
SSD 与旋转磁盘的比较
优点：
没有机械部件，随机访问速度快。
能耗较低。
抗震性更好。
读写延迟通常远低于机械磁盘。
缺点：
闪存块存在写入寿命限制。
单位容量成本高于机械磁盘。
随机写性能通常不如随机读。
目前 SSD 已经在便携设备中广泛替代机械磁盘，在笔记本、台式机甚至服务器中也越来越常见。
局部性
一个编写良好的计算机程序常常具有良好的局部性 (locality) 。也就是，它们倾向于引用邻近于其他最近引用过的数据项的数据项，或者最近引用过的数据项本身。这种倾向性，被称为局部性原理 (principle of locality), 是一个持久的概念。
**局部性分为两种形式：时间局部性和空间局部性。**在一个具有良好时间局部性的程序中，被引用过一次的内存位置很可能在不远 的将来再被多次引用 。 在一个具有良好空间局部性的程序中，如果一个内存位置被引用了一次，那么程序很可能在不远的将来引用附近的一个内存位置。
现代计算机系统的各个层次，从硬件到操作系统、再到应用程序，它们的设计都利用了局部性 。在硬件层，局部性原理允许计算机设计者通过引入称为高速缓存存储 器的小而快速的存储器来保存最近被引用的指令和数据项，从而提高对主存的访问速度。 在操作系统级，局部性原理允许系统使用主存作为虚拟地址空间最近被引用块的高速缓存 。
对程序数据引用的局部性
下面给出一个函数sumvec()：
intsumvec(intv[N]){inti,sum=0;for(i=0;i<N;i++)sum+=v[i];returnsum;}变量sum在每次循环迭代中被引用一次，对于sum来说有很好的时间局部性。sum是标量，所以没有空间局部性。
向量v的元素是顺序读取的，对于变量v函数有很好的空间局部性，但是时间局部性很差，因为每个向量元素只被访问一次。
对于循环体中的每个变量，这个函数要么有好的空间局部性，要么有好的时间局部性，所以我们可以断定 sumvec 函数有良好的局部性。
sumvec 这样顺序访问一个向最每个元素的函数，我们说它具有步长为 1 的引用模式。有时我们称步长为 1 的引用模式为顺序引用模式。一个连续向鼠中，每隔 k 个元素进行访问，就称为步长为 k 的引用模式。步长为 1 的引用模式是程序中空间局部性常见和重要的来源。一般而言，随着步长的增加，空间局部性下降。
对千引用多维数组的程序来说，步长也是一个很重要的问题。
下面给出函数sumarrayrows，它对一个二维数组的元素求和。双重嵌套循环按照行优先顺序 (row major order)读数组的元素。内层循环读第一行的元素，然后读第二行，依此类推。
intsumarrayrows(inta[M][N]){inti,j,sum=0;for(i=0;i<M;i++)for(j=0;j<N;j++)sum+=a[i][j];returnsum;}函数 sumarrayrows 具有良好的空间局部性，因为它按照数组被存储的行优先顺序来访问这个数组 。其结果是得到一个很好的步长为 1 的引用模式，具有良好的空间局部性。数组a的引用格式如下：
| 地址 | 0 | 4 | 8 | 12 | 16 | 20 |
|---|---|---|---|---|---|---|
| 内容 | a00a_{00}a00 | a01a_{01}a01 | a02a_{02}a02 | a10a_{10}a10 | a11a_{11}a11 | a12a_{12}a12 |
| 访问顺序 | 1 | 2 | 3 | 4 | 5 | 6 |
下面给出另一个同样是对一个二维数组的元素求和的函数sumarraycols，与sumarrayrows的区别是交换了i和j的循环，这样导致sumarraycols的局部性很差。
intsumarrayrows(inta[M][N]){inti,j,sum=0;for(j=0;j<N;j++)for(i=0;i<M;i++)sum+=a[i][j];returnsum;}| 地址 | 0 | 4 | 8 | 12 | 16 | 20 |
|---|---|---|---|---|---|---|
| 内容 | a00a_{00}a00 | a01a_{01}a01 | a02a_{02}a02 | a10a_{10}a10 | a11a_{11}a11 | a12a_{12}a12 |
| 访问顺序 | 1 | 3 | 5 | 2 | 4 | 6 |
存储器层次结构
硬件与软件的特性正好互补。
硬件层面：存储技术中，速度越快的设备每字节成本越高、容量越小；CPU与主存之间的速度差距正在扩大。
软件层面：编写良好的程序往往表现出良好的局部性（时间局部性和空间局部性）。
两者的互补性催生了存储器层次结构这一组织方法，所有现代计算机系统均采用此设计。
| 层级 | 存储设备 | 特点 | 访问速度 |
|---|---|---|---|
| L0 | CPU寄存器 | 容量极小，成本最高 | 1个时钟周期内 |
| L1/L2/L3 | 高速缓存（SRAM） | 容量较小，成本较高 | 几个时钟周期内 |
| L4 | 主存（DRAM） | 容量较大，成本较低 | 几十到几百个时钟周期 |
| L5 | 本地磁盘 | 容量大，成本低 | 慢 |
| L6 | 远程二级存储（分布式文件系统、Web服务器） | 容量极大，成本最低 | 最慢，需网络访问 |
从上往下：存储设备变得更慢、更便宜、容量更大。
从下往上：每一层保存着从下一层取出的数据副本（如L1缓存保存从L2取出的缓存行，主存保存从磁盘取出的块）。
存储器层次结构中的缓存
高速缓存（Cache）：一个小而快速的存储设备，作为更大、更慢设备中数据的缓冲区域。
缓存（Caching）：使用高速缓存的过程。
核心思想：存储器层次结构中，第 k 层（更快、更小）作为第 k+1 层（更大、更慢）的缓存，每一层都缓存来自较低一层的数据对象。
第 k+1 层存储器被划分为连续的数据对象组块，称为块，每个块有唯一地址/名字。
块可以是固定大小（通常）或可变大小（如 Web 服务器上的 HTML 文件）。
数据总是以块为传送单元在相邻层之间复制。
不同层对之间的块大小可以不同：越靠近 CPU 的层块越小（如 L1L0 用 1 个字），越远离 CPU 的层块越大（如 L5L4 用几百到几千字节），以补偿较长的访问时间。
缓存命中与不命中
当程序需要第 k + 1 层的某个数据对象 d 时，它首先在当前存储在第 k 层的一个块中查找 d 。如果 d 刚好缓存在第 k 层中，那么就是我们所说的缓存命中。从k层直接读取d比从k+1层读取快。
如果第 k 层中没有缓存数据对象 d, 那么就是我们所说的缓存不命中 (cache miss)。当发生缓存不命中时，第 k 层的缓存从第 k + 1 层缓存中取出包含 d 的那个块，如果第 k 层的缓存已经满了，可能就会覆盖现存的一个块。
覆盖一个现存的块的过程称为替换 (replacing) 或驱逐 (evicting) 这个块。被驱逐的这 个块有时也称为牺牲块 (victim block) 。决定该替换哪个块是由缓存的替换策略 (replacement policy)来控制的。
缓存不命中的种类
| 类型 | 说明 |
|---|---|
| 强制性不命中（Cold Miss） | 冷缓存（空缓存）时首次访问必然不命中，缓存"暖身"后不再出现 |
| 冲突不命中（Conflict Miss） | 缓存足够大，但因放置策略限制（如块 i 只能映射到 i mod 4），多个块映射到同一位置导致反复不命中 |
| 容量不命中（Capacity Miss） | 程序某阶段的工作集（Working Set）超过缓存容量，缓存太小无法容纳 |
放置策略（Placement Policy）
决定从第 k+1 层取出的块放在第 k 层的哪个位置。
灵活策略：任意块可放任意位置，但硬件实现成本高（定位代价大）。
严格策略：第 k+1 层的块 t 只能放在第 k 层的特定位置（如 t mod 4），硬件缓存常用此策略，但可能引发冲突不命中。
缓存管理
不同层次的缓存由不同逻辑管理：
寄存器文件（L0）：由编译器管理，决定加载时机和寄存器分配。
L1/L2/L3 高速缓存：完全由硬件逻辑管理。
主存（DRAM）：在虚拟内存系统中，由操作系统 + CPU 地址翻译硬件共同管理。
本地磁盘：在分布式文件系统（如 AFS）中，由本地客户端进程管理。
高速缓存存储器
通用的高速缓存存储器组织结构
计算机的高速缓存被组织成一个有S=2sS=2^sS=2s个高速缓存组的数组。每个组包含E个高速缓存行，每个行是由一个B=2bB=2^bB=2b字节的数据块 (block)组成的，一个有效位 (valid bit) 指明这个行是否包含有意义的信息，还有 t=m-(b+s)个标记位 (tag bit)(是当前块的内存地址的位的一个子集），它们唯一地标识存储在这个高速缓存行中的块。
高速缓存可描述为元组 (S, E, B, m)。
S =2s2^s2s：高速缓存组（Set）数
E：每组包含的高速缓存行（Line）数
B =2b2^b2b：每行的数据块大小（字节）
m：物理地址位数（地址空间 M = 2^m）
t = m − (s + b)：标记位（Tag）数
缓存容量C=S×E×BC = S × E × BC=S×E×B（仅计数据字节，不含有效位和标记位）
每行包含：1 位有效位 + t 位标记位 + B 字节数据块。
假设有一条加载指令，指示CPU从主存地址A中读取一个字，它将地址A发送给高速缓存。如果高速缓存正保存着地址 A 处那个字的副本，它就立即将那个字发回给 CPU。下面我们来看下它是如何工作的：
m 位地址被划分为三段：[标记 t 位 | 组索引 s 位 | 块偏移 b 位]。CPU 访问地址 A 时分三步：
- 组选择：用 s 位组索引定位到具体组。
- 行匹配：在该组内逐行检查——有效位为 1 且标记位匹配则命中。
- 字抽取：用 b 位块偏移从数据块中取出目标字节。
直接映射高速缓存
每组仅一行，实现最简单，但也最容易发生冲突不命中。不命中时替换策略极其简单：直接用新块覆盖当前行。
工作示例（S=4, E=1, B=2, m=4）：地址空间仅 16 字节，8 个内存块映射到 4 个组，块 0 和块 4 都映射到组 0，靠标记位区分。模拟读序列 0→1→13→8→0 可观察到：第 5 步读地址 0 时，因之前读地址 8 已将块 4 装入组 0，块 0 被驱逐，产生冲突不命中。
冲突不命中与抖动（Thrashing）
当程序访问的两个数组恰好映射到同一组时，会在两组数据间反复驱逐/加载，称为抖动，性能可下降 2~3 倍。
经典案例：dotprod(x[8], y[8])，x 从地址 0 开始，y 从地址 32 开始，块大小 16 字节，缓存仅 2 组。x[0]~x[3] 与 y[0]~y[3] 全部映射到组 0，每次迭代都冲突不命中。
解决方法：在数组末尾添加 B 字节填充（如 float x[12] 代替 float x[8]），使 x 和 y 的块映射到不同组，即可消除抖动。
级相联高速缓存
直接映射高速缓存中冲突不命中造成的问题源于每个组只有一行，组相联高速缓存的每个组都保存有多于一个的高速缓存行。一个1<E<C/B的高速缓存通常称为 E 路 组相联高速缓存。
三个关键步骤
- 组选择：与直接映射高速缓存完全相同：组索引位标识组
- 行匹配与字选择：比直接映射更复杂，需要并行检查组内所有行：
- 有效位必须设置
- 某一行的标记位必须与地址中的标记位匹配
- 若命中，用块偏移从块中选择起始字节
- 不命中时的行替换：有空行直接放入，无空行选择牺牲行
全相联高速缓存
全相联是组相联的特例：整个高速缓存只有一个组，即E=C/BE=C/BE=C/B，所有行都在该组中。
组选择：只有一个组，默认总是选择组 0。地址中没有组索引位，只划分为：
| 标记（t 位） | 块偏移（b 位） |
行匹配与字选择：与组相联原理相同，但规模更大——需要并行搜索所有行的标记。
三种映射方式对比：
| 特性 | 直接映射 | 组相联 | 全相联 |
|---|---|---|---|
| 每组行数 E | 1 | 1 < E < C/B | C/B |
| 组数 S | C/B | C/(B×E) | 1 |
| 地址划分 | 标记|组索引|块偏移 | 标记|组索引|块偏移 | 标记|块偏移 |
| 冲突不命中 | 最多 | 中等 | 无 |
| 硬件复杂度 | 最低 | 中等 | 最高 |
高速缓存写策略
| 策略 | 做法 | 优点 | 缺点 |
|---|---|---|---|
| 直写 | 每次写缓存时，立即写回低一层 | 实现简单 | 总线流量大 |
| 写回 | 先只更新缓存，等到该行被替换时才写回 | 减少总线流量，利用局部性 | 需要额外维护修改位 |
写回需要给每一行增加一个 dirty bit：如果该行被修改过，替换时就必须写回主存；如果没有被修改，则可以直接丢弃。
写不命中
| 策略 | 做法 | 特点 |
|---|---|---|
| 写分配 | 先把低层块加载到缓存，再更新 | 利用空间局部性，但每次不命中都要传块 |
| 非写分配 | 不加载到缓存，直接写低层 | 避免传块，但无法利用缓存局部性 |
常见组合是：
直写缓存：通常配合 非写分配。
写回缓存：通常配合 写分配。
现代系统更倾向于采用写回 + 写分配模型，因为越往下层，传送代价越高，减少不必要传送更重要。
