存储系统

• 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）是常见的辅助存储设备。

存储器层次结构的主要思想是上一层的存储器作为低一层存储器的高速缓存。当 CPU 要从存储器中存取数据时，先访问 Cache，若不在 Cache 中，则访问主存，若不在主存中，则访问磁盘，此时，操作数从磁盘读出送到主存，然后从主存送到 Cache。

Cache——主存层 主要解决 CPU 和主存速度不匹配的问题，主存和 Cache 之间的数据调动是由硬件自动完成的， 主存一辅存层 主要解决存储系统的容量问题，主存和辅存之间的数据调动是由硬件和操作系统共同完成的，两者对于应用程序员都是透明的。

RAM

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

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

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

随机存储器主要分为 SRAM 和 DRAM 两种。

SRAM

SRAM（Static RAM，静态随机存取存储器）使用触发器（通常由 4-6 个晶体管组成）构成存储器的基本存储单元，存储每个比特的数据，如下图所示：

只要电源持续供应，数据无需刷新即可保持稳定。

SRAM 通过将触发器组织成二维阵列构成存储器，每行连接一个字线（Word Line），控制该行所有单元的访问。 每列连接一对位线（Bit Line），用于传输数据。

SRAM 主要用于 CPU 缓存（L1/L2/L3 Cache）、寄存器、嵌入式系统中的小型高速存储。

DRAM

DRAM（Dynamic RAM，动态随机存储器）使用 1 个晶体管和 1 个电容器（1T1C 结构）构成存储器的基本存储单元，存储每个比特的数据。

• 电容器存储电荷，表示 1 比特数据（有电荷为 1，无电荷为 0）。
• 晶体管作为开关，控制电容器与外部位线（bit line）的连接，读写数据。

与触发器不同，电容器具有 动态特性，会随时间漏电，导致数据丢失，因此需要 定期刷新（通常每几毫秒）以恢复电荷。

DRAM 和 SRAM 的存储阵列在宏观上类似，都采用二维矩阵结构，通过字线和位线实现随机访问，主要区别在于基本存储单元的不同：

它以低成本和高容量著称，主要用于 计算机主内存（如系统 RAM）、显卡内存等。

SRAM 和 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 和 CDMROM 这两种：

ERPOM 可以通过紫外线照射来擦除数据，然后重新写入数据。写入数据和擦除数据都较为繁琐，且需要物理操作。常用作电脑的 BIOS 芯片，支持随机存取。

CDROM 是一种光盘存储设备，数据在生产时一次性写入，不能被修改（只能读取）。

2 - 内存

DRAM 芯片

DRAM 芯片是一种动态随机存取存储器，通过 1T1C（1 晶体管 +1 电容器）存储单元以行列矩阵形式组织数据，依靠电容器电荷存储比特，需定期刷新以防止数据丢失。其高容量、低成本特性使其广泛用于计算机主内存。

刷新方式

DRAM 的刷新方式包括：

• 集中刷新（Burst Refresh），暂停数据访问，在短时间内快速 刷新所有行，效率高但延迟大；
• 分散刷新（Distributed Refresh），将刷新操作均匀分布在时间段内，与正常访问交错，延迟小但控制复杂；
• 异步刷新（Asynchronous Refresh），由外部控制器根据需要触发刷新，灵活但依赖控制器设计。

这些刷新方式的具体对比如下表所示：

多模块存储器

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

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

单体多字存储器

按同一地址码并行地访问各自对应单元，每一个单元为一个字，每字 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 - 外存

机械硬盘

机械硬盘（Hard Disk Drive, HDD）是一种使用磁性存储介质来存储和读取数据的非易失性存储设备，广泛应用于计算机和数据存储系统中。

存储区域

为了理解机械硬盘是如何存储数据的，需要理解如下概念：

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

CHS 地址

当磁盘驱动器访问磁盘中的扇区时，需要根据 CHS 地址（Cylinder-Head-Sector Address，柱面 - 磁头 - 扇区地址）定位到特定的扇区。 CHS 地址可以理解为盘块在磁盘中的编号，它通过以下三个字段来唯一标识磁盘上的一个扇区：

• 柱面号（Cylinder Number）：目标扇区在哪一个柱面上 $$\text{\small 柱面号位数} =\lceil log_2 \text{\small（柱面数量）} \rceil$$

• 磁头号：目标扇区在哪一个盘面上 $$\text{\small 磁头号位数} =\lceil log_2 \text{\small（盘面数量）} \rceil$$

• 扇区号：目标扇区具体是磁道中的哪一个扇区 $$\text{\small 扇区号位数} =\lceil log_2 \text{\small（磁道中的扇区数量）} \rceil$$

示例

假设一个磁盘有 1000 个柱面、4 个盘面、32 个扇区/磁道：

• 柱面号位数：$\lceil \log_2(1000) \rceil \approx \lceil 9.97 \rceil = 10$ 位
• 磁头号位数：$\lceil \log_2(4) \rceil = 2$ 位
• 扇区号位数：$\lceil \log_2(32) \rceil = 5$ 位
• CHS 地址总位数：$10 + 2 + 5 = 17$ 位

通过 CHS 地址（例如，C=500, H=2, S=15），磁盘驱动器可以精确定位到特定扇区。

性能指标

平均存取时间

平均存取时间是磁盘完成一次读写操作的平均耗时，由寻道时间（Seek Time）、旋转延迟（Rotational Latency）和传输时间（Read/Write Time）这三部分构成：

• 寻道时间：磁头从当前位置移动到目标磁道所需的时间，通常与磁头移动距离和致动器性能有关。
• 旋转延迟：盘片旋转使目标扇区到达磁头下方所需的时间，通常为盘片旋转半圈的平均时间，取决于转速。
• 传输时间：读取或写入目标扇区数据的实际时间，与扇区大小和数据传输率相关。

平均存取时间的计算公式为：

$$\text{\small 平均存取时间} = \text{\small 寻道时间} + \text{\small 旋转延迟时间} + \text{\small 传输时间}$$

数据传输率

数据传输率表示磁盘每秒向主机传输数据的字节数，反映硬盘的读写速度。假设磁盘转速为 $r$ 传/秒，每条磁道容量为 $N$ 字节，则数据传输率 $D_r$ 为：

$$D_{r} = rN$$

RAID

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

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

RAID 的实现涉及以下核心技术：

• 磁盘镜像：将相同数据写入多块磁盘，提高可靠性。典型如 RAID1。
• 条带化：将数据分段交叉存储在多个磁盘上，提升性能。典型如 RAID0，但不具备容错能力。
• 奇偶校验：通过冗余校验位在部分磁盘损坏时重建数据，兼顾可靠性与存储效率。用于 RAID3/5/6。
• Cache 机制：提高读写性能，但本身不增加可靠性，除非使用掉电保护的写缓存。

常见 RAID 等级如 RAID1（镜像）、RAID5（条带化 + 奇偶校验）、RAID6（双重奇偶校验）等在性能与容错能力之间做出不同权衡。

固态硬盘

固态硬盘（Solid State Drive, SSD）是一种使用闪存（NAND Flash）作为存储介质的非易失性存储设备，与传统机械硬盘（HDD）相比，SSD 在性能、耐用性和能效等方面具有显著优势。SSD 具备以下特点：

• 无机械部件：SSD 没有旋转盘片、磁头或机械臂等移动部件，它使用闪存存储芯片来存储数据。这意味着它不会受到机械故障的威胁，具有更高的耐用性。
• 更快的读写速度：SSD 的读写速度远远超过传统的机械硬盘，因为数据可以立即访问，无需等待盘片旋转和磁头寻道。这使得计算机启动更快，应用程序响应更迅速。
• 低访问时间：由于 没有机械延迟，SSD 的访问时间极低，通常在微秒级别。这有助于加快文件读取和数据检索。
• 长寿命：虽然每个存储单元有写入次数的限制，但现代 SSD 使用错误检查和纠正（ECC）技术，以延长其寿命，并且通常拥有较长的保修期。
• 无碎片化：SSD 的数据存储方式基于闪存单元，读取速度不受数据物理位置的影响，因此不会像 HDD 那样因数据碎片化而降低性能。
• 局限性：
  • 容量限制：SSD 的高容量型号（例如 4TB 以上）价格昂贵，而 HDD 在大容量存储上更具优势。
  • 写入寿命有限：尽管现代技术已大幅延长寿命，但重度写入场景下仍需关注寿命问题。

机械和固态硬盘对比

以下是从多个维度对 SSD 和 HDD 进行的详细对比：

4 - Cache

cache 原理

缓存是一种临时存储数据的硬件或软件组件，旨在加快后续对该数据的访问速度。当您请求数据时，计算机会先检查缓存中是否存在该数据。如果存在（称为“缓存命中”，Cache Hit），则可以直接从缓存中获取数据，而无需访问内存，从而节省时间和资源。如果缓存中不存在该数据（称为“缓存未命中”，Cache Miss），则需要从内存获取数据，并将其存储在缓存中，以备将来使用。

cache 工作原理

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

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

时间局部性

如果一个数据项被访问，那么它在不久的将来很可能再次被访问。

这种特性常见于循环结构和频繁访问的变量，例如循环中的计数器或者经常读取的配置值。

在缓存设计中，利用时间局部性意味着一旦数据被加载到缓存中，它应该在那里保留一段时间，因为很可能很快会再次需要它。

空间局部性

如果一个数据项被访问，那么存储在其附近的数据项也很可能在不久的将来被访问。

这种特性在数组遍历或结构体访问时尤为明显，因为这些数据元素通常在内存中是连续存储的。

利用空间局部性的缓存设计会在访问一个数据项时，同时把它附近的数据也加载到缓存中，因为这些数据很可能在接下来的操作中被用到。

cache 概念

• cache 行（cache line）：cache 行中包含 各种标记字段（flag）和 数据（cache 块）
• 缓存块（cache 块）：cache 中的一块存储空间，是与主存进行数据交换的基本单元
• 主存块：主存中的一块存储空闲，主存块的大小一般与 cache 块一致
• 块内偏移：某一个地址在块内的偏移，找到对应的块后，通过块内偏移找到改地址的具体位置
• 块大小：用于判断块内偏移的位数，比如$1024 = 2^{10}$，所以 1KB 的块对应的块内偏移位数为 10

缓存块

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

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

cache 中的存储空间可以被分为若干个 cache 块，主存也可以被分为若干个主存块，主存和 cache 间的数据置换是以 块 为基本单位的。 这可以和页式内存进行类比，虚拟内存和物理内存都被分为若干个页面，物理内存空间的置换以 页面 为基本单位。

缓存块的大小？

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

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

cache 和主存映射方式

直接映射

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

假设主存块的数量为 N，cache 块的数量为 M。 那么第 k 个主存块对应的 cache 块号为 k % M。

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

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

全相联映射

在全相联缓存（full associative）中，主存中的任何块可以映射到缓存中的任何缓存块。

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

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

组相联映射

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

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

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

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

上图是一个二路组相连的硬件结构概要图，通过物理地址中的组号（index）找当 cache 中的相应组。然后再用标记字段（tag）去与组中每个 cache 块进行匹配，并检查 valid 字段是否设置为 1，如果符合以上条件的话则通过二路选择器输出 cache 块中的内容。

映射方式对比

假设 cache 有 M 个 cache 块，对于块号为 k 的主存块：

• 直接映射：被映射到块号 k % M 的 cache 块
• 全相连映射：可能被映射到任意一个 cache 块
• 组相连映射：对于 m 路组相连，被映射到组号为 k % (M / m) 的 cache 组中的任意一个 cache 块

cache 地址结构

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

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

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

cache 存储结构

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

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

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

cache 中的块替换算法

块替换算法适用于全相联映射和组相联映射，因为一个主存块可能被多个 cache 块中的某一个 所缓存。但是在直接映射方式中不存在替换算法，因为一个主存块只可能被一个 cache 块所缓存，如果需要替换的话直接替换对应的 cache 块就行。

cache 块替换的过程如下：

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

当我们访问一个物理地址时未命中时，需要将对应的主存块加载到 cache 中，如果这个该主存块对应的 cache 块都满了的话，就需要替换掉其中的某个 cache 块，替换算法包含 FIFO、LRU 和 LFU 等。 这里的具体思想与操作系统中的页面置换算法一致，请参考页面置换算法

cache 写策略

因为 cache 实际上存储的是主存的一个小副本，所以对于写操作，就需要考虑两者间的数据一致性的问题。

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

命中时

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

• 直写法（Write Through）：
  • 每次写操作都会同时更新缓存和主存。
  • 这种写策略是 同步的，每次更新缓存时要同步地更新主存。
• 回写法 （Write Back）
  • 当数据被修改时，它首先被缓存在 cache 中，只有当 cache 块被替换时才写入对应的主存块。
  • 这种写策略是 异步的，并不是写入 cache 后立马就要写入主存，可以多次写入 cache 后在另一个时刻再将 cache 块写入主存。

未命中时

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

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

策略的组合

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

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

5 - 虚拟存储器

虚拟存储器

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

物理内存

物理内存（Physical Memory）指的是计算机系统中的实际硬件内存，即随机存取存储器（RAM）。 物理内存是计算机直接用于存储和操作数据的地方，所有进程的数据和代码实际上都是存储在物理内存上。

虚拟内存

虚拟内存（Virtual Memory）是一种计算机系统内存管理技术，它使得进程可以认为自己拥有一个连续且独立的内存空间， 即使实际上物理内存可能不够用或者是分散的。

进程使用虚拟地址来访问内存中的数据和指令，而不需要了解物理内存的详细情况。 进程使用虚拟地址去访问虚拟内存， 当进程访问虚拟内存时，操作系统会将虚拟地址转化为物理地址， 进而根据物理地址去访问物理内存。

页式虚拟存储器

将虚拟地址空间和物理地址空间都划分为固定大小的块，称为“页”（Page）。 程序运行时，操作系统只将部分页面加载到物理内存中，其余页面保存在硬盘上。 当程序访问不在物理内存中的页面时，会发生缺页中断，操作系统负责将所需的页面从硬盘加载到物理内存，并替换掉暂时不用的页面。

页面划分和地址结构

在页式虚拟存储器中，虚拟内存空间被划分为一个个虚拟页面（VP，Virtual Page），物理内存空间被划分为一个个物理页面（PP，Physical Page）。

虚拟地址（VA, Virutal Address）被划分为 虚拟页面号（VPN，Virutal Page Number）和 页内偏移（Offset）这两个字段。

在使用虚拟地址去访问虚拟内存时，我们可以根据虚拟页面号找到该地址所在的虚拟页面，在找到虚拟页面后，我们可以根据页内偏移找到该地址在虚拟页面内的偏移大小。

同理， 物理地址（PA, Physical Address）被划分为 物理页面号（PPN，Physical Page Number）和 页内偏移（Offset）这两个字段。

在使用物理地址去访问虚拟内存时，我们可以根据物理页面号找到该地址所在的物理页面，在找到物理页面后，我们可以根据页内偏移找到该地址在物理页面内的偏移大小。

地址翻译机构

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）：地址在页面内的偏移

其中 VPO = PPO = offset，页面大小 = $2^{\text{offset}}$

虚拟页面个数 = $2^{\text{VPN}}$，物理页面个数 = $2^{\text{PPN}}$

地址翻译过程

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

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

举一个实际 例子 说明一下：

假设虚拟内存为 16MB，物理内存为 1MB，页面大小为 4KB，则翻译虚拟地址0x321654

• VPO 和 PPO 的位数为 12（$4\text{ KB} = 2^{12}\text{B}$），地址对应的 page offset 为0x654
• 虚拟地址的总位数为 24（$16\text{ MB} = 2^{24}\text{B}$）
• 物理地址的总位数为 20（$1\text{ MB} = 2^{20}\text{B}$）
• VPN 的位数为 24 - 12 = 12，虚拟地址对应的 VPN 为0x321
• PPN 的位数为 20 - 12 = 8，
• 虚拟地址格式为 | VPN (12bits) | VPO (12bits) |
• 物理地址格式为 | PPN ( 8bits) | PPO (12bits) |
• VPN 为0x321，找到页表的第0x321个页表项，判断其中的 valid 字段是否为 1，如果为 0，则调用缺页中断，如果为 1，则找到其中的 PPN，并使用 PPN 和 PPO 组成物理地址。

多级页表

单级页表会有什么问题？

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

假如我们有一个 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）中的一种高速缓存，用于加速 虚拟地址（VA）到 物理地址（PA）的地址转换过程。 TLB 存储了最近用过的虚拟地址到物理地址的映射，以减少每次内存访问时的地址翻译延迟。

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

存储结构

TLB 是一个硬件结构，但从逻辑上可以将其理解为一张表。

与 cache 存储结构 类似， TLB 由许多表项（TLB Entry）构成，每一个表项包含多个字段，其中 tag 和 PPN 是必须的，其他字段是可选的。

TLB 和 cache 对比

TLB 和页表的关系类似于 cache 与主存的关系，TLB 和 cache 都是一个硬件结构，不过两者发挥作用的场合不同。TLB 和 Cache 的区别如下表所示：

TLB 中也包含三种映射方式：直接映射、全相联映射、组相联映射。

在访问 TLB 时，虚拟地址中虚拟页号（VPN）被按照映射方式进行不同的切分。在访问 cache 时，物理地址中的主存块号被按照映射方式进行不同的切分。

两者的对比如下所示：

在直接映射中，通过 TLB 行号去对应行的表项进行查询。

在组相联映射中，通过 TLB 组号去对应组进行查询（遍历组中的所有 TLB 表项）。

在全相联映射中，遍历 TLB 中的所有表项。

地址结构

当我们在通过 TLB 进行 虚拟页号（VPN）→ 物理页号（PPN）的翻译时，访问 TLB 需要使用到 VPN。 从逻辑上而言，VPN 可以被分为 标记 和 匹配字段这两个部分：

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