第三章存储系统

第一节存储器概述

「存储器」按计算机层次分类

主存储器
- 简称主存（或内存），CPU可以直接的随机进行访问。
辅助存储器
- 简称辅存（或外存），永久性存储信息，内容要调入主存才可以被CPU访问。
高速缓冲存储器
- 简称Cache，位于主存和CPU之间，存放当前CPU经常使用的指令和数据。

「存储器」按存储介质分类

磁表面存储器(磁盘、磁带)
磁芯存储器
半导体存储器 (MOS 型存储器、双极型存储器)
光存储器(光盘)

「存储器」按存取方式分类

随机存储器 RAM
- 可随机存取，用作主存或高速缓冲存储器，分为静态RAM和动态RAM
只读存储器 ROM
- 只能随机读出不能写入，与随机存储器可共同作为主存的一部分，统一构成主存的地址域
串行访问存储器
- 按其物理位置的先后顺序寻址
- 顺序存取存储器（如磁带）
  - 只能按某种顺序存取，存取速度慢。
- 直接存取存储器（如磁盘、光盘）
  - 不像顺序存取存储器完全按顺序存取
  - 存取信息时先寻找整个存储器中的小区域（如磁盘上的磁道）
  - 在小区域内顺序查找

「存储器」按信息的可保存性分类

易失性存储器（如RAM）
非易失性存储器（如ROM）
破坏性读出
- 读出后一般紧接一个再生的操作
非破坏性读出
- 被堵单元原存储信息不被破坏

「存储器」性能指标

存储容量 = 存储字数 x 字长（如1M x 8位）
单位成本(每位价格) = 总成本/总容量
存储速度：数据传输率 = 数据的宽度/存取周期（或称存储周期）
存取时间（ $T_{a}$ ）
- 指从启动一次存储器操作到完成该操作所经历的时间,
- 分为
  - 读出时间
  - 写入时间
存取周期（ $T_{m}$ ）
- 又称读写周期或访问周期。
- 它是指存储器进行一次完整的读写操作所需的全部时间
- 即连续两次独立访问存储器操作(读或写操作)之间所需的最小时间间隔。
主存带宽（ $B_{m}$ ）
- 又称数据传输率
- 表示每秒从主存进出信息的最大数量
- 单位为字/秒、字节/秒(B/s)或位/秒(b/s)

存储周期与存储时间的关系

存取时间不等于存取周期，通常存取周期大于存取时间
读写操作之后，总要有一段恢复内部状态的复原时间。
破坏性读出的存储器
- 存取周期往往比存取时间大得多，甚至可达 $T = 2 T_{a}$
- 因为存储器中的信息读出后需要马上进行再生。

「存储器」多级层次存储结构

存储器层次结构的主要思想是上一层的存储器作为低一层存储器的高速缓存。

第二节主存储器

主存储器由DRAM实现，靠近处理器的Cache层由SRAM实现

「主存」SRAM 工作原理

存储元：存放一个二进制位，是存储器的最基本的构件
存储单元：地址码相同的多个存储元构成
存储体：若干存储单元的集合构成
静态随机存储器 SRAM
- 存储元用双稳态触发器(六晶体管MOS)，信息被读出后不需要再生(非破坏性读出)
- 优点：存取速度快
- 缺点：集成度低、功耗较大，价格昂贵
- 一般用于高速缓冲存储器 Cache

「主存」DRAM 工作原理

动态随机存储器（DRAM）
- 利用存储元电路中栅极电容上的电荷来存储信息的，
- DRAM 的基本存储元通常只使用一个晶体管，所以它比SRAM 的密度要高很多。
- 优点：容易集成、位价低、容量大、功耗低
- 缺点：存取速度比 SRAM的慢
- 用途：用于大容量的主存系统
- 刷新周期
  - DRAM 电容上的电荷一般只能维持1~2ms，因此即使电源不断电，信息也会自动消失。
  - 为此，每隔一定时间必须刷新，通常取 2ms，称为刷新周期。

「主存」DRAM常见的刷新方式

「DRAM刷新方式」集中刷新

指在一个刷新周期内，用一段固定的时间
- 依次对存储器的所有行进行逐一再生
- 在此期间停止对存储器的读写操作
- 称为“死时间”，又称访存“死区”。
优点：读写操作时不受刷新工作影响
缺点：集中刷新期间(死区)不能访问存储器

「DRAM刷新方式」分散刷新

把对每行的刷新分散到各个工作周期中，分为两部分
- 前半部分用于正常读、写或保持
- 后半部分用于刷新
优点
- 没有死区
缺点
- 加长了系统的存取周期，降低了整机的速度。
  - 如存储芯片的存取周期为 0.5us，则系统的存取周期为1us。

「DRAM刷新方式」异步刷新

异步刷新是前两种方法的结合
- 它既可缩短“死时间”
- 又能充分利用最大刷新间隔为 2ms 的特点
具体做法
- 将刷新周期除以行数
- 到两次刷新操作之间的时间间隔 t
- 利用逻辑电路每隔时间 t 产生一次刷新请求
优点
- 避免使CPU连续等待过长的时间
- 减少了刷新次数
- 根本上提高了整机的工作效率

「主存」DRAM刷新需要注意的问题

刷新对 CPU 是透明的，即刷新不依赖于外部的访问
动态 RAM 的刷新单位是行，由芯片内部自行生成行地址
刷新操作类似于读操作，刷新时不需要选片，即整个存储器中的所有芯片同时被刷新

「主存」SRAM和DRAM的比较

「主存」存储器芯片的内部结构

存储体(存储矩阵)
- 存储体是存储单元的集合
- 由行选择线(X)和列选择线(Y) 来选择所访问单元
- 存储体的相同行、列上的位同时被读出或写入
地址译码器
- 用来将地址转换为译码输出线上的高电平，以便驱动相应的读写电路。
I/O 控制电路
- 用以控制被选中的单元的读出或写入，具有放大信息的作用。
片选控制信号
- 在访问某个字时，用来“选中”多个芯片扩展后的存储器中该存储字所在的芯片
读/写控制信号
- 根据 CPU 给出的读命令或写命令，控制被选中单元进行读或写。

「存储器」ROM 只读存储器的特点

ROM 为非易失性存储器
- 一旦有了信息，就不能轻易改变，即使掉电也不会丢失
- 它在计算机系统中是只供读出的存储器
ROM 和 RAM 都是支持随机访问的存储器
ROM 优点
- 结构简单，位密度比可读写存储器的高
- 具有非易失性，可靠性高

「存储器」ROM的类型

存储器	缩写	特点
掩模式只读存储器	MROM	可靠，集成度高，便宜，不灵活
一次可编程存储器	PROM	用户自己写入，只可写入一次
可擦除可编程存储器	EPROM	可编程器多次改写，但编程次数有限，写入时间长
闪存存储器	Flash	便宜，集成度高，电可擦除，重写速度快
固态硬盘	SSD	控制单元+Flash，快速擦除重写，读写快，低功耗，价格高

「主存」基本构成

「主存 & CPU」指令执行过程

CPU 把被访问单元地址送到 MAR 中
通过地址线将主存地址送到主存中的地址寄存器
地址译码器进行译码选中相应单元
CPU将读写信号通过控制线送到主存的读写控制电路
- 如果是写操作
  - 那么CPU 同时将要写的信息送到MDR 中
  - 在读写控制电路的控制下，经数据线将信号写入选中的单元
- 如果是读操作
  - 那么主存读出选中单元的内容送到数据线，然后送到 MDR 中

「主存 & CPU」总线的宽度

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

「主存」地址引脚复用技术

DRAM 芯片容量较大，地址位数较多
行地址和列地址通过相同的引脚分先后两次输入
地址引脚数可减少一半

「主存」单体多字存储器（多模块存储器）

特点
- 存储器中只有一个存储体
- 每个存储单元存储 m 个字
- 总线宽度也为 m 个字
- 一次并行读出 m 个字
- 地址必须顺序排列并处于同一存储单元
优点
- 在一个存取周期内，每隔1/m存取周期， CPU 向主存取一条指令
- 提高了单体存储器的工作速度
缺点
- 指令和数据在主存内必须是连续存放的
  - 遇到转移指令，或操作数不能连续存放，提高效果不明显

「主存 & ⭐️」多体并行存储器（多模块存储器）

组成
- 多体模块
  - 独立的读写控制电路
  - 独立的地址寄存器
  - 独立的数据寄存器
  - 相同的容量和存取速度
  - 既能并行工作，又能交叉工作
种类
- 高位交叉编址
- 低位交叉编址

「多体并行」高位交叉编址（顺序方式）

高位地址表示体号
低位地址表示体内地址
如图 3.7 所示，存储器共有4个模块 $M_{0}$ ~ $M_{3}$ ，每个模块有n个单元，各模块的地址范围如图中所示。

高位交叉方式下
- 把低位的体内地址送到由高位体号确定的模块内进行译码
- 访问一个连续主存块时
  - 在一个模块访问完才转到下一个模块访问
  - CPU总是按顺序访问存储模块
- 各模块不能被并行访问，因而不能提高存储器的吞吐率。
注意：
- 模块内的地址是连续的
- 存取方式仍是串行存取
- 存储器仍是顺序存储器

「多体并行」低位交叉编址（交叉方式）

低位地址为体号
高位地址为体内地址

低位交叉方式下
- 把高位的体内地址送到由低位体号确定的模块内进行译码。
- 采用流水线的方式并行存取
  - 不改变每个模块存取周期，提高存储器的带宽
交叉存储器
- 采用低位交叉编址的存储器
- 因程序连续存放在相邻模块中

设模块字长等于数据总线宽度，模块存取一个字的存取周期为T，总线传送周期为r
- 交叉存储器（低位交叉）
  - 存储器交叉模块数应大于等于 $m = T / r$
  - 流水线不间断
    - 保证启动模块后经过 $m \times r$ 的时间后再次启动该模块时
    - 上次的存取操作已经完成
  - 连续存取 m 个字所需的时间为
    - $t_{1} = T + (m - 1) r$
- 顺序方式
  - 连续读取 m 个字所需的时间为
    - $t_{2} = m T$
- 可见低位交叉存储器的带宽大大提高。
低位交叉编址模块数为4的流水线存取方式。

「多体并行 & 题」低位交叉编址计算题

第三节主存储器与CPU的连接

「主存 & CPU」连接原理

主存储器连接CPU，通过
1. 数据总线
2. 地址总线
3. 控制总线
$数据总线的位数 \times 工作频率 = n \times 数据传输率$
地址总线的位数
- 决定可寻址的最大内存空间
控制总线(读/写)，指出
1. 总线周期的类型
2. 本次输入/输出操作完成的时刻

「内存条 & CPU」信息通道

内存条插槽就是存储器总线
内存条中的信息
- 通过内存条的引脚
- 通过插槽内的引线
  - 连接到主板上
    - 通过主板上的导线
      - 连接到 CPU 芯片

「主存 & CPU」位扩展法

CPU 的数据线数与存储芯片的数据位数不一定相等
- 对存储芯片扩位（进行位扩展，增加存储字长）
- 使其数据位数与CPU的数据线数相等
位扩展的连接方式
- 将多个存储芯片的
  - 地址端、片选端、读写控制端相应并联
  - 数据端分别引出
举例，如图3.12所示
- 8片8K×1位的 RAM 芯片组成8K×8位的存储器
- 8片 RAM 芯片的地址线 $A_{12} \sim A_{0} 、 \overset{―}{C S} 、 \overset{―}{W E}$ 都分别连在一起
  - 每片的数据线依次作为CPU数据线的一位

注意：
- 仅采用位扩展时，各芯片
  - 连接地址线的方式相同
  - 连接数据线的方式不同
- 在某一时刻选中所有芯片，所以通过
  - 片选信号 $\overset{―}{C S}$
- 连接到所有芯片。

「主存 & CPU」字扩展法

字扩展
- 指增加存储器中字的数量，而位数不变。
- 将芯片的地址线、数据线、读写控制线相应并联
  - 由片选信号来区分各芯片的**地址范围****

注意：
- 仅采用字扩展时，各芯片
  - 连接地址线的方式相同
  - 连接数据线的方式相同
  - 某一时刻只需选中部分芯片，所以通过
    - 片选信号 $\overset{―}{C S}$
    - 译码器
  - 设计连接到相应的芯片

「主存 & CPU」字位同时扩展法

同时扩展字和位

注意：
- 采用字位同时扩展时，各芯片
  - 连接地址线的方式相同
  - 连接数据线的方式不同
  - 而且需要通过
    - 片选信号 $\overset{―}{C S}$
    - 译码器
  - 设计连接到相应的芯片。

「存储芯片」地址分配和片选

CPU 要实现对存储单元的访问
- 首先片选，选择存储芯片
- 然后字选，依地址码选择相应的存储单元，进行数据存取
- 片内的字选
  - 由CPU送出的N条低位地址线完成的
  - 地址线直接接到所有存储芯片的地址输入端
  - （N由片内存储容量 $2^{N}$ 决定）
片选信号的产生，分为
- 线选法
- 译码片选法

「存储芯片」线选法

001选中第一片，010选中第二片

线选法
- 用除片内寻址外的高位地址线
  - 直接
  - 经反相器
- 分别接至各个存储芯片的片选端
- 当某地址线信息为“0” 时
  - 就选中与之对应的存储芯片
片选地址线每次寻址时
- 一位有效
- 不允许多位有效
保证每次只选中一个芯片(或芯片组)。
假设 4 片 $2 K \times 8$ 位存储芯片用线选法构成 $8 K \times 8$ 位存储器
各芯片的片选信号见表 3.2 ，低位地址线 $A_{10} \sim A_{0}$ 作为字选线，用于片内寻址。

	优点：不需要地址译码器，线路简单。缺点：地址空间不连续，选片的地址线必须分时为低电平(否则不能工作)，不能充分利用系统的存储器空间，造成地址资源的浪费。

「存储芯片」译码片选法

000选中第一片，001选中第二片

译码片选法
- 用除片内寻址外的高位地址线通过
  - 地址译码器芯片
- 产生片选信号

「存储芯片」线选法与片选法的对比

用8片8Kx8位的存储芯片组成64Kx8位存储器
- 地址线为16位，数据线为8位
需要8个片选信号
- 线选法
  - 除去片内寻址的13位地址线，仅余高3位
  - 不足以产生8个片选信号
- 译码片选法
  - 用一片 74LS138 作为地址译码器，则
  - $A_{15} A_{14} A_{13} = 000$ 时选中第一片
  - $A_{15} A_{14} A_{13} = 001$ 时选中第二片（3位二进制编码）

「存储器 & CPU」地址线的连接

字选译码
- 由芯片内的片内逻辑完成
片选译码
- 由外接译码器逻辑完成
存储芯片的容量不同，其地址线数也不同
- CPU 的地址线数 > 存储芯片的地址线数
CPU地址线的低位
- 字选使用
  - 译码是由芯片的片内逻辑完成的。
- 与存储芯片的地址线相连
CPU地址线的高位
- 片选使用
  - 译码由外接译码器逻辑完成。
- 扩充存储芯片使用

「存储器 & CPU」数据线的连接

CPU 的数据线数与存储芯片的数据线数不一定相等
- 相等时
  - 可直接相连
- 不等时
  - 对存储芯片扩位，使其数据位数与CPU 的数据线数相等

「存储器 & CPU」读/写命令线的连接

CPU 读/写命令线一般可直接与存储芯片的读/写控制端相连
- 通常高电平为读，低电平为写。
有些 CPU 的读/写命令线是分开的
- （读为 $\overset{―}{R D}$ ，写为 $\overset{―}{W E}$ ，均为低电平有效）
CPU 的读命令线应与存储芯片的允许读控制端相连
CPU 的写命令线应与存储芯片的允许写控制端相连

「存储器 & CPU」片选线的连接

片选线的连接
- 是CPU与存储芯片连接的关键。
片选线的作用
- 存储器由许多存储芯片叠加而成
- 哪一片被选中完全取决于该存储芯片的片选控制端 $\overset{―}{C S}$
  - 是否能接收到来自CPU 的片选有效信号。
片选有效信号为低电平有效
- 片选有效信号与CPU 的访存控制信号 $\overset{―}{M R E Q}$ （低电平有效）有关
  - 因为只有当CPU 要求访存时，才要求选中存储芯片
- 若CPU 访问 I/O，则 $\overset{―}{M R E Q}$ 为高，表示不要求存储器工作。

第四节外部存储器

「磁盘」存储器的优缺点

优点
- 存储容量大，位价格低
- 记录介质可重复使用
- 记录信息可长期保存而不丢失，甚至可脱机存档
- 非破坏性读出，读出时不需要再生。
缺点
- 存取速度慢
- 机械结构复杂，对工作环境要求较高

「磁盘」磁盘设备的组成

硬盘存储器的组成
- 磁盘驱动器
  - 核心部件是磁头组件和盘片组件
  - 温彻斯特盘是一种可移动磁头固定盘片的硬盘存储器
- 磁盘控制器
  - 硬盘存储器和主机的接口，主流的标准有 IDE、SCSI、SATA 等
- 盘片
存储区域
- 磁头数
  - 等于记录面数，表示硬盘共有多少个磁头
  - 磁头用于读取/写入盘片上记录面的信息
  - 一个记录面对应一个磁头
- 柱面数
  - 表示硬盘每面盘片上有多少条磁道。
  - 在一个盘组中，不同记录面的相同编号(位置)的诸磁道构成一个圆柱面。
- 扇区数
  - 表示每条磁道上有多少个扇区。

「磁盘」性能指标

记录密度
- 道密度是沿磁盘半径方向单位长度上的磁道数
- 位密度是磁道单位长度上能记录的二进制代码位数
- 面密度是位密度和道密度的乘积。
磁盘的容量
- 非格式化容量是指磁记录表面可利用的磁化单元总数，它由道密度和位密度计算而来
- 格式化容量是指按照某种特定的记录格式所能存储信息的总量
- 格式化后的容量比非格式化容量要小
平均存取时间
- 构成部分
  - 寻道时间(磁头移动到目的磁道的时间)
  - 旋转延迟时间(磁头定位到要读写扇区的时间)
  - 传输时间(传输数据所花费的时间)
- 寻道时间和旋转延迟时间通常取平均值
  - 寻道和找扇区的距离远近不一
数据传输率
- 磁盘存储器在单位时间内向主机传送数据的字节数
- 假设磁盘转数为r转/秒，每条磁道容量为N字节，则数据传输率为

D_{r} = r N

「磁盘」磁盘地址

主机向磁盘控制器发送寻址信息，磁盘的地址一般如下图所示。
举例
- 若系统中有4个驱动器
- 每个驱动器带一个磁盘
- 每个磁盘 256 个磁道、16个盘面
- 每个盘面划分为16个扇区
- 则每个扇区地址要18位二进制代码
其格式如下图所示

「磁盘」磁盘阵列（RAID独立冗余磁盘阵列）

RAID(独立冗余磁盘阵列)
- 是指将多个独立的物理磁盘组成一个独立的逻辑盘
- 数据在多个物理盘上分割交叉存储、并行访问
- 具有更好的存储性能、可靠性和安全性
为什么要用磁盘阵列？
- 在 RAID1~RAID5几种方案中，无论何时有磁盘损坏，都可随时拔出受损的磁盘再插入好的磁盘，而数据不会损坏，提升了系统的可靠性。
RAID 的分级
- RAID0：无冗余和无校验的磁盘阵列。
- RAID1：镜像磁盘阵列。
- RAID2：采用纠错的海明码的磁盘阵列。
- RAID3：位交叉奇偶校验的磁盘阵列。
- RAID4：块交叉奇偶校验的磁盘阵列。
- RAID5：无独立校验的奇偶校验磁盘阵列。

「SSD」固态硬盘

固态硬盘(SSD)是一种基于闪存技术的存储器
与U盘并没有本质上的差别，只是容量更大，存取性能更好
一个SSD = 一个或多个闪存芯片 + 闪存翻译层
闪存芯片 替代传统旋转磁盘中的机械驱动器
闪存翻译层将来自 CPU的逻辑块读写请求翻译成对底层物理设备的读写控制信号
闪存翻译层 $\approx$ 磁盘控制器
数据以页为单位读写，页数据全部擦除后，才可以写
一旦一个块被擦除，块中的每个页都可以直接再写一次
随机写很慢的原因
- 擦除块比较慢，毫秒级。
- 试图修改包含数据的页，需要将该页所在的块全部复制到新的块中。

第五节高速缓冲存储器

「Cache」程序访问的局部性原理

时间局部性
- 指在最近的未来要用到的信息
- 很可能是现在正在使用的信息，因为程序中存在循环。
空间局部性
- 指在最近的未来要用到的信息
- 很可能与现在正在使用的信息在存储空间上是邻近的
- 因为指令通常是顺序存放、顺序执行的
- 数据一般也是以向量、数组等形式簇聚地存储在一起的
高速缓冲技术就是利用局部性原理
- 把程序中正在使用的部分数据存放在一个高速的、容量较小的Cache 中
- 使CPU的访存操作大多数针对Cache 进行，从而提高程序的执行速度

「Cache」基本工作原理

Cache
- 位于存储器层次结构的顶层
- 由SRAM构成
- 基本结构如图3.17所示。
- Cache 和主存都被划分为相等的块
  - 为便于 Cache 和主存间交换信息，
- Cache 块又称 Cache 行
  - Cache每块由若干字节组成，块的长度称为块长(Cache 行长)

「基本工作原理」同时访问Cache和主存

某些计算机中也采用同时访问 Cache 和主存的方式
- 若Cache 命中，则主存访问终止
- 若Cache 未命中，访问主存并替换Cache

「Cache」命中率

「Cache & 题」Cache性能的计算

「Cache」实现策略

数据查找。如何快速判断数据是否在Cache 中。
地址映射。主存块如何存放在 Cache 中，如何将主存地址转换为 Cache 地址。
替换策略。Cache 满后，使用何种策略对 Cache 块进行替换或淘汰。
写入策略。如何既保证主存块和Cache 块的数据一致性，又尽量提升效率。

「Cache & 主存」映射方式

三种映射关系
- 直接映射
- 全相连映射
- 组相连映射

「直接映射」原理 & 优缺点

原理
- 主存中的每一块只能装入Cache 中的唯一位置。
- 若这个位置已有内容，则产生块冲突，原来的块将无条件地被替换出去(无须使用替换算法)。
优缺点
- 直接映射实现简单，但不够灵活，即使 Cache 的其他许多地址空着也不能占用，这使得直接映射的块冲突概率最高，空间利用率最低。
直接映射的关系可定义为

C a c h e 行 号 = 主 存 块 号 m o d C a c h e 总 行 数

「直接映射」CPU访存过程

首先根据访存地址中间的 c 位，找到对应的 Cache 行
将对应Cache行中的标记和主存地址的高t位标记进行比较
若相等且有效位为 1
- 则访问Cache“命中”
- 此时根据主存地址中低位的块内地址
- 在对应的 Cache 行中存取信息
若不相等或有效位为 0
- 则“不命中”
- 此时 CPU 从主存中读出该地址所在的一块信息送到对应的 Cache 行中
- 将有效位置 1 ，并将标记设置为地址中的高 t 位
- 同时将该地址中的内容送 CPU

「直接映射」地址映射结构

标记 + Cache 行号 = 主存字块标记

「全相连映射」原理 & 优缺点

原理
- 主存中的每一块可以装入Cache中的任何位置
- 每行的标记用于指出该行取自主存的哪一块
- 所以 CPU 访存时需要与所有Cache 行的标记进行比较
优点
- 比较灵活，Cache 块的冲突概率低，空间利用率高，命中率高
缺点
- 是标记的比较速度较慢，实现成本较高，通常需采用昂贵的按内容寻址的相联存储器进行地址映射。

「全相连映射」地址映射结构

「组相连映射」原理 & 优缺点

原理
- 组间采用直接映射、而组内采用全相联映射
- 组相连映射是对直接映射和全相联映射的一种折中
  - 当 Q=1 时变为全相联映射，
  - 当 Q=Cache 行数时变为直接映射。
- 每组有 r 个 Cache 行，则称之为r 路组相联,
- 每组有 2 个 Cache 行，因此称为二路组相联。
组相联映射的关系

C a c h e 组 号 = 主 存 块 号 m o d C a c h e 组 数 (Q)

组相连映射路数的选择
- 路数越大，即每组Cache 行的数量越大
  - 发生块冲突的概率越低，电路也越复杂
- 路数适当可使组相联映射的成本接近直接映射，而性能接近全相联映射

「组相连映射」地址映射结构

「组相连映射」CPU访存过程

根据访存地址中间的组号找到对应的 Cache 组
将对应 Cache 组中每个行的标记与主存地址的高位标记进行比较
若有一个相等且有效位为 1
- 则访问 Cache 命中
- 此时根据主存地址中的块内地址，在对应 Cache 行中存取信息
若都不相等或有效位为 0
- 则访问 Cache 不命中
- CPU 从主存读出该地址所在的一块信息送对应 Cache 组的任意一个空闲行中
- 将有效位置 1，并设置标记，同时将该地址中的内容送 CPU

「注意事项」标记 & Tag

Cache 行中的标记与映射关系表中的标记 Tag 并不相同
- 映射关系表中的标记位（Tag）
  - 是主存块号中的一部分
    - 若计算机主存地址为32位，为直接映射，块内偏移地址为5bit，则映射表中的标记（Tag）与 Cache 行号共同构成了主存块号
- Cache 行中的标记
  - 由数据位、标记位（Tag）、有效位、脏位（若使用回写法）、LRU位（若使用LRU算法）构成

「直接映射 & 题 & ⭐️」

「映射关系」三种映射的比较

直接映射的每个主存块只能映射到 Cache 中的某一固定行
全相联映射可以映射到所有 Cache 行
N路组相联映射可以映射到N行

当Cache 大小、主存块大小一定时	直接映射	全相联映射
命中率	最低	最高
判断开销	最小	最大
所需时间	最短	最长
标记所占的额外空间开销	最小	最大

「Cache」Cache中主存块的替换算法

随机算法
- 随机地确定替换的Cache 块
- 实现简单，但未依据程序访问的局部性原理，命中率较低
先进先出算法 FIFO
- 选择最早调入的行进行替换
- 容易实现，未依据程序访问的局部性原理，最早进入的主存块也可能是目前经常要用的
近期最少使用算法 LRU
- 依据程序访问的局部性原理，选择近期内长久未访问过的 Cache 行作为替换的行
- 平均命中率要比 FIFO 的高，是堆栈类算法
最不经常使用算法
- 将一段时间内被访问次数最少的存储行换出。
- 每行也设置一个计数器，新行建立后从 0 开始计数
- 每访问一次，被访问的行计数器加 1
- 需要替换时比较各特定行的计数值，将计数值最小的行换出
- 这种算法与LRU类似，但不完全相同

「替换算法」LRU算法

LRU 算法对每个 Cache 行设置一个计数器
用计数值来记录主存块的使用情况，并根据计数值选择淘汰某个块
计数值的位数与 Cache 组大小有关，2 路时有一位 LRU 位，4 路时有两位 LRU 位
假定采用四路组相联
- 有5个主存块{1,2,3,4,5}映射到 Cache 的同一组
- 对于主存访问序列{1,2,3,4,1,2,5,1,2,3,4,5}
- 采用 LRU 算法的替换过程如图 3.23 所示
左边的数字是对应 Cache 行的计数值
右边的数字是存放在该行中的主存块号

「LRU算法」LRU计数器变化规则

命中时
1. 所命中的行的计数器清零，比其低的计数器加 1，其余不变
未命中且还有空闲行时
1. 新装入的行的计数器置 0，其余全加 1
未命中且无空闲行时
1. 计数值为3的行的信息块被淘汰，新装行的块的计数器置 0，其余全加 1

注意：
- 若计数值等于3的时候，计数器不再增加
- 计数值仍然可以保证是 0、1、2、3 的序列

「LRU算法」抖动现象

当集中访问的存储区超过Cache 组的大小时，命中率可能变得很低
如上例的访问序列变为{1,2,3,4,5,1,2,3,4,5,⋯}
- 而 Cache 每组只有4行，那么命中率为0，这种现象称为抖动

「Cache」写策略

写策略的目的
- 因为 Cache 中的内容是主存块副本，当对Cache中的内容更新时，需用写策略保证内容一致
使用写策略后的两种情况
- 写命中
- 写不命中

「写策略 & 写命中」全写法

又称 写直通法，write-through
原理
- 当 CPU 对 Cache 写命中时，必须把数据同时写入Cache 和主存。
- 当某一块需要替换时，不必把这一块写回主存，用新调入的块直接覆盖即可。
优点
- 实现简单，能随时保持主存数据的正确性。
缺点
- 是增加了访存次数，降低了 Cache 的效率。
写缓冲(Write Buffer)
- 减少全写法直接写入主存的时间损耗，在Cache 和主存之间加一个写缓冲，如下图所示。
- CPU 同时写数据到 Cache 和写缓冲中，写缓冲再控制将内容写入主存。
- 写缓冲是一个 FIFO 队列，写缓冲可以解决速度不匹配的问题。
- 出现频繁写时，会使写缓冲饱和溢出。

「写策略 & 写命中」回写法

又称 write-back
原理
- 当 CPU 对 Cache 写命中时，只把数据写入 Cache
- 而不立即写入主存，只有当此块被换出时才写回主存。
优点
- 减少了访存次数
缺点
- 存在不一致的隐患。
为了减少写回主存的开销，每个 Cache 行设置一个修改位(脏位)。
- 若修改位为1，则说明对应Cache 行中的块被修改过，替换时需要写回主存
- 若修改位为0，则说明对应Cache 行中的块未被修改过，替换时无须写回主存

「写策略 & 写不命中」写分配法

write-allocate
加载主存中的块到 Cache 中，然后更新这个 Cache 块。
优点
- 试图利用程序的空间局部性
缺点
- 每次不命中都需要从主存中读取一块。

「写策略 & 写不命中」非写分配法

not-write-allocate
只写入主存，不进行调块。

「写策略」使用搭配

非写分配法通常与全写法合用
写分配法通常和回写法合用

「多级Cache」写策略方法

L1 to L2 全写、L2 to 主存回写
现代计算机的 Cache 通常设立多级 Cache
假定设 3 级 Cache
- 按离CPU 的远近可各自命名为L1 Cache、L2 Cache、L3 Cache
离 CPU 越远，访问速度越慢，容量越大
指令 Cache 与数据 Cache 分离一般在 L1 级
- 此时通常为写分配法与回写法合用。
下图是一个含有两级 Cache 的系统
- L1 Cache 对 L2 Cache 使用全写法
- L2 Cache 对主存使用回写法
  - 由于 L2 Cache 的存在，其访问速度大于主存
  - 因此避免了因频繁写时造成的写缓冲饱和溢出。

「虚拟存储器」基本概念

虚拟存储器将主存或辅存的地址空间统一编址，形成一个庞大的地址空间。

CPU 使用虚地址时，由辅助硬件找出虚地址和实地址之间的对应关系
- 并判断这个虚地址对应的存储单元内容是否已装入主存。
若已在主存中，则通过地址变换，CPU 可直接访问主存指示的实际单元
若不在主存中，则把包含这个字的一页或一段调入主存后再由CPU访问。
若主存已满，则采用替换算法置换主存中的交换块(即页面)。
虚拟存储器也采用和Cache类似的技术
- 将辅存中经常访问的数据副本存放到主存中
- 但是缺页(或段)而访问辅存的代价很大，提高命中率是关键
- 因此虚拟存储机制采用全相联映射
  - 每个虚页面可以存放到对应主存区域的任何一个空闲页位置
- 在处理一致性问题时，采用回写法

「虚拟存储器」页式虚拟存储器

页式虚拟存储器以页为基本单位。
虚拟空间与主存空间都被划分成同样大小的页
- 主存的页称为实页、页框
- 虚存的页称为虚页
虚拟地址
- 分为两个字段
  - 虚页号
  - 页内地址
- 到物理地址的转换
  - 由页表实现的
页表
- 是一张存放在主存中的虚页号和实页号的对照表
- 它记录程序的虚页调入主存时被安排在主存中的位置。
- 长久地保存在内存中。

页表

有效位 = 装入位
脏位 = 修改位
引用位 = 使用位
有效位也称装入位，用来表示对应页面是否在主存
- 若为 1 ，则表示该虚拟页已从外存调入主存，此时页表项存放该页的物理页号
- 若为 0 ，则表示没有调入主存，此时页表项可以存放该页的磁盘地址
脏位也称修改位，用来表示页面是否被修改过
- 虚存机制中采用回写策略，利用脏位可判断替换时是否需要写回磁盘。
引用位也称使用位，用来配合替换策略进行设置
- 例如是否实现最先调入(FIFO 位)或最近最少用(LRU 位)策略等。

CPU执行指令步骤
- CPU执行指令时，需要先将虚拟地址转换为主存物理地址。
- 页表基址寄存器存放进程的页表首地址
- 然后CPU根据虚拟地址高位部分的虚拟页号找到对应的页表项
  - 若装入位为 1 ，则取出物理页号，和虚拟地址低位部分的页内地址拼接，形成实际物理地址
  - 若装入位为 0 ，则说明缺页，需要操作系统进行缺页处理
地址变换的过程
优点
- 页面的长度固定，页表简单，调入方便
缺点
- 由于程序不可能正好是页面的整数倍
- 最后一页的零头将无法利用而造成浪费
- 并且页不是逻辑上独立的实体
- 所以处理、保护和共享都不及段式虚拟存储器方便

快表

为什么要使用快表？
- 由地址转换过程可知，访存时先访问一次主存去查页表，再访问主存才能取得数据。
- 如果缺页，那么还要进行页面替换、页面修改等
  - 因此采用虚拟存储机制后，访问主存次数更多了
- 依据程序执行的局部性原理
  - 快表(TLB) ：高速缓冲器组成，存放经常访问的页对应的页表项
  - 慢表(Page)：放在主存中的页表
- 在地址转换时，首先查找快表，若命中，则无须访问主存中的页表。

快表的构成
- 快表通常采用全相联或组相联方式
- 每个 TLB 项由页表表项内容加上一个 TLB 标记字段组成
- TLB 标记用来表示该表项取自页表中哪个虚页号对应的页表项
  - TLB 标记的内容在
    - 全相联方式下就是该页表项对应的虚页号
    - 组相联方式下则是对应虚页号的高位部分
      - 虚页号的低位部分用于选择 TLB 组的组索引

「虚拟存储器」具有TLB和Cache的多级存储系统

图3.27是一个具有 TLB 和 Cache 的多级存储系统
- 其中 Cache 采用二路组相联方式。
CPU 给出一个 32 位的虚拟地址，TLB 采用全相联方式，每一项都有一个比较器，查找时将虚页号与每个 TLB 标记字段同时进行比较
- 若有某一项相等且对应有效位为 1，则 TLB 命中，此时可直接通过 TLB 进行地址转换
- 若未命中，则TLB 缺失，需要访问主存去查页表。
图中所示的是两级页表方式
- 虚页号被分成页目录索引和页表索引两部分
  - 进行地址转换（页目录索引+页表索引=页表项）
  - 并将相应表项调入 TLB
- 若 TLB 已满，则还需要采用替换策略。
完成由虚拟地址到物理地址的转换后，Cache 机构根据映射方式将物理地址划分成多个字段，然后根据映射规则找到对应的 Cache 行或组
将对应Cache 行中的标记与物理地址中的高位部分进行比较
- 若相等且对应有效位为 1
  - 则 Cache 命中，此时根据块内地址取出对应的字送 CPU。

查找时，快表和慢表也可以同步进行
若快表中有此虚页号，则能很快地找到对应的实页号，并使慢表的查找作废
- 从而就能做到虽采用虚拟存储器但访问主存速度几乎没有下降。
举例
- 在一个具有 Cache 和 TLB的虚拟存储系统中
- CPU 一次访存操作可能涉及 TLB、页表、Cache、主存和磁盘的访问
访问过程如图 3.28 所示。

CPU 访存过程中存在三种缺失情况
- TLB 缺失：要访问的页面的页表项不在TLB 中
- Cache 缺失：要访问的主存块不在Cache 中
- Page 缺失：要访问的页面不在主存中
三种缺失的可能组合情况如表 3.3 所示

最好的情况是第1种组合，此时无须访问主存
第2种和第3种组合都需要访问一次主存
第4种组合需要访问两次主存
第5种组合发生“缺页异常”，需要访问磁盘，并且至少访问两次主存。
Cache 缺失处理由硬件完成
缺页处理由软件完成，操作系统通过“缺页异常处理程序”来实现
TLB 缺失既可用硬件又可用软件来处理。

「虚拟存储器」段式虚拟存储器

段式虚拟存储器中的段是按程序的逻辑结构划分的，各个段的长度因程序各异。
虚拟地址分为两部分：段号和段内地址
虚拟地址到实地址之间的变换是由段表来实现的
段表是程序的逻辑段和在主存中存放位置的对照表
段表的每行记录与某个段对应的段号、装入位、段起点和段长等信息
段的长度可变，所以段表中要给出各段的起始地址与段的长度

CPU 根据虚拟地址访存

根据段号与段表基地址 拼接成对应的段表行,然后根据该段表行的装入位判断该段是否已调入主存
- 段表基地址寻找指定的段表
- 装入位为 “1” ，表示该段已调入主存
- 装入位为 “0” ，表示该段不在主存中
已调入主存时，从段表读出该段在主存中的起始地址与段内地址(偏移量) 相加，得到对应的主存实地址（物理地址）

段式虚拟存储器的优缺点

优点
- 段的分界与程序的自然分界相对应，因而具有逻辑独立性
- 使得它易于编译、管理、修改和保护，也便于多道程序的共享
缺点
- 因为段长度可变，分配空间不便，容易在段间留下碎片，不好利用，造成浪费

「虚拟存储器」段页式虚拟存储器

程序按逻辑结构分段，每段再划分为固定大小的页
主存空间也划分为大小相等的页
- 程序对主存的调入、调出仍以页为基本传送单位。
每个程序对应一个段表，每段对应一个页表
- 段的长度必须是页长的整数倍，段的起点必须是某一页的起点。
虚地址分为段号、段内页号、页内地址三部分。

CPU虚地址访存

首先根据段号得到段表地址
然后从段表中取出该段的页表起始地址，与虚地址 段内页号合成，得到页表地址
最后从页表中取出实页号，与页内地址拼接形成主存实地址

段页式虚拟存储器的优缺点

优点：可以按段实现共享和保护。
缺点：在地址变换过程中需要两次查表，系统开销较大。

虚存与 Cache 的比较

相同之处
- 最终目标都是为了提高系统性能，两者都有容量、速度、价格的梯度。
- 都把数据划分为小信息块，并作为基本的传递单位，虚存系统的信息块更大。
- 都有地址的映射、替换算法、更新策略等问题。
- 依据程序的局部性原理应用“快速缓存的思想”，将活跃的数据放在相对高速的部件中。
不同之处
- Cache 主要解决系统速度，而虚拟存储器却是为了解决主存容量。
- Cache 全由硬件实现，是硬件存储器，对所有程序员透明；而虚拟存储器由OS和硬件共同实现，是逻辑上的存储器，对系统程序员不透明，但对应用程序员透明。
  - 透明：不可见
  - 不透明：可见
- 对于不命中性能影响，因为 CPU 的速度约为 Cache 的10倍，主存的速度为硬盘的100 倍以上，因此虚拟存储器系统不命中时对系统性能影响更大。
- CPU 与 Cache 和主存都建立了直接访问的通路，而辅存与CPU 没有直接通路。也就是说在 Cache 不命中时主存能和CPU 直接通信，同时将数据调入 Cache；而虚拟存储器系统不命中时，只能先由硬盘调入主存，而不能直接和CPU通信。

本章小结

「存储器」存储器的层次结构主要体现在何处?

存储器的层次结构主要体现在Cache-主存和主存-辅存这两个存储层次上。

「存储器层次结构」为何要分这些层次?

Cache-主存层次在存储系统中主要对CPU访存起加速作用，即从整体运行的效果分析，CPU 访存速度加快，接近于 Cache 的速度，而寻址空间和位价却接近于主存。
主存-辅存层次在存储系统中主要起扩容作用，即从程序员的角度看，他所使用的存储器的容量和位价接近于辅存，而速度接近于主存。
综合上述两个存储层次的作用,从整个存储系统来看,就达到了速度快、容量大、位价低的优化效果。

「存储器层次结构」计算机如何管理这些层次?

主存与Cache 之间的信息调度功能全部由硬件自动完成。
而主存与辅存层次的调度目前广泛采用虚拟存储技术实现
即将主存与辅存的一部分通过软/硬结合的技术组成虚拟存储器，程序员可用这个比主存实际空间(物理地址空间)大得多的虚拟地址空间(逻辑地址空间)编程
当程序运行时，再由软/硬件自动配合完成虚拟地址空间与主存实际物理空间的转换。
因此，这两个层次上的调度或转换操作对于程序员来说都是透明的。

「存储器」存取周期和存取时间有何区别?

存取时间仅为完成一次操作时间
存取周期不仅包含操作时间，而且包含操作后线路的恢复时间
- 存取周期=存取时间+恢复时间。

「虚拟存储器」页面是设置得大一些好还是设置得小一些好?

页面不能设置得过大，也不能设置得过小。
页面太小时，平均页内剩余空间较少，可节省存储空间，但会使得页表增大，而且页面太小时不能充分利用访存的空间局部性来提高命中率;
页面太大时，可减少页表空间，但平均页内剩余空间较大，会浪费较多存储空间，页面太大还会使页面调入/调出的时间较长。

常见问题和易混淆知识点

「存储器」存取时间Ta就是存储周期Tm吗?

存 取 时 间 T_{a} \neq 存 储 周 期 T_{m}

不是。
存取时间 $T_{a}$ 是执行一次读操作或写操作的时间，分为读出时间和写入时间。
- 读出时间是从主存接收到有效地址开始到数据稳定为止的时间;
- 写入时间是从主存接收到有效地址开始到数据写入被写单元为止的时间。
存储周期 $T_{m}$ 是指存储器进行连续两次独立地读或写操作所需的最小时间间隔。
所以存取时间 $T_{a}$ 不等于存储周期 $T_{m}$ ，通常存储周期 $T_{n}$ 大于存取时间 $T_{a}$ 。

「Cache」行的大小和命中率之间有什么关系?

行的长度较大，可以充分利用程序访问的空间局部性，使一个较大的局部空间被一起调到Cache 中，因而可以增加命中机会。
但是，行长也不能太大，主要原因有两个:
- 行长大使失效损失变大。
  - 若未命中，则需花更多时间从主存读块。
- 行长太大，Cache 项数变少，因而命中的可能性变小。

「Cache」发生取指令 Cache 缺失的处理过程是什么?

程序计数器恢复当前指令的值。
对主存进行读的操作。
将读入的指令写入 Cache 中，更改有效位和标记位。
重新执行当前指令。

第三章 存储系统 ​

第一节 存储器概述 ​

「存储器」按计算机层次分类 ​

「存储器」按存储介质分类 ​

「存储器」按存取方式分类 ​

「存储器」按信息的可保存性分类 ​

「存储器」性能指标 ​

「存储器」多级层次存储结构 ​

第二节 主存储器 ​

「主存」SRAM 工作原理 ​

「主存」DRAM 工作原理 ​

「主存」DRAM常见的刷新方式 ​

「DRAM刷新方式」集中刷新 ​

「DRAM刷新方式」分散刷新 ​

「DRAM刷新方式」异步刷新 ​

「主存」DRAM刷新需要注意的问题 ​

「主存」SRAM和DRAM的比较 ​

「主存」存储器芯片的内部结构 ​

「存储器」ROM 只读存储器的特点 ​

「存储器」ROM的类型 ​

「主存」基本构成 ​

「主存 & CPU」指令执行过程 ​

「主存 & CPU」总线的宽度 ​

「主存」地址引脚复用技术 ​

「主存」单体多字存储器（多模块存储器） ​

「主存 & ⭐️」多体并行存储器（多模块存储器） ​

「多体并行」高位交叉编址（顺序方式） ​

「多体并行」低位交叉编址（交叉方式） ​

「多体并行 & 题」低位交叉编址计算题 ​

第三节 主存储器与CPU的连接 ​

「主存 & CPU」连接原理 ​

「内存条 & CPU」信息通道 ​

「主存 & CPU」位扩展法 ​

「主存 & CPU」字扩展法 ​

「主存 & CPU」字位同时扩展法 ​

「存储芯片」地址分配和片选 ​

「存储芯片」线选法 ​

「存储芯片」译码片选法 ​

「存储芯片」线选法与片选法的对比 ​

「存储器 & CPU」地址线的连接 ​

「存储器 & CPU」数据线的连接 ​

「存储器 & CPU」读/写命令线的连接 ​

「存储器 & CPU」片选线的连接 ​

第四节 外部存储器 ​

「磁盘」存储器的优缺点 ​

「磁盘」磁盘设备的组成 ​

「磁盘」性能指标 ​

「磁盘」磁盘地址 ​

「磁盘」磁盘阵列（RAID独立冗余磁盘阵列） ​

「SSD」固态硬盘 ​

第五节 高速缓冲存储器 ​

「Cache」程序访问的局部性原理 ​

「Cache」基本工作原理 ​

「基本工作原理」同时访问Cache和主存 ​

「Cache」命中率 ​

「Cache & 题」Cache性能的计算 ​

「Cache」实现策略 ​

「Cache & 主存」映射方式 ​

「直接映射」原理 & 优缺点 ​

「直接映射」CPU访存过程 ​

「直接映射」地址映射结构 ​

「全相连映射」原理 & 优缺点 ​

「全相连映射」地址映射结构 ​

「组相连映射」原理 & 优缺点 ​

「组相连映射」地址映射结构 ​

「组相连映射」CPU访存过程 ​

「注意事项」标记 & Tag ​

「直接映射 & 题 & ⭐️」 ​

「映射关系」三种映射的比较 ​

「Cache」Cache中主存块的替换算法 ​

「替换算法」LRU算法 ​

「LRU算法」LRU计数器变化规则 ​

「LRU算法」抖动现象 ​

「Cache」写策略 ​

「写策略 & 写命中」全写法 ​

「写策略 & 写命中」回写法 ​

「写策略 & 写不命中」写分配法 ​

「写策略 & 写不命中」非写分配法 ​

「写策略」使用搭配 ​

「多级Cache」写策略方法 ​

第三章存储系统

第一节存储器概述

「存储器」按计算机层次分类

「存储器」按存储介质分类

「存储器」按存取方式分类

「存储器」按信息的可保存性分类

「存储器」性能指标

「存储器」多级层次存储结构

第二节主存储器

「主存」SRAM 工作原理

「主存」DRAM 工作原理

「主存」DRAM常见的刷新方式

「DRAM刷新方式」集中刷新

「DRAM刷新方式」分散刷新

「DRAM刷新方式」异步刷新

「主存」DRAM刷新需要注意的问题

「主存」SRAM和DRAM的比较

「主存」存储器芯片的内部结构

「存储器」ROM 只读存储器的特点

「存储器」ROM的类型

「主存」基本构成

「主存 & CPU」指令执行过程

「主存 & CPU」总线的宽度

「主存」地址引脚复用技术

「主存」单体多字存储器（多模块存储器）

「主存 & ⭐️」多体并行存储器（多模块存储器）

「多体并行」高位交叉编址（顺序方式）

「多体并行」低位交叉编址（交叉方式）

「多体并行 & 题」低位交叉编址计算题

第三节主存储器与CPU的连接

「主存 & CPU」连接原理

「内存条 & CPU」信息通道

「主存 & CPU」位扩展法

「主存 & CPU」字扩展法

「主存 & CPU」字位同时扩展法

「存储芯片」地址分配和片选

「存储芯片」线选法

「存储芯片」译码片选法

「存储芯片」线选法与片选法的对比

「存储器 & CPU」地址线的连接

「存储器 & CPU」数据线的连接

「存储器 & CPU」读/写命令线的连接

「存储器 & CPU」片选线的连接

第四节外部存储器

「磁盘」存储器的优缺点

「磁盘」磁盘设备的组成

「磁盘」性能指标

「磁盘」磁盘地址

「磁盘」磁盘阵列（RAID独立冗余磁盘阵列）

「SSD」固态硬盘

第五节高速缓冲存储器

「Cache」程序访问的局部性原理

「Cache」基本工作原理

「基本工作原理」同时访问Cache和主存

「Cache」命中率

「Cache & 题」Cache性能的计算

「Cache」实现策略

「Cache & 主存」映射方式

「直接映射」原理 & 优缺点

「直接映射」CPU访存过程

「直接映射」地址映射结构

「全相连映射」原理 & 优缺点

「全相连映射」地址映射结构

「组相连映射」原理 & 优缺点

「组相连映射」地址映射结构

「组相连映射」CPU访存过程

「注意事项」标记 & Tag

「直接映射 & 题 & ⭐️」

「映射关系」三种映射的比较

「Cache」Cache中主存块的替换算法

「替换算法」LRU算法

「LRU算法」LRU计数器变化规则

「LRU算法」抖动现象

「Cache」写策略

「写策略 & 写命中」全写法

「写策略 & 写命中」回写法

「写策略 & 写不命中」写分配法

「写策略 & 写不命中」非写分配法

「写策略」使用搭配

「多级Cache」写策略方法