cover.png#计组学习笔记5

存储器概述

存储器用来保存程序和数据。

CPU 执行指令时，绝大多数指令都要访问存储器：

• 取指令需要访问指令存储器
• load / store 需要访问数据存储器
• 函数调用需要访问栈
• cache 缺失需要访问主存
• 缺页需要访问外存

所以存储器不是单独的外围部件，而是影响 CPU 性能的核心部件。

理想的存储器应该同时满足：

• 速度快
• 容量大
• 价格低
• 掉电后不丢失

但现实中这些目标互相矛盾。

越快的存储器通常越贵、容量越小；越大的存储器通常越慢、离 CPU 越远。

因此现代计算机采用存储器层次结构。

存储器分类

按存储元件分类

常见存储器可以分为：

类型	典型用途	特点
半导体存储器	cache、主存、U 盘、SSD	速度快，适合集成电路实现
磁表面存储器	硬盘	容量大，非易失，机械访问较慢
光存储器	光盘	非易失，常用于分发和归档

主存和 cache 主要由半导体存储器实现。

外部辅助存储器主要包括磁盘、U 盘和 SSD。

按存取方式分类

存储器可以按访问方式分为：

类型	访问方式	例子
顺序存取存储器	必须按顺序访问	磁带
直接存取存储器	先定位到区域，再顺序读写	磁盘
随机存取存储器	任意单元访问时间基本相同	SRAM、DRAM
相联存储器	按内容进行查找	TLB、cache 标记比较

这里的随机存取不是随机数的意思。

它指的是：访问任意地址所需时间和地址位置无关。

RAM 就是随机存取存储器。

按可修改性分类

按信息是否能被修改，可分为：

• RAM：可读可写
• ROM：通常只读，写入条件受限制

ROM 也不一定绝对不能写。

例如 EPROM、EEPROM、Flash 都可以在特定条件下重新写入。

按易失性分类

按断电后信息能否保存，可分为：

类型	掉电后数据	例子
易失性存储器	丢失	SRAM、DRAM、cache
非易失性存储器	保留	ROM、Flash、磁盘、SSD

主存通常由 DRAM 实现，是易失的。

磁盘和 SSD 是非易失的，所以可以长期保存文件。

主存储器

主存储器是 CPU 可以直接按地址访问的存储器。

CPU 发出的地址经过地址总线送到主存，主存根据控制信号完成读或写。

主存储器通常包括：

• 存储体
• 地址译码器
• 地址寄存器
• 数据寄存器
• 读写控制逻辑

存储容量

如果主存有 \(2^n\) 个存储单元，每个存储单元有 \(w\) 位，则容量为： \[ 容量=2^n \times w \]

地址线根数决定可寻址单元数。

数据线根数决定一次能传送的数据位数。

例如：

• 20 根地址线，按字节编址，可寻址 \(2^{20}B=1MB\)
• 32 根地址线，按字节编址，可寻址 \(2^{32}B=4GB\)
• 64 根数据线，一次可传送 64 位，也就是 8 字节

访问时间和存取周期

存储器性能常用两个时间指标：

指标	含义
存取时间	从发出地址和命令到数据有效所需时间
存取周期	两次连续存储器访问之间的最小时间间隔

存取周期通常不小于存取时间。

因为一次访问完成后，存储器内部可能还要恢复状态，才能进行下一次访问。

读操作

主存读操作的大致过程：

• CPU 给出地址
• 地址译码器选择对应存储单元
• 控制逻辑发出读命令
• 存储单元内容送到数据线上
• CPU 接收数据

读操作不会改变主存中原来的内容。

写操作

主存写操作的大致过程：

• CPU 给出地址
• CPU 把要写入的数据送到数据线上
• 控制逻辑发出写命令
• 地址译码器选中对应存储单元
• 数据写入存储单元

写操作会覆盖目标单元的旧内容。

存储器层次结构

程序运行时，并不是所有数据都同等频繁地被访问。

大量访问集中在少量最近用过或相邻的数据上。

这就是局部性原理。

局部性

局部性分为两类：

类型	含义	例子
时间局部性	最近访问过的内容，之后还可能访问	循环变量、循环体指令
空间局部性	访问某地址后，附近地址也可能被访问	顺序执行指令、数组连续访问

cache 利用局部性，把主存中最近可能用到的块复制到 CPU 附近。

虚拟存储器也利用局部性，只把当前活跃的页面放入主存。

层次结构

典型存储层次从快到慢为：

层次	位置	速度	容量	每位价格
寄存器	CPU 内部	最快	最小	最高
cache	CPU 内部或附近	很快	小	高
主存	主板内存条	较快	较大	中
SSD / 磁盘	外存	慢	大	低
光盘 / 磁带	外存或离线存储	更慢	很大	很低

越靠近 CPU：

• 速度越快
• 容量越小
• 价格越高
• 由硬件自动管理的比例越高

越远离 CPU：

• 速度越慢
• 容量越大
• 价格越低
• 需要操作系统或用户更多参与

层次结构的基本思想

靠近 CPU 的小容量高速存储器，保存远处大容量低速存储器中一部分内容的副本。

如果 CPU 要访问的数据在高速层中，就直接访问高速层。

如果不在，就从低速层取一块调入高速层。

这种结构的目标是：

\[ 平均访问时间接近高速存储器 \]

同时：

\[ 容量和价格接近低速存储器 \]

半导体随机存取存储器

半导体 RAM 是内部存储器的主要实现方式。

它主要分为：

• SRAM
• DRAM

SRAM 常用于 cache。

DRAM 常用于主存。

SRAM

SRAM 是静态随机存取存储器。

典型 SRAM 存储元由六个 MOS 管组成，所以也称 6T SRAM。

一个 SRAM 单元通过触发器保存 1 位信息。

只要不断电，触发器就能保持状态，不需要周期性刷新。

SRAM 基本操作

SRAM 单元有三种基本状态：

• 保持：字选择线无效，单元与位线隔离，内部触发器保持原状态
• 读出：字选择线有效，单元状态影响位线电平，由读出电路判断 0 或 1
• 写入：位线给出新值，字选择线有效，新值写入触发器

SRAM 特点

SRAM 的特点：

• 速度快
• 不需要刷新
• 控制简单
• 单元面积大
• 集成度低
• 成本高

所以 SRAM 适合做容量较小但速度要求高的 cache。

DRAM

DRAM 是动态随机存取存储器。

典型 DRAM 存储元由一个 MOS 管和一个电容组成，所以也称 1T DRAM。

电容上有电荷表示 1，电荷少或无电荷表示 0。

因为电容会漏电，所以 DRAM 必须周期性刷新。

DRAM 基本操作

DRAM 的读出具有破坏性。

读出时需要检测电容电荷状态，这个过程会影响原来的电荷。

因此读出后必须重写，也就是恢复原信息。

DRAM 的基本操作包括：

• 读
• 写
• 刷新

刷新就是在电容电荷消失前，把每一行重新读出并写回。

DRAM 特点

DRAM 的特点：

• 单元面积小
• 集成度高
• 成本低
• 容量大
• 速度比 SRAM 慢
• 需要刷新
• 控制比 SRAM 复杂

所以 DRAM 适合做大容量主存。

SRAM 和 DRAM 比较

项目	SRAM	DRAM
基本单元	触发器	MOS 管加电容
是否刷新	不需要	需要
读出是否破坏	不破坏	破坏性读出
速度	快	较慢
集成度	低	高
成本	高	低
典型用途	cache	主存

SRAM 和 DRAM 芯片

存储芯片内部不是一个简单的一维数组。

它通常由存储阵列、地址译码器和 I/O 控制电路组成。

地址译码

地址译码的作用是把二进制地址转换成某一条选择线有效。

译码方式主要有：

• 一维译码
• 二维译码

一维译码也叫线选法。

如果有 \(n\) 位地址，则译码器最多需要 \(2^n\) 条输出线。

地址位数较多时，输出线数量太大，不适合大容量芯片。

二维译码把地址分成行地址和列地址：

• 行地址选择某一行
• 列地址选择该行中的某些位

这样可以显著减少译码器规模。

DRAM 芯片通常采用二维译码。

行地址和列地址复用

DRAM 为了减少芯片引脚数量，常把行地址和列地址分时送入同一组地址引脚。

典型过程：

• 先送行地址
• 通过 RAS 锁存行地址
• 再送列地址
• 通过 CAS 锁存列地址

这样可以减少地址引脚数。

代价是访问控制更复杂。

刷新

DRAM 刷新的基本单位通常是行。

刷新周期指对同一行两次刷新之间允许的最大时间间隔。

刷新方式可以理解为：

• 集中刷新：在一段时间内集中刷新所有行
• 分散刷新：把刷新分散到各个存储周期中
• 异步刷新：在刷新周期内均匀安排刷新请求

集中刷新实现简单，但刷新期间不能正常访问主存。

异步刷新对 CPU 的影响较小。

SDRAM 和 DDR

SDRAM 是同步 DRAM。

它和系统时钟同步工作，读写操作按时钟节拍组织。

传统异步 DRAM 中，CPU 发出地址和控制信号后，需要等待 DRAM 完成。

SDRAM 则把访问过程划分为多个受时钟控制的阶段，便于和总线、存储控制器配合。

SDRAM 的基本特点

SDRAM 常见特点：

• 同步时钟控制
• 支持突发传送
• 内部分成多个 bank
• 可以流水化访问

突发传送适合 cache 块填充。

因为 cache 缺失时通常不是取一个字节，而是取一个主存块。

DDR SDRAM

DDR 表示 Double Data Rate。

它在时钟上升沿和下降沿都传输数据。

如果总线时钟频率为 \(f\)，数据总线宽度为 \(w\) 位，则理论带宽为： \[ 带宽 = f \times 2 \times \frac{w}{8} \]

DDR2、DDR3 等继续通过内部预取、提高总线频率、改进电气特性等方式提高带宽。

需要注意：

内存标称频率、核心频率、总线频率和数据传输率不是同一个概念。

很多内存型号中的数字反映的是等效数据传输率。

内存条和芯片扩展

单个存储芯片的容量和位宽有限。

实际主存通常由多个芯片组成内存条。

扩展方式主要有：

• 位扩展
• 字扩展
• 字位同时扩展

位扩展

位扩展用于增加数据位宽。

例如用 \(4K \times 1\) 位芯片组成 \(4K \times 8\) 位存储器，需要 8 片芯片并联。

所有芯片共用地址线和读写控制线。

每片芯片提供 1 位数据。

8 片合起来提供 8 位数据。

字扩展

字扩展用于增加存储单元个数。

例如用 \(8K \times 8\) 位芯片组成 \(32K \times 8\) 位存储器，需要 4 片芯片。

每片芯片的数据位宽已经是 8 位。

因此数据线可以共用。

高位地址经过片选译码后选择其中一片。

字位同时扩展

如果单片芯片容量和位宽都不够，就需要同时扩展。

做题时可以按两个方向分别计算： \[ 芯片片数 = \frac{目标字数}{单片字数} \times \frac{目标字长}{单片字长} \]

例如用 \(16K \times 4\) 位芯片组成 \(64K \times 16\) 位存储器：

• 字方向需要 \(64K/16K=4\) 组
• 位方向每组需要 \(16/4=4\) 片
• 总共需要 \(4 \times 4=16\) 片

多模块存储器

多模块存储器利用多个存储模块并行工作，提高主存吞吐率。

它不一定降低单个模块的访问时间。

但可以让多个连续访问在不同模块中重叠进行。

多模块编址方式主要有：

• 连续编址
• 交叉编址

连续编址

连续编址也叫高位交叉。

高位地址表示模块号，低位地址表示模块内地址。

这种方式下，一个模块内部地址连续。

例如 4 个模块，每个模块有 \(n\) 个单元：

• 模块 0：地址 \(0\) 到 \(n-1\)
• 模块 1：地址 \(n\) 到 \(2n-1\)
• 模块 2：地址 \(2n\) 到 \(3n-1\)
• 模块 3：地址 \(3n\) 到 \(4n-1\)

连续访问地址时，往往先集中访问同一个模块。

所以连续编址对顺序访问的吞吐率提升不明显。

交叉编址

交叉编址也叫低位交叉。

低位地址表示模块号，高位地址表示模块内地址。

连续地址会分布到不同模块中。

例如 4 体交叉：

地址	模块
0	M0
1	M1
2	M2
3	M3
4	M0
5	M1

这样连续访问可以轮流启动不同模块。

如果模块存取周期为 \(T\)，总线传送周期为 \(\tau\)，模块数为 \(m\)，为了连续不断地传送，理想情况下需要： \[ m \ge \frac{T}{\tau} \]

模块数越多，越容易隐藏单个模块的恢复时间。

外部辅助存储器

外存用于长期保存大量信息。

外存特点：

• 容量大
• 每位成本低
• 非易失
• 访问速度远慢于主存

常见外存包括：

• 磁盘
• U 盘
• SSD
• 光盘
• 磁带

磁盘存储器

磁盘是一种典型的直接存取存储器。

它不是像 DRAM 那样任意地址访问时间相同。

访问磁盘时，需要先移动磁头，再等待盘片旋转到合适位置。

磁盘结构

磁盘驱动器主要包括：

• 盘片
• 主轴
• 磁头
• 移动臂
• 控制电路
• 接口

每个盘面有多个同心圆，称为磁道。

多个盘面上半径相同的磁道构成柱面。

每个磁道划分为若干扇区。

磁盘读写通常以扇区为基本单位。

容量计算

磁盘格式化后的数据容量通常按扇区计算： \[ 容量 = 记录面数 \times 每面磁道数 \times 每磁道扇区数 \times 每扇区字节数 \]

如果一个硬盘有 4 个盘片、8 个记录面、每面 20000 个磁道、每磁道 1000 个扇区、每扇区 512B，则容量为： \[ 8 \times 20000 \times 1000 \times 512B \]

平均存取时间

磁盘一次访问的时间主要包括：

• 寻道时间
• 旋转等待时间
• 数据传输时间

平均存取时间可写成： \[ T_{avg}=T_{seek}+T_{rotation}+T_{transfer} \]

其中平均旋转等待时间约为半圈时间。

如果磁盘转速为 \(r\) 转每秒，则： \[ T_{rotation} \approx \frac{1}{2r} \]

转速越高，平均旋转等待时间越小。

但机械结构限制了磁盘访问延迟。

这也是磁盘随机访问远慢于主存和 SSD 的重要原因。

数据传输率

磁盘数据传输率受以下因素影响：

• 盘片转速
• 每磁道扇区数
• 扇区大小
• 控制器和接口带宽

连续读写大文件时，传输率比较重要。

随机读写大量小文件时，寻道和旋转等待常常更重要。

RAID

RAID 是冗余磁盘阵列。

它把多个磁盘组织成一个逻辑磁盘，用来提高性能或可靠性。

常见级别：

RAID	基本思想	特点
RAID 0	条带化，无冗余	性能高，但无容错
RAID 1	镜像	可靠性高，容量利用率低
RAID 3	位级或小条带，专用校验盘	大块连续传输性能好
RAID 4	块级条带，专用校验盘	小块并行读较好，校验盘可能成瓶颈
RAID 5	块级条带，分布式校验	避免专用校验盘瓶颈，服务器常用

RAID 不能代替备份。

RAID 主要解决磁盘故障下的可用性问题。

如果用户误删文件，RAID 也会把删除结果同步到阵列中。

Flash、U 盘和 SSD

Flash 是一种非易失性半导体存储器。

U 盘和 SSD 都基于 Flash。

SSD 不是磁盘。

它只是对外提供类似磁盘的块设备接口。

Flash 基本特点

Flash 读写有几个限制：

• 读写以页为单位
• 擦除以块为单位
• 写入前通常必须先擦除
• 同一块擦写次数有限

页通常比块小。

一个块中包含多个页。

所以 Flash 的写入管理比 DRAM 和 SRAM 复杂得多。

SSD

SSD 内部通常包括：

• Flash 芯片
• 控制器
• 缓存
• 闪存翻译层 FTL

FTL 把操作系统发出的逻辑块地址转换为 Flash 内部的物理页和块。

它还负责：

• 坏块管理
• 磨损均衡
• 垃圾回收
• 地址映射

SSD 随机访问性能远好于机械硬盘。

但 SSD 写入仍然受擦除块、写放大和寿命限制影响。

存储器的数据校验

存储器和总线传输过程中，数据可能出错。

错误来源包括：

• 电路噪声
• 存储元件翻转
• 传输干扰
• 磁盘或 Flash 介质损坏

数据校验码的目标是发现错误，必要时纠正错误。

基本概念

原始数据增加若干校验位后，形成编码。

如果传输或存储过程中某些位出错，接收端根据校验规则判断是否发生错误。

编码能力和码距有关。

码距是任意两个合法码字之间不同位的最小个数。

如果最小码距为 \(d\)：

• 检测 \(e\) 位错误需要 \(d \ge e+1\)
• 纠正 \(t\) 位错误需要 \(d \ge 2t+1\)
• 纠正 \(t\) 位并检测 \(e\) 位错误需要 \(d \ge e+t+1\)

奇偶校验码

奇偶校验码在数据位之外增加 1 位校验位。

偶校验要求整个码字中 1 的个数为偶数。

奇校验要求整个码字中 1 的个数为奇数。

例如数据为 1000001。

数据中有两个 1。

如果采用偶校验，校验位为 0。

如果采用奇校验，校验位为 1。

奇偶校验的特点：

• 能发现奇数个位错误
• 不能发现偶数个位错误
• 不能定位错误位
• 不能纠错

它适合成本低、只需要简单检错的场景。

海明校验码

海明码可以定位并纠正一位错误。

其基本思想是：

每个校验位负责检查一组数据位。

如果某一位出错，不同校验组得到的错误结果组合成一个错误位置编号。

这个错误位置编号称为校验综合或 syndrome。

校验位位数

如果数据位数为 \(k\)，校验位数为 \(m\)，为了能表示所有单比特错误位置以及无错状态，需要： \[ 2^m \ge k+m+1 \]

其中：

• \(k+m\) 表示码字中任意一位可能出错
• \(1\) 表示无错状态

例如 \(k=4\)。

若 \(m=2\)，则 \(2^2=4 < 4+2+1\)，不够。

若 \(m=3\)，则 \(2^3=8 \ge 4+3+1\)，够。

所以 4 位数据至少需要 3 位海明校验位。

校验位位置

海明码通常把校验位放在编号为 2 的幂的位置：

• 第 1 位
• 第 2 位
• 第 4 位
• 第 8 位

其余位置放数据位。

对于 7 位海明码：

位号	1	2	3	4	5	6	7
内容	P1	P2	D1	P4	D2	D3	D4

每个校验位检查位号二进制表示中对应位为 1 的位置。

例如：

• P1 检查位号最低位为 1 的位置：1、3、5、7
• P2 检查位号第二位为 1 的位置：2、3、6、7
• P4 检查位号第三位为 1 的位置：4、5、6、7

接收端重新计算各组校验结果。

如果综合值为 0，说明无单比特错误。

如果综合值为非 0，则该值就是出错位号。

SECDED

普通海明码可以纠正一位错误，但无法可靠区分两位错误。

实际存储器常采用 SECDED：

• SEC：single error correction，单错纠正
• DED：double error detection，双错检测

做法是在普通海明码基础上增加一个总奇偶校验位。

这样可以：

• 纠正一位错误
• 检测两位错误
• 避免把两位错误误当作一位错误去纠正

ECC 内存通常就使用类似思想。

CRC 校验码

CRC 是循环冗余校验码。

它常用于磁盘、网络和总线传输中的检错。

CRC 把二进制数据看作多项式。

发送端用生成多项式 \(G(x)\) 对数据多项式进行模 2 除法，把余数作为校验位附加在数据后面。

模 2 运算中：

• 加法等价于异或
• 减法也等价于异或
• 不产生进位和借位

CRC 生成过程

设数据多项式为 \(M(x)\)，生成多项式为 \(G(x)\)，\(G(x)\) 的阶数为 \(r\)。

发送端先把数据左移 \(r\) 位： \[ M(x)x^r \]

然后做模 2 除法： \[ M(x)x^r \div G(x) \]

得到 \(r\) 位余数 \(R(x)\)。

发送码字为： \[ C(x)=M(x)x^r+R(x) \]

接收端再用 \(G(x)\) 去除接收到的码字。

如果余数为 0，认为没有检测到错误。

如果余数非 0，说明发生错误。

CRC 的检错能力强，但通常不用于直接纠错。

高速缓冲存储器

cache 是位于 CPU 和主存之间的小容量高速存储器。

它保存主存中一部分块的副本。

CPU 访问内存时，先查 cache。

如果数据在 cache 中，称为命中。

如果数据不在 cache 中，称为缺失。

cache 的基本单位

cache 和主存之间交换的基本单位是块。

在 cache 中通常叫 cache 行。

主存中的块装入 cache 后，占据一个 cache 行。

cache 行中通常包含：

• 有效位
• 标记位
• 脏位
• 数据块

有效位表示该行内容是否有效。

标记位用于判断该行保存的是哪个主存块。

脏位用于回写法，表示该行是否被修改过但还没有写回主存。

命中率和平均访问时间

命中率为： \[ h=\frac{命中次数}{访问总次数} \]

缺失率为： \[ 1-h \]

如果 cache 命中时间为 \(T_c\)，缺失损失为 \(T_m\)，则平均访问时间可写为： \[ AMAT=T_c+(1-h)T_m \]

也常写为： \[ AMAT=Hit\ Time+Miss\ Rate \times Miss\ Penalty \]

命中率越高，平均访问时间越接近 cache 访问时间。

但如果缺失损失很大，即使命中率已经很高，少量缺失也会显著拖慢程序。

CPU 访问 cache 的过程

CPU 访问某个地址时：

• 根据地址中的索引字段找到 cache 行或 cache 组
• 比较地址中的标记字段和 cache 中保存的标记
• 如果标记相等且有效位为 1，则命中
• 根据块内偏移取出对应字节或字
• 如果不命中，则从主存调入对应块

cache 判断是否命中，靠的是标记比较，不是只看行号。

因为多个主存块可能映射到同一个 cache 位置。

cache 映射方式

主存块放入 cache 的位置由映射方式决定。

常见映射方式：

• 直接映射
• 全相联映射
• 组相联映射

直接映射

直接映射中，每个主存块只能放到 cache 的一个固定行。

映射关系通常为： \[ cache行号 = 主存块号 \bmod cache行数 \]

地址划分

设主存地址共 \(m\) 位，cache 有 \(2^s\) 行，块大小为 \(2^b\) 字节。

则地址划分为：

字段	位数	作用
标记 tag	\(m-s-b\)	区分映射到同一行的不同主存块
行号 index	\(s\)	选择 cache 行
块内地址 offset	\(b\)	选择块内字节

直接映射硬件简单，命中判断快。

缺点是冲突较严重。

如果程序反复访问两个映射到同一 cache 行的主存块，即使 cache 其他行空着，也会不断互相替换。

这叫冲突缺失。

全相联映射

全相联映射中，任意主存块可以放入 cache 的任意行。

地址只分为：

• 标记
• 块内地址

访问时需要把地址标记和所有 cache 行的标记同时比较。

优点：

• 冲突最少
• cache 空间利用灵活

缺点：

• 硬件比较器多
• 成本高
• 容量较大时速度和复杂度难以接受

全相联常用于 TLB 这类表项较少但查找要求高的结构。

组相联映射

组相联映射是直接映射和全相联映射的折中。

cache 被分成若干组。

一个主存块只能映射到某一组，但可以放在该组的任意一路中。

如果每组有 \(E\) 行，就称为 \(E\) 路组相联。

地址划分

设主存地址共 \(m\) 位，cache 有 \(2^s\) 组，块大小为 \(2^b\) 字节。

则地址划分为：

字段	位数	作用
标记 tag	\(m-s-b\)	区分同组内不同主存块
组号 set index	\(s\)	选择 cache 组
块内地址 offset	\(b\)	选择块内字节

组内需要并行比较多路标记。

路数越高，冲突越少，但硬件越复杂，命中时间也可能增加。

地址划分例子

假设：

• 主存地址空间为 64MB，按字节编址
• cache 数据区容量为 4KB
• 4 路组相联
• 块大小为 64B

主存地址位数： \[ 64MB=2^{26}B \]

所以地址共 26 位。

块内地址位数： \[ 64B=2^6B \]

所以 offset 为 6 位。

cache 行数： \[ \frac{4KB}{64B}=64 \]

4 路组相联，所以组数： \[ \frac{64}{4}=16=2^4 \]

组号为 4 位。

标记位数： \[ 26-4-6=16 \]

因此地址划分为：

tag	set index	block offset
16 位	4 位	6 位

三种映射方式比较

映射方式	放置限制	查找复杂度	冲突缺失	典型用途
直接映射	每块只有一个位置	最低	最多	简单 cache
全相联	任意位置	最高	最少	TLB、小容量 cache
组相联	固定组内任选一路	中等	中等	现代 cache 常用

实际处理器中，L1 cache 常采用低路数组相联，以控制命中时间。

L2 / L3 cache 容量更大，常采用更高关联度。

cache 替换算法

当 cache 缺失且目标组已满时，需要选择一个旧块替换出去。

替换算法影响命中率和硬件复杂度。

FIFO

FIFO 选择最早进入 cache 的块淘汰。

优点：

• 实现简单
• 只需记录进入顺序

缺点：

• 不考虑最近是否被访问
• 可能淘汰很快还会被访问的块

LRU

LRU 选择最近最少使用的块淘汰。

它利用时间局部性。

最近没用过的块，将来也相对不容易马上用到。

优点：

• 命中率通常较好

缺点：

• 精确实现复杂
• 路数较高时代价明显

实际硬件常用近似 LRU。

LFU

LFU 选择访问次数最少的块淘汰。

它考虑长期访问频率。

但它可能保留过去很热、现在不再使用的块。

所以硬件中不如 LRU 常见。

随机替换

随机替换随机选择一个块淘汰。

优点是硬件简单。

在某些场景下，它的平均效果并不差。

TLB 和高关联结构中常见随机或伪随机策略。

cache 写策略

读缺失时只需要从主存调入块。

写操作更复杂。

因为 cache 中的数据是主存数据的副本，写 cache 后必须考虑主存是否同步更新。

全写法

全写法也叫写直达，write through。

写命中时，同时写 cache 和主存。

优点：

• cache 和主存容易保持一致
• 发生替换时不需要写回旧块
• 实现相对简单

缺点：

• 写操作流量大
• 主存带宽压力大

通常会配合写缓冲区，减少 CPU 等待。

回写法

回写法也叫 write back。

写命中时只修改 cache，并把脏位置 1。

当该行被替换时，如果脏位为 1，再写回主存。

优点：

• 减少主存写次数
• 对频繁写同一块的数据更有利

缺点：

• 控制复杂
• cache 和主存可能暂时不一致
• 和 DMA、多处理器共享主存时需要额外一致性机制

写分配和非写分配

写缺失时也有两种策略：

策略	做法
写分配	先把主存块调入 cache，再写 cache
非写分配	不调入 cache，直接写主存

常见搭配：

• 写回法配合写分配
• 全写法配合非写分配

但具体实现由处理器设计决定。

cache 一致性问题

cache 中的数据只是主存块副本。

如果系统中只有一个 CPU，且所有主存访问都经过 cache，一致性问题比较简单。

但以下场景会变复杂：

• I/O 设备通过 DMA 直接读写主存
• 多个 CPU 各自有私有 cache
• 设备和 CPU 同时共享某片内存区域

例如：

CPU 修改了 cache 中某个块，但还没写回主存。

此时 DMA 从主存读这个块，就会读到旧值。

又如：

I/O 设备修改了主存某块，但 CPU 的 cache 中还保存旧副本。

此时 CPU 继续读 cache，就会读到旧值。

解决思路包括：

• 写直达
• cache 失效
• cache 刷新
• 总线监听
• 多处理器 cache 一致性协议

cache 缺失对性能的影响

处理器越来越快时，主存速度跟不上 CPU 的问题更明显。

没有 cache 缺失时，流水线可以接近理想 CPI。

一旦发生 cache 缺失，CPU 可能等待几十到几百个时钟周期。

CPI 公式

考虑访存阻塞后： \[ CPI = CPI_{base} + Memory\ Stall\ Cycles\ per\ Instruction \]

如果每条指令平均访存次数为 \(A\)，缺失率为 \(m\)，缺失损失为 \(P\)，则： \[ CPI = CPI_{base} + A \times m \times P \]

对于分离的指令 cache 和数据 cache，可以分别计算： \[ CPI = CPI_{base} + I_{miss} \times P_I + D_{access} \times D_{miss} \times P_D \]

其中：

• \(I_{miss}\) 表示取指缺失率
• \(P_I\) 表示指令 cache 缺失损失
• \(D_{access}\) 表示每条指令平均数据访问次数
• \(D_{miss}\) 表示数据 cache 缺失率
• \(P_D\) 表示数据 cache 缺失损失

CPU 频率越高，同样的主存访问时间折算成时钟周期数越多。

所以高性能 CPU 更依赖 cache。

cache 设计问题

cache 设计需要在命中时间、命中率、缺失损失和硬件成本之间取舍。

cache 容量

容量增大通常能降低容量缺失。

但容量过大会带来：

• 命中时间增加
• 面积增大
• 功耗增加
• 成本增加

L1 cache 通常容量不大，因为它在流水线前端和访存阶段的关键路径上。

块大小

块越大，越能利用空间局部性。

但块过大也有问题：

• cache 行数减少
• 冲突可能增加
• 缺失损失增加
• 总线传输时间增加

块大小需要适中。

顺序访问数组时，大块有利。

随机访问时，大块可能浪费带宽。

关联度

关联度提高可以减少冲突缺失。

但关联度越高：

• 标记比较器越多
• 选择逻辑越复杂
• 命中时间可能增加

实际设计中常用组相联作为折中。

多级 cache

现代处理器通常采用多级 cache：

• L1：最小最快，常分为 I-cache 和 D-cache
• L2：容量较大，速度较慢
• L3：更大，常在多个核心间共享

多级 cache 的目的：

• L1 保证短命中时间
• L2 / L3 降低访问主存的次数
• 主存承担大容量

指令 cache 和数据 cache

L1 cache 常分为指令 cache 和数据 cache。

这样可以：

• 取指和数据访问并行
• 减少流水线结构冒险
• 分别优化读指令和读写数据的访问模式

统一 cache 容量利用更灵活。

分离 cache 带宽更好。

虚拟存储器

虚拟存储器把主存看作外存的高速缓存。

每个进程看到的是一个独立、连续、很大的虚拟地址空间。

程序使用虚拟地址。

真正访问主存时，需要把虚拟地址转换为物理地址。

这个转换由硬件 MMU 和操作系统共同完成。

为什么需要虚拟存储器

虚拟存储器解决几个问题：

• 让程序以为自己拥有连续的大地址空间
• 让多个进程互不干扰
• 只把当前需要的部分装入主存
• 支持存储保护
• 支持共享代码和共享库
• 简化程序装入和链接

没有虚拟存储器时，程序员和操作系统必须直接管理物理主存位置。

这会使多道程序运行和内存保护都很困难。

虚拟地址和物理地址

CPU 执行程序时产生的是虚拟地址。

MMU 将虚拟地址转换为物理地址。

物理地址用于访问 cache 和主存。

基本关系：

\[ 虚拟地址 \xrightarrow{MMU} 物理地址 \xrightarrow{cache/主存} 数据 \]

虚拟存储器是软硬件协同机制：

• 硬件负责快速地址转换、权限检查、触发异常
• 操作系统负责页表维护、缺页处理、页面替换、磁盘交换

进程虚拟地址空间

每个进程都有自己的虚拟地址空间。

典型虚拟地址空间中包含：

• 代码段
• 只读数据段
• 已初始化数据段
• 未初始化数据段
• 堆
• 共享库映射区
• 栈
• 内核映射区

程序中看到的地址通常是虚拟地址。

不同进程可以使用相同的虚拟地址，但映射到不同的物理页框。

这就是进程隔离的基础。

例如进程 A 和进程 B 都可以有虚拟地址 0x400000。

但它们对应的物理地址可以完全不同。

分页式虚拟存储器

分页式虚拟存储器把虚拟地址空间划分为固定大小的页。

主存也划分为同样大小的页框。

页面是虚拟地址空间中的单位。

页框是物理主存中的单位。

页面和页框大小相同。

常见页面大小为 4KB。

虚拟地址划分

分页系统中，虚拟地址可分为：

字段	含义
虚拟页号 VPN	指出访问哪个虚拟页
页内偏移 VPO	指出页内哪个字节

物理地址可分为：

字段	含义
物理页号 PPN	指出主存中的哪个页框
页内偏移 PPO	指出页框内哪个字节

地址转换只改变页号，不改变页内偏移。

所以： \[ VA = VPN \parallel VPO \]

\[ PA = PPN \parallel PPO \]

并且： \[ VPO=PPO \]

如果页面大小为 \(2^p\) 字节，则页内偏移为 \(p\) 位。

页表

页表记录虚拟页到物理页框的映射。

每个进程有自己的页表。

页表项通常包含：

• 装入位或有效位
• 物理页号
• 访问权限
• 修改位
• 使用位
• 其他控制位

装入位为 1，表示该虚拟页已在主存中。

装入位为 0，表示该页不在主存，访问时发生缺页异常。

地址转换过程

分页地址转换基本过程：

• 从页表基址寄存器得到页表起始地址
• 用虚拟页号 VPN 查找页表项
• 检查装入位和访问权限
• 如果合法且页面在主存中，取出物理页号 PPN
• PPN 和页内偏移拼接成物理地址
• 用物理地址访问 cache 或主存

如果装入位为 0，则发生缺页异常。

操作系统负责把页面从外存调入主存，并更新页表。

缺页异常

缺页是异常的一种。

发生缺页时，硬件转入操作系统异常处理程序。

操作系统大致执行：

• 判断访问是否合法
• 找到该虚拟页在外存中的位置
• 在主存中找一个空闲页框
• 如果没有空闲页框，则选择一个页框替换
• 如果被替换页被修改过，则写回外存
• 从外存读入缺失页面
• 更新页表
• 返回到发生缺页的指令重新执行

缺页处理代价非常高。

因为它需要访问磁盘或 SSD。

所以虚拟存储器依赖程序局部性。

只要缺页率很低，系统仍然可以高效运行。

页表过大问题

页表大小由虚拟地址空间和页面大小决定。

如果虚拟地址为 32 位，页面大小为 4KB： \[ 页数=\frac{2^{32}}{2^{12}}=2^{20} \]

每个页表项如果占 4B，则单个进程页表大小为： \[ 2^{20} \times 4B = 4MB \]

如果虚拟地址更大，一级页表会更大。

常见解决方法：

• 多级页表
• 反置页表
• 哈希页表
• 只为实际使用的地址范围建立页表

多级页表的思想是：

把页表本身也分页。

没有使用到的虚拟地址区域，不需要分配下级页表。

TLB

TLB 是 Translation Lookaside Buffer，也叫快表。

它是页表项的高速缓存。

页表通常在主存中。

如果每次访存都先访问主存查页表，再访问主存取数据，那么一次访存会变成至少两次访存。

TLB 用来缓存最近使用的虚拟页到物理页的映射。

TLB 表项

TLB 表项通常包含：

• 虚拟页号标记
• 物理页号
• 有效位
• 访问权限
• 修改位
• 使用位
• 进程标识 ASID

ASID 用来区分不同进程的相同虚拟页号。

如果没有 ASID，进程切换时通常需要刷新 TLB 或做额外处理。

TLB 命中

TLB 命中时：

• 用 VPN 在 TLB 中查找
• 找到匹配项
• 检查权限
• 取出 PPN
• 拼接页内偏移形成物理地址

这个过程很快，通常在 CPU 流水线中完成。

TLB 缺失

TLB 缺失不一定是缺页。

它只表示页表项不在 TLB 中。

处理方式：

• 硬件查页表并填入 TLB
• 或触发异常，由操作系统查页表并填入 TLB

如果页表项有效，填入 TLB 后重新访问即可。

如果页表项无效，才是真正缺页。

TLB、页表和 cache 的关系

一次访存可能经历：

• TLB 查找
• 页表访问
• cache 查找
• 主存访问
• 缺页时外存访问

常见情况：

情况	结果
TLB 命中，cache 命中	最快
TLB 命中，cache 缺失	需要访问主存填 cache
TLB 缺失，页表项有效	补充 TLB 后继续
页表项无效	缺页异常，操作系统介入

TLB 缺失比 cache 缺失更复杂。

缺页异常比普通 cache 缺失慢得多。

CPU 访存过程

在具有虚拟存储器和 cache 的系统中，一条 load 指令访问内存的大致过程：

• CPU 产生虚拟地址
• MMU 用虚拟页号查 TLB
• TLB 命中则得到物理页号
• TLB 缺失则访问页表
• 如果页表项无效，则发生缺页异常
• 得到物理地址后访问 cache
• cache 命中则返回数据
• cache 缺失则访问主存，把块调入 cache
• 如果主存访问也涉及缺页，则由操作系统处理

这里要区分几个概念：

• TLB 缺失是地址转换缓存缺失
• cache 缺失是数据或指令块不在 cache
• 缺页是页面不在主存

三者层次不同，代价也不同。

分段式虚拟存储器

分段式虚拟存储器按程序逻辑结构划分地址空间。

一个段可以对应：

• 代码段
• 数据段
• 栈段
• 堆段
• 共享库段

分段地址通常由段号和段内地址组成。

段表项中保存：

• 段基址
• 段长
• 装入位
• 访问权限

地址转换时：

• 根据段号查段表
• 检查段是否在主存
• 检查段内地址是否越界
• 检查访问权限
• 段基址加段内地址得到物理地址

分段优缺点

分段的优点：

• 符合程序逻辑结构
• 便于共享和保护
• 段可以按逻辑意义分别设置权限
• 适合支持动态增长的数据结构

分段的缺点：

• 段长不固定
• 主存分配复杂
• 容易产生外部碎片

分页对程序员和编译器更透明。

分段更接近程序逻辑结构。

段页式虚拟存储器

段页式结合分段和分页。

程序先按逻辑结构分段。

每个段内部再分页。

虚拟地址通常分为：

• 段号
• 段内页号
• 页内偏移

转换过程：

• 用段号查段表
• 得到该段页表的位置和段长等信息
• 用段内页号查该段的页表
• 得到物理页号
• 拼接页内偏移形成物理地址

段页式的特点：

• 逻辑上保留分段的共享和保护优势
• 物理分配上利用分页避免外部碎片
• 地址转换过程更复杂

存储保护

虚拟存储器不仅用于扩大地址空间，也用于保护。

保护的核心思想是：

程序只能访问自己有权限访问的地址范围。

常见保护检查包括：

• 地址是否映射
• 页面或段是否在允许范围内
• 是否允许读
• 是否允许写
• 是否允许执行
• 当前特权级是否足够

如果检查失败，硬件触发异常。

操作系统决定终止进程、发送信号或进行其他处理。

特权级

现代处理器通常有多个特权级。

以 RISC-V 为例，常见模式包括：

• M 模式：机器模式，权限最高
• S 模式：监管模式，操作系统内核运行
• U 模式：用户模式，普通应用程序运行

用户程序在 U 模式下不能直接访问内核数据结构，也不能执行特权指令。

如果用户程序需要系统服务，需要通过异常或系统调用进入更高特权级。

访问权限

页表项或段表项中通常有权限位。

典型权限：

• R：可读
• W：可写
• X：可执行

例如代码段通常可读可执行，但不可写。

数据段通常可读可写，但不可执行。

这种机制可以防止许多非法访问。

例如：

• 写只读代码段
• 执行数据页
• 用户态访问内核页
• 访问未映射地址

这些都会触发异常。

存储器层次的统一理解

第七章的内容看起来很多，但核心可以统一为一句话：

把常用的信息放在更快的位置，不常用的信息放在更大更便宜的位置。

cache 是主存的缓存。

主存是外存的缓存。

TLB 是页表的缓存。

寄存器是程序当前工作数据的最快保存位置。

这些机制都依赖局部性。

cache 和虚拟存储器比较

项目	cache	虚拟存储器
上层	CPU	主存
下层	主存	外存
交换单位	cache 块	页面
命中时访问	cache	主存
缺失时处理	硬件为主	操作系统为主
缺失代价	几十到几百周期	极高，可能访问磁盘
地址依据	物理地址为主	虚拟地址到物理地址转换
主要目标	提高访存速度	扩大地址空间、保护、共享

TLB 和 cache 比较

项目	TLB	cache
缓存内容	页表项	指令或数据块
查找依据	虚拟页号	物理地址或部分地址
命中结果	得到物理页号	得到指令或数据
缺失后果	查页表或异常	访问下一级存储器

TLB 不保存普通数据。

它保存地址转换结果。

cache 保存真正的指令或数据。

典型题型整理

地址线和容量

按字节编址时：

\[ 地址线根数=\log_2(可寻址字节数) \]

例如主存最大空间为 4GB： \[ 4GB=2^{32}B \]

需要 32 根地址线。

如果按字编址，则地址线数量和字长有关，不能直接按字节数计算。

芯片扩展

芯片扩展题按两个方向看：

• 目标字数除以单片字数
• 目标字长除以单片字长

总片数为两者乘积。

片选信号由高位地址译码产生。

片内地址由低位地址提供。

cache 地址划分

cache 地址划分题一般按以下步骤：

• 求主存地址位数
• 求块内偏移位数
• 求 cache 行数
• 求组数或行号位数
• 剩余高位为 tag

对于 \(E\) 路组相联： \[ 组数=\frac{cache数据区容量}{块大小 \times E} \]

cache 命中率

按地址序列判断命中或缺失时：

• 先把地址转换为块号
• 根据映射方式确定 cache 行或组
• 检查 tag 是否匹配
• 缺失时按替换算法更新 cache 内容

块号计算： \[ 主存块号=\left\lfloor \frac{地址}{块大小} \right\rfloor \]

块内偏移： \[ 块内偏移=地址 \bmod 块大小 \]

虚拟地址转换

分页地址转换题一般按以下步骤：

• 根据页面大小求页内偏移位数
• 剩余高位为虚拟页号
• 查页表得到物理页号
• 物理页号和页内偏移拼接成物理地址
• 若页表项无效，则发生缺页异常

如果有 TLB，则先查 TLB。

TLB 命中时不需要访问页表。

TLB 缺失但页表有效，不等于缺页。

小结

存储器系统的核心矛盾是速度、容量和成本不能同时最优。

解决方法是建立层次结构。

本章重点包括：

• 主存由地址、数据和控制信号共同完成读写
• SRAM 快但贵，适合 cache
• DRAM 慢但容量大，适合主存
• 多模块交叉存储器可以提高连续访问吞吐率
• 磁盘访问时间由寻道、旋转等待和传输时间组成
• SSD 随机访问快，但写入受擦除块和寿命限制
• 奇偶校验能检错，海明码能纠错，CRC 适合强检错
• cache 利用局部性降低平均访存时间
• 直接映射、全相联和组相联是三种基本映射方式
• 写直达和写回是两类基本写策略
• 虚拟存储器提供大地址空间、保护和共享
• TLB 缓存页表项，减少地址转换开销

理解存储器层次结构时，要一直抓住两个问题：

• 这一层缓存的是下一层的什么内容
• 命中和缺失分别由谁处理

掌握这两个问题，就能把 cache、TLB、主存、外存和虚拟存储器联系起来。