存储器层次结构

存储器概述

基本术语：

• 记忆单元/存储基元/存储元/位元（Cell）
  • 具有两种稳态的能够表示二进制数码 0 和 1 的物理器件
• 存储单元/编址单位（Addressing Unit）
  • 具有相同地址的位构成一个存储单元，也称为一个编址单位
• 存储体/存储矩阵/存储阵列（Bank）
  • 所有存储单元构成一个存储阵列
• 编址方式（Addressing Mode）
  • 按字节编址、按字编址
• 存储器地址寄存器（Memory Address Register, MAR）
  • 用于存放主存单元地址的寄存器
• 存储器数据寄存器（Memory Data Register, MDR/MBR）
  • 用于存放主存单元中的数据的寄存器

按工作性质/存取方式分类：

• 随机存取存储器 Random Access Memory (RAM)
  • 按地址访问，每个单元读写时间一样，且与各单元所在位置无关。如：内存。
  • 原意主要强调地址译码时间相同。现在的 DRAM 芯片采用行缓冲，因而可能因为位置不同而使访问时间有所差别。
• 顺序存取存储器 Sequential Access Memory (SAM)
  • 数据按顺序从存储载体的始端读出或写入，因而存取时间的长短与信息所在位置有关。例如：磁带。
• 直接存取存储器 Direct Access Memory (DAM)
  • 直接定位到读写数据块，在读写数据块时按顺序进行。如磁盘。
• 相联存储器 Associate Memory (AM)，Content Addressed Memory (CAM)
  • 按内容检索到存储位置进行读写。例如：快表。

按存储介质分类：

• 半导体存储器：双极型，静态 MOS 型，动态 MOS 型
• 磁表面存储器：磁盘（Disk）、磁带 （Tape）
• 光存储器：CD，CD-ROM，DVD

按信息的可更改性分类：

• 读写存储器（Read/Write Memory)：可读可写
• 只读存储器（Read Only Memory)：只能读不能写

按断电后信息的可保存性分类：

• 非易失（不挥发）性存储器（Nonvolatile Memory）
  • 信息可一直保留， 不需电源维持。
  • 如 ：ROM、磁表面存储器、光存储器等
• 易失（挥发）性存储器（Volatile Memory）
  • 电源关闭时信息自动丢失。（如：RAM、Cache 等）

按功能/容量/速度/所在位置分类：

• 寄存器（Register）
  • 封装在 CPU 内，用于存放当前正在执行的指令和使用的数据
  • 用触发器实现，速度快，容量小（几 ~ 几十个）
• 高速缓存（Cache）
  • 位于 CPU 内部或附近，用来存放当前要执行的局部程序段和数据
  • 用 SRAM 实现，速度可与 CPU 匹配，容量小（几 MB）
• 主存储器 MM（Main (Primary) Memory）
  • 位于 CPU 之外，用来存放已被启动的程序及所用的数据
  • 用 DRAM 实现，速度较快，容量较大（几 GB）
• 外存储器 AM （辅助存储器 Auxiliary/Secondary Storage）
  • 位于主机之外，用来存放暂不运行的程序、数据或存档文件
  • 用磁表面或光存储器实现，容量大而速度慢

内存与外存的关系及其比较：

• 外存储器（外存/辅存）
  • 存取速度慢
  • 成本低、容量很大
  • 不与 CPU 直接连接，先传送到内存，然后才能被 CPU 使用。
  • 属于非易失性存储器，用于长久存放系统中几乎所有的信息
• 内存储器（内存/主存）
  内存储器（简称内存或主存）
  • 存取速度快
  • 成本高、容量相对较小
  • 直接与 CPU 连接，CPU 对内存中可直接进行读、写操作
  • 属于易失性存储器（volatile），用于临时存放正在运行的程序和数据

主存的结构：

指令执行过程中需要访问主存时，CPU 首先把被访问单元的地址送到主存地址寄存器（MAR）中，然后通过地址线将主存地址送到主存中的地址寄存器，以便地址译码器进行译码，选中相应单元，同时，CPU 将读/写信号通过控制线送到主存的读写控制电路。

1. 如果是写操作，CPU 同时将要写的信息送主存数据寄存器（MDR）中，在读写控制电路的控制下，经数据线将信息写入选中的单元；
2. 如果是读操作，则主存读出选中单元的内容送数据线，然后被送到 MDR 中。

数据线的宽度与 MDR 的宽度相同，地址线的宽度与 MAR 的宽度相同

主存的主要性能指标：

• 按字节连续编址，每个存储单元为 1 个字节（8 个二进位）
• 存储容量：所包含的存储单元的总数（单位：MB 或 GB）
• 存取时间 $T_{\mathrm{A}}$：从 CPU 送出内存单元的地址码开始，到主存读出数据并送到 CPU（或者是把 CPU 数据写入主存）所需要的时间（单位：ns）
  • 分读取时间和写入时间
• 存储周期 $T_{\mathrm{MC}}$：连读两次访问存储器所需的最小时间间隔，它应等于存取时间加上下一次存取开始前所要求的附加时间
  • 因此，$T_{\mathrm{MC}}$ 比 $T_{\mathrm{A}}$ 大
  • 因为存储器由于读出放大器、驱动电路等都有一段稳定恢复时间，所以读出后不能立即进行下一次访问。
  • 就像一趟火车运行时间和发车周期是两个不同概念一样。

为了缩小存储器和处理器两者之间在性能方面的差距，通常在计算机内部采用层次化的存储器体系结构：

• 速度越快，容量越小，越靠近 CPU。
• CPU 可以直接访问内部存储器；而外部存储器信息要先被取到主存，再被 CPU 访问。
• 数据一般只在相邻层之间复制传输，而且总是从慢速存储器复制到快速存储器。

半导体随机存取存储器

六管静态 MOS 管存储元件

非破坏性读出。

信息存储原理：看作带时钟的 RS 触发器。

• 保持时：
  • 字线为 0（低电平）
• 写入时：
  • 位线上是被写入的二进位信息 0 或 1
  • 置字线为 1
  • 存储单元(触发器)按位线的状态设置成 0 或 1
• 读出时：
  • 置 2 个位线为高电平
  • 置字线为 1
  • 存储单元状态不同，位线的输出不同

单管动态 MOS 存储元件

读写原理：字线上加高电平，使 T 管导通。

• 写「0」时，数据线加低电平，使 $\mathrm{C_S}$ 上电荷对数据线放电；
• 写「1」时，数据线加高电平，使数据线对 $\mathrm{C_S}$ 充电；
• 读出时，数据线上有一读出电压。它与 $\mathrm{C_S}$ 上电荷量成正比。

优缺点：

• 优点：电路元件少，功耗小，集成度高，用于构建主存储器
• 缺点：速度慢、是破坏性读出（需读后再生）、需定时刷新

刷新：DRAM 的一个重要特点是，数据以电荷的形式保存在电容中，电容的放电使得电荷通常只能维持几十个毫秒左右，相当于 1M 个时钟周期左右，因此要定期进行刷新（读出后重新写回），按行进行（所有芯片中的同一行一起进行），刷新操作所需时间通常只占 1% ~ 2% 左右。

静态存储元件与动态存储元件比较

• 静态存储元件（SRAM）：
  • MOS 管多，功耗大，集成度低；
  • 可保持记忆状态，无须刷新；
  • 读写速度快；
  • 价格昂贵。
• 动态存储元件（DRAM）：
  • MOS 管少，功耗小，集成度高；
  • 必须定时刷新；
  • 读写速度慢；
  • 价格较低。

SRAM 芯片和 DRAM 芯片

存储器芯片由存储体、I/O 读写电路、地址译码和控制电路等组成。

• 存储体/存储矩阵：存储单元的集合；
• 地址译码器：将地址转换为译码输出线上的高电平；
• 驱动器：X 选择线负载大，所以加驱动器；
• I/O 控制电路：控制被选中单元的读/写，有放大信息的作用；
• 片选信号：选中某个芯片
• 读/写控制信号：控制被选中单元进行读或写。

存储体阵列组织*

字片式存储体阵列组织

位片式存储体阵列组织

CPU 与存储器之间的通讯方式

• 异步方式（读操作）过程（需握手信号）
  • CPU 送地址到地址线，主存进行地址译码
  • CPU 发读命令，然后等待存储器发回「完成」信号
  • 主存收到读命令后开始读数，完成后发「完成」信号给 CPU
  • CPU 接收到「完成」信号，从数据线取数
  • 写操作过程类似
• 同步方式的特点
  • CPU 和主存由统一时钟信号控制，无需应答信号（如「完成」）
  • 主存总是在确定的时间内准备好数据
  • CPU 送出地址和读命令后，总是在确定的时间取数据
  • 存储器芯片必须支持同步方式

SDRAM 芯片技术

SDRAM 是同步存储芯片，每步操作都在系统时钟控制下进行，有确定的等待时间。

同步方式：

• DDR SDRAM：双倍数据速率同步动态随机存取存储器，每个时钟内传送两个数据
• DDR2 SDRAM：双倍数据速率第二代同步动态随机存取存储器，每个时钟内传送四个数据
• DDR3 SDRAM：双倍数据速率第三代同步动态随机存取存储器，每个时钟内传送八个数据

内存条和内存条插槽

• 内存条：把若干片 DRAM 芯片焊装在一小条印制电路板上制成
• 内存条插槽：存储器总线

内存条必须插在主板上的内存条插槽中才能使用（相同颜色插槽可以并行传输）。

存储器控制器、存储器总线、内存条、DRAM 芯片之前的连接：

存储器芯片的扩展

• 字扩展（位数不变、扩充容量）
  • 用 16K $\times$ 8 位芯片扩成 64K $\times$ 8 位存储器需几个芯片？地址范围各为什么？
    • 字方向扩展 4 倍，即 4 个芯片。0000-3FFFH, 4000-7FFFH, 8000-BFFFH, C000-FFFFH，地址共 16 位，高两位由外部译码器译码生成 4 个输出，分别连到 4 个片选信号，片内地址有 14 位
  • 地址线、读/写控制线等对应相接，片选信号连译码输出
• 位扩展（字数不变，位数扩展）
  • 用 4096 $\times$ 1 位芯片构成 4K $\times$ 8 位存储器需几个芯片？地址范围各是多少？
    • 位方向扩展 8 倍，字方向无需扩展。即 8 个芯片，地址范围都一样：000-FFFH，地址共 12 位，全部作为片内地址
  • 芯片的地址线及读/写控制线对应相接，而数据线单独引出
• 字位同时扩展（字和位同时扩展）
  • 用 16K $\times$ 4 位芯片构成 64K $\times$ 8 位存储器需几个芯片，地址范围各是多少？
    • 字向 4 倍、位向 2 倍，8 个芯片。0000-3FFFH, 4000-7FFFH, 8000-BFFFH, C000-FFFFH
  • 地址线、读/写控制线等对应相接，片选信号则分别与外部译码器各个译码输出端相连

有两种容量扩展方式：交叉编址和连续编址。上述例子都是连续编址。

DRAM 芯片的扩展：

• 由 8 片 DRAM 芯片构成
• 每片 16Mx8 bits
• 行地址、列地址各 12 位
• 每行共 4096 列（8 位/列）
• 选中某一行并读出之后，再由列地址选择其中一列送出

一个 32 位 int 型数据若存放在 8 ~ 11 这 4 个单元，则需要访问 1 次内存；若放在 6 ~ 9 这 4 个单元，则需要访问 2 次内存。因此数据要对齐存放。

主存地址 27 位，片内地址 24 位，与高 24 位主存地址相同。主存低 3 位地址的作用是确定 8 个字节中的哪个，即用来「选片」。

芯片内地址不连续，交叉编址，可同时读写所有芯片。

若要片内地址连续，则地址 A 应该这样划分：高 3 位为片选信号，中 12 位为行地址，低 12 位为列地址。

内部结构：

多模块存储器

多模块技术，即多个存储器同时工作。

双口存储器（能同时进行两个数据的读/写）：两套独立的读/写控制电路、地址缓存、地址译码及地址线和数据线， 通常作为双口 RAM 或指令预取部件。

多模块存储器：

• 包含多个小体；
• 每个体有其自己的 MAR、MDR 和读写电路；
• 可独立组成一个存储模块；
• 可同时对多个模块进行访问。

根据不同的编址方式可分为：连续编址、交叉编址。

连续编址方式：

在连续编址的多模块主存储器中，主存地址的高位表示模块号（体号），低位表示模块内地址（体内地址），地址在模块内连续。

编址方式下，总是把低位的体内地址送到由高位体号所确定的模块内进行地址译码。

对于连续编址的多模块主存储器，当访问一个连续主存块时，总是先在一个模块内访问，等到该模块全部单元访问完才转到下一个模块访问，因而这种情况下不能提高存储器的吞吐率。

交叉编址方式：

在交叉编址的多模块存储器中，主存地址的低位表示模块号，高位表示模块内地址。

交叉编址方式下，总是把高位的体内地址送到由低位体号所确定的模块内进行译码。

交叉编制方式：轮流启动、同时启动

• 每个存储模块一次读写的位数（即存储字）正好等于存储器总线中的数据位数（即总线传输单位），则采用轮流启动方式；
• 具有 m 个体的多模块存储器，每隔 1/m 个存储周期启动一个体；
• 存取速度提高 m 倍。

如果所有存储模块一次并行读写的总位数正好等于存储器总线中的数据位数，则可以采用同时启动方式。

外部辅助存储器

磁盘存储器

磁盘存储器的信息存储原理：

磁盘的磁道和扇区：

磁盘的内部逻辑结构

磁盘读写的三个步骤：

1. 寻道：磁盘控制器把磁盘地址送到磁盘驱动器的磁盘地址寄存器后，便产生寻道命令，以启动磁头定位伺服系统根据柱面号移动磁头到指定的柱面（磁道），并选择指定的磁头准备进行读写。此操作完成后，发出寻道结束信号给磁盘控制器，并转入旋转等待操作。
2. 旋转等待：盘片旋转开始时，首先将扇区计数器清零，以后每来一个扇区标志脉冲，扇区计数器加 1，把计数内容与磁盘地址寄存器中的扇区号进行比较，如果一致，则输出扇区符合信号，说明要读写的信息已经转到磁头下方。
3. 读写：扇区符合信号送给磁盘控制器后，磁盘控制器的读写控制电路开始动作。如果是写操作，就将数据送到写入电路，写入电路根据记录方式生成相应的写电流脉冲；如果是读操作，则由读出放大电路读出内容送磁盘控制器。

寻道操作：

旋转等待操作：

读写操作：

温切斯特磁盘的磁道记录格式：

磁盘存储器的性能指标

记录密度：

提高盘片上的信息记录密度：

• 增加磁道数目：提高磁道密度
• 增加扇区数目：提高位密度，并采用可变扇区数

存储容量指整个存储器所能存放的二进制信息量，它与磁表面大小和记录密度密切相关。

磁盘的未格式化容量是指按道密度和位密度计算出来的容量，它包括了可利用的所有磁化单元的总数，未格式化容量（或非格式化容量）比格式化后的实际容量要大。格式化后的实际容量只包含数据区。

低密度存储方式，容量：

• 未格式化：$\text{磁盘总容量} = \text{记录面数} \times \text{理论柱面数} \times \text{内圆周长} \times \text{最内道位密度}$
• 格式化（记录面数约为盘片数的两倍）：$\text{磁盘实际数据容量} = 2 \times \text{盘片数} \times \text{磁道数/面} \times \text{扇区数/磁道} \times 512 \text{B/扇区}$。
  • 早期扇区大小为 512 字节，现在为 4096 字节，即 4K 扇区。

数据传输速率：单位时间内从存储介质上读出或写入的二进制信息量。

平均存取时间为 $T = \text{平均寻道时间} + \text{平均旋转等待时间} + \text{数据传输时间}$：

• 平均寻道时间：磁头寻找到指定磁道所需平均时间（大约 5ms）
• 平均旋转等待时间：指定扇区旋转到磁头下方所需平均时间，取磁盘旋转一周所需时间的一半（大约 4~6ms）（转速：4200/5400/7200/10000rpm）
• 数据传输时间：（大约 0.01ms/扇区）

操作流程：

1. 所有磁头同步寻道（由柱面号控制）
2. 选择磁头（由磁头号控制）
3. 被选中磁头等待
4. 扇区到达磁头下方（由扇区号控制）
5. 读写该扇区中数据

磁盘存储器的链接

磁盘的「最小读写单位」是扇区。

因此，磁盘按成批数据交换方式进行读写，采用「直接存储器存取」（DMA, Direct Memory Access）方式进行数据输入输出，需用专门的 DMA 接口来控制外设与主存间直接数据交换，数据不通过 CPU。

通常把专门用来控制总线进行 DMA 传送的接口硬件称为 DMA 控制器。

冗余磁盘阵列

RAID（Redundant Array of Independent Disks）技术，即磁盘冗余阵列。

RAID 基本思想：将多个独立操作的磁盘按某种方式组织成「磁盘阵列」（Disk Array），以增加容量，利用类似于主存中的多体交叉技术，将数据存储在多个盘体上，通过使这些盘并行工作来提高数据传输速度，并用「冗余」（redundancy） 磁盘技术来进行「错误恢复」（error correction）以提高系统可靠性。

特性：

1. RAID 是一组物理磁盘驱动器，在操作系统下被视为一个单逻辑驱动器。
2. 数据分布在一组物理磁盘上。
3. 冗余磁盘用于存储「奇偶校验」信息，保证磁盘万一损坏时能恢复数据。

RAID 级别：目前已知的 RAID 方案分为 8 级（0~7 级），以及 RAID 10（结合 0, 1 级）、RAID 30（结合 0, 3 级）、RAID 50（结合 0, 5 级）等。

RAID 0

不遵循特性 3，无冗余，适用于容量和速度要求高的非关键数据存储的场合。

与单个大容量磁盘相比，RAID 0 的优势在于：

1. 连续分布或大条区交叉分布时，如果两个 I/O 请求访问不同盘上的数据，则可并行发送。减少了 I/O 排队时间。具有较快的 I/O 响应能力。
2. 小条区交叉分布时，同一个 I/O 请求有可能并行传送其不同的数据块（条区），因而可达较高的数据传输率。例如，可以用在视频编辑和播放系统中，以快速传输视频流。

RAID 0 级阵列的数据映射：

RAID 1

镜像盘实现一对一冗余（100% redundancy）：

1. 读：一个读请求可由其中一个定位时间更少的磁盘提供数据。
2. 写：一个写请求对对应的两个磁盘并行更新。故写性能由两次中较慢的一次写来决定，即定位时间更长的那一次。
3. 检错：数据恢复简单。当一个磁盘损坏时，数据仍能从另一个磁盘读取。

特点：可靠性高，但价格昂贵。常用于可靠性要求很高的场合，如系统软件的存储，金融、证券等系统。

RAID 1 级阵列的数据映射：

RAID 2

用「海明校验法」生成多个冗余校验盘，实现纠正一位错误、检测两位错误的功能。

采用条区交叉分布方式，且条区非常小（有时为一个字或一个字节）。这样，可获得较高的数据传输率，但 I/O 响应时间差。

采用海明码，虽然冗余盘的个数比 RAID1 少，但校验盘与数据盘成正比。所以冗余信息开销太大，价格贵。读操作性能高（多盘并行）。写操作时要同时写数据盘和校验盘。

RAID 2 已不再使用，因为冗余信息开销太大，价格较贵。

RAID 2 级阵列的数据映射：

RAID 3

采用奇偶校验法生成单个冗余盘。

与 RAID 2 相同，也采用条区交叉分布方式，并使用小条区。这样，可获得较高的数据传输率，但 I/O 响应时间差。

用于大容量的 I/O 请求的场合，如：图像处理、CAD 系统中。

某个磁盘损坏但数据仍有效的情况，称为简化模式。此时损坏的磁盘数据可以通过其它磁盘重新生成。数据重新生成非常简单，这种数据恢复方式同时适用于 RAID 3、4、5 级。

RAID 3 级阵列的数据映射：

RAID 4

用一个冗余盘存放相应块（块：较大的数据条区）的奇偶校验位。

采用独立存取技术，每个磁盘的操作独立进行，所以，可同时响应多个 I/O 请求。因而它适合于要求 I/O 响应速度块的场合。

对于写操作，校验盘成为 I/O 瓶颈，因为每次写都要对校验盘进行。

• 少量写（只涉及个别磁盘）时，有「写损失」，因为一次写操作包含两次读和两次写。
  • 两次读：读原数据和读校验位
  • 两次写：写新数据和写新校验位
• 大量写（涉及所有磁盘的数据条区）时，则只需直接写入奇偶校验盘和数据盘。因为奇偶校验位可全部用新数据计算得到，而无须读原数据。

RAID 4 级阵列的数据映射：

RAID 5

与 RAID 4 的组织方式类似，只是奇偶校验块分布在各个磁盘中。

所以，所有磁盘的地位等价，这样可提高容错性，并且避免了使用专门校验盘时潜在的 I/O 瓶颈。

与 RAID 4 一样，采用独立的存取技术，因而有较高的 I/O 响应速度。

小数据量的操作可以多个磁盘并行操作。

成本不高但效率高，所以，被广泛使用。

RAID 5 级阵列的数据映射：

RAID 6

冗余信息均匀分布在所有磁盘上，而数据仍以块交叉方式存放。

「双维块交叉奇偶校验」独立存取盘阵列，容许双盘出错。

它是对 RAID 5 的扩展，主要是用于要求数据绝对不能出错的场合。

由于引入了第二种奇偶校验值，对控制器的设计变得十分复杂，写入速度也比较慢，用于计算奇偶校验值和验证数据正确性所花费的时间比较多。

RAID 6 级以增大开销的代价保证了高度可靠性。

RAID 6 级阵列的数据映射：

$P_0$ 代表第 0 条区的奇偶校验位，$P_A$ 代表数据块 A 的奇偶校验位。

RAID 7

在 RAID6 的基础上，采用 Cache 技术使传输率和响应速度都有较大提高

Cache 分块大小和磁盘阵列中数据分块大小相同，一一对应。

有两个独立的 Cache，双工运行。在写入时将数据同时分别写入两个独立的 Cache，这样即使其中有一个 Cache 出故障，数据也不会丢失。

• 写入磁盘阵列以前，先写入 Cache 中。同一磁道的信息在一次操作中完成。
• 读出时，先从 Cache 中读出，Cache 中没有要读的信息时，才从 RAID 中读。

Cache 和 RAID 技术结合，弥补了 RAID 的不足（如：分块的写请求响应性能差等），从而以高效、快速、大容量、高可靠性，以及灵活方便的存储系统提供给用户。

Flash 存储器和 U 盘

只读存储器 ROM (Read-Only Memory)：

• MROM（Mask ROM）：掩膜只读存储器
• PROM（Programmable ROM）：可编程只读存储器
• EPROM（Erasable PROM ）：可擦除可编程只读存储器
• EEPROM（E2PROM, Electrically EPROM）：电可擦除可编程只读存储器
• Flash Memory（闪存，快擦存储器）：快擦型电可擦除重编程 ROM

Flash 存储元：

1. 控制栅加足够正电压时，浮空栅储存大量负电荷，为 0 态；
2. 控制栅加足够负电压时，浮空栅少带或不带负电荷，为 1 态。

三种操作：

1. 擦除：将所有浮空栅置为 1 态
2. 编程：将浮空栅置为 0 态
3. 读取：根据浮空栅的电荷状态判断 0/1 态

• 写入：快擦（所有单元为 1）+ 编程（需要之处写 0）
• 读出：控制栅加正电压，若状态为 0，则读出电路检测不到电流；若状态为 1，则能检测到电流。

Flash 存储器的特点：读快写慢。

固态硬盘

固态硬盘（SSD, Solid State Disk, 亦称为电子硬盘）并不是一种磁表面存储器，而是一种使用 NAND 闪存组成的外部存储系统，与 U 盘并没有本质差别，只是容量更大，存取性能更好。

它用「闪存颗粒」代替了磁盘作为存储介质，利用闪存的特点，以区块写入和抹除的方式进行数据的读取和写入。

写操作比读操作慢得多。

闪存的擦写次数有限，所以频繁擦写会降低其写入使用寿命。

SSD 中一个闪存芯片由若干个「区块」（block）组成，每个区块由若干「页」（page）组成，通常，页大小为 512B~4KiB，每个区块由 32~128 个页组成，因而区块大小为 16KiB~512KiB。数据按页为单位进行读写。

限制：

• 写一个页的信息之前，必须先擦除该页所在的整个区块
• 擦除后区块内的页必须按顺序写入信息
• 只有有限的擦除/编程次数

某一区块进行了几千到几万次重复写之后，就会被磨损而变成坏区块，不能再被使用。

闪存翻译层中有一个专门的均化磨损（wear leveling）逻辑电路，试图将擦除操作平均分布在所有区块上，以最大限度地延长 SSD 的使用寿命。

存储器的数据校验

基本原理

措施：

1. 从计算机「硬件本身的可靠性」入手，在电路、电源、布线等各方面采取必要的措施，提高计算机的抗干扰能力；
2. 采取相应的「数据检错和校正」措施，自动地发现并纠正错误。

大多采用「冗余校验」思想，即除原数据信息外，还增加若干位编码，这些新增的代码被称为校验位。

比较结果：

1. 没有检测到错误，得到的数据位直接传送出去。
2. 检测到差错，并可以纠错。数据位和比较结果一起送入纠错器，将正确数据位传送出去。
3. 检测到错误，但无法确认哪位出错，因而不能进行纠错处理，此时，报告出错情况。

码字和码距

由若干位代码组成的一个字叫码字。

两个码字中具有不同代码的位的个数叫这两个码字间的「距离」。

码制中各码字间最小距离为码距，它就是这个码制的距离。

例如 8421 码中，码距为 1，因为任意两个码字间至少有 1 位不同。

数据校验中「码字」指数据位和校验位按某种规律排列得到的代码。

码距与检错、纠错能力的关系：

• 若能检测 $e$ 位错误，则码距 $d$ 至少为 $e+1$；
• 若能纠正 $t$ 位错误，则码距 $d$ 至少为 $2t+1$。
• 若能同时检测 $e$ 位错误和纠正 $t$ 位错误，则码距 $d$ 至少为 $e+t+1$。

奇偶校验码

基本思想：增加一位奇（偶）校验位并一起存储或传送，根据终部件得到的相应数据和校验位，再求出新校验位，最后根据新校验位确定是否发生了错误。

实现原理（假设数据 $B = b_{n-1}\dots b_0$ 从源部件传送至终部件，在终部件接受到的数据为 $B' = b_{n-1}'\dots b_0'$）：

1. 在源部件求出奇（偶）校验位 $P$
   • 奇校验：$P = b_{n-1} \oplus \dots \oplus b_0 \oplus 1$
   • 偶校验：$P = b_{n-1} \oplus \dots \oplus b_0$
2. 在终部件求出奇（偶）校验位 $P'$
   • 奇校验：$P' = b_{n-1}' \oplus \dots \oplus b_0' \oplus 1$
   • 偶校验：$P' = b_{n-1}' \oplus \dots \oplus b_0'$
3. 计算最终校验位 $P^{*} = P \oplus P'$
   • 若 $P^{*} = 1$，则终部件接受的数据有奇数位错；
   • 若 $P^{*} = 0$，则终部件接受的数据正确或有偶数位错。

奇偶校验码的码距为 2，只能检测 1 位错误，不能纠正错误。

开销小，适用于校验一字节长的代码，故常被用于存储器读写检查或按字节传输过程中的数据校验。因为一字节长的代码发生错误时，1 位出错的概率较大，两位以上出错则很少，所以可用奇偶校验。

海明码

相关的 3B1B 视频。

基本思想：将整个数据按某种规律分成若干组，对每组进行相应的奇偶检测，提供多位检错信息，从而对错误位置进行定位，并将其纠正。

实质上是一种多重奇偶校验码。

最终比较时按位进行异或，以确定是否有差错。这种异或操作所得到的结果称为「故障字」（syndrome word）。显然，校验码和故障字的位数是相同。

每一组一个校验位，校验码位数等于组数，每一组内采用一位奇偶校验。

假设数据位数为 $n$，校验码为 $k$ 位，则故障字位数也为 $k$ 位。$k$ 位故障字所能表示的状态最多为 $2^{k}$，每种状态可用来说明一种出错情况。

若只有一位错误：

1. 数据中某一位错，有 $n$ 种可能
2. 校验码中某一位错，有 $k$ 种可能
3. 无错误，有 1 种可能

因此有

$$2^{k} - 1 \ge n + k$$

基本思想：$n$ 位数据位和 $k$ 位校验位按某种方式排列为一个 $n+k$ 位的码字，将该码字中每个出错位的位置与故障字的数值建立关系，通过故障字的值确定该码字中哪一位发生了错误，并将其取反来纠正。

规则：

1. 若故障字每位全部是 $0$，则表示没有发生错误；
2. 若故障字中有且仅有一位为 $1$，则表示校验位中有一位出错，不需纠正；
3. 若故障字中多位为 $1$，则表示有一个数据位出错，其在码字中的出错位置由故障字的数值来确定，纠错时将出错位取反即可。

以 8 位数据进行单个位检错和纠错为例进行说明。假定数据 $M = M_8 \dots M_1$ 与校验位 $P = P_4 \dots P_1$，按规则将 $M, P$ 按一定的规律排到一个 12 位码字中。

1. 故障字为 0000 时，表示无措；
2. 校验位出错时，故障字只可能是 0001, …, 1000；因此 $P_1, \dots, P_4$ 分别位于码字的第 1, 2, 4, 8 位；

于是码字的排列为：

$$M_8 M_7 M_6 M_5 P_4 M_4 M_3 M_2 P_3 M_1 P_2 P_1$$

采用偶校验，校验位与数据位之间的关系：

$$\left\lbrace\begin{aligned} P_4 &= M_5 \oplus M_6 \oplus M_7 \oplus M_8 \\ P_3 &= M_2 \oplus M_3 \oplus M_4 \oplus M_8 \\ P_2 &= M_1 \oplus M_3 \oplus M_4 \oplus M_6 \oplus M_7 \\ P_1 &= M_1 \oplus M_2 \oplus M_4 \oplus M_5 \oplus M_7 \end{aligned}\right.$$

上述海明码码距为 3，若有一位出错，则因该位至少要参与两组校验位的生成，因而至少引起两个校验位的不同。

这种码制能发现两位错，或对单个位出错进行定位和纠错。这种码称为单纠错码（SEC）。

具有发现两位错和纠正一位错的能力，称为单纠错和双检错码（SEC-DED）。需要将码距扩大到 4，还需增加一位校验位 $P_5$，将其排列在码字的最前面，并使得数据中每一位都参与三个校验位的生成，即 $P_5 = M_1 \oplus M_2 \oplus M_3 \oplus M_5 \oplus M_6 \oplus M_8$。任意一个数据位发生错误时，引起三个校验位发生变化。

循环冗余校验码

循环冗余校验码（CRC, Cyclic Redundancy Check）具有很强的检错、纠错能力，用于大批量数据存储和传送中的数据校验。

为什么大批量数据不用奇偶校验？在每个字符后增加一位校验位会增加大量的额外开销；尤其在网络通信中，对传输的二进制比特流没有必要再分解成一个个字符，因而无法采用奇偶校验码。

基本思想：

• 数据信息 $M(x)$ 是一个 $n$ 位的二进制数据。将其左移 $k$ 位后，用一个约定的「生成多项式」$G(x)$ 相除，$G(x)$ 是一个 $k+1$ 位的二进制数，相除后得到的 $k$ 位余数就是校验位。校验位拼接到 $M(x)$ 后，形成一个 $n+k$ 位的代码，称该代码为 CRC 码，也称为 $(n+k, n)$ 码。
• 一个 CRC 码一定能被生成多项式整除，当数据和校验位一起送到接受端后，只要将接受到的数据和校验位用同样的生成多项式相除，如果正好除尽，表明没有发生错误；若除不尽，则表明某些数据位发生了错误。通常要求重传一次。

假设要传输的数据信息为 6 位 100011，报文多项式为 $M(x) = x^5 + x + 1$。若约定生成多项式为 $G(x) = x^3 + 1$，则校验位位数为 3，除数为 1001。

生成校验位时，用 $x^3 \cdot M(x)$ 除以 $G(x)$，即 $100011000 \div 1001$。相除时采用「模 2」运算，即异或运算。

高速缓冲存储器

在较短时间间隔内，程序产生的地址往往集中在一个很小范围内。这种现象称为「程序访问的局部性」：

• 时间局部性：指被访问的某个存储单元在一个较短的时间间隔内很可能又被访问；
• 空间局部性：指被访问的某个存储单元的邻近单元在一个较短的时间间隔内很可能也被访问。

程序具有访问局部性特征的原因：

• 指令：指令按序存放，地址连续，循环程序段或子程序段重复执行
• 数据：连续存放，数组元素重复、按序访问

在 CPU 和主存之间设置一个快速小容量的存储器，其中总是存放最活跃（被频繁访问）的程序和数据，由于程序访问的局部性特征，大多数情况下，CPU 能直接从这个高速缓存中取得指令和数据，而不必访问主存。

这个高速缓存就是位于主存和 CPU 之间的 Cache。

Cache 是一种小容量高速缓冲存储器，它由 SRAM 组成。

Cache 直接制作在 CPU 芯片内，速度几乎与 CPU 一样快。

程序运行时，CPU 使用的一部分数据/指令会预先成批拷贝在 Cache 中，Cache 的内容是主存储器中部分内容的映象。

当 CPU 需要从内存读（写）数据或指令时，先检查 Cache，若有，就直接从 Cache 中读取，而不用访问主存储器。

操作过程：

指令最初给出的是「虚拟地址」。

实现

主存被分成若干大小相同的块，称为主存块（Block），Cache 也被分成相同大小的块，称为 Cache 行（line）或槽（Slot）。

在系统启动或复位时，每个 cache 行都为空，其中的信息无效，只有装入了主存块后信息才有效。为了说明 cache 行中的信息是否有效，每个 cache 行需要一个有效位（valid bit）。

有了有效位，就可通过将有效位清零来淘汰某 cache 行中的主存块，称为冲刷（flush），装入一个新主存块时，再使有效位置 1。

缓存机制需要解决的一些问题：

1. 如何分块？
2. 主存块和 Cache 行之间如何映射？
3. Cache 已满该怎么办？
4. 写数据时怎样保证 Cache 与 MM 的一致性？
5. 如何根据主存地址找到 Cache 行？

Cache 对程序员（编译器）是透明的，程序员不必关心 Cache 的存在，即无需了解 Cache 是否存在或如何设置。

Cache 的映射：Cache 行比主存块少，多个主存块映射到一个 Cache 行：

• 直接（Direct）：每个主存块映射到 Cache 的固定行；
• 全相联（Full Associate）：每个主存块映射到 Cache 的任一行；
• 组相联（Set Associate）：每个主存块映射到 Cache 固定组的任一行。

直接映射

也称为「模映射」（Module Mapping），映射关系为

$$\text{Cache 行号} = \text{主存块号} \bmod \text{Cache 行数}$$

块（行）都从 0 开始编号。

假定 Cache 有 $2^c$ 行，主存有 $2^m$ 块，即以 $m$ 位主存块号中低 $c$ 位作为对应的 Cache 行号来进行 Cache 映射。即主存块号的低 $c$ 位正好是它要装入的 Cache 行号。

在 Cache 中，给每一行设置一个 $t$ 位长的标记（tag），此处 $t = m - c$，主存某块调入 Cache 后，就将其块号的高 $t$ 位设置在对应的 Cache 行的标记中。

根据上面的分析，主存地址被分为以下三个字段：

其中高 $t$ 位为标记，中间 $c$ 位为 Cache 行号（行索引），剩下的地位地址为块内地址。

特点：

• 容易实现，命中时间短
• 无需考虑淘汰（替换）问题
• 不够灵活，Cache 存储空间得不到充分利用，命中率低

直接映射的组织示意图：

如下图所示，V 为「有效位」，1 表示信息有效，0 表示信息无效。

• 开机或复位时，所有行的有效位为 0
• 某行被替换后使其有效位为 1
• 某行装入新块时，使其有效位为 1
• 使有效位为 0 来冲刷 Cache（如进程切换，DMA 传送时等）
• 为操作系统设置 Cache 冲刷指令

计算 Cache 容量：

全相联映射

全相联映射的基本思想是一个主存块可装入 Cache 任意一行中。

在全相联映射 Cache 中，每行的标记用于指出该行取自主存的哪个块。

因为一个主存块可能在任意一个 Cache 行中，所以，需要比较所有 Cache 行的标记，因此，主存地址中无须 Cache 行索引，只有标记和块内地址两个字段。

全相联映射方式下，只要有空闲 Cache 行，就不会发生冲突，因而块冲突概率低。

全相联映射方式的时间开销和所用元件开销都较大，实现起来比较困难，不适合容量较大的 cache。

全相联映射的组织示意图：

组相联映射

组相联映射，又称为「组件模映射」「组件全映射」。

将 Cache 所有行分组，把主存块映射到 Cache 固定组的任一行中，映射关系如下

$$\text{Cache 组号} = \text{主存块号} \bmod \text{Cache 组数}$$

特点：

• 结合直接映射和全相联映射的优点
• 每组 2 或 4 行（称为 2-路或 4-路组相联）较常用

组相联映射的组织示意图：

性能

命中情况：

• 命中 Hit：要访问的信息在 Cache 中
  • Hit Rate(命中率)：在 Cache 中的概率
  • Hit Time(命中时间)：在 Cache 中的访问时间（判断时间 + Cache 访问）
• 缺失 Miss：要找到信息不在 Cache 中
  • Miss Rate(缺失率)：不在 Cache 中的概率
  • Miss Penalty(缺失损失)：访问一个主存块所花时间
  • 命中时间远小于缺失损失

设 $t_{\text{avg}}$ 为平均访问时间，命中率为 $\alpha$，$t_c$ 为 Cache 访问时间，$t_m$ 为主存访问时间，则

$$t_{\text{avg}} = \alpha t_c + (1 - \alpha)(t_c + t_m) = t_c + (1 - \alpha)t_m$$

关联度：一个主存块映射到 Cache 中，可能存档的位置个数

• 直接映射：1，关联度最低
• 全相联映射：Cache 行数，关联度最高
• N-路组相联映射：N，关联度居中

Cache 大小和块大小一定时，缺失率直接映射最高，全相联映射最低；命中时间直接映射最小，全相联映射最大。

关联度越高，总的标记位数越多，额外空间开销越大：

-4 为块内地址。

替换算法

组相联映射时，假定第 0 组的两行分别被主存第 0 和 8 块占满，此时若需调入主存第 16 块，根据映射关系，它只能放到 Cache 第 0 组，因此，第 0 组中必须调出一块，那么调出哪一块呢？这就是淘汰策略问题，也称「替换算法」。

常用的替换算法：

• 先进先出 FIFO（First In First Out）
• 最近最少用 LRU（Least Recently Used）
• 最不经常用 LFU（Least Frequently Used）
• 随即替换（Random）

先进先出（FIFO）

FIFO 不是一种栈算法，命中率不随组的增大而提高。

最近最少用（LRU）

最近最少用算法 LRU 是一种栈算法，命中率随组的增大而提高。

当分块局部化范围（即某段时间集中访问的存储区）超过了 Cache 存储容量时，命中率变得很低。极端情况下，假设地址流为 1, 2, 3, 4，且 Cache 每组只有 3 行，则 FIFO 和 LRU 命中率都为 0。这种现象称为颠簸（Thrashing/PingPong）。

LRU 具体实现时，并不是通过移动块来实现的，而是通过给每个 cache 行设定一个计数器，通过计数值来记录这些主存块的使用情况，称为 LRU 位。

计数器变化规则：

• 每组 4 行时，计数器有 2 行，计数值越小说明越被常使用。
• 命中时，被访问行的计数器置 0，比其低的计数器加 1，其余不变。
• 未命中且该组未满时，新行计数器置为 0，其余全加 1。
• 未命中且该组已满时，计数值为 3 的那一行中的主存块被淘汰，新行计数器置为 0，其余加 1。

即计数值为 0 的行中的主存块最常被访问，计数值为 3 的行中的主存块最不常被访问，先被淘汰。

替换

直接映射映射唯一，无需考虑替换。

对于全相联映射和 N-路组相联映射，替换过程为：

1. 从主存块取出一个新块
2. 选择一个有映射关系的空 Cache 行
3. 若对应 Cache 行被占满时又需调入新主存块，则必须考虑从 Cache 行中替换出一个主存块

替换算法举例：

一致性问题

因为 Cache 中的内容是主存块副本，当对 Cache 中的内容进行更新时，就存在 Cache 和主存如何保持一致的问题。

可能出现 Cache 一致性问题的情形：

• 当多个设备都允许访问主存时

处理 Cache 读比 Cache 写更容易，故指令 Cache 比数据 Cache 容易设计。

写操作有两种情况：

• 写命中（Write Hit）：要写的单元已经在 Cache 中
  • 全写法 Write Through（通过式写、写直达、直写）：
    • 同时写 Cache 和主存单元
    • 使用写缓存
  • 回写法 Write Back（写回、延迟写）：
    • 只写 Cache，不写主存
    • 缺失时一次写回，每行有个修改位（脏位 dirty bit），表示该行是否被修改过
    • 大大降低主存带宽需求，控制可能很复杂
• 写不命中（Write Miss）：要写的单元不在 Cache 中
  • 写分配 Write Allocate
    • 将主存块装入 Cache，然后更新相应单元
    • 试图利用空间局部性，但每次都要从主存读一个块
  • 非写分配 Non Write Allocate
    • 直接写主存单元，不把主存块装入到 Cache

直写 Cache 可用非写分配或写分配；回写 Cache 通常用写分配。

全写法：写缓冲

在 Cache 和 Memory 之间加一个 Write Buffer

• CPU 同时写数据到 Cache 和 Write Buffer
• Memory controller（存控）将缓冲内容写主存

Write buffer(写缓冲) 是一个 FIFO 队列

• 一般有 4 项
• 在存数频率不高时效果好

当频繁写时，易使写缓存饱和，发生阻塞。解决方案：

• 加一个二级 Cache
• 使用 Write Back 方式的 Cache

性能举例

Cache 性能由缺失率确定，缺失率与 Cache 大小、Block 大小等有关。Cache 越大，缺失率越低，成本越高；Block 大小与 Cache 大小有关，不能太大也不能太小。

Cache命中率主要由程序的空间局部性和时间局部性决定。因此，为了提高程序的性能，程序员须编写出具有良好访问局部性的程序

考虑程序的访问局部性通常在数据的访问局部性上下工夫。数据的访问局部性主要是指数组、结构等类型数据访问时的局部性，这些数据结构的数据元素访问通常是通过循环语句进行的，所以，如何合理地处理循环对于数据访问局部性来说是非常重要的。

多级 Cache

多 Cache 系统

• 单极/多级？
  • 外部（Off-chip）Cache： 不做在 CPU 内而是独立设置一个 Cache
  • 片内（On-chip）Cache： 将 Cache 和 CPU 作在一个芯片上
  • 单级 Cache：只用一个片内 Cache
  • 多级 Cache：同时使用 L1 Cache 和 L2 Cache，甚至有 L3 Cache，L1 Cache 更靠近 CPU，其速度比 L2 快，其容量比 L2 小
• 联合/分立？
  • 分立：指数据和指令分开存放在各自的数据和指令 Cache 中
    • 一般 L1 Cache 都是分立 Cache，因为其命中时间比命中率更重要
  • 联合：指数据和指令都放在一个 Cache 中
    • 一般 L2 Cache 是联合 Cache，其命中率比命中时间更重要，因为缺失时需从主存取数，并要送 L1, L2 Cache，损失大

虚拟存储器

一方面，由于技术和成本等原因，主存容量受到限制,另一方面，系统程序和应用程序要求主存容量越来越大。因此虚拟存储技术应运而生。

虚拟存储技术实质：

• 程序员在比实际主存空间大得多的逻辑地址空间中编写程序
• 程序执行时，把当前需要的程序段和相应的数据块调入主存，其他暂不用的部分存放在磁盘上
• 指令执行时，通过硬件将逻辑地址（也称虚拟地址或虚地址）转化为物理地址（也称主存地址或实地址）
• 在发生程序或数据访问失效（缺页）时，由操作系统进行主存和磁盘之间的信息交换

CPU 通过存储器管理部件（MMU, Memory Management Unit）将指令中的逻辑地址（也称虚拟地址或虚地址，VA, Virutal Address）转换为主存的物理地址（也称为主存地址或实地址，PA, Physical Address）。

在地址转换过程中，MMU 会检查是否发生了访问信息不在主存或地址越界、访问越权或越级等存储保护错：

• 若发现信息不在主存，则由操作系统将数据从外存读到主存。
• 若发现存储保护错，则由操作系统进行相应的异常处理。

虚拟存储技术既解决了编程空间受限的问题，又解决了多道程序共享主存带来的安全问题。

通过页表（Page Table）建立虚拟空间和物理空间之间的映射。

虚拟地址空间

Linux 在 x86 上的虚拟地址空间

• 内核空间（Kernel）
  • 与进程相关的数据结构
  • 物理存储区
  • 内核代码和数据
• 用户空间
  • 用户栈（User Stack）
  • 共享库（Shared Libraries）
  • 堆（heap）
  • 可读写数据（Read/Write Data）
  • 只读数据（Read-only Data）
  • 代码（Code）

程序在「链接」时确定虚拟地址；装入时生成页表以建立虚拟地址与物理地址之间的映射。（编辑、编译、汇编、链接、装入）

每个用户程序都有相同的虚拟地址空间。

虚拟存储管理机制为每个进程提供了一个极大的虚拟地址空间，它是主存和外存的抽象。虚存机制带来了一个假象，使得每个进程好像都独占地使用主存，并且主存空间极大。

好处：

1. 每个进程具有一致的虚拟地址空间，从而可以简化存储管理；
2. 它把主存看成是外存的一个缓存，在主存中仅保存当前活动的程序段和数据区，并根据需要在外存和主存之间进行信息交换，通过这种方式，使有限的主存空间得到了有效利用；
3. 每个进程的虚拟地址空间是私有的、独立的，因此，可以保护各自进程不被其他进程破坏。

虚拟存储器管理

实现方式：

1. 分页式
2. 分段式
3. 段页式

分页式

在分页式虚拟存储系统中，虚拟地址空间被划分成大小相等的页面，外存和主存之间按页面（page）为单位交换信息。

虚拟地址空间中的页称为虚拟页、逻辑页或虚页，简称为 VP （virtual page）；主存空间也被划分成同样大小的页框（页帧），有时把页框也称为物理页或实页，简称为 PF（page frame）或 PP（physical page）。

虚拟存储管理采用「请求分页」的思想，每次访问指令或数据仅将当前需要的页面从硬盘等外存调入主存某页框中，而进程中其他不活跃的页面保留在硬盘上。

当访问某个信息所在页不在主存时发生缺页异常，此时，从外存将缺失页面装入主存。

页分类：

• 未分配页：没有和任何内容相关联的页称为「未分配页」。
  • 虚拟地址空间中有一些「空洞」的没有内容的页面。如上面的图片所示，堆区和栈区都是动态生长的，因而在栈和共享库映射区之间、堆和共享库映射区之间都可能没有内容存在。
• 已分配页：代码和数据等有内容的区域所关联的页面。
  • 缓存页：已调入主存而被缓存在 DRAM 中的页面；
  • 未缓存页：未调入主存而存在外存上的页。

与「Cache-主存」层次相比：

• 页大小（2KB ~ 64KB）比 Cache 中的 Block 大得多
• 采用全相联映射
  • 因为缺页的开销比 Cache 缺失开销大的多：
    • 缺页时需要访问磁盘（约几百万个时钟周期）
    • 而 Cache 缺失时，访问主存仅需几十到几百个时钟周期
  • 因此，页命中率比 Cache 命中率更重要。「大页面」和「全相联」可提高页命中率。
• 通过软件来处理「缺页」
  • 缺页时需要访问磁盘（约几百万个时钟周期）
  • 慢，不能用硬件实现
• 采用 Write Back 写策略
  • 避免频繁的慢速磁盘访问操作
• 地址转换用硬件实现
  • 加快指令执行

页表：建立各个「虚拟页」（虚拟地址中）和所存放的「主存页框号」（主存空间中）或磁盘上存储位置之间的关系。

页表首址记录在页表基址寄存器中。

进程中的每个虚拟页在页表中都有一个对应的表项，称为页表项。页表项内容包括

• 该虚拟页的存放位置：建立虚拟页和物理页框之间的映射，用于进行虚拟地址到物理地址的转换。
• 装入位（valid）：有效位。
  • 若为 1，表示该虚拟页已从外存调入主存，是一个「缓存页」。此时，存放位置字段指向主存物理页号（即页框号或实页号）。
  • 若为 0，则表示没有被调入主存，此时：
    • 若存放位置字段为 null，则说明是一个「未分配页」；
    • 否则是一个「未缓存页」，其存放位置字段给出该虚拟页在磁盘上的起始地址。
• 修改位（dirty）：说明页面是否被修改过。
• 使用位：说明页面的使用情况，配合替换策略来设置，因此也称替换控制位。
• 存取权限位：说明页面是可读可写、只读还是只可执行等，用于存储保护。
• 禁止缓存位：说明页面是否可以装入 cache，通过正确设置该位，可以保证磁盘、主存和 cache 数据的一致性。

页表的项数由什么决定？ 理论上由虚拟地址空间大小决定。

各进程有相同虚拟空间，故理论上每个进程的页表大小一样。实际大小看具体实现方式，如「null」页面如何处理等。

主存中的页表示例：

• 未分配页：进程的虚拟地址空间中「null」对应的页（如 VP0、VP4）
• 已分配的缓存页：有内容对应的已装入主存的页（如 VP1、VP2、VP5 等）
• 已分配的未缓存页：有内容对应但未装入主存的页（如 VP3、VP6）

虚拟地址分为两个字段：

• 高位字段：虚拟页号
• 低位字段：页内地址

主存物理地址也分为两个字段：

• 高位字段：物理页号
• 低位字段：页内地址

由于虚拟页和物理页（页框）大小一样，所以二者页内地址相等。

逻辑地址转换为物理地址的过程：

虚拟页与主存页框之间采用全相联方式进行映射，高位地址是索引。

地址变换过程：

1. 首先根据页表基址寄存器的内容，找到主存中对应的页表起始位置（即页表基地址）；
2. 然后将虚拟地址高位字段中的虚页号作为索引，找到对应的页表项：
   • 若装入位为 1，则取出物理页号，和虚拟地址中的页内地址拼接，形成访问主存时实际的物理地址；
   • 若装入位为 0，则说明缺页，需要操作系统进行缺页处理。

信息访问中可能出现的异常情况：

1. 缺页（page fault）
   • 产生条件：当 Valid（有效位 / 装入位）为 0 时
   • 相应处理：从磁盘读到内存，若内存没有空间，则还要从内存选择一页替换到磁盘
     上，替换算法类似于 Cache，采用回写法，淘汰时，根据「dirty」位确定是否要写磁盘
   • 当前指令执行被阻塞，当前进程被挂起，处理结束回到原指令继续执行
2. 保护违例（protection violation fault）或访问违例
   • 产生条件： 当 Access Rights （存取权限）与所指定的具体操作不相符时
     • R: Read-only
     • R/W: Read/Write
     • X: Execute only
   • 相应处理：在屏幕上显示「内存保护错」或「访问违例」信息
   • 当前指令的执行被阻塞，当前进程被终止

从上述地址转换过程可看出，访存时首先要到主存查页表，然后才能根据转换得到的物理地址访问主存。如果缺页，则还要进行页面替换、页表修改等，访问主存的次数就更多了。因此，采用虚拟存储器机制后，使得访存次数增加了。

把经常要查的页表项放到 Cache 中，这种在 Cache 中的页表项组成的页表称为「后备转换缓冲器」（Translation Lookaside Buffer, TLB），通常称为快表，相应地称主存中的页表为慢表。

这样，在地址转换时，首先到快表中查页表项，如果命中，则无须访问主存中的页表。

快表中内容可能不在 Cache 中。

每个表项的内容由页表项内容加上一个 TLB 标记字段组成：TLB 标记字段用来表示该表项取自页表中哪个虚拟页对应的页表项。

因此，TLB 标记字段的内容：

• 在全相联方式下就是该页表项对应的虚拟页号；
• 组相联方式下则是对应虚拟页号中的高位部分，而虚拟页号的低位部分作为 TLB 组索引用于选择 TLB 组。

CPU 访存时，地址中虚页号被分成 tag + index，tag 用于和 TLB 页表项中的 tag 比较，index 用于定位需要比较的表项

TLB 全相联时，没有 index，只有 Tag，虚页号需与每个 Tag 比较；TLB 组相联时，则虚页号高位为 Tag，低位为 index，用作组索引。

一个 TLB 和 Cache 都采用组相联映射的过程：

1. CPU 给出的是一个 32 位的虚拟地址，首先，由 CPU 中的 MMU 进行虚拟地址到物理地址的转换；
2. 然后由处理 cache 的硬件根据物理地址进行存储访问.
3. MMU 对 TLB 查表时，20 位的虚拟页号被分成标记（tag）和组索引两部分：
   1. 首先由组索引确定在 TLB 的哪一组进行查找。
   2. 查找时将虚拟页号的标记部分与 TLB 中该组每个标记字段同时进行比较：
      • 若有某个相等且对应有效位 V 为 1，则 TLB 命中，此时，可直接通过 TLB 进行地址转换；
      • 否则 TLB 缺失，此时，需要访问主存去查慢表。
4. 该例是两级页表方式，虚拟页号被分成页目录索引和页表索引两部分，根据这两部分可得到对应的页表项，从而进行地址转换；
5. 并将对应页表项的内容送入 TLB 形成一个新的 TLB 表项，同时，将虚拟页号的高位部分作为 TLB 标记填入新的 TLB 表项中。
6. 若 TLB 已满，还要进行 TLB 替换（为降低替换算法开销，TLB 常采用随机替换策略）。
7. 在 MMU 完成地址转换后，cache 硬件根据映射方式将转换得到的主存物理地址划分成多个字段：
   1. 然后根据 cache 索引，找到对应的 cache 行或 cache 组；
   2. 将对应各 cache 行中的标记与物理地址中的高位地址进行比较：
      • 若相等且对应有效位为 1，则 cache 命中，此时，根据块内地址取出对应的字。需要的话，再根据字节偏移量从字中取出相应字节送 CPU。

快表示例：

TLB 和 Cache 的访问过程：

命中：

缺失：

CPU 访存过程：

TLB, page, cache 缺失组合：

• 最好的情况：全部 hit，此时无需访问主存
• 好的情况：hit, hit, miss 或 miss, hit, hit，需要访存 1 次
• 最坏的情况：miss, miss, miss，需访问磁盘，并访存至少 2 次
• 好坏之间：miss, hit, miss，不需访问磁盘，访存至少 2 次

分段式

• 程序员或 OS 将程序模块或数据模块分配给不同的主存段，一个大程序有多个代码段和多个数据段构成，是按照程序的逻辑结构划分而成的多个相对独立的部分。
  • 例如，代码段、只读数据段、可读写数据段等
• 段通常带有段名或基地址，便于编写程序、编译器优化和操作系统调度管理
• 分段系统将主存空间按实际程序中的段来划分，每个段在主存中的位置记录在段表中，并附以「段长」项
• 段表由段表项组成，段表本身也是主存中的一个可再定位段

段式虚拟存储器的地址映像：

分段式虚存的地址转换：

段页式

基本思想：

• 段、页式结合：
  • 程序的虚拟地址空间按模块分段、段内再分页，进入主存仍以页为基本单位
• 逻辑地址由段地址、页地址和偏移量三个字段构成
• 用段表和页表（每段一个）进行两级定位管理
• 根据段地址到段表中查阅与该段相应的页表首地址，转向页表，然后根据页地址从页表中查到该页在主存中的页框地址，由此再访问到页内某数据

存储保护

存储保护：为避免多道程序相互干扰，防止某程序出错而破坏其他程序的正确性或不合法地访问其他程序或数据区，应对每个程序进行存储保护。

操作系统程序和用户程序都需要保护。

以下情况发生存储保护错

• 地址越界（转换得到的物理地址不属于可访问范围）
• 访问越权（访问操作与所拥有的访问权限不符）
  • 页表中设定访问（存取）权限

访问属性的设定

• 数据段可指定 R/W 或 RO；程序段可指定 R/E 或 RO

最基本的保护措施：规定各道程序只能访问属于自己所在的存储区和共享区

• 对于属自己存储区的信息：可读可写，只读/只可执行
• 对共享区或已获授权的其他用户信息：可读不可写
• 对未获授权的信息（如 OS 内核、页表等）：不可访问

为了对操作系统的存储保护提供支持，硬件必须具有以下三种基本功能：

• 支持至少两种运行模式：
  • 管理模式（Supervisor Mode）
    执行系统程序（内核）时处理器所处的模式称为管理模式（Supervisor Mode）
    • 或称管理程序状态，简称管态、管理态、核心态、内核态
  • 用户模式（User Mode）
    CPU 执行非操作系统的用户程序时，处理器所处的模式就是用户模式
    • 或称用户状态、目标程序状态，简称为目态或用户态
• 使一部分 CPU 状态只能由内核程序读写而不能由用户程序读写：这部分状态包括：
  User/Supervisor 模式位、页表首地址、TLB 等
  • OS 内核可以用特殊的指令（一般称为管态指令或特权指令）来读写这些状态
• 提供让 CPU 在管理模式（内核态）和用户模式（用户态）相互转换的机制：「异常」和「陷阱」（系统调用）使 CPU 从用户态转到内核态；异常处理中的「返回」指令使 CPU 从内核态态转到用户态

通过上述三个功能并把页表保存在 OS 的地址空间，OS 就可以更新页表，并防止用户程序改变页表，确保用户程序只能访问由 OS 分配给的存储空间。

RISC-V 的三种特权模式：

• 机器模式（Machine Mode）也称为 M 模式（11）。
  • M 模式是 RISC-V 中硬件线程（hart）可以执行的最高权限模式
  • 在 M 模式下运行的 hart 可访问所有资源和所有内存，具有启动和配置系统等系统底层支撑功能
  • 因此，M 模式是所有标准 RISC-V 处理器都必须实现的运行模式
  • 通常，用于嵌入式系统的简单 RISC-V 微控制器仅支持 M 模式。
• 用户模式（User Mode）也称为 U 模式（00）。
  • 为阻止不可信代码通过特权指令访问系统中重要的信息或控制系统的行为
  • RISC-V 把处理器执行普通应用程序时的模式定义为用户模式
  • 在 U 模式下只能执行各类普通指令，不能执行特权指令
  • 安全的嵌入式系统一般支持 M 模式 + U 模式，执行 ecall 指令从 U -> M 模式，执行 mret 指令从 M -> U 模式
• 监管模式（Supervisor Mode）也称为 S 模式（01）。
  • 复杂的 RISC-V 系统会使用请求分页虚拟存储管理方式，对应的运行模式为支持存储保护的 S 模式
  • 因此，操作系统内核程序运行在 S 模式下

RISC-V 采用可灵活组合特权模式的方式来实现不同的系统。

• 仅支持 M 模式的系统
  • 因为所有程序都在 M 模式下执行，所以所有代码都可直接访问系统中的重要信息，因此，这种系统易受到不可信代码的控制和攻击，只能用于安全性和可靠性要求不高的场合，例如，只运行少数甚至一个程序的微控制器。
• 支持 M 模式和 U 模式的系统
  • 安全的嵌入式系统一般都属于这种系统。通过将不可信代码限制在较低特权的 U 模式执行，来保证系统的重要信息得到保护。
  • 处理器具有物理内存保护（Physical Memory Protection，PMP）功能，允许 M 模式指定 U 模式可以
    访问的物理内存地址空间范围。
  • 在 U 模式下，如果处理器在取指令或执行 Load/Store 指令时，发生了与配置寄存器设置的权限不相符的操作，则会引起异常。
  • 只有在 M 模式下才能执行级别较高的特权指令，以避免不可信代码对系统的破坏。
• 支持 M 模式、S 模式和 U 模式的系统
  • S 模式比 U 权限高，但比 M 低。S 模式下不能使用 M 模式下的 CSR 寄存器和指令。
  • S 模式支持页式虚拟存储管理机制，因而这种系统可实现现代操作系统的功能。
  • 在 M 模式下发生的异常总是在 M 模式下处理，S 模式下发生的异常，只可能在 M 或 S 模式下处理，不可能移交到 U 模式下处理。

S 模式下的页式虚拟存储管理机制

RV32 的分页方案 Sv32：4GB 虚拟空间、4KB 页面、页目录项（PDE）和页表项（PTE）都占 32 位，内容如下：

• V：有效位。0 表示对应页不在主存，发生缺页故障（page fault）。
• R、W、X： 存取权限位。表示是否可读、可写和可执行。当指令执行时实际发生的操作与存取权限发生矛盾，则会引起访存故障或取指令故障。若全为 0，则说明是页目录项，其中 PPN 存放的是所指向的下一级页表所在的物理页（即页框）号。
• U：是否 U 模式可访问。0 表示 U 模式不能访问该页，但 S 模式可以；1 表示 U 模式下能访问该页，而默认 S 模式不能。若不能访问时进行了访存操作，则引起访存故障。默认 S 模式不能访问 U=1 的页面，可防止恶意程序哄骗操作系统窃取其它程序的数据。
• G：指定全局映射。全局映射指存在于整个地址空间的映射，通常用于 OS 自身使用的页面。页目录项时，G=1 说明其下一级所有页表项都是全局映射。将全局映射标记为非全局映射只会降低性能，而将非全局映射标记为全局映射则会发生访存故障。
• A：访问位。记录自上一次 A 位被清除以来，该页是否被访问过。
• D：脏位。记录自上一次 D 位被清除以来，该页是否被写过。
• RSW：留给操作系统使用，硬件可忽略。
• PPN：物理页（页框）号。

Sv32 中地址转换过程