第 5 章存储器层次结构¶

依据：2016 年版教材第 5 章及配套大纲。Cache 和虚拟存储既有简单应用，也有结合程序访存的综合应用要求。下文编号指大纲“考核内容与考核要求”。

复习导航：大纲要求与笔记位置¶

大纲条目	层次	位置	学完应能做到
1 存储器概述	领会	第 1 节	说明分类方式、主存基本结构、容量与存储周期的概念、层次化结构
2 半导体随机存取存储器	领会	第 2 节	说明 SRAM 与 DRAM 特点、刷新、SDRAM 读写、突发传输与行缓存
3 芯片扩展及其与 CPU 的连接	领会；简单应用	第 3 节	说明扩展方式与内存条组织，计算容量、芯片数、引脚数与地址划分
4 半导体只读存储器和 Flash	领会	第 4 节	说明各类 ROM 特点及 Flash 的读写原理
5 高速缓冲存储器 Cache	识记；领会；简单应用；综合应用	第 5 节	计算容量、命中率、平均访问时间、映射行号，分析访存过程的命中情况
6 虚拟存储器	识记；领会；简单应用；综合应用	第 6 节	说明页表功能、缺页处理与 TLB，完成地址转换，分析访存全过程

第 5、6 条是本章仅有的两条同时含综合应用的条目，要求综合运用映射、替换、写策略或页表、Cache 知识分析完整访存过程。其余条目以领会为主，其中第 3 条含简单应用。

本章学习目标¶

本章讨论存储器为什么要分层、各层怎样配合工作。程序访问的局部性是分层能够生效的前提，Cache 与虚拟存储分别是这一原理在两个层次上的应用。计算内容包括容量与芯片数、地址字段划分、命中率与平均访问时间、地址转换。综合应用还要求把 Cache 与虚拟存储放进一次完整的访存过程中分析。

1 存储器概述（1，领会）¶

单一存储器难以同时满足高速、大容量和低成本的要求，因此计算机采用分层组织，由寄存器、Cache、主存和辅存共同保存数据。越靠近CPU，层次的速度通常越快、容量越小，单位容量成本也越高。较快的上层保存下层中近期可能使用的内容，使大部分访问能够在较短时间内完成。这一组织方式依赖程序访问的局部性，具体机制见第 5 节。

容量=单元数×每单元位数。8K×8位是8192个单元、每单元8位，共8 KiB。8K×16位则是16 KiB。存取时间是完成一次读写所需的时间。存储周期是连续两次独立操作允许的最小间隔，其中可能包含恢复时间。

按访问方式可分随机、顺序、直接和相联访问；“随机存取”强调访问时间与位置关系弱，不表示随机选地址。主存地址位数必须结合编址单位。32位字节地址能编码2³²字节的位置；若按字编址，则须另乘字长。

2 半导体随机存取存储器（2，领会）¶

项目	SRAM	DRAM
存储基础	双稳态电路	电容电荷
刷新	不需周期刷新	需周期刷新
常见特点	快、密度较低、单位成本高	密度高、单位成本较低
常见用途	Cache	主存
断电	信息丢失	信息丢失

DRAM读取通常涉及感应和恢复电荷。刷新不等于CPU主动把全部数据重新写入一遍。行列地址可分时复用相同引脚：2ʳ行、2ᶜ列的阵列有2^(r+c)个位置，外部地址引脚不一定需要r+c根，要结合复用方式。

SDRAM按同步时序工作，典型访问为激活行 → 行内容进入行缓存 → 按列读写 → 必要时预充电换行。突发传输在给出一次起始位置后连续传多个数据，省去重复寻址的开销。访问同一已打开的行，与切换行相比代价不同。

DDR在时钟上升沿和下降沿传输。DDR2、DDR3通过预取与接口组织提高传输率。标称数据传输率不要直接再乘2。教材的DDR代际介绍用于理解本书例题，不代表现今产品规格。

3 芯片扩展与 CPU 连接（3，领会、简单应用）¶

单片存储芯片的字宽或单元数不足时，需要组合多片芯片。位扩展让多片芯片共享地址和片选信号，各片数据线并列，每个字的位数由此增加。字扩展保留原有字宽，用低位地址选择片内单元、高位地址译码选择芯片组，可寻址的单元数由此增加。同时采用两种方式称为字位扩展。

若目标M字×W位，单片m字×w位：

位扩展片数＝ W / w；字扩展组数＝ M / m；总片数＝ (M / m) × (W / w)。

例：用8K×8位芯片组成32K×16位存储器，位扩展2片/组、字扩展4组，共8片。每片13位内部地址，整体15位字地址，高2位选组、低13位片内寻址。若CPU按字节编址，还要分析最低位的字节选择，不能把15位字地址原样当作全部字节地址线。

连接时需要匹配地址线、数据线、片选和读写控制，确定地址范围且避免重叠。DRAM内存条容量还取决于芯片密度、每片数据宽度、每rank芯片数和rank数；含校验位的物理容量不一定等于可用数据容量。

4 ROM 和 Flash（4，领会）¶

ROM适于保存固件等非易失内容。PROM可编程写入，EPROM可紫外擦除，EEPROM可电擦写。Flash同样是非易失存储器，通常按较大的块擦除、按页等单位编程，更新不能简单视作SRAM那样的任意覆盖。Flash的擦写寿命、控制器管理与速度特征，都会影响SSD的设计。

5 高速缓冲存储器 Cache（5，识记、领会、简单应用、综合应用）¶

5.1 局部性与基本概念¶

程序访问通常具有两种局部性。时间局部性指近期访问过的内容很可能再次被访问，例如循环中反复使用的变量。空间局部性指某个地址被访问后，其相邻地址也可能随后被访问，例如顺序遍历数组。

Cache利用这两种特性保存近期使用的数据及其相邻内容。CPU可以请求一个字节或一个字，Cache与主存之间却通常按块交换数据。一个主存块装入Cache的一行，该块的大小就等于这一行数据区的大小。

命中率h=命中次数/访问次数，缺失率m=1−h。把“缺失损失P”定义为命中检查之外的额外时间时：AMAT=命中时间+缺失率×P。若题目给的是缺失时完整访问时间Tmiss，则用h×Thit+(1−h)×Tmiss，避免重复计算。

5.2 映射与地址划分¶

设按字节编址，地址宽A位，Cache数据容量C字节，块B字节，E路组相联，组数S=C/(B×E)。若均为2的幂：块内偏移b=log₂B，组索引s=log₂S，标记t=A−s−b。

主存块号=⌊地址/B⌋；组号=主存块号 mod S；标记=⌊主存块号/S⌋。

映射	放置位置	查找与冲突
直接映射	固定一行，E=1	比较简单，同位置块容易冲突
全相联	任意行，S=1	无组索引，需比较多行标记
E路组相联	固定组内任一行	折中，组内需替换选择

例：32位地址、Cache数据区4 KiB、块16 B、2路。总行256，组128；偏移4位、索引7位、标记21位。地址12345678H的块内偏移8，组号67H，标记2468AH。

Cache的容量可以仅指数据区，也可以包含管理信息。若含标记与状态位，容量（位）=行数×(数据块位数+标记位+有效位+脏位等)+替换信息。不能将题目中的“数据区容量”当成含所有开销的总位数。

5.3 替换和写策略¶

LRU替换最久未使用的行，FIFO替换最早进入的行，随机替换则是任选一行。命中时LRU更新近期次序，FIFO的进入次序通常不变。替换只在目标组没有空行、又需要装入新块时才发生。

写直达同时更新Cache和下层，常用写缓冲。写回只修改Cache并置脏位，替换脏行时才回写。写分配让写缺失先调入块再写，非写分配则直接写下层。这两个维度可以组合，题目要分别确认。

5.4 访问序列分析¶

分析访问序列时，需要为每次访问记录地址、块号、组号和标记，再根据该组当前的有效行判断是否命中。发生缺失时，依照替换策略确定装入位置；若替换掉的是写回Cache中的脏行，还要记录回写。本次访问结束时的状态，就是下一次判断的依据。

例如，一个初始为空的直接映射Cache有4行，每块4 B，依次读取字节地址0、1、4、0、16、0。将地址除以4取整，得到块号0、0、1、0、4、0；块号对4取模，得到行号0、0、1、0、0、0。第一次访问0时装入块0，因此接下来的地址1命中。访问4会装入行1，不影响行0，所以再次访问0仍命中。访问16时，块4占用行0并替换块0，最后一次访问0便再次缺失。六次访问中命中两次，命中率为1/3。

综合程序题还要确定数组布局、元素宽度、循环次序、读写次数、初始状态以及变量是否已分配寄存器。行优先二维数组按行连续，跨行扫描常降低空间局部性。不同数组映射到同一组，可能反复冲突。只看总容量足够，并不能保证高命中。

6 虚拟存储器（6，识记、领会、简单应用、综合应用）¶

虚拟存储将程序使用的虚拟地址映射为主存物理地址，并借助辅存提供更大的地址空间与保护、隔离。分页按固定大小的页组织，分段按逻辑单元组织、长度可变，段页式把两者结合起来。

分页系统将地址分为页号与页内偏移两部分。页大小为2ᵖ B时，低p位表示页内偏移，其余高位表示虚页号VPN。地址转换用物理页框号PFN替换VPN，并保留页内偏移，两者是位字段的直接拼接。页表负责保存页号映射；页表项一般还包括有效或驻留信息、保护位、修改位、访问位等。

例：页4 KiB，虚拟地址12345H，VPN=12H，偏移345H；若页表给出PFN=ABH，则物理地址AB345H。不能把VPN直接当PFN，也不能把页号与偏移相加而忘记移位。

TLB缓存近期使用的页表项，以VPN（及必要的地址空间标识等）查询映射。TLB保存的是地址转换信息，Cache保存的是指令或数据块。TLB缺失不等于缺页：页可能已在主存，仅映射尚未缓存。

在串行查询的教学模型中，一次访问先查询TLB。命中时可直接获得页框号。未命中时再查页表；若页面已在主存，就把映射填入TLB并形成物理地址。得到物理地址后查询数据Cache，Cache未命中时再从主存调入数据块。

若页表表明页面不在主存，访问就会触发缺页异常。操作系统完成调页并更新映射后，程序才能恢复相应访问。实际硬件可能重叠一部分查询步骤，多级页表也会增加访问次数。因此时延计算要采用题目给定的组织方式。

Cache缺失通常由硬件处理，缺页要由操作系统参与处理，TLB缺失则可由硬件页表遍历或软件处理。缺页处理可能涉及选择牺牲页、脏页写回、读入目标页、更新页表与TLB。

简单时延例：单级页表、无Cache、无缺页，TLB查询1 ns，主存50 ns，TLB命中率98%，串行查询。命中51 ns，未命中101 ns，平均0.98×51+0.02×101=52 ns。不要把这个模型套到有多级页表、并行TLB/Cache访问的题目。

7 考核要求¶

本章重点为 CPU 与主存之间的连接、内存条插槽与存储器总线的关系、芯片扩展方式、内存条组织方式、DRAM 芯片内存储单元的编址方式、程序访问的局部化特性、Cache 基本工作原理、主存块与 Cache 行的映射关系、虚拟地址向物理地址的转换；难点为 SDRAM 读写过程、突发与行缓存概念、映射关系与地址转换。

8 教材本章习题¶

本节按“单项选择题／填空题／简答题”分节，答案依据教材附录。

自测题（自编）	参考答案与辨析
16K×8 芯片组成 64K×32 需几片？	字扩展 4 组 × 位扩展 4 片＝16 片。
8 KiB 直接映射 Cache、块 32 B、32 位字节地址，字段？	偏移 5、索引 8、标记 19 位。
命中 2 ns、缺失率 5%、额外损失 40 ns，AMAT？	2＋0.05×40＝4 ns。
TLB 未命中需要访问磁盘吗？	不一定，先看页面是否驻留。
LRU 与 FIFO 命中时都更新队列吗？	LRU 更新使用次序，FIFO 不改变入队先后。
Cache 采用写回，替换任意行都写主存吗？	仅有效且脏的牺牲行需要回写。

9 闭卷复习与跨章联系（补充）¶

本章与第 4 章的接口是 MEM 段：Cache 命中与否直接决定一条指令的访存代价，进而影响 CPI。与第 6 章的接口是 I/O 与 DMA 对主存的占用，两者共享同一套存储带宽。虚拟存储与操作系统课程的内存管理是同一机制的不同视角。本章侧重地址转换与硬件协作，操作系统侧侧重分配、置换策略与进程隔离。

第 5 章 存储器层次结构¶