一、存储系统基本概念
1. 存储系统的层次结构
- 层次思想：上一层的存储器作为低一层存储器的高速缓存，上一层的内容是下一层的内容的一部分
- Cache —— 主存层
- 解决 CPU 和主存速度不匹配的问题
- 数据调度由硬件自动完成
- 对所有程序员透明
- 主存 —— 辅存层
- 解决存储系统容量的问题
- 数据调度由硬件和操作系统共同完成【换入换出技术】
- 对应用程序员透明
- 逐渐发展形成虚拟存储系统
- 主存与 CPU，Cache，辅存都能交换信息
- Cache 和主存能与 CPU 直接交换信息
- 辅存要通过主存与 CPU 交换信息
2. 存储器的分类
（1）按在计算机中的作用分类
- 主存储器【主存/内存】
- 用来存放计算机运行期间所需的程序和数据
- 容量较小
- 存取速度较快
- 价格较高
- 辅助存储器【辅存/外存】
- 用来存放当前暂时不用的程序和数据以及一些需要永久性保存的信息
- 容量大
- 存取速度较慢
- 单位成本低
- 高速缓存存储器【Cache】
- 位于主存和 CPU 之间
- 用来存放当前 CPU 经常使用的指令和数据，以便 CPU 能高速地访问它们
- 现代计算机通常将其制作在 CPU 内
- 存取速度可与 CPU 速度相匹配
- 存储容量小
- 价格高
（2）按存储介质分类
- 磁表面存储器：磁盘，磁带
- 磁芯存储器
- 半导体存储器：MOS 型存储器，双极型存储器
- 光存储器：光盘
（3）按存取方式分类
- 随机存储器【RAM】
- 存储器的任何一个存储单元都可以随机存取
- 存取时间与存储单元的物理位置无关
- 主要用于做主存或高速缓冲存储器
- 读写方便，使用灵活
- RAM 分为静态 RAM 和动态 RAM
- RAM 主要为用户编程设置的
- 只读存储器【ROM】
- 存储器的内容只能随机读出而不能写入
- 信息一旦写入就不变，断电后也不消失
- 通常用于存放固定不变的程序，常数和汉字字库
- ROM 与 RAM 一起统一构成主存的地址域
- ROM 和 RAM 的存取方式均为随机存取
- 操作系统的内存储器既有 RAM 也有 ROM
- 广义上的 ROM 现在可通过电擦除进行写入，写入速度比读取速度慢
- ROM 存放系统程序，标准子程序和各类常数
- 串行访问存储器
- 对存储单元进行读写操作时，需按其物理位置的先后顺序寻址
- 顺序存取存储器：磁带
- 存取速度慢，只能按某种顺序存取
- 直接存取存储器：磁盘、光盘
- 既不是随机存取，也不是顺序存取
- 相联存储器
- 按内容访问
- 快表
（4）按信息的可保存性分类
- 易失性存储器
- 断电后，存储信息消失【RAM，主存，Cache】
- 非易失性存储器
- 断电后，信息仍保存【ROM，磁表面存储器，光存储器】
- 破坏性读出
- 信息读出后，原存储信息被破坏【DRAM 芯片，读出数据后要进行重写】
- 非破坏性读出
- 信息读出后，原存储信息不被破坏【SRAM 芯片，磁盘，光盘】
3. 存储器的性能指标
（1）存储容量
- 存储容量 = 存储字数 字长 （1 M 8 bit）
- 存储字数表示存储器的地址空间大小【MAR】
- 字长表示一次存取操作的数据量【MDR】
（2）单位成本
- 每位价格 = 总成本 / 总容量
（3）存取速度
- 数据传输率 = 数据宽度 / 存取周期
- 数据传输率中的 K, M 是 10 的次方不是 2 的次方，只有存储容量是 2的次方
- 存取周期 = 存取时间 + 恢复时间
- 存取时间 $T_a$ = 从启动一次存储器到完成该操作所经历的时间
- 存取周期 $T_m$ = 存储器进行一次完整的读写操作所需的全部时间
- 主存带宽 $B_m$ = 数据传输率 = 每秒从主存进出信息的最大数量 = 单位字 / 秒
二、主存储器
1、主存储器的基本组成
（1）基本元件
- MOS 管，作为通电”开关”
- 电容，存储电容（即存储二进制 0/1）
（2）存储芯片的结构
- 译码驱动电路：译码器将地址信号转化为字选通线的高低电平
- 存储矩阵（存储体）：由多个存储单元构成，每个存储单元又由多个存储元构成
- 读写电路：每次读 / 写一个存储字
- 读 RD / 写 WR控制线：决定芯片是进行读还是写操作（可能分开两根，也可能只有一根）
- 片选线 CS：确定哪个存储芯片被选中，可用于容量扩充
- 引脚最低数目：片选线（1）+控制线（2）+ 数据线 + 地址线
地址复用技术： - 由于DRAM 芯片容量大，地址位数多，为了减少地址引脚线，采用地址复用技术
- DRAM 因为分两次发送，长度相同，因此地址线可以复用，线数减少了一半
- 引脚数 = 地址线减半 + 数据线不变 + 行通选 (1) + 列通选 (1) + 读写控制线 (2)
- 片选线用行通选线替代
- 总容量 = 存储单元个数 * 存储字长
- 常见的描述：8 K × 8 位，即 $2^{13}×8 bit$ = 8 KB
（3）寻址方式
- 题目上没有明确指定按字编址，那么就默认是按字节编址【一字节8位】
- 32位的计算机中：32位(bit) = 4字节(byte) = 1字(word)
- 64位的计算机中：64位(bit) = 8字节(byte) = 1字(word)
- 存放一个机器字的存储单元，通常称为字存储单元，相应的单元地址叫字地址
- 存放一个字节的存储单元，称为字节存储单元，相应的地址称为字节地址
- 如果计算机中可编程的最小单位是字存储单元，则该计算机称为按字寻址的计算机
- 如果计算机中可编程的最小单位是字节，则该计算机称为按字节寻址的计算机
- 一个机器字可以包含数个字节，所以一个存储单元也可以包含数个能够单独编制的字节地址
（4）主存储器的组成部分
- 数据线的宽度 = MDR 的宽度 = 存储字长
- 地址线的宽度 = MAR 的宽度 = 存储字数
- 下图总容量 = $2^{36}×64$ 位= $2^{39} B$
2、DRAM 和 SRAM
（1）比较
| SRAM | DRAM | |
|---|---|---|
| 主要用途 | 高速缓存 | 主机内存 |
| 存储信息 | 双稳态触发器 | 电容 |
| 破坏性读出 | 非，即使信息被读出后，它仍保持其原状态而不需要再生 | 是 |
| 需要刷新 | 不要 | 需要 |
| 送行列地址 | 同时送 | 分两次送 |
| 运行速度 | 快 | 慢 |
| 集成度 | 低 | 高 |
| 存储成本 | 高 | 低 |
（2）DRAM 的刷新
1）刷新的概念
- DRAM电容的电荷维持时间短，即使电源不断电，信息也会自动消失
- 因此每隔一段时间必须刷新，一般取2ms，即刷新周期（再生周期）
- DRAM的刷新是以行为单位的
- 一次完整的刷新过程只需要占用一个存储周期
2）集中刷新
- 在规定的一个刷新周期内，对全部存储单元集中一段时间逐行进行刷新，此刻必须停止读 / 写操作
刷新过程 - 用 0.5μs ×128=64μs 的时间对 128 行进行逐行刷新
- 由于这 64μs 的时间不能进行读/写操作，故称为死时间或访存死区”
- 由于存取周期为 0.5μs，刷新周期为 2 ms，即 4000 个存取周期
为什么刷新与存取不能并行 - 因为内存就一套地址译码和片选装置，刷新与存取有相似的过程
- 它要选中一行【这期间片选线、地址线、地址译码器全被占用着】
- 同理，刷新操作之间也不能并行【意味着一次只能刷一行】
3）分散刷新
- 是指对每行存储单元的刷新分散到每个存取周期内完成
- 其中，把机器的存取周期tc分成两段，前半段tM用来读 / 写或维持信息，后半段tR用来刷新
刷新过程 - 在每个存取操作后绑定一个刷新操作，延长了存取周期
- 这样存取周期就成了 0.5μs + 0.5μs =1μs
- 但是由于与存取操作绑定，就不需要专门给出一段时间来刷新了
- 这样，每有 128 个读取操作，就会把 0-127 行全部刷新一遍
- 故每隔 128μs 就可将存储芯片全部刷新一遍【即刷新周期是 1μs×128=128μs 远短于 2 ms】
- 而且不存在停止读 / 写的死时间，但是存取周期长了，整个系统速度降低了
- 分散刷新的刷新周期 128μs ，其实不需要这么频繁，会导致浪费
4）异步刷新
- 既可以缩短“死时间”【仍然存在死时间】，又充分利用最大刷新间隔为2ms的特点
刷新过程 - 具体操作为：在 2 ms 内对 128 行各刷新一遍
- 即每隔 15.6μs 刷新一行 (2000μs/128≈15.6μs)，而每行刷新的时间仍为 0.5μs
- 这样，刷新一行只能停止一个存取周期
- 但对每行来说，刷新间隔时间仍为 2 ms，而死时间为 0.5μs
- 相对每一段来说，是集中式刷新，相对整体来说，是分散式刷新
特点 - 将 DRAM 的刷新安排在 CPU 对指令的译码阶段，这个阶段 CPU 不访问存储器
- 既克服了分散刷新需独占 0.5μs 用于刷新，使存取周期加长且降低系统速度的缺点
- 又不会出现集中刷新的访存“死区”问题
- 从根本上提高了整机的工作效率
3、只读存储器 ROM
（1）ROM 的特点
- 结构简单，位密度比可读写存储器高
- 具有非易失性，可靠性高
（2）ROM 的类型
1）掩模式只读存储器 MROM
- 内容在生产过程中写入，任何人不可重写
- 可靠性高，集成度高，价格便宜但灵活性差
2）一次可编程只读存储器 PROM
- 用于用户实现一次性编程
- 一次写入后不可更改
3）可擦除可编程只读存储器 EPROM
- 用于用户实现多次性编程
- 可多次重写，但次数有限，写入时间过长
4）Flash 存储器
- 既可在不加电的情况下长期保存信息，又能在线进行快速擦除和重写
- 需要先擦除后写入，写速度一般比读速度慢
- 每个存储元只需要单个 MOS 管，位密度比 RAM 高
- U盘就是基于Flash的只读存储器
- 价格便宜，集成度高，电可擦除重写且擦除重写速度快
5）固态硬盘 SSD
- SSD 是基于闪存的硬盘，是一种非易失性存储器，采用随机访问方式
- 由控制单元和存储单元（Flash 芯片）组成
- 可长期保存信息，快速擦除和重写
- 相比传统硬盘也有读写速度快、低功耗的特性，但价格较高
4、多模块存储器
（1）概念
- 一种空间并行技术，利用多个结构完全相同的存储模块的并行工作来提高存储器的吞吐率
（2）单体并行存储器
- 定义：存储器中只有一个存储体，每个存储单元存储 m 个字，总线宽也为 m 个字，地址必须顺序排列并处于同一存储单元
- 过程：在一个存取周期内，从同一地址取出 m 条指令，然后将指令逐条送至 CPU
- 缺点：指令和数据在主存内必须是连续存放的，一旦遇到转移指令，或操作数不能连续存放，这种方法的效果就不明显
（3）多体并行存储器
由多体模块组成，每块都有相同容量和读取速度，各模块都有独立的读写控制电路、MAR 和 MDR，既能并行工作也能交叉工作
1）高位交叉编址（顺序方式）【竖】
- 特点：先在一个模块内访问，等到该模块访问完之后才转到下一个模块访问
- 编号：高位地址表示体号【模块号】，低位地址表示体内地址
- 优点：
- 某个模块进行存取时，其它模块不工作
- 某一模块出现故障时，其它模块可以照常工作
- 通过增添模块来扩充存储器容量比较方便
- 缺点：各模块串行工作，存储器的带宽受到了限制，并不能提高吞吐量
2）低位交叉编址（交叉方式）【横】
- 特点：
- 连续地址分布在相邻的不同模块内，同一模块内的地址是不连续的
- 地位交叉编制是交叉存放的，满足程序的局部性原理
- 编号：高位地址表示体内地址，低位地址表示体号【模块号】
- 优点：对连续字的成块传送可实现多模块并行存取，提高了存储器的带宽
- 计算：每个模块按“模 m”交叉编址，模块号 = 单元地址 % m
- 启动方式：
- 轮流启动方式：
- 设模块字长等于数据总线宽度，模块存取周期为 T，总线周期为 r
- 存储器交叉模块的数目最小为 m = T / r
- 每隔 1/m 个存取周期轮流启动各模块，则每隔 1/m 个存取周期就可读出或写入一个数据，存取速度提高 m 倍
- 当模块数目不小于 m 时，就可以保证 T 时间之后再启动该模块，上次的存取操作已经完成，流水线就不会断
- **连续存取 m 个字的时间为 T + (m – 1) r
- 判断发送访问冲突的规则：给定的访存地址在相邻的四次访问中出现在同一个存储模块中【m=4 时】
- 同时启动方式：
- 所有模块一次并行读 / 写的总位数正好等于数据总线位数
- 同时启动所有模块进行读 / 写
- 轮流启动方式：
- 计算带宽
5、主存储器与 CPU 的连接
（1）连接原理
- 主存储器通过数据总线、地址总线和控制总线与 CPU 连接
- 数据总线的位数与工作频率的乘积正比于数据传输速率
- 地址总线的位数决定了可寻址的最大内存空间
- 控制总线（读 / 写）指出总线周期的类型和本次输入 / 输出操作完成的时刻
- CPU 读指令，通过地址线去访问存储器的 MAR（地址寄存器）
- MAR（地址寄存器）通过选通线去访问矩阵中的数据
- 矩阵需要通过数据线与 MDR（数据寄存器）进行接发
（2）主存容量的扩展
1）位扩展法
- $8 K 8 位$ 的存储器 = 8片 $8 K1 位$ 的 RAM 组成
- 地址线并行，数据线一一接上
2）字扩展法
- 线选法
- $16 K 8 位$的存储器 = 2片 $8 K8 位$的存储器
- 地址线是 $A0$~$A{12}$ 共 13 位，译码线是 $A{13}$ 和 $A{14}$ 共 2 位
- 由片选信号来区分各芯片的地址范围
- 当 $A{13}$ 为 1 时，第一块工作，$A{14}$ 的 CS 必须为 0
- 谁工作，数据线就接送谁的数据，即将 CS 设置为 1
- 2 位二进制时：只能利用 01，10
- 译码片实现
- 有 4 块芯片，不需要 4 条线而只需要两条
- 地址线是 $A0$~$A{12}$ 共 13 位，译码线是 $A{13}$ 和 $A{14}$ 共 2 位
- 2 位二进制时：可以利用 00，01，10，11
- 【译码器】一个二进制转十进制的物理元件，将左边三根地址线表示的二进制意义映射到右边十进制的选通线
比较
3）字位同时扩展法
- 一块芯片只有 4 位，因此通过 2 片叠加先实现位拓展
- 等价于实现了一个 8 位的存储芯片
- 再通过译码片选的方式实现字拓展
- 在不同的地址线中选择不同的芯片组合进行工作
三、外部存储器
1、磁盘存储器
2、固态硬盘 SSD
（1）原理
- 基于闪存技术 Flash Memory，属于电可擦除 ROM，即 EEPROM
（2）组成
- 闪存翻译层：负责翻译逻辑块号，找到对应页（Page）
- 存储介质：多个闪存芯片（Flash Chip），每个芯片包含多个块（block），每个块包含多个页（page）
（3）读写性能特性
- 以页为单位读 / 写：相当于磁盘的“扇区”
- 以块为单位“擦除”：擦干净的块，其中的每页都可以写一次，读无限次
- 支持随机访问：系统给定一个逻辑地址，闪存翻译层可通过电路迅速定位到对应的物理地址
- 读快，写慢：要写的页如果有数据，则不能写入，需要将块内其他页全部复制到一个新的（擦除过的块）中，再写入新的页
（4）与机械硬盘相比的特点
- SSD 读写速度快，随机访问性能高，用电路控制访问位置；机械硬盘通过移动磁臂旋转磁盘控制访问位置，有寻道时间和旋转延迟
- SSD 安静无噪音、耐摔抗震、能耗低、造价更贵
- SSD 的一个“块”被擦除次数过多（重复写同一个块）可能会坏掉，而机械硬盘的扇区不会因为写的次数太多而坏掉
（5）磨损均衡技术
- 思想：将“擦除”平均分在各个块上，以提升使用寿命
- 动态磨损均衡：写入数据时，优先选择累计擦除次数少的新闪存块
- 静态磨损均衡：SSD 检测并自动进行数据分配、迁移，让老旧的闪存块承担以读为主的存储任务，让较新的闪存块承担更多的写任务
四、高速缓存存储器
1、Cache 的基本原理
（1）基本概念
- 高速缓冲存储器就是存在于主存与 CPU 之间的一级存储器，有了它 CPU 可以直接对其存取数据，从而减少了时间，提高了系统的运行速度
- CPU 与 Cache / 主存的信息交互单位为字，Cache 与主存的信息交互单位为块
- 一个块通常由若干字组成
- Cache 利用了局部性原理：将程序中正在使用的部分存在在容量较小但速度更快的 cache 中
（2）局部性原理
- 时间局部性：
- 在最近的未来要用到的信息，很可能是现在正在使用的信息（指令和数据）
- 例如循环
- 空间局部性：
- 在最近的未来要用到的信息（指令和数据），很可能与现在正在使用的信息在存储空间上是邻近的
- 例如对数组的访问，如果数组按行存的，则先行再列的访问方式空间局部性更好
（3）读写过程
- CPU、Cache、和主存三者的读写关系
- Cache 会从主存中一并读取目标数据以及附近空间的数据
【通常以块为单元取出】【速度如图需要 1000 ns】 - CPU 要取数据会优先从 Cache 中读取，因为速度快
【速度如图 5 ns】 - CPU 计算完后，会把数据再次返回给 Cache
【速度也是 5 ns】
- Cache 会从主存中一并读取目标数据以及附近空间的数据
- 整个过程全部由硬件实现
（4）性能分析
设 $t_c$ 为访问一次 Cache 所需的时间，$t_m$ 为访问一次主存所需的时间
- Cache 命中率 H = $\frac{Cache 的总命中次数}{Cache 的总命中次数+访问主存的总次数}$
- 缺失（未命中）率 M = 1 – H
- Cache – 主存系统的平均访问时间 t
- 先访问 Cache，未命中再访问主存：$t=Ht_c+(1-H)(t_c+t+m)$
- 同时访问 Cache 和主存：$t=Ht_c+(1-H)t_m$
- 系统平均访问时间 = $命中的概率命中所需要花费的时间+缺失的概率平均访存次数*一次总线读突发总线事务所需时间$ 【13 年统考大题】
- 性能效率 = $\frac{访问 Cache 的时间}{系统平均访问时间}$
（5）要解决的关键问题
- 地址映射：主存块如何存放在 Cache 中，如何将主存地址转换为 Cache 地址
- 替换策略：Cache 满后，使用何种策略对 Cache 块进行替换或淘汰
- 写入 / 更新策略：如何既保证主存块和 Cache 块的数据一致性，又尽量提升效率
2、Cache-主存映射方式
（1）全相联映射
- 只规定了主存需要映射到 Cache 中
- 没有规定它映射到 Cache 中的哪一个位置
- 通常使用按内容访问的相联存储器进行地址映射
优点 - 映射灵活
- 块冲突概率比较低
- 空间利用率也高
缺点 - 成本高
- 速度慢耗时多
（2）直接映射
- 规定好了主存中每一块都放置在 cache 中的哪个地方
- 相邻块之间映射的位置也是相邻的
- 因为主存的容量肯定比 cache 大得多，所以其实它相当于一轮轮映射过去
- 主存地址长度：主存中存储单元个数为 $2^{10}$， 则主存地址长度就是10
- Cache 地址长度：Cache 中存储单元个数为 $2^{10}$， 则 Cache 地址长度就是10
- Cache 行的总位数： = 标记位数t + 数据位 + 1 位有效位 + 1 位脏位 (回写策略)
- t：【主存区号】【Tag 位】【主存字块标记】
- 通过主存区的标记位数就能知道这个 cache 是属于主存的第几区
- t = 主存地址长度 – Cache 地址长度
- t = 主存大小 / Cache 大小
- c：【Cache 块的地址位数】
- 如有 1 k 个 Cache 行，则 Cache 块的地址位数=10
- m：【主存块的地址位数】
- 如有 1 k个主存块，则主存块的地址位数=10
- b：【块内地址位数】
- 如块的大小为 32 B，按字节编制，块内地址位数=5
- 标记项：
- 包括有效位，脏位，替换算法位，标记位
- 每个 Cache 行对应一个标记项
优点
- 简单、成本低、易实现
- 由于物理位置也是相邻的所以地址变换速度快
- 不需要替换算法
缺点 - 映射方式不够灵活
- 空间利用率最低
- 块冲突概率最高
（3）组相联映射
- 先按号分组【组间是直接映射】
- 组内再任意放【组内是全相联映射】
- 所属分组 = 主存块号 % 分组数
- Cache 的总块数：$2^c$
- Cache 分组个数：$2^q$ 【分块个数 / 组内块数】
- 组内包含的块数：$2^r$ 【r=1，每组包含 2 块，即二路组相联】
优点 - 另外两种方式的折中，综合效果较好
例题
- 假设主存容量为 512 KB, Cache 容量为 4 KB, 每个字块为 16 个字，每个字为 32 位
- Cache 地址为多少位？可容纳多少块？
- 主存地址为多少位？可容纳多少块？
- 在直接映射方式下，主存的第几块映射到 Cache 中的第五块（设起始字块号为 1）
- 画出直接映射方式下主存地址字段中各段的位数
- 假设主存容量为 $512 K16$ 位，Cache 容量为 $409616$ 位，块长为 4 个 16 位的字，访存地址为字
- 在直接映射下，设计主存的地址格式
- 在全相联映射下，设计主存的地址格式
- 在二路组相联映射方式下，设计主存的地址格式
- 若主存容量为 $512 K*32$ 位，块长不变，在四路组相联映射下，设计主存的地址格式
3、Cache 替换算法
（1）随机算法
- 若Cache已满，则随机选择一块替换
- 实现简单，但完全没考虑局部性原理，命中率低，实际效果很不稳定
（2）先进先出 FIFO
- 按调入 cache 的先后顺序来淘汰，先进的先替换
- 需要记录进入 cache 的先后次序
- 实现起来比较简单
- 没有考虑局部性原理
- 会有抖动现象：频繁的换入换出现象（刚被替换的块很快又被调入）
（3）近期最少使用 LRU
- 把最近比较少用的替换掉
- 需要记录进入 cache 的先后次序
- 需要软件计数器来记录使用的频率
- 实现起来是比较复杂且开销大
- 根据程序访问局部性原理选择近期使用得最少的存储块作为替换的块
（4）最不经常使用 LFU
- 只统计使用次数，用的最少的就替换掉谁
- 需要硬件设计计数器支持
4、Cache 写策略
（1）写命中
1）全写法【写直达法】
- 当 CPU 对 Cache 写命中时，必须把数据同时写入 Cache 和主存，一般使用写缓冲（write buffer）
- 访存次数增加，速度变慢，但更能保证数据一致性
- 在写的时候 cpu 将数据通过数据总线橙色箭头方向传输
- 由于 cpu 写给 cache 的速度和写入主存的速度会差很多
- 所以需要设计一个缓冲，先写到缓冲块中，再慢慢写入
2）回写法
- 当 CPU 对 Cache 写命中时，只修改 Cache 的内容，而不立即写入主存，只有当此块被换出时才写回主存
- 减少了访存次数，但存在数据不一致的隐患
- 在 cpu 执行写操作时，先按橙色线写入 cache 存储体中
- 此时并没有修改主存的内容，会在 cache 中设计一个脏位
- 当一块中的任何一个单元被修改时，脏位 (修改位) 被置“1”
- 需要替换掉这一块时，如果修改位为“1”，则必须先把这一块写回到主存中，然后才能再调入新的块
- 如果修改位为“0”，则这一块不必写回主存，只要用新调入的块覆盖这一块即可
（2）写不命中
1）写分配法
- 当 CPU 对 Cache 写不命中时，把主存中的块调入 Cache ，在 Cache 中修改
- 搭配回写法使用
2）非写分配法
- 当 CPU 对 Cache 写不命中时只写入主存，不调入 Cache
- 搭配全写法使用
（3）多级 Cache
- 现代计算机通常采用多级 Cache 结构
