存储系统

• 1: 存储系统
• 2: 内存
• 3: 外存
• 4: Cache
• 5: 虚拟存储器

# 存储器层次结构

## 存储器分类

## 层次化存储器的基本结构

## 半导体随机存取存储器

- SRAM存储器
- DRAM存储器
- Flash存储器

## 主存储器

- DRAM芯片和内存条
- 多模块存储器
- 主存和CPU之间的连接

## 外部存储器

- 磁盘存储器
- 固态硬盘

## 高速缓冲存储器

- cache的基本原理
- cache和主存之间的映射方式
- cache中主存块的替换算法
- cache写策略

## 虚拟存储器

- 基本概念
- 页式虚拟存储器
- 段式虚拟存储器
- 段页式虚拟存储器

1 - 存储系统

存储系统的层次结构

1. 寄存器（Registers）:
   • 寄存器是位于处理器内部的最快速存储单元。
   • 它们提供极快的数据访问速度，但其容量非常有限。
2. 一级缓存（L1 Cache）:
   • L1缓存位于处理器内部，比寄存器稍大，但比其他缓存慢。
   • 它通常分为数据缓存（用于存储数据）和指令缓存（用于存储指令）。
3. 二级缓存（L2 Cache）:
   • L2缓存比L1缓存大，并且位于处理器和主内存之间。
   • 它的速度比L1慢，但比主内存快。
4. 三级缓存（L3 Cache）:
   • 在某些系统中，还有L3缓存，这是一种更大但速度更慢的缓存。
   • 它位于L2缓存和主内存之间，旨在进一步减少对主内存的访问。
5. 主内存（RAM）:
   • 就是我们常说的内存，比缓存慢，但比硬盘快得多，并且容量比缓存大。
   • 主内存用于存储正在运行的程序和当前使用的数据。
6. 辅助存储（如硬盘驱动器或固态驱动器）:
   • 辅助存储设备提供大量的永久存储。
   • 与RAM相比，这些设备访问速度较慢，但能够存储更多的数据，并且在断电时不会丢失数据。
   • 硬盘驱动器（HDD）和固态驱动器（SSD）是常见的辅助存储设备。

半导体随机存储器

半导体随机存储器的英文为 Semiconductor Random-Access Memory （ RAM ）。

首先说一下这个名词中的几个部分：

• 半导体：这种存储器使用半导体材料（如硅）制成。晶体管是构成半导体存储器的基本组成部分。
• 随机：随机的意思是随机访问，意味着可以以几乎恒定的时间访问存储器中的任意位置，它与其他存储技术（如磁盘或磁带）不同，后者需要按顺序访问数据。

随机存储器主要分为SRAM和DRAM，注意两者的区别：

半导体随机存储器是 易失性 的，这意味着一旦断电，其中存储的信息就会丢失。SRAM 主要用于实现cache，DRAM 主要用于实现主存。

Flash存储

Flash存储器是一种 非易失性 的电子存储设备，它利用半导体技术来存储数据。通常用于长期数据存储，如USB闪存驱动器、固态硬盘（SSD）和移动设备的内部存储。它在读取速度上比RAM慢，但优于传统的硬盘驱动器（HDD）。

Flash存储器使用电子方式来擦写和重新编程存储单元。这意味着可以通过电信号快速擦除和写入数据。数据存储在小型存储单元中，每个单元由浮动门晶体管组成。这些晶体管可以保持其充电状态，从而代表不同的数据位。

Flash存储主要分为 NAND Flash 和 NOR Flash 这两种类型。

ROM

ROM（Read-Only Memory）是一种 非易失性 存储设备，主要用于永久性地存储数据。

ROM主要用于读取操作。虽然早期的ROM在制造过程中就已经被编程，不能修改，但现代的ROM（如EPROM和Flash存储器）可以被重新编程。

ROM常用于存储固件，这是一种软件程序，直接嵌入在硬件设备中，用于控制设备的基本操作。例如，BIOS（基本输入输出系统）通常存储在ROM中。

注意一下ROM和RAM的对比如下：

ROM 类型：

• EPROM：可以通过紫外线照射来擦除数据，然后重新写入数据。写入数据和擦除数据都较为繁琐，且需要物理操作。常用作电脑的 BIOS 芯片，支持随机存取。
• CDROM： 一种光盘存储设备，数据在生产时一次性写入，不能被修改（只能读取）。

2 - 内存

DRAM 芯片

刷新方式

多模块存储器

利用多个结构完全相同的存储模块的并行工作来提高存储器的吞吐率：

• 单体多字存储器
• 多体交叉存储器
  • 高位交叉存储器
  • 低位交叉存储器

单体多字存储器

按同一地址码并行地访问各自对应单元，每一个单元为一个字，每字 m 位。可以同时选中存储器的 n 个单元，可以将带宽提高 n 倍。

仅做简单了解，这里不详细说明，考试重点在多体交叉存储器。

多体交叉存储器

在多体交叉存储器的实现方案中，有两种编码方式：高位交叉编制和低位交叉编址。其中低位交叉编址可以实现多个存储器的并行访问，高位交叉编址只能增大存储器的空间。

高位交叉编址

在高位交叉编址中，地址分为两个部分，高位用于存储存储器的下标，低位用于存储地址在该存储器内的偏移。

连续的数据在同一个存储器内编址，当一个存储器满了，接下来的数据在下一个存储器中编址。 如下图所示，若计算机地址空间大小为 4n，存储器 M0 中存储地址 0 到 n-1 的数据，存储器 M0 中存储地址 n 到 2n-1 的数据，以此类推。

所以在高位交叉编址中，相邻地址的数据存储在一个存储体中。

在这种地址组织形式下，多个存储器芯片 串行工作，只需要一个地址存储器即可，不必为每个芯片都配一个地址存储器（根据程序的局部性原理） 。

这种串行工作方式是无法提高 CPU 的性能的。 如上图所示，所有存储器都共享一个地址寄存器（AR，Address Register）和数据寄存器（DR，Data Regsiter）。

低位交叉编址

在低位交叉编址中，地址分为两个部分，低位用于存储存储器的下标，高位用于存储地址在该存储器内的偏移。

连续的数据交叉地在不同的存储器之间编址。 如下图所示，若计算机地址空间大小为 4n，地址为 0~3 的数据分别存储在 M0、M1、M2 和 M3 上，地址为 4~7 的数据也分别存储在 M0、M1、M2 和 M3 上，以此类推。

所以在低位交叉编址中，相邻地址的数据存储在不同存储体中。

在这种地址组织形式下，多个存储芯片是 并行工作 的，且相邻地址处在不同的存储体中，因此就可以实现存储体的并行访问； 为了并行访问，每一个存储体均需要一个地址寄存器；

使用 低位交叉编制 这种编址方式，计算机可以实现对于多个存储器的并行访问。 如上图所示，每个存储器都单独地配有一个地址寄存器（AR，Address Register）和数据寄存器（DR，Data Regsiter）。

并行访问存储器可以采用 流水线 的方式，与 指令流水线 概念类似，在并行存储器的流水线中，对于每一个存储器中存储单元的读取可以被分为三个阶段：

• $P_1$：送地址和命令（送地址至存储器的 AR 中）
• $P_2$：存储器读取数据（读取数据到 DR 中，该周期也称作 存储周期）
• $P_3$：传送数据（从 DR 中读取数据并传输到内存的物理地址中）

假设 CPU 的时钟周期为 $t$，$P_1$ 和 $P_3$ 的耗时为一个时钟周期即 $t$。$P_2$ 的耗时为四个时钟周期即 $4 \times t$，那么对于上图所示的 四体交叉存储器，读取 八个字长的数据 的流水线如下所示：

主存容量的扩展

虽然单体存储芯片的容量和字长在不断扩大，但是在实际应用的过程中，任然会出现芯片的容量或者字长满足不了应用的情况，因此就有了存储扩展的需求；

假设存储芯片的字长为 $N$，存储字数为 $M$，则存储芯片的容量为 $M \times N$。

常见的存储扩展包括三种：位扩展、字扩展、字位扩展：

• 位扩展：扩展字长
• 字扩展：扩展字数
• 字位扩展：同时扩展字长和字数

位扩展

如上图所示，用 $16K \times 8\ bit$ 的存储芯片用来构建 $16K \times 32\ bit$ 的存储器。

需要的芯片数量为 $(16K \times 32) / (16K \times 8) = 4$。

由于是位扩展，所以四个芯片的片选信号要连接在一起，并处在常有效的状况；（片选信号是读写操作的开关）。

由于原存储器的 $8$ 位的，扩展之后变为 $32$ 位，这 $32$ 位的位线同 CPU 的 $32$ 位数据线相连接，所有存储芯片并行工作，贡献 $32$ 位数据中的不同 $8$ 位；

图中，4 个存储器共同构成 $64KB = 2^{16}B$ 的存储空间，所以地址总线为 $16$ 位，即从 $A_{0}$ 到 $A_{15}$。 但是由于 $16KB$ 的存储芯片只需要 $14$ 根地址线，因此只需要 $14$ 位地址线与存储线相连，即从 $A_{2}$ 到 $A_{15}$。 这里 $A_{0}$ 到 $A_{1}$ 不被使用，因为这 低两位地址线 相当于被用来扩展字长。

字扩展

如上图所示，用 $16K \times 8\ bit$ 的存储芯片用来构建 $64K \times 8\ bit$ 的存储器。

需要的芯片数量为 $(64K \times 8) / (16K \times 8) = 4$。

地址总线的位数为 $16$， 但是由于 $16KB$ 的存储芯片只需要 $14$ 根地址线，因此只需要 $14$ 位地址线与存储线相连，即从 $A_{0}$ 到 $A_{13}$。 高两位地址线 $A_{14}$ 到 $A_{15}$ 与片选译码器相连，由此产生片选信号。

字位扩展

如上图所示，用 $16K \times 8\ bit$ 的存储芯片用来构建 $32K \times 16\ bit$ 的存储器。

需要的芯片数量为 $(32K \times 16) / (16K \times 8) = 4$。

地址总线的位数为 $16$，地址线 $A_{1} \sim A_{14}$ 与存储器相连，$A_{0}$ 不使用，被用来扩展字长。$A_{15}$ 用来产生片选信号。

视频讲解

3 - 外存

磁盘存储器

存储区域

1. Heads（磁头）：磁头是位于硬盘驱动器的读/写臂上的设备，用于读取和写入磁盘上的数据。每个盘片（硬盘通常包含多个盘片，每个盘片都有两个表面）上都有一个磁头，因此每个磁头都可以读取或写入盘片上的数据。磁头通过移动到不同的磁道（track）来寻找并访问数据。
2. Track（磁道）：磁道是磁盘上的一个同心圆环。
3. Cylinders（柱面）：柱面是硬盘上的一个数据存储区域，由相同半径位置上的多个盘片上的磁道组成。换句话说，它是所有盘片上相同半径位置的磁道的集合。
4. Sectors（扇区）：扇区是磁盘上的最小数据存储单元。磁盘通常被划分成许多扇区，每个扇区可以存储一定数量的数据。扇区的大小通常是512字节或4KB。操作系统和磁盘控制器使用扇区作为数据的最小单元，以读取和写入数据。

性能指标

• 平均存取时间 = 寻道时间（磁头移动到目的磁道的时间） + 旋转延迟时间（磁头定位到要读取扇区的时间） + 传输时间（传输数据所花费的时间），由于寻道和找扇区的距离远近不一，所以寻道时间和旋转延迟时间通常取平均值。
• 数据传输率：磁盘单位时间向主机传送数据的字节数。假设磁盘转速为 $r$ 传/秒，每条磁道容量为 $N$ 字节，则数据传输率为 $D_{r} = rN$

RAID

RAID全称为独立磁盘冗余阵列（Redundant Arrar of Independent Disks） 由于磁盘存储介质数据的可靠性容易受到环境影响，而发生数据错误的代价非常大，因此需要考虑存储的容灾与恢复。

RAID将多个独立的物理磁盘组成一个独立的逻辑盘，数据在多个物理盘上分割交叉存储、并行访问，具有更好的存储性能、可靠性和安全性。

固态硬盘SSD

• 无机械部件：SSD没有旋转盘片、磁头或机械臂等移动部件，它使用闪存存储芯片来存储数据。这意味着它不会受到机械故障的威胁，具有更高的耐用性。
• 更快的读写速度：SSD的读写速度远远超过传统的机械硬盘，因为数据可以立即访问，无需等待盘片旋转和磁头寻道。这使得计算机启动更快，应用程序响应更迅速。
• 低访问时间：由于没有机械延迟，SSD的访问时间极低，通常在微秒级别。这有助于加快文件读取和数据检索。
• 长寿命：虽然每个存储单元有写入次数的限制，但现代SSD使用错误检查和纠正（ECC）技术，以延长其寿命，并且通常拥有较长的保修期。
• 无碎片化：SSD不会发生碎片化问题，因此无需定期进行碎片整理操作。

4 - Cache

cache 原理

cache 工作原理

缓存（cache）是计算机系统中的一种用于加速数据访问的技术，其原理是在高速存储介质中暂时存储常用数据，以便更快地满足后续的访问请求。

缓存对于程序执行的加速主要来自于 计算机程序 的 时间局部性 和 空间局部性：

1. 时间局部性：
   • 如果一个数据项被访问，那么它在不久的将来很可能再次被访问。
   • 这种特性常见于循环结构和频繁访问的变量，例如循环中的计数器或者经常读取的配置值。
   • 在缓存设计中，利用时间局部性意味着一旦数据被加载到缓存中，它应该在那里保留一段时间，因为很可能很快会再次需要它。
2. 空间局部性：
   • 如果一个数据项被访问，那么存储在其附近的数据项也很可能在不久的将来被访问。
   • 这种特性在数组遍历或结构体访问时尤为明显，因为这些数据元素通常在内存中是连续存储的。
   • 利用空间局部性的缓存设计会在访问一个数据项时，同时把它附近的数据也加载到缓存中，因为这些数据很可能在接下来的操作中被用到。

cache 概念

• 缓存块（cache 块）：cache 中的一块存储空间
• 主存块：主存中的一块存储空闲，主存块的大小一般与 cache 块一致
• 块内偏移：某一个地址在块内的偏移，找到对应的块后，通过块内偏移找到改地址的具体位置
• 块大小：用于判断块内偏移的位数，比如$1024 = 2^{10}$，所以 1KB 的块对应的块内偏移位数为 10

缓存块

什么是缓存块？

Cache block（缓存块），也被称为缓存行（cache line），是计算机系统中用于存储的最小数据单元，它是缓存中的一个固定大小的数据块。每个缓存块包含一定数量的字节或字（通常是 2 的幂次方个字节），并用于存储从主存（或更低级别的缓存）中加载的数据。

cache block 的目的是为了方便对于主存（main memory）数据的缓存，主存数据块的大小与缓存块大小一致，这样就可以将 cache block 和 main memory block 对应起来。

缓存块的大小？

Cache block 的大小在不同计算机体系结构中可以有所不同，通常以字节（bytes）或字（words）为单位来表示。典型的缓存块大小可以是 32 字节、64 字节、128 字节等。较大的缓存块可以容纳更多的数据，提高了数据的局部性，但在某些情况下，较小的缓存块可能更适合，特别是对于小规模的数据访问。

cache block 的大小在题目中一般会给你。

cache 和主存映射方式

1. 直接映射

在直接映射（directed mapped）缓存中，每个主存块只能映射到缓存中的一个特定缓存块。这意味着每个主存块只有一个缓存块可以存储它。

例子

假设我们有一个 256KB 的缓存，其中每个缓存块是 64B，对于直接映射的cache：

• 缓存被分为 256KB / 64B = 4096 个缓存块。
• 内存中的数据可以直接映射到这 4096 个位置中的其中一个，比如第 10000 个主存块映射到 10000 % 4096 = 1808个缓存块。
• 当一个新的数据块需要被加载时，它会替换掉当前映射到该位置的数据块，不管缓存的其他位置是否为空。

2. 全相联映射

在全相联缓存（full associative）中，主存中的任何块可以映射到缓存中的任何缓存块。这意味着主存块的地址没有限制，可以映射到任何可用的缓存块。

例子

假设我们有一个 256KB 的缓存，其中每个缓存块是 64B，对于全相联映射的cache：

• 缓存被分为 256KB / 64B = 4096 个缓存块。
• 全相联缓存中的每个主存块可以放置在任何缓存块中，即第 0 到第 4095 个缓存块都可以存储该主存块。
• 当缓存满时，基于某种替换策略替换掉 4096 个缓存块中的某一个。

3. 组相联映射

组相联缓存（set associative 或 group associative）是直接映射缓存和全相联缓存之间的一种折中方案。它将缓存块分为多个组，每个组包含多个缓存块。主存块可以映射到组中的一个缓存块。

N 路组相联

当我们说一个缓存是 N路组相连 的，意味着缓存被分为多个组，每个组有N个缓存块（N路）。这样，当一个内存地址被映射到一个特定的组时，它可以放在该组的任何一个缓冲块（一路）上。如果一个组是满的，新的数据会根据某种替换策略来替换组中的一个缓存块。

例子

假设我们有一个 256KB 的缓存，其中每个缓存块是 64B，我们希望有 4 路组相联的组织。

• 这意味着缓存被分为 256KB / 64B = 4096 个缓存块。
• 因为是 4 路组相联，所以这些块被进一步组织为 4096 / 4 = 1024 个组。
• 每个组包含 4 个位置（即 4 路），任何内存地址映射到这个组的时候，可以放在这四个位置中的任何一个。
• 比如第 10000 个主存块位于第 10000 % 1024 = 784个组，可能对应组内的任何一个缓存块。

cache 地址结构

当给定一个物理地址时，需要判断该地址对应的主存块可能被哪些 cache 块所缓存，并且检查所有可能的 cache 块的 tag 字段以判断是否被缓存，所以 cache 地址的结构从逻辑上可以分为如下部分：

• 标记（tag）：判断当前地址是否命中对应的 cache 块
• cache 块匹配字段：通过该字段判断主存块可能被哪些 cache 块缓存
  • 对于直接映射为块号（cache block number）：位数为$log_2{(\text{cache 块数量})}$
  • 对于全相联映射为空，因为每一个主存块都可能被任何一个 cache 块所缓存
  • 对于组相联映射为组号（group number）：位数为$log_2{(\text{组数})}$
• 块内地址（block offset）：物理地址在主存块内的偏移

总结三种不同映射方式的地址结构如下：

cache 存储结构

cache 的存储结构可以理解为一张表：

其中字段的含义与页表近似：

• 有效位：该 cache 行是否存储有缓存数据，位数为1位。
• 标记：根据物理地址中的 tag 字段与该字段匹配，以判断是否命中，位数按照cache地址结构进行计算。
• 修改位：标记该 cache 是否修改过，与写策略相关。
  • 如果采用全写法，则无需设置修改位。
  • 如果采用写回法，设置1位修改位。
• 访问位：用于记录访问信息，服务于块替换算法，其位数取决于替换算法。
  • 如果采用LRU替换算法，则修改位的位数为$log_2{(\text{主存快对应的缓存块数量})}$。
• 数据块：缓存的数据块，为物理内存中数据块的一个副本。

cache 中的块替换算法

块替换算法适用于全相联映射和组相联映射，因为一个主存块可能被多个cache块中的某一个 所缓存，查询和替换过程如下：

• 根据 cache 块匹配字段找到所有可能缓存 该物理地址对应主存块 的 cache 块
• 遍历所有可能缓存该主存块的cache块
  • 如果cache块的有效位为0，则替换该cache块，将主存块加载进来，并将有效位设置为1，停止遍历
  • 如果cache块的tag字段与物理地址的tag字段相匹配，则表示该次地址查询命中cache，停止遍历
• 如果遍历完所有cache块都无法满足如上条件时，则根据块替换算法选择一个cache块进行替换

当我们访问一个物理地址时未命中时，需要将对应的主存块加载到 cache 中，如果这个该主存块对应的 cache 块都满了的话，就需要替换掉其中的某个 cache 块，替换算法包含如下种类：

• LRU
• FIFO
• 随机算法
• LFU

这里的具体思想与操作系统中的页面置换算法一致，请参考页面置换算法

cache 写策略

cache 的写策略代表当我们对某个物理地址上的数据进行写入时，应该如何写入对应的存储单元，以及如何协调cache和主存之间的数据一致性，写策略按照地址查询是否命中cache可以分为四种方式。

如果某次地址查询命中 cache，可以使用如下策略：

• write-through（全写法）：每次写操作都会同时更新缓存和主存。
• write-back（回写法）：当数据被修改时，它首先被缓存在 cache 中，只有当 cache 块被替换时才写入对应的主存块。

如果没有命中 cache，也有如下策略：

• write-allocate（写分配）：物理地址对应主存块被加载到 cache 块中（先执行一次对应主存块的读操作），然后更新 cache 块
• not-write-allocate（非写分配）：不加载主存块至 cache 中，直接更新主存块，只有当执行读操作时才将主存块加载进入cache块

命中和未命中的方法常常通过如下方式一起使用：

• 全写法（write-through）和非写分配法（not-write-allocate）通常会一起使用，适用于那些写操作不频繁或者写操作不太可能访问同一数据的情况。
• 回写法（write-back）和写分配法（write-allocate）通常会一起使用，适用于那些写操作频繁的情况。

不同映射方式对比

视频讲解

5 - 虚拟存储器

虚拟存储器

虚拟存储器是一种计算机内存管理技术，它在物理内存和磁盘存储之间创建了一个抽象的、扩展的内存空间，以提供更大的可用内存容量。

虚拟内存和物理内存

1. 虚拟内存（Virtual Memory）：
   • 虚拟内存是一种计算机内存管理技术，它将计算机的物理内存扩展到磁盘上，从而提供了更大的可用内存空间。
   • 每个进程拥有自己的虚拟地址空间，这个地址空间通常比物理内存大得多。
   • 进程使用虚拟地址来访问内存中的数据和指令，而不需要了解物理内存的详细情况。
2. 物理内存（Physical Memory）：
   • 物理内存是计算机上实际存在的内存硬件，包括 RAM（随机存储器）芯片和其他存储设备。
   • 物理内存是计算机硬件用来存储正在运行的进程和操作系统内核的数据和指令的地方。
   • 物理地址是实际的内存地址，对应于计算机硬件上的存储器芯片中的位置。

页式虚拟存储器

地址翻译机构

CPU 中的内存管理单元（Memory Management Unit，MMU）是计算机体系结构的重要组成部分，它负责虚拟内存到物理内存的地址映射和内存访问的控制。MMU 的主要功能包括：

• 地址转换：MMU 负责将程序使用的虚拟地址转换为对应的物理地址。
• 地址保护：MMU 实施内存保护策略，以确保不同的程序或进程无法越界访问彼此的内存空间。
• 内存访问权限：MMU 根据地址映射和保护位（在页表或段表中定义）来控制内存访问权限，包括读、写、执行等。

页表

页表（page table）是操作系统维护的一张表，用于将虚拟地址转化为物理地址，每个运行的进程都有自己页表。 进程的页表存储在其内存空间中的内核空间中， 详见进程内存空间。 在进程执行时，MMU 使用当前活动进程的页表来执行地址转换。

单级页表

单级页表结构

一个典型的页表结构如下图所示：

页表中的每一行叫做页表项（PTE, page table entry），页表项可包含如下内容：

• 虚拟页框号（VPN，Virtual Page Number）：对于单级页表而言，VPN 并不需要实际存储在页表的字段中，其隐性地作为页表项的下标进行存储。
• 物理页框号（PPN，Physical Page Number）：当前 VPN 所对应的物理页号。
• 有效位（Valid Bit）：有效位用于指示虚拟页是否有效。如果有效位为 1，表示虚拟页是有效的，可以用于地址转换。如果有效位为 0，表示虚拟页无效，访问它会导致错误。
• 修改位（Dirty Bit）：修改位用于指示虚拟页的内容是否已被修改。如果修改位为 1，表示虚拟页的内容已被更改，可能需要写回到磁盘或其他非易失性存储介质。
• 访问位（Accessed Bit）：访问位用于指示虚拟页是否已被访问。如果访问位为 1，表示虚拟页已被访问。这对于操作系统的页面置换算法很有用。
• 保护位（Protection Bits）：保护位用于指定虚拟页的访问权限，例如读取、写入或执行权限。这有助于操作系统实施内存保护策略。
• 缓存位（Caching Bits）：缓存位用于指示是否允许将虚拟页的内容缓存在高速缓存中。这有助于控制内存访问的性能。

通过单级页表的地址翻译过程

虚拟地址和物理地址的格式

• 虚拟地址（Virutal Address）分为两个部分：
  • 虚拟页框号（VPN, Virtual Page Number）：当前地址所在的页框在虚拟内存对应的所有页框中的下标
  • 页内偏移（VPO, Virutal Page Offset）：地址在页面内的偏移
• 物理地址（Physical Address）同样分为两个部分：
  • 物理页框号（PPN, Physical Page Number）：当前地址所在的页框在物理内存对应的所有页框中的下标
  • 页内偏移（PPO, Physical Page Offset）：地址在页面内的偏移

地址翻译过程

PPO 和 VPO 的内容一致，所以地址翻译主要在于通过将 VPN 转化为 PPN，VPN 的值为对应的页表项（PTE）在页表中下标，在找到对应的页表项后，判断 Valid 字段是否为 1：

• 如果为 0 的话，调用缺页中断
• 如果为 1 的话，读取其中的 PPN，完成地址翻译

多级页表

单级页表会有什么问题？

在单级页表中，为了管理大型虚拟地址空间，需要创建庞大的页表，其中包含了大量的页表项，这会导致页表本身需要占用大量的内存空间。

假如我们有一个 32 位 4GB 的虚拟地址空间、4KB 的页面和一个 4 字节的 PTE，那么我们将需要一个 4MB 的页面表始终驻留在内存中，即使应用程序只引用虚拟地址空间的一小块。

多级页表结构

在多级页表中，虚拟页号 VPN 被分割为多个字段，假设被分割为 k 个字段的话，第 k 个字段对应的页表中的查询内容为 PPN，前 k-1 个字段对应的页表中的查询内容为下一级页表的位置。

如果当前多级页表对应的一级页表有 $m^k$ 个 PTE，将 VPN 分割为 k 个长度相同的子字段后，每个子字段对应的页表的 PTE 个数为$log_k{m^k} = m$。

其中，第一层有 $m$ 个页表，第二层最多有 $m^2$ 个页表在内存中存在， $\cdots$ ，第 k 层最多有 $m^k$ 个页表在内存中存在。

多级页表是如何节省内存的？

只有一级页表需要始终在主存中，对于其他层次的页表，可以按需分配，如果使用到的，就在内存中创建对应的页表结构，如果没使用到，就不需要为其分配内存。 这代表了巨大的潜在节省，因为典型程序的 4GB 虚拟地址空间中的大部分都是未分配的。

对于 k 级页表而言，前 k-1 级页表中 PTE 存储的关键字段都是下一级页表的位置，如果其中某个 PTE 的有效位为 0 的话， 那么操作系统无需为该页表项对应的下一级页表分配内存空间。

TLB

TLB（Translation Lookaside Buffer）是 CPU 内存管理单元（MMU）中的一种高速缓存，用于加速虚拟地址到物理地址的地址转换过程。 TLB 存储了最近用过的虚拟地址到物理地址的映射，以减少每次内存访问时的地址翻译延迟。

TLB 和页表的关系类似于 cache 与主存的关系，TLB 是一个有限大小的高速缓存，存储着页表中最近使用的某些页表项的副本。

由于页表存储在内存中，所以每一次通过页表的地址翻译过程都至少需要一次访存，开销还是比较大的。 所以为了降低这个开销，TLB 就应运而生，与 Cache 类似，你可以从概念上将 TLB 理解成一个硬件结构，与 Cache 类似，因为离 CPU 更近，所以其访问速度感更快。

如下图所示，TLB 将虚拟页号 VPN 从逻辑上分为两个部分：

• 标记（TLBT, 即 TLB Tag）：判断当前 VPN 是否命中 TLB 中的缓存项
• 匹配字段（Match Field），通过该字段判断 VPN 可能被哪些 TLB 表项所缓存，这里 TLB 与 Cache 类似，同样具有三种映射方式，每一种映射方式匹配字段会具有不同的位数。
  • 对于直接映射，匹配字段为 TLB 表项编号，即行编号（TLB entry index），其位数为 $log_2{(\text{\small TLB 行数})}$
  • 对于全相联映射，匹配字段位数为 $\text{\small 空}$，因为每一个 VPN 都可能被任何一个 TLB 行所缓存
  • 对于组相联映射，匹配字段为组号（TLB group index），位数为 $log_2{(\text{\small TLB 组数})}$

TLB 由许多表项（TLB Entry）构成，其表项个数决定了其容量大小。每一个表项包含两个字段，第一个是字段标志 TLBT（TLB Tag）字段，这里的标志字段与上文对于 VPN 的划分中的 TLBT 是相同的东西。 第二个字段是 PPN（物理页号），若进行地址翻译时命中 TLB 的某一行，则加载这一行的 PPN 以替换虚拟地址中的 VPN，实现地址翻译。

请求页式管理

请求页式管理（Demand Paging）是一种计算机操作系统中的内存管理技术，它允许进程在需要时才将页面（或者说虚拟内存中的数据块）加载到物理内存中，而不是一次性将整个进程加载到内存中。这个概念的核心思想是，将物理内存划分成固定大小的页框（page frame），并将虚拟内存划分成相应大小的页面（page）。

页面错误

当进程尝试访问一个虚拟页面，但该页面当前未加载到物理内存中时，会触发页面错误（page fault）。此时，操作系统会将相应的页面从磁盘加载到物理内存，进行页面替换。

那么如何判断访问的页面是否在物理内存中呢？

通过 查询 TLB 和 页表 以判断某个虚拟地址对应的页面是否在内存中。

从虚拟地址（VA）中提取出虚拟页号（VPN），再查询 TLB 和 页表中是否存在包含 VPN 的记录。如果存在的话，则说明待访问的虚拟页面在内存中，否则就不在。

页面替换

如果物理内存已满，操作系统需要选择一个页面来替换。通常，操作系统会选择一个不再需要的页面进行替换，这个决策基于使用的页面替换算法。

地址翻译过程