计算机组成原理学习笔记（三）——存储系统

参考资料：《计算机组成原理》（秦磊华版）

目录

• 1 存储器概述
• 1.1 存储器分类
• 1.2 主存的主要技术指标
• 1.3 主存中数据的存放
• 1.3.1 存储字长与数据字长的概念
• 1.3.2 大端和小端数据存放方式
• 1.3.3 边界对齐的数据存放方式
• 1.4 主存的基本结构和工作过程
• 1.5 存储系统层次结构
• 2 半导体存储器
• 2.1 静态 MOS 存储器（SRAM）
• 2.1.1 静态 MOS 存储单元
• 2.1.2 静态 MOS 存储器的阵列结构
• 2.2 动态 MOS 存储器（DRAM）
• 2.2.1 动态 MOS 存储单元
• 2.2.2 动态 MOS 存储器的刷新
• 2.3 只读存储器
• 2.4 新型存储器
• 3 主存的组织以及与 CPU 的连接
• 3.1 存储器的扩展
• 3.1.1 位扩展
• 3.1.2 字扩展
• 3.1.3 字位同时扩展
• 4 并行主存系统
• 4.1 双端口存储器
• 4.2 单体多字存储器
• 4.3 多体交叉存储器
• 4.3.1 高位多体交叉存储器
• 4.3.2 低位多体交叉存储器
• 5 高速缓冲存储器（cache）
• 5.1 程序访问的局部性原理
• 5.2 cache 的工作原理
• 5.2.1 主存地址的划分
• 5.2.2 cache 的基本结构
• 5.2.3 cache 的组织
• 5.2.4 CPU 访问 cache 的流程
• 5.2.5 cache 的命中率
• 5.3 相联存储器
• 5.4 cache 的地址映射及变换方法
• 5.4.1 全相联映射（Associative Mapping）
• 5.4.2 直接映射（Direct Mapping）
• 5.5 替换算法
• 5.5.1 先进先出算法（FIFO，First In Firs Out）
• 5.5.2 近期最少使用算法（LRU，Least Recently Used）
• 5.5.3 最不经常使用算法（LFU，Least Frequently Used）
• 5.5.4 随机替换算法（Random Replacement）
• 5.6 cache 的写策略
• 5.6.1 写回法 WB（Write-Back）
• 5.6.2 写直达法 WT（Write-Through）
• 5.7 多 cache 结构
• 6 虚拟存储器
• 6.1 虚拟存储器的工作原理
• 6.2 虚拟存储器的地址映射与变换
• 6.3 页式虚拟存储器
• 6.3.1 页式虚拟存储器的地址划分
• 6.3.2 地址转换的基本原理
• 6.3.3 结合 cache 的页式虚拟存储器地址转换
• 6.3.4 利用 TLB 加速虚拟存储器地址转换
• 6.4 段式虚拟存储器
• 7 存储保护
• 8 习题

设计大容量、高速度、成本低的存储系统是计算机发展追求的目标之一。

1 存储器概述

1.1 存储器分类

1.2 主存的主要技术指标

1. 容量
2. 存储速度
3. 存储器的可靠性

1.3 主存中数据的存放

1.3.1 存储字长与数据字长的概念

1. 存储字长 ： 主存的一个存储单元所存储的二进制位数。
2. 数据字长（简称字长）：计算机一次能处理的二进制数的位数 。

存储字长与数据字长不一定相同，例如，对于字长为 32 位的计算机，所采用的存储字长可以是 16 位、32 位或 64 位 。

1.3.2 大端和小端数据存放方式

数据在内存中存储的方式：大端模式与小端模式

采用大、小模式对数据进行存放的主要区别在于存放字节的顺序，大端方式将数据的高位字节存放在主存低地址单元，小端方式将数据的低位字节存放在低地址单元。

采用大端方式进行数据存放符合入类的正常思维，而采用小端方式进行数据存放利于计算机处理。

有的处理器系统采用了小端方式进行数据存放，如 Intel 的奔腾；有的处理器系统采用了大端方式进行数据存放，如 Power PC 处理器；还有的处理器同时支持大端和小端方式，如 ARM 处理器 。 除处理器外，现在有些外设的设计中也存在着使用大端或者小端进行数据存放的选择 。

大端与小端模式的差别不仅体现在处理器中的寄存器，在指令集、系统总线等各个层次中也可能存在大端与小端模式的差别，必须深入理解大端和小端模式的上述差别。

1.3.3 边界对齐的数据存放方式

现代计算机中内存空间按照字节编址，从理论上讲似乎对任何类型变量的访问可以从任何地址开始，但实际情况是在访问特定类型变量时经常在特定的内存地址访问，这就需要各种类型数据按照一定的规则在空间上排列，而不是顺序的一个接一个的存放，这就是对齐。

数据按照边界对齐的方式存放可以提高存储系统的访问效率，此时，一个读写周期就可以访问一个字，否则可能需要花费两个甚至更多个读写周期才能访问一个字。

为了实现字节编址的边界对齐存储，对字节、单字、半字和双字的存储单元地址提出了一定的限制，具体表现在（假设计算机字长为 32 位）：

• 双字数据起始地址的最末 3 位为 000（8字节的整数倍），表示访问一个 64 位字长的字，如果要访问其中的某字节或半字则用低 3 位中的部分位来选择。

• 单字数据起始地址的最末两位为 00（4字节的整数倍）。

• 半字数据起始地址的最末一位为 0（2字节的整数倍）。

• 字节数据的存储按照单字数据处理。

按照上述的方式存放数据可以确保任何一次访问都可在一个存取周期完成，无论访问的是一个字节、半字、单字还是双字。

支持字节、半字、字访问的存储子系统要求进行地址的强制对齐，因此按照半字访问时需要忽略字节地址后一位，按照字访问时需要忽略字节地址后两位。

比如说 12 位的字节地址，我分别按照字节、半字和字访问 0000 1100 1000 即 200 的地址时，正常访问即可。

但假设我按半字访问 0000 1100 1001 即 201 的地址时， 直接访问会导致访问出来的内容不正确，因此我需要强制对齐到 0000 1100 1000 即 200 的地址，因此我需要需要忽略字节地址后一位。

再假设我按半字访问 0000 1100 1011 即 203 的地址时， 直接访问会导致访问出来的内容不正确，因此我需要强制对齐到 0000 1100 1000 即 200 的地址，因此我需要需要忽略字节地址后两位。

1.4 主存的基本结构和工作过程

主存储区里由存储体加上一些外围电路构成，外围电路包括地址译码驱动器、数据寄存器和存储器控制电路：

• 地址译码驱动器接收来自 CPU 的 n 位地址信号，经译码、驱动后形成 2ⁿ 个地址选择信号，每次选中一个存储单元。

• 数据寄存器寄存 CPU 送来的 m 位数据，或寄存从存储体中读出的 m 位数据。

• 控制线路接收 CPU 的读写控制信号后产生存储器内部的控制信号，将指定地址的信息从存储体读出送到数据寄存器供 CPU 使用，或将来自 CPU 并已存入数据寄存器的信息写入存储体中的指定单元。
  

存储器的大致工作过程如下：

1. CPU 执行某条指令时，若需要与存储器交换数据，则先要给出该数据在存储器中的地址。

2. 该地址经地址译码驱动器后选中存储体中该地址对应的存储单元，然后由控制线路控制读出或写入。

3. 读出或写入数据：

   • 读出时，将选中的存储单元所存的数据送入数据寄存器，原存储单元中的内容不变，而 CPU 从数据寄存器中取走该数据，然后进行指令所要求的处理。

   • 写入时，将 CPU 送来并已存放于数据寄存器中的数据写入选中的存储单元，如果该存储单元原先存有数据，经写入操作后，原数据将被新数据所取代。

1.5 存储系统层次结构

对存储系统的基本要求是存储速度快、存储容量大、成本价格低，很显然，在同样的技术条件下，这些要求之间是相互矛盾的，存储系统层次结构的设计就是要利用相关技术克服上述矛盾，并构建一个存储速度快、存储容量大、成本价格低的存储系统。

上图所示的是一个由高速缓冲存储器、主存和辅存三级存储体系构成的分级结构，3 种不同类型的存储器承担的职能各不相同，其中：

• 使用高速缓存的主要目的是提高 CPU 对存储系统的访问速度，缓解快速 CPU 与主存之间的速度差异问题。
• 使用主存是为了能容纳系统的核心软件和较多的用户程序及数据，因为指令和数据只有从外存调入内存才能被 CPU 访问。
• 使用辅存的目的是缓解主存容量不足的矛盾。

基于这种分级结构，就构成了一个满足应用需求的存储速度快、存储容量大、成本价格低的存储系统：

2 半导体存储器

半导体存储器的主要特点是存取速度快、体积小、价廉、可靠，现已成为实现主存的首选器件，通常的半导体存储器分为随机存储器 RAM 和只读存储器 ROM。

2.1 静态 MOS 存储器（SRAM）

2.1.1 静态 MOS 存储单元

存储体以静态 MOS 存储元为基本单元组成的存储器称为静态 MOS 存储器。

存储单元是存储器中的最小存储单位，其作用是存储一位二进制信息，作为存储单元的电路，需具备以下基本功能：

• 具有两种稳定状态。
• 两种稳定状态经外部信号控制可以相互转换。
• 经控制，能读出其中的信息。
• 无外部原因，其中的信息能长期保存。

2.1.2 静态 MOS 存储器的阵列结构

静态 MOS 存储器一般由存储体、地址译码电路、I/O 电路和控制电路等组成，下图所示的是一个 4096 × 1 位的静态 MOS 存储器结构框图：

1. 存储体：由静态 MOS 存储元组成，4096 个存储单元排列成二维的阵列组织，X，Y 方向的各 6 根地址线经过 X，Y 译码器后各产生 64 根选择线，存储矩阵为 64 × 64，在每个 X，Y 选择线的交叉点有一个存储单元。

2. 地址译码器：存储器中地址译码器的作用是将地址翻译成驱动存储单元门控管的控制信号，选择相应的存储单元。

   常见的地址译码器的设计方案有两种，一种是单译码结构，另一种是双译码结构：

   • 单译码结构中，地址译码器只有一个，译码器的输出选择对应的字。由于存储单元有行、列选通控制信号，而单译码结构只能提供一组选通控制信号，要选通存储单元，必须将所有存储单元的行、列选通控制信号连接在一起，然后与单译码器的输出线相连。

     单译码结构的缺点是当 n 较大时，译码器将变得复杂而庞大，使存储器的成本迅速上升，性能下降，所以单译码结构只适用于小容量存储器。
     

   • 考虑到单译码结构耗费译码线较多，为减少驱动器数量，降低成本，因此现在存储器一般采用双译码结构，这种结构中有 X 和 Y 两个方向的译码器，译码器的输出分别与存储单元的行、列选通线相连接。
     

3. 驱动器：每条选择线要控制与它相连接的所有存储单元，负载很大，因此要用驱动器来增加其负载能力。

4. I/O 电路：I/O 电路用来控制数据的输入和输出，也就是对被选中单元进行的读写控制，它处在存储单元和数据总线之间。读出时，数据经输出驱动送至数据总线；写入时，数据总线上的数据送往 I/O 电路，再写入对应存储单元。

5. 读写控制电路：读或写操作由 CPU 发出的读写命令（R/W）来控制。

6. 片选电路：由于一块集成芯片的容量有限，要组成一个大容量的存储器，往往需要将多块芯片连接起来使用，通过片选信号可以很好地解决存储芯片的选择问题，此时存储器被访问时并不是所有的芯片同时工作，只有片选信号有效的存储芯片才能对它进行读或写操作。

2.2 动态 MOS 存储器（DRAM）

2.2.1 动态 MOS 存储单元

动态存储单元中，信息以电荷形式存储在 T1 或 T2 管的栅极电容 C1 或 C2 上，由于电容容量小，所存电荷会在一段时间后逐渐泄漏（一般为 ms 级），为使所存信息能长期保存，需要在电容电荷泄露完之前定时地补充电荷，这一过程称为刷新。

四管动态存储单元的读操作过程也能对所读单元的 T1 或 T2 管的栅极电容 C1 或 C2 充电，从这个意义上看，读操作具有刷新功能。但读操作的刷新不能代替整个存储器的刷新，一方面由于只有被读过的单元才能被刷新，另一方面，对同一单元两次读操作的时间间隔也很难满足刷新间隔的要求。

为进一步提高集成度，可以只用一个 MOS 管和一个电容构成单管动态存储单元，显然，单管动态存储单元与四管动态存储单元相比，具有功耗更小、集成度更高的优点。

2.2.2 动态 MOS 存储器的刷新

DRAM 靠电容电荷存储信息，电荷易泄漏，需定期补充以保持信息不变，补充电荷的过程称为刷新过程，信息存储到泄漏完毕之间必须完成刷新。

上一次对存储器刷新结束到下一次对整个存储器刷新结束所需要时间称为刷新间隔或刷新周期。

存储体采用双译码结构，因此刷新按行进行，刷新一块芯片所需的刷新周期数由芯片矩阵的行数决定。

关于动态存储器刷新的几点说明：

1. 采用不同材料及不同生产工艺生产的动态存储器的刷新间隔可能不同，常见的有 2ms、4ms、8ms 等，在设计刷新电路时需要了解刷新间隔。

2. 动态存储器的刷新按行进行，因此设计刷新电路同样需要清楚动态存储芯片内部的行列结构。一般要结合存储芯片的容量、地址复用、双译码等因素来考察动态存储芯片的行列结构，或参考芯片的技术手册。

3. 刷新地址由刷新地址计数器产生而不是由 CPU 发出，刷新地址计数器的位数与动态存储芯片内部行结构有关。如某动态存储芯片内部有 256 行，则刷新地址计数器至少为 8 位，在每个刷新间隔内，该计数器的值从00000000 到 11111111 循环一次。

4. 读操作不能代替刷新操作，读操作虽然具有刷新功能，但读操作与刷新操作又有所不同，刷新操作只需要给出行地址，而不需要列地址，另外，刷新操作也不受芯片片选信号的控制。

为了便于比较不同刷新方式，设动态存储器存储体为 128 行 × 128 列结构，存储器的读写周期 tc = 0. 5 μs，刷新间隔为 2 ms，以下为不同的动态 RAM 的刷新方式：

• 集中刷新方式：由于存储器体内部行列结构为 128 × 128，因此刷新操作应该在 2 ms 内对 128 个行进行一次刷新。在不考虑刷新的情况下，2 ms 内可进行 4000 次读写或保持操作。在集中刷新方式下，2 ms 内的前 3872 个读写周期都用来进行读写或保持，2 ms 内的最后 128 个读写周期集中用于刷新。

  集中刷新的优点是读写操作期间不受刷新操作的影响，因此存储器的速度比较快，不足是存在 “死时间”，即刷新期间的 128 个读写周期内，CPU 不能访问存储器，而存储器芯片内部行数越多，死时间就越长。

  采用集中刷新后存储系统的平均读写周期为：
  $tc = 2~ms/(4000 - 128) = 0.5165~μs$tc=2 ms/(4000−128)=0.5165 μs

• 分散刷新方式：分散刷新方式把系统周期 ts 分为两部分，前半段用来进行读写或保持，后半段作为刷新时间，因此 ts = 1μs。每过 128 个 ts，整个存储器就被刷新一次。显然，在 2 ms 内可进行约 15 次刷新。虽然这种刷新方式不存在死时间，但因刷新过于频繁，严重影响了系统的速度，故不适合应用于高速存储器。

• 异步刷新方式：异步刷新是集中刷新和分散刷新方式的结合，它是先用要刷新的行数对 2 ms 进行分割，然后再将已分割的每段时间分为两部分，第一部分时间用于读写或保持，最后留出一个读写周期时间用于刷新。先将 2 ms 分成 128 个 15.5 μs 的时间段，然后将每个时间段中最后的 0.5 μs 用来刷新一行。这样既充分利用了 2 ms 时间，又能保持系统的高速特性。

• 透明刷新方式：由于指令译码期间不访问存储器，可利用这段时间对动态存储器进行刷新，而不占用 CPU 时间，由于这种刷新方式对 CPU 透明，所以称为透明刷新方式。

2.3 只读存储器

信息只能读出不能随意写入的存储器，称为只读存储器，记为 ROM。它的特点是通过一定方式将信息写入之后，信息就固定在 ROM 中且具有非易失性，即使电源断电，保存的信息也不会丢失。因此，只读存储器主要用来存放一些不需要修改的程序，如微程序、子程序、某些系统软件和用户软件等。

按照制造工艺的不同，可将 ROM 分为：

• 掩膜式只读存储器 MROM：MROM 的存储元可以由半导体二极管、双极型晶体管或 MOS 电路构成，它由制造厂家在生产过程中按要求做好，用户不能修改，MROM 具有以下特点：

  • 存储的信息一次写入后再不能修改，灵活性差。

  • 信息固定不变，可靠性高。

• 可编程只读存储器 PROM：PROM 是一种由用户编程且只能编程一次的 ROM，PROM 存储器出厂时每个存储单元的内容都为 1 或都为 0，使用时，可根据应用的需要对存储的内容修改一次，从而克服 MROM 使用不便的问题，需注意都是，PROM 中的信息只能被用户修改一次。

• 可擦除可编程只读存储器 EPROM：EPROM 是一种可多次写入的 ROM，其特点是写入的信息可长期保存，当不需要这些信息或希望进行修改时，可进行擦除和重写。

• 电擦除可编程只读存储器 E²PROM：E²PROM 又记为 EEPROM，是电可擦除电可改写的只读存储器，与 EPROM 相比，E²PROM 的写操作可随机进行，而不必先擦除存储单元的内容再写入新的信息，E²PROM 将不易丢失数据和修改灵活的优点有机地结合在一起。

2.4 新型存储器

• Flash Memory：Flash Memory 也称闪存，是一种快速擦写、具有不挥发性的存储器，可以在线进行擦除和重写。目前其集成度和价格已接近 EPROM，因而它是 EPROM 和 E²PROM 的理想替代器件。特别是由于它的集成度提高以及抗振动、高可靠性、低价格等特点，可用它组成固态大容量存储器装置来代替小型硬盘存储。与 E²PROM 相比，它的写数时间短，特别适合存放实时采集的重要数据，运行速度比磁盘要快很多。

  Flash Memory 与 EPROM 的逻辑结构相似，最主要的区别在于存储单元的结构和工艺。Flash Memory 的工作方式有读工作方式、编程工作方式、擦除工作方式和功耗下降方式。它的编程和擦除方式采用写命令到命令寄存器的方法来管理编程和擦除。

• 带高速缓存的 DRAM（CDRAM）

• 同步 DRAM（SDRAM）

• DDR SDRAM

• Rambus DRAM（RDRAM）

• FPM-DRAM

3 主存的组织以及与 CPU 的连接

单片存储芯片的存储容量有限，要获得一个大容量的存储器，通常需要用多片存储芯片按照一定的组织方式并与 CPU 连接来实现，这就是存储器的组织。在存储器组织过程中，要实现存储芯片与 CPU 地址线、数据线和控制线的连接，其中：

• 连接的地址线的数量与 CPU 要访问的主存容量有关。

• 连接的数据线的数量与计算机字长有关。

• 对于 RAM 而言，控制线包括片选信号和读写控制，而对于 ROM 而言则只有片选信号线。

• DRAM 没有片选控制线，进行容量扩展时，利用 RAS 的非和 CAS 的非控制芯片的选择。

可以从上述 4 方面的连接线来检查存储器的组织是否正确。

3.1 存储器的扩展

由于存储芯片的容量及字长与目标存储器的容量及字长之间可能存在差异，因此在使用存储芯片组织一定容量与字长的存储器时，一般可采用位扩展、字扩展或字位同时扩展等方法来组织。

3.1.1 位扩展

位扩展又叫字长扩展或数据总线扩展，工作时各芯片并行工作。

当存储芯片的数据位小于 CPU 对数据位的要求时，采用位扩展方式可解决此类问题。位扩展时，将所有存储芯片的地址线、读写控制线并联同时分别与 CPU 的地址线和读写控制线连接，而将各存储芯片的数据线依次与 CPU 的数据线相连，所有芯片的片选控制线并联连接低电平。

仅进行位扩展时，所需存储芯片的数量为：
$\bf{L = 存储器的数据位 / 存储芯片的数据位}$L=存储器的数据位/存储芯片的数据位

3.1.2 字扩展

字扩展也称容量扩展、字数扩展或地址总线扩展，工作时同一时刻仅有一个芯片工作。

当存储芯片的存储容量不能满足存储器对存储容量的要求时，可采用字扩展方式来扩展存储器。字扩展时，将所有存储芯片的数据线、读写控制线各自并联同时分别与 CPU 的数据线和读写控制线连接，而将各存储芯片的片选信号由 CPU 多余的地址线产生，片选信号的产生方法可进一步分为线选法、全译码法和部分译码法。

仅进行字扩展时，所需要的芯片数量为：
$\bf{K = 存储器的容量 / 存储芯片的容量~~~(注意二者单位一致)}$K=存储器的容量/存储芯片的容量   (注意二者单位一致)

3.1.3 字位同时扩展

当存储芯片的数据位和存储容量均不能满足存储器的数据位和存储总容量要求时，可以采用字位同时扩展的方式来组织存储器，其中通过位扩展可以满足数据位的要求，通过字扩展可以满足存储总容量的要求。

4 并行主存系统

目前，主存的存取速度已经成为计算机系统的性能瓶颈，除通过选择高速元件来提高存储器访问速度外，也可以通过存储体的并行工作来提高存储器的访问速度，缓解 CPU 与主存速度不匹配的矛盾。

4.1 双端口存储器

双端口存储器是指同一个存储器具有两组相互独立端口的存储器，每个端口有各自独立的数据端口、地址端口以及读写控制端口、片选端口等，每个端口可独立进行读写操作。双端口存储器的结构有多种，下图是一种基本的双端口存储器结构示意图：

1. 并行读写：当左右两个端口的地址不同时，两个端口使用各自的地址线、数据线和控制线对存储器同时进行读写操作，而不发生冲突。

2. 冲突处理：当两个端口的访问地址相同时，便会发生读写冲突。为解决冲突问题，每个端口各设置一个标志BUSY。当冲突发生时，由判断逻辑决定哪个端口优先进行读写操作，而将另一个端口 BUSY 置 1（BUSY 变为高电平）以延迟其对存储器的访问。优先端口读写操作完成后，被延迟端口的 BUSY 标志复位（变为低电平）后，便可进行被延迟的操作。

   由于冲突访问不可避免，因此双端口存储器的速度不可能提高两倍。

4.2 单体多字存储器

单体多字存储器的构造与存储器位扩展方式完全相同，该方式采用多个并行的存储模块共用一套地址寄存器的方式，按同一地址并行访问不同存储模块的同一单元，从而实现在同一个存储周期内访问多个存储字，提高主存带宽。

充分发挥单体多字存储器特点的前提是指令和数据在主存中连续存放，此时，主存带宽最多可提高 n 倍（n 为存储体的个数），当遇到转移指令或数据没有连续存放时，该结构存储器的加速效果就不明显。

4.3 多体交叉存储器

多体交叉存储器也由多个存储模块构成，这些模块的容量和存取速度相同，具有各自独立的地址寄存器、地址译码器、驱动电路和读写控制电路。根据对多个模块编址方式的不同，又可分为高位多体交叉和低位多体交叉两种方式。

4.3.1 高位多体交叉存储器

高位多体交叉方式的主要目的是为了扩展存储器的容量，与存储字扩展完全相同，即用高位段地址经过译码后产生片选信号，选择不同的存储体，而低位段地址直接选择一个存储体内的不同存储单元。高位交叉的这种组织方式将地址顺序分配给一个模块后，接着按顺序为下一个模块分配地址，因此，高位多体交叉方式又称完全顺序方式。

由上图可以看出高位多体交叉方式下数据组织的特点：

• 相邻的地址在同一存储体内。
• 不同存储体中的地址不相邻。

由于程序具有局部性和连续性的特点，当采用高位交叉组织存储器时，同一个存储体中的地址单元是连续的，这样执行程序过程中的指令和数据基本分布在同一个存储体中，往往导致一个存储体访问频繁，而其他存储体基本处于空闲状态，无法实现存储体并行工作。

高位多体交叉的存储器一般应用在共享存储器的多机系统中，在这些系统中，各处理机通常访问各自所需的数据对象，当这些数据对象放在不同存储体中时，存取操作可并行进行。

4.3.2 低位多体交叉存储器

与高位多体交叉的地址组织方式不同，低位多体交叉方式下，用高位段地址直接选择一个存储体内的不同存储单元，而低位段地址经过译码后产生片选信号，选择不同的存储体，因此称为低位多体交叉方式。

低位交叉方式在进行地址划分时，将顺序的 M 个地址依次分配给 M 个存储模块后，再将下面的 M 个地址又依次分配给 M 个存储模块，照此法将全部线性地址分配完。

从上图可以看出低位多体交叉方式下数据组织的特点：

• 相邻的地址处在不同存储体内。
• 同一存储体中的地址不相邻。

设存储模块的存储周期是 T，总线传输周期及相应的处理延迟总和为 τ，交叉模块数为 m，要实现流水线方式存取，应该满足的条件是：
$T = m \tau$T=mτ

即每个模块启动后经过 τ 时间的延时，就可以启动下一个模块。

上图为 m = 4 时，CPU 以流水方式访问各存储模块的示意图，从中可以看出：

• 每个存储模块的存储周期仍然为 T。
• 各个存储体错开 1/4 个存储周期分时启动读写操作，各存储体的内容也分时传送，每个存储周期内可访存 4 次。

低位交叉存储器比较适合单处理机内的高速数据存取以及带 cache 的主存，为简化硬件电路，一般存储体的模数 M 取 2 的方幂，有的则采用质数个模，以进一步减少访问存储器的冲突概率。

5 高速缓冲存储器（cache）

虽然 CPU 主频的提升会带动系统性能的改善，但系统性能的提高不仅取决于 CPU，还与系统架构、指令结构、信息在各个部件之间的传送速度及存储部件的存取速度等因素有关，特别是和 CPU 与内存之间的存取速度有关。

若 CPU 工作速度较高，但内存存取速度相对较低，则造成 CPU 等待，降低处理速度，浪费 CPU 的能力。

减少 CPU 与内存之间的速度差异的途径主要有以下 4 种：

• 在基本总线周期中插入等待周期，但这样会浪费 CPU 的能力。

• 采用新型高速存储器，包括双端口存储器、低位多体交叉存储器等。

• 采用存取时间较快的 SRAM 作存储器。

• 在慢速的 DRAM 和快速 CPU 之间插入一至多级速度较快、容量较小的 SRAM，起到缓冲作用，使 CPU 既可以以较快速度存取 SRAM 中的数据，又不使系统成本上升过高，这就是 cache 法。

cache 法是目前计算机系统中广泛使用的一种减少 CPU 与内存之间速度差异的方法，可以通过思考如何解决下列 4 方面的问题来研究 cache 的工作原理：

• 内存中的数据放在 cache 的什么地方？向 cache 中放置数据时登记什么信息？

• CPU 访问存储器时如何判断所访问的内容是否在 cache 中？

• cache 放满时，如有新的数据调入，按照什么策略替换 cache 中原有的数据？

• 写 cache 时是否写主存？

5.1 程序访问的局部性原理

对大量典型程序运行情况的分析结果表明，在一个较短的时间间隔内，由程序产生的地址往往集中在存储器逻辑地址空间的很小范围内，这种对局部范围的存储器地址频繁访问，而对此范围以外的地址则访问甚少的现象，就称为程序访问的局部性。

局部性又表现为时间局部性和空间局部性：

• 时间局部性是指当程序访问一个存储位置时，有很大的可能性程序会在不久的将来再次访问同一位置，程序的循环结构和过程调用就很好地体现了时间局部性。
• 空间局部性指一旦程序访问了 某个存储单元，则不久之后，其附近的存储单元也将被访问。因为计算机中数据通常以向量、数组、树、表、记录等形式连续地放置在主存的相邻位置，而对指令而言，在不发生转移的情况下也是顺序存储、顺序执行。

利用程序的局部性原理，可以在主存和 CPU 通用寄存器之间设置 cache，把正在执行的指令地址附近的一部分指令或数据从主存调入这个存储器，供 CPU 在一段时间内使用，从而提高 CPU 访问存储系统的速度。当程序继续执行时，程序访问的时间局部性和空间局部性也随着时间逐渐变化，新的数据将不断从主存调入 cache，替换掉其中旧的数据。

5.2 cache 的工作原理

5.2.1 主存地址的划分

为了便于比较和快速查找，cache 和主存都被分成若干大小相等的块，每块又包含若干个字。显然，cache 分块数远远小于主存的分块数。除分块外，还根据不同的地址映射方法对 cache 和主存地址进行不同的逻辑划分，其中有的映射方法还对主存的块地址继续划分为标记和索引两部分。

图中不同字段的作用分别如下：

• 主存块地址：是对 CPU 访问主存单元地址按块大小划分后得到的一个地址，用于标识 CPU 所访问的主存单元所在的主存块号，通过该地址可以缩小查找的范围。

• 块内偏移地址：又称块内地址，表示 CPU 所要访问的单元在某块内的偏移值，找到数据所在的块后，根据该值可以定位 CPU 要访问的具体单元。

• 索引：索引是对主存块地址进一步划分后得到的更细粒度的地址，用于指示 CPU 访问 cache 的位置，即作为cache 存储体的地址指示器，指出 CPU 访问 cache 存储体的范围，如指定 cache 的某一行或某几行。不同的映射方法索引字段的位数不同，所指示的 cache 存储体地址的范围大小也不同。特殊地，当某种映射方法对主存块地址不再划分出索引字段时，表示 CPU 将在 cache 的全部范围内进行查找。

• 标记：标记也是对主存块地址进一步划分后得到的更细粒度的地址，作为判断 CPU 要访问的内容是否在 cache 中的依据。不同的地址映射方法具有不同的标记产生方法，特殊地，当某种映射方法对主存块地址不再划分出索引字段时，则主存块号整体作为标记使用。

要注意区分不同映射方式下对主存地址的不同划分，这是掌握 cache 工作原理的关键。

5.2.2 cache 的基本结构

cache 结构主要包括 3 部分：

• 第一部分是数据存储体，用于存放主存数据的副本；
• 第二部分是标记存储体，用于存放标记，不同类型的映射方法标记位数不同，因此，所需要的标记存储体的容量也不同；
• 第三部分是有效位，用来标识存放在 cache 中的数据是否有效，CPU 查找 cache 以及 cache 更新时都需要使用有效位。

在设计 cache 的容量时，要综合考虑数据存储体、标记存储体和有效位等 3 部分的容量。

5.2.3 cache 的组织

cache 与 CPU 之间通过数据线、地址线和控制线相连，同时 cache 的地址线和数据线分别通过单向缓冲区和双向缓冲区与系统总线相连，从而与主存相连。当 CPU 根据主存地址在 cache 中找到要访问的内容（称为命中）时，地址线和数据线缓冲关闭，CPU 访问 cache，当不命中时，打开地址和数据缓冲区，CPU 访问主存，数据通过数据线反馈给 CPU 的同时还要根据某种规则装入 cache 的数据存储体中，同时登记标记，具体位置由访问主存的地址中划定的索引字段确定。

5.2.4 CPU 访问 cache 的流程

根据上面的流程图，下面以读操作为例，分析高速缓存系统的工作流程：

• （1）对 CPU 访问存储器的地址进行逻辑划分得到标记、索引、块内地址。

• （2）按照索引字段的值从 cache 标记存储体的特定单元读出标记值，并与（1）中的标记值进行比较。

• （3）比较结果相同（称为命中），形成 cache 地址。

• （4）根据形成的 cache 地址访问 cache 数据存储体，其中标记部分定位访问数据存储体的范围，然后由块地址在该范围内找到具体的访问单元。

• （5）从 cache 中读出信息送往 CPU。

• （6）比较结果不同（称为缺失），执行 cache 替换策略。

• （7A）cache 未满，将信息从主存调入 cache 的数据存储体中，存放的具体位置与采用的地址映射方法有关，仍然由索引字段指出。

• （7B）cache 已满，将 cache 数据存储体中某单元的数据块交换到主存中，被换出数据的单元地址也由索引字段指出。

• （8）从主存向 cache 数据存储体调入数据块，同时将 CPU 访问单元的信息直接传送给 CPU。

• （9）更新 cache 标记存储体中特定单元中的标记，单元的地址与采用的地址映射方法有关，仍然由索引字段指出。

我们可以根据上述内容得出不同情况下 CPU 访问 cache 的流程：

1. cache 命中的流程：（1）→（2）→（3）→（4）→（5）

2. cache 缺失但未满的流程：（1）→（2）→（6）→（7A）→（8）→（9）

3. cache 缺失且已满的流程：（1）→（2）→（6）→（7B）→（7A）→（8）→（9）

5.2.5 cache 的命中率

为评价 cache 系统的效果，引入命中率的概念。设 N_c 为某程序运行期间命中 cache 的次数，N_m 为从主存中访问信息的次数，则命中率（hit ratio）H 定义为：
$H = \frac {N_c} {N_c + N_m}$H=Nc​+Nm​Nc​​

则 1 - H 为缺失率（miss ratio），或称为未命中率，若以 t_c 表示命中时 cache 的访问时间，t_m 表示未命中时主存的访问时间，则 cache / 主存系统的平均访问时间 t_a 为：
$t_a = Ht_c + (1 - H)t_m$ta​=Htc​+(1−H)tm​

设计高速缓冲存储器的目标是，以较小的硬件开销而使 cache / 主存系统的平均访问时间 t_a 越接近 t_c 越好，若以 e = t_c / t_a 作为访问效率，则有：
$E = \frac {t_c} {t_a} = \frac {t_c} {Ht_c + (1 - H)t_m} = \frac {1} {H + (1 - H)r} = \frac {1} {r + (1 - r)H}$E=ta​tc​​=Htc​+(1−H)tm​tc​​=H+(1−H)r1​=r+(1−r)H1​

其中 r = t_m / t_c 表示主存访问时间与 cache 访问时间的倍数。

存储系统的访问效率与 r 和 H 有关，命中率 H 的值越接近 1，访问效率越高，另外 r 的值不能太大，一般以 5 ~ 10 为宜。

5.3 相联存储器

与一般存储器不同，相联存储器是一种按内容访问的存储器（Content Addressable Memory，CAM），举个例子，在课堂上点名就是典型的按内容访问，如果是按座位的行列编号（对应地址访问）点名，则需要通过这名学生所在座位的行列号，如第五排第四列等信息进行，显然按座位号点名没有直接喊学生的名字方便，通过这个简单的例子我们能体会到按内容访问的特点就是快速。

相联存储器一般由存储体、检索寄存器、屏蔽寄存器、符合寄存器、比较线路、代码寄存器、控制线路等几部分组成：

• 检索寄存器：用来存放检索字，其位数和相联存储器的存储单元位数相等。

• 屏蔽寄存器：屏蔽寄存器也称为表征码寄存器，用于存放屏蔽码，以确定检索寄存器参与检索的位数。

• 符合寄存器：存放按检索项内容检索 cache 存储体时命中的存储体单元的地址，符合寄存器的位数与相联存储器的存储单元数相等。

• 比较线路：把检索项和从存储体中读出的单元内容的相应位进行比较，如果比较结果为相同（即符合），就把符合寄存器的相应位置 “1”，表示该字已被检索到。

• 代码寄存器：用来存放存储体中读出的数据，或者存放向存储体中写入的数据。

• 存储体：由高速半导体存储器构成，以求快速存取，用于存放标记，相联存储器中的存储体即 cache 中的标记存储体。

• 译码选择电路：根据符合寄存器的状态译码选出被检索命中的地址，并将其中的内容读出送代码寄存器。

在计算机系统中，相联存储器主要用于虚拟存储器中存放段表、页表和快表以及高速缓冲存储器中的查找。

5.4 cache 的地址映射及变换方法

地址映射是指把主存地址空间映射到 cache 的地址空间，即把存放在主存中的程序或数据按照某种规则装入到 cache，并建立两者之间地址的对应关系，实现这一功能的函数称为映像函数。地址变换是指在程序运行时，根据地址映像函数把主存地址变换成 cache 地址。地址映射与变换方法相关，不同的地址映射方法具有不同的地址变换方法。

为便于比较，下面对不同映射方法的举例皆基于下列假设：

• cache 的容量为 4K 字节。

• cache 和主存储器中，数据块的大小为 256 字节，即 cache 被分成 16 块，cache 块也称为 cache 行。

• 主存储器的容量为 1M 字节，主存地址 20 位，主存被划分成 4096 个块。

• 指令或数据从主存的 0 号单元开始存放。

5.4.1 全相联映射（Associative Mapping）

全相联映射方式下，只对主存和 cache 分块，因此，两者的地址只包含块号和块内地址两部分，全相联映射方式下主存地址的逻辑划分为：

根据假设，f 字段长 12 位，w 字段长 8 位，这里块号（对应 f 字段）为标记，全相联映射方式下对主存地址的逻辑划分中不包含索引，因此，该映射方式下主存地址与 cache 地址之间的对应关系为多对多，即主存中的块可装入 cache 中的任意行，与此同时，将块地址（即标记）填入 cache 标记存储体的对应行中，作为 cache 行与主存块之间的映射关系。

由于没有索引，地址变换时，需要将 cache 所有行的标记部分送到比较器中与当时访问地址中的标记部分进行对比，判断 CPU 所要访问的内容是否存在于 cache 中。

举个例子，假定 CPU 访问主存第 1085 号单元（从0开始编址），先将该地址变成二进制地址，并划分成块地址和块内地址两部分：
$000000000100~~~~00111101$000000000100    00111101

即主存 1085 号单元处于主存第 4 块内第 61 个单元，其中 000000000100 对应该字所在的主存块号即标记部分，后面 8 位 00111101 对应该字的块内地址。

第一次访问该字时 cache 不命中，此时映射算法将该字所在的主存块调入 cache 任意一空行的数据存储体中（本例假定在 cache 第 10 行中），同时将块号 000000000100 作为标记存入 cache 标记存储体第 10 行中，作为 cache 行与主存块之间的映射关系。

若在访问第 1085 号单元后 CPU 接着访问第 1087 号单元，该单元地址对应的二进制值为：
$000000000100~~~~00111111$000000000100    00111111

地址变换时将 cache 标记存储体中所有标记送往比较电路与 000000000100 比较，显然，本次比较的结果将发现主存第 1087 号单元的内容存放在 cache 第 10 行中，由于一行中包含 256 个字节，因此第 1087 号单元属于该块内第 63 个单元，即通过二进制地址的最后 8 位从该行中选出 CPU 所要访问的字节。

再看慕课上的一个例子：

全相联映射方式具有以下特点：

• 主存数据块可以映射到 cache 的任意一行，因此 cache 利用率高。
• 只要 cache 中还有空行就不会引起冲突，因此 cache 的冲突率低。
• 因每次地址变换时要比较 cache 所有行的标记值，因此比较电路复杂，且复杂程度与 cache 的行数有关。
• 适合于小容量 cache 使用。

5.4.2 直接映射（Direct Mapping）

直接映射采用了与全相联不同的主存地址划分方法，在对主存分块的基础上，直接映射还对主存分区，每个分区中包含的块数与 cache 中包含的行数相同，直接映射对主存地址的逻辑划分为：

这里主存区号（对应 f 字段）为标记、区内块号（r 字段）为索引，根据假设，直接映射方式下，主存被分成 256 个区，每区中有 16 块，每块 256 字节，因此，w 字段 8 位，r 字段 4 位，f 字段为 8 位。

根据直接映射的算法，主存数据块调入到 cache 的位置就由索引字段指定，同理，标记在标记存储体中的位置也由该索引字段的值确定。

举个例子，假定 CPU 访问主存第 1085 号单元（从 0 开始编址），该地址采用直接映射进行的逻辑划分为：
$00000000~~~~0100~~~~00111101$00000000    0100    00111101

其中前 8 位对应该字所在主存区号即标记部分，中间 4 位对应区内块号即索引字段，后面 8 位对应块内地址。

第一次访问该字时 cache 不命中，根据映射算法，该字所在的主存块将调入 cache 数据存储体第 4 行中，同时将区号 00000000 作为标记存入 cache 标记存储体第 4 行中，作为 cache 行与主存块之间的映射关系。

假定在访问第 1085 号单元后 CPU 接着访问主存第 1087 号单元，将该单元地址按照直接映射算法进行逻辑划分后得到：
$00000000~~~~0100~~~~00111111$00000000    0100    00111111

地址变换时，只需将 cache 标记存储体中第 4 行所存储的标记值与 00000000 比较，显然，这次比较的结果是访问 cache 命中，CPU 将从 cache 数据存储体第 4 行中读取所访问的信息，即第 4 行中的第 63 个单元中的数据。

然而，当 CPU 继续访问主存 5183 号单元时，对应的二进制地址为：
$00000001~~~~0100~~~~00111111$00000001    0100    00111111

仍然会访问 cache 第四行，但由于第四行的标记不等于 00000001，因此，本次访问不命中，CPU 从主存中读取数据，并用 5183 号单元所在的主存块将 cache 第四行中原来的块替换出来。

直接映射方式具有以下特点：

• 由于主存的一个数据块只能映射到 cache 的特定行，因此 cache 利用率低。
• 索引值相同的所有主存块映射到 cache 的同一行，因此 cache 的冲突率高。
• 地址变换时只根据索引值取 cache 特定行的标记值进行比较，因此，比较电路简单，与 cache 的行数无关。
• 适合于大容量 cache 使用。

再看慕课上的一个例子：

5.5 替换算法

如果 cache 中已经装满数据，当新的数据块要装入时，必须将 cache 中原存的数据块替换掉，常用替换算法主要有四种。

替换算法与 cache 的组织方式紧密相关：

• 对于直接映射的 cache 来说，因一个主存块只有一个特定的行位置可存放，所以不需要使用任何替换算法，只要有新的数据块调入，此特定行位置上的原数据一定会被换出。
• 对于全相联映射的 cache 来说，执行替换算法时，涉及全部 cache 行。
• 对于组相联映射的 cache 来说，执行替换算法只涉及特定组中的行。

5.5.1 先进先出算法（FIFO，First In Firs Out）

基本思想：按照数据块进入 cache 的先后决定替换的顺序，即在需要进行替换时，选择最先被调入 cache 中的块作为替换块。

实现方法：为每个数据块记录它们进入 cache 的先后次序。

优点：系统开销较小。

缺点：不考虑程序访问的局部性，可能会把一些需要经常使用的块（如循环程序块）也作为最早进入 cache 的块而替换掉，因此可能导致 cache 的命中率不高。

举例：

5.5.2 近期最少使用算法（LRU，Least Recently Used）

基本思想：将近期内长久未被访问过的行或数据块换出。

具体操作：每个行或数据块设置一个未访问次数计数器，cache 每命中一次，命中的行或数据块的计数器清零，其他各数据块计数器增 1，当需要替换时，比较各特定行的计数值，将计数值最大的行换出。

优点：保护了刚调入 cache 的新数据，符合 cache 工作原理，因而使 cache 有较高的命中率。

举例：

5.5.3 最不经常使用算法（LFU，Least Frequently Used）

基本思想：将一段时间内被访次数最少的那行数据换出。

具体操作：每行或数据块设置一个计数器，新调入行或数据块的数据从 0 开始计数，每访问一次被访问行或数据块的计数器增 1，当需要替换时，对这些特定行或数据块的计数值进行比较，将计数值最小的行或数据块换出。

缺点：一段期间访问情况不能严格反映近期访问情况，例如特定行中的 A、B 两行，A 行在期间的前期多次被访问而后期未被访问，但累积计数值很大，B 行是前期不常用而后期却正被频繁访问，但可能由于累积计数小于 A 行而被 LFU 算法换出。

举例：

5.5.4 随机替换算法（Random Replacement）

基本思想：需要进行替换时，从特定的行位置中随机地选取一行进行替换。

优点：这种策略硬件实现最容易，而且速度也比前几种策略快。

缺点：随意换出的数据很可能马上又要用，从而降低命中率和 cache 工作效率，但这个负面效应随着 cache 容量的增大会减少，模拟研究表明随机替换策略的功效只是稍逊于 LFU 和 LRU。

5.6 cache 的写策略

CPU 在执行程序期间除对 cache 进行大量的读操作外，也存在对 cache 的写操作，常见的写策略主要有写回法和写直达法两种。

需要注意的是，当考虑多处理机和采用 DMA 方式的外设时，无论采用 WB 还是 WT 写策略，任何一种写 cache 的方法都可能导致 cache 与主存中数据的不一致性，这需要其他同步机制来解决这一问题。

5.6.1 写回法 WB（Write-Back）

使用这种策略，当 CPU 对 cache 写命中时，只修改 cache 的内容而不立即写入主存，只有当此行被换出时才写回主存，这种策略使 cache 不仅在读方向而且在写方向上都起到高速缓存作用。为支持这种策略，每个 cache 行必须配置一个修改位，也称为脏位，以反映此行是否被 CPU 修改过，如被修改过则该位为 1，反之则为 0。当某行被换出时，根据此行的脏位为 1 还是为 0，决定是将该行内容写回主存还是简单地丢弃。

对于 cache 写未命中的处理，先将相关主存块按照映射算法调入 cache，然后再对其进行修改。显然，这种写 cache 与写主存异步进行方式可显著减少写主存次数，但写回法也带来 cache 与主存的数据的不一致性，可能会导致 DMA 操作获得的数据不是最新的数据。

5.6.2 写直达法 WT（Write-Through）

也称写贯通法或全写法，其基本思想是当 cache 写命中时，同时对 cache 和主存中同一数据块进行修改，当 cache 写未命中时，直接向主存写入新的信息，但此时是否将修改过的主存块调入 cache，写直达法却有两种选择。一种是将数据调入 cache，称为写分配法 WA（Write-Allocate），另一种是不取主存块到 cache，而是直接写主存，称为非写分配法 NWA（No-Write-Allocate）。

写直达法是写 cache 与写主存同步进行，其优点是 cache 每行无须设置一个修改位以及相应的判测逻辑，而且发生块替换时，被换出的数据块不需要写回主存。80486 处理器片内 cache 采用的就是写直达法，这可从其组织结构中无修改位看出。写直达法的缺点是，cache 对 CPU 向主存的写操作无高速缓冲功能，降低了 cache 的功效。

写直达法较好地维护了单 CPU 环境下 cache 与主存的内容一致性，但是在多处理器系统中各 CPU 都有自己的 cache，当一个主存块在多个 cache 中都有一份副本时，即使某个 CPU 以写直达法来修改它所访问的 cache 主存内容时，仍然无法保证其他 CPU 中 cache 内容的同步更新。

5.7 多 cache 结构

在前面的三级存储系统中，cache 是其中一级，且处在 CPU 与主存之间，不过，近年来，多 cache 在计算机系统中已普遍采用。多 cache 结构分两种，一种是多级 cache，即 CPU 片内和片外都设立 cache，另一种是指令和数据分开的 cache，称独立 cache。

• 片内和片外两级 cache

  将 cache 和处理器集成在同一芯片内，这个 cache 称为第一级 cache（L1）。由于 L1 在 CPU 芯片内，因而减少了对片外总线的访问，加快了存取速度，提高了系统性能。

  因为 L1 cache 的容量通常较小，若 CPU 要访问的数据不在 L1 cache 时，就要通过总线访问主存，而主存和总线的速度较慢，这将影响系统的速度，为解决这个问题，在 CPU 片外与主存间再设置一个 cache，这就是通常所说的 cache，这里称为第二级 cache（L2）。多级缓存的使用，大大提高了系统的性能。

• 统一和独立 cache

  L1 cache 刚出现时，通常将指令和数据都存放其中，称为统一 cache。后来由于计算机系统结构中采用了一些新技术（如指令预取），需要将指令 cache 和数据 cache 分开设计，这就是独立 cache 结构。

  统一 cache 的优点是设计和实现相对简单，而且由于指令和数据都在其中，命中率相对较高。但由于执行部件存取数据时，指令预取器又要从同一 cache 读指令，两者发生冲突，所以采用独立 cache 结构来解决这个问题。

6 虚拟存储器

6.1 虚拟存储器的工作原理

存储系统设计的基本目标是设计一个访问速度快、存储容量大的存储系统。在存储系统中采用 cache 大大提高了存储系统的访问速度，然而它不能解决存储系统的容量矛盾，一方面，受技术和成本的限制，主存空间不可能无限扩大，最大主存空间受限于 CPU 可寻址主存空间，另一方面，程序员总希望能够有一个大于主存空间的编程空间，这样编写程序不受实际主存大小的限制，再者，计算机系统中同时运行着多个进程，每个进程都需要有自己的地址空间，不可能为每个进程都提供整个地址空间的存储器。虚拟存储器是解决上述问题的有效方法，目前，几乎所有的计算机都采用了虛拟存储器系统。

在存储系统的层次结构中，虚拟存储器处于 “主存-辅存” 存储层次，通过在主存和辅存之间增加部分软件（如操作系统）和必要的硬件（如地址映射与转换机构、缺页中断结构等），使辅存和主存构成一个有机的整体，就像一个单一的、可供 CPU 直接访问的大容量主存。程序员可以用虚拟存储器提供的地址（称为虚拟地址）进行编程，这样，在实际主存空间大小没有增加的情况下，用户编程不再受实际主存空间大小的限制，因此，把这种存储系统称为虚拟存储器。注意，由于虚拟存储器的存在，程序员使用比主存空间更大的逻辑地址空间编程序，因此在作业运行的时候，需要将作业当前执行的部分调入内存，而其余部分仍然存放在磁盘中，从而减少对主存的消耗。

在虚拟存储系统中程序运行时，CPU 以虚拟地址访问主存，由存储管理控制部件 MMU（Memory Management Unit）找出虚地址和实地址之间的对应关系，并判断这个虚地址对应的内容是否已经在主存中。如果已经在主存中，则通过 MMU 的地址变换机构将虛拟地址变换成物理地址，CPU 直接访问主存单元，如果不在主存中，则把包含这个字的一页或一个程序段（与采用的虚拟存储器的类型有关）调入主存，并向 MMU 中填写相关的标志。

根据虚拟存储器中对主存逻辑结构划分的粒度不同，虚拟存储器可分成 3 种不同的类型，分别是页式、段式和段页式虚拟存储器。

6.2 虚拟存储器的地址映射与变换

在虚拟存储器中有 3 种地址空间：

• 第一种地址空间是虚拟地址空间，也称为虚拟空间，它是应用程序员用来编写程序的地址空间。
• 第二种地址空间是主存地址空间，也称物理地址空间或实地址空间。
• 第三种地址空间是辅存地址空间，也就是磁盘存储器的地址空间。

与这 3 种地址空间相对应，有 3 种地址，即虚拟地址、主存地址和磁盘存储器地址（也称磁盘地址或辅存地址）。

我们知道，cache 中的地址映射是将主存中的数据按照某种规则调入 cache，虛拟存储器中的地址映像也有类似的功能，它把虚拟地址空间映像到主存空间，也就是将用户利用虚拟地址访问的内容按照某种规则从辅助存储器装入到主存储器中，并建立虚地址与实地址之间的对应关系。而地址变换则是在程序被装入主存后，在实际运行时，把虚拟地址变换成实地址或磁盘存储器地址，以便 CPU 从主存或磁盘中读取相应的信息。

6.3 页式虚拟存储器

以页（Page）为逻辑结构划分和信息传送单位的虚拟存储器称为页式虚拟存储器，在页式虚拟存储器中，虚拟空间和主存空间均划分成固定大小的页，不同类型的计算机对页大小的划分不同，有的页大小只有几百字节，也有的计算机系统中页的大小达几千字节。

6.3.1 页式虚拟存储器的地址划分

在页式虚拟存储器中，虚拟地址被划分成虚拟页号（Virtual Page Number，v*n）和虚拟页偏移量（Virtual Page Offset，VPO），同时物理地址被划分成物理页号（Physical Page Number，PPN）和物理页偏移量（Physical Page Offset，PPO）两部分。v*n 和 PPN 分别构成虚拟地址和物理地址的高位部分，VPO 和 PPO 分别构成虚拟地址和物理地址的低位地址，其位数决定了页面大小。因为物理页和虚拟页大小相同，因此 VPO 和 PPO 的位数相同。

6.3.2 地址转换的基本原理

物理地址由 PPN 和 PPO 两部分构成，虚拟地址到物理地址的映射本质上就是如何将 v*n 转换成对应的 PPN，页虚拟存储器中虚拟地址到物理地址转换的基本原理如图所示：

页式虚拟存储器中虚拟地址与物理地址之间的转换基于页表进行，页表是一张保存虚拟页号和物理页号（也称实页号）之间对应关系的表格，由若干个表项组成，每一个表项又包括有效位和物理页号两部分。页表常驻内存，并通过虚地址中的虚页号作为索引来访问，因此，页表项的数量与虚拟地址中虛页号字段的位数有关，如虚页号字段为 20 位，则页表中表项的数量为 2²⁰。利用虚页号实现虚拟地址转换成物理地址的过程如图所示：

图中的页表基址寄存器（Page Table Base Register，PTBR）用于指出页表在内存中的位置，通过与 v*n 相结合就能访问到页表中与虚拟页号 v*n 相对应的物理页号 PPN，从而实现虚拟地址到物理地址的转换。

6.3.3 结合 cache 的页式虚拟存储器地址转换

在任何既使用虚拟存储器又使用 cache 的存储系统中，一般采用物理地址访问 cache，下图展示了一个结合 cache 的页式虚拟存储器的地址转换过程：

图中所用符号的意义如下：

• VA（Virtual Address）：虛拟地址。
• PTEA（Page Table Entry Address）：页表项地址。
• PTE（Page Table Entry）：页表项。
• PA（Physical Address）：物理地址。

图（a）展示了页面命中时，CPU硬件执行的步骤：

1. 处理器生成一个虛拟地址，并把它传送给 MMU；

2. MMU 利用页表基址寄存器 PTBR 和虚页号生成页表项地址 PTEA，访问存放在高速缓存 / 主存中的页表，请求与虚拟页号对应的页表项内容。

3. 高速缓存 / 主存向 MMU 返回页表项 PTE，以构成所访问信息的物理地址。

4. 若返回的 PTE 中有效位为 1，则 MMU 利用返回的 PTE 构造物理地址，并利用构造出的物理地址访问高速缓存 / 主存。

5. 高速缓存 / 主存返回所请求的数据给处理器。

图（a）中当返回的PTE中有效位为 0 时，表示 CPU 要访问的页不在主存中，此时将出现页面不命中的情况，此时，将不能按照图（a）的处理流程来访问存储系统。处理缺页要求硬件和操作系统内核协作完成，图（b）给出了页面不命中的处理流程：

1. 处理器生成一个虚拟地址，并把它传送给 MMU。

2. MMU 利用页表基址寄存器 PTBR 和虚页号生成页表项地址 PTEA，访问存放在高速缓存 / 主存中的页表，请求与虚拟页号对应的页表项内容。

3. 高速缓存 / 主存向 MMU 返回页表项PTE，以构成所访问信息的物理地址。

4. 若 PTE 中有效位为 0，则表明所访问的页不在主存，MMU 触发一次异常，调用操作系统内核中的缺页异常处理程序。

5. 缺页处理程序根据替换算法确定出将被淘汰的页，如果这个页面的修改位为 1，则把该页面换出到磁盘，否则直接丢弃。

6. 缺页处理程序从磁盘中调入新的页，并更新存储器中的 PTE。

7. 缺页处理程序返回到原来的进程，驱使导致缺页的指令重新启动。CPU 将引起缺页的指令重新发送给 MMU，然后再重新执行图（a）中的（2）~（5）步。

6.3.4 利用 TLB 加速虚拟存储器地址转换

从上面的分析不难发现，即使不发生缺页异常，CPU 必须访问一次高速缓存 / 主存获得 PTE 后才能实现虚拟地址到物理地址的转换，如果发生缺页异常，则需要访问高速缓存 / 主存 3 次才能实现虚拟地址到物理地址的转换。为了降低虚拟存储器地址转换的开销，根据局部性原理，现代处理器都维护着一个转换旁路缓冲器 TLB（Translation Look-aside Buffer）作为页表映像的一部分。TLB 的组织与 cache 的组织方式类似，一般具有较高的关联度，大多采用全相联或组相联方式。当采用组相联方式时，按照组相联 cache 的地址划分方法，将虚页号划分成 TLB 标记和 TLB 索引两部分，便于快速判断所要访问的页面是否在主存，当页命中时还能在 MMU 中利用 TLB 返回的 PTE 完成虚拟地址到物理地址的转换。

下图展示了利用 TLB 加速虚拟存储器地址转换的基本流程：

图中（a）展示了 TLB 命中时所包括的步骤：

1. 处理器生成虚拟地址，并把它传送给 MMU；

2. MMU 利用虚页号 v*n 查询 TLB；

3. 如果 TLB 访问命中（页表项在 TLB 中且相应 PTE 中有效位为 1），则 TLB 向 MMU 返回与 v*n 对应的 PTE。

4. MMU 利用返回的 PTE 构造物理地址，并利用构造出的物理地址访问高速缓存 / 主存。

5. 高速缓存 / 主存返回 CPU 请求的数据给处理器。

图中（b）展示了 TLB 不命中（假定访问主存命中）时所包括的步骤：

1. 处理器生成一个虚拟地址，并把它传送给 MMU；

2. MMU 利用虚页号 v*n 查询 TLB；

3. 如果 TLB 访问不命中，则向 MMU 返回 TLB 访问缺失信息；

4. MMU 利用页表基址寄存器 PTBR 和虚页号生成页表项地址 PETA，访问存放在高速缓存 / 主存中的页表，请求与虚拟页号对应的页表项内容。

5. 高速缓存 / 主存向 MMU 返回页表项 PTE，以构成所访问信息的物理地址。

6. 若返回的 PTE中 有效位为 1，则 MMU 利用返回的 PTE 构造物理地址，并利用构造出的物理地址访问高速缓存 / 主存。

7. 高速缓存 / 主存返回所请求的数据给处理器。

对比图（a）和图（b）不难发现，采用 TLB 且访问 TLB 命中时，能减少一次访问主存的次数，因此又将 TLB 称为快表，而将存放在主存中的页称为慢表。

下图给出了页式虚拟存储系统中 TLB 和 cache 命中时详细的存储访问过程：

上图中的 TLB 采用全相联，因此 TLB 中的标记部分保存的是虛页号。cache 采用直接映射。TLB 根据 MMU 发过来的虚页号从快表中读出对应的物理页号，并与来自虚拟地址的页内偏移地址构成物理地址访问 cache。访问 cache 时，根据其组织方式将物理地址重新划分成标记和索引两部分，并利用索引字段将 cache 中特定行（组）的标记值取出，与地址中的标记值进行比较，当 cache 命中时，将命中行中的数据取出送往 CPU，该次存储访问完成。

需要说明的是，在包含快表和慢表的页式虚拟存储系统中，在进行地址变换时，往往同时查快表和慢表，如果查快表命中，则从快表中获得与虚页号对应的实页号同时终止查慢表的过程，这样就可以在几乎不降低主存访问效率的情况下访问虛拟存储器。页式虚拟存储器中，页的大小固定且都取 2 的整数次幂个字节，因此，在页式虚拟存储系统中可以将虚拟存储空间和实存空间进行静态的固定划分，与所运行的程序无关，即页式虚拟存储器对程序员透明。页式虚拟存储器面向存储器自身的物理结构分页，有利于存储空间的利用与调度。但页式虚拟存储器不能反映程序的逻辑结构，一个在逻辑上独立的程序模块被划分成很多个页面，给程序的执行、保护和共享等都带来了不便。

6.4 段式虚拟存储器

以段作为基本信息单位在主存与辅存之间进行传送和定位的虛拟存储器称为段式虚拟存储器，一般将主存空间按照实际运行程序中的段来划分，因此段长可大可小。

段式虚拟存储器中使用段表实现虚拟地址到物理地址的转换，段表项除包含段基址和装入位外，为了适应段长的可变特性，还需要增加一个段长字段。段基址是该段在主存中的起始地址，指向段中的第一个字；装入位表示该段装入主存与否；段长表示程序段占用了多少主存空间，它可用来检查访问地址是否越界。段表中还可以设置其他控制字段，如读、写和只能执行等，以作为对段保护的依据。

段式虚拟存储器虚拟地址由段号和段内偏移地址两部分组成，基于段表的虚拟地址与物理地址变换过程如下图所示，程序运行时根据段表基址寄存器的值与虚拟地址中的段号访问段表，获取该段的段基址。当装入位有效时，段基址与段内地址拼接组成物理地址。对于多道程序环境，一般为每道程序分配一个段表。

与页式虚拟存储器不同，段式虛拟存储器面向程序的逻辑结构分段，一个在逻辑上独立的程序模块可以作为一段来处理，从而使存储空间的划分与程序的自然段对应。以大小可变的段为单位进行调度、传送与定位，有利于对程序的编译、执行、共享与保护。另一方面，由于段的大小可变，不利于存储空间的管理、调度与优化。同时，由于段内必须连续，而各段的首尾地址又没有规律，必然导致地址计算比页式虚拟存储器要复杂。

7 存储保护

为了保证计算机系统能正确运行，当多个用户共享主存时，应防止由于一个用户程序出错而破坏其他用户的程序和系统软件，以及一个用户程序访问不是分配给它的主存区域。

在多道程序运行的情况下，为保证各用户信息资源的安全，系统应提供存储保护。具体来说，在系统中有多道程序处理时，某一程序改写或占用其他程序的存储空间，以及非法的写操作都是不允许的。

在虚拟存储器中，通常采用页保护、段保护和键保护方式。页、 段的保护属同一类型，每道程序都有自己的段表和页表。段表、页表都有自己的保护功能，当虚拟的段号或页号出错时，在段表和页表中将找不到相应的实段或页，也就访问不了主存，也就不会侵犯其他程序空间。

这种段表、页表给出的保护是在形成主存地址前的保护，若是在地址变换中出现错误，则产生了错误的主存地址，此时可采用键保护。

键保护的基本思想是，为主存每一页分配一个键，称为存储键，每个用户的实存页面的键都相同。每道程序都有访问键，当数据要写入某一页时，访问键要与存储键比较。若两键符合，则允许访问该页，否则拒绝访问。

对于没有采用虚拟存储器的主存储器而言，可采用越界保护方式进行存储保护。系统对每个用户程序划定存储区域，用确定上、下界地址值的方式实现区域保护，用户程序不能改变上、下界值，所以它如果出现错误，也只可能破坏自身的程序，影响不到别的用户程序和系统程序，这是一种禁止越界的保护方式。

8 习题

习题 1 计算机系统中采用层次化存储体系结构的目的是什么？层次化存储体系结构如何构成？

采用层次化存储体系的目的包括两方面：

• 其一是解决快速的 CPU 和慢速的主存之间的速度差异；
• 其二是解决主存容量不够大的问题。

存储系统的分级结构由 Cache、主存和辅助存储器三级结构构成，其理论基础是时间局部性原理和空间局部性原理，Cache-主存存储层次解决了主存速度不快的问题，而主存-辅存存储层次解决了主存容量不足的问题。

习题 2 动态 MOS 存储器为什么要刷新？如何刷新？
动态存储单元中，信息以电荷形式存储在 T1 或 T2 管的栅极电容中，由于电容容量小，所存电荷会在一段时间后逐渐泄漏（一般为 ms 级），为使所存信息能长期保存，需要在电容电荷泄露完之前定时地补充电荷，这一过程称为刷新。

刷新的方法：

• 刷新方式：
  • 集中刷新：存在 CPU 死时间。
  • 分散刷新：刷新次数过多，降低了存储器的速度。
  • 异步刷新：前两者的折中。
• 刷新按行进行，因此设计刷新电路时需要知道动态存储器的内部行、列结构。
• 刷新地址由刷新地址计数提供。