408计组-存储系统

1. 概览

1.1 分类

存储器有如下的分类：

按在计算机中的作用分类

• 主存储器/主存/内存储器/内存

  CPU 可以直接随机对其访问

  容量小、存取速度快、单位成本高

• 辅助存储器/辅存/外存储器/外存

  辅存的内容需要调入主存后才能被 CPU 访问

  容量大、存取速度较慢、单位成本低

• 高速缓冲存储器/Cache

  CPU 的各级缓存，Cache 的存取速度可与 CPU 的速度相匹配

Cache、主存能与 CPU 直接交换信息，而辅存需要通过主存与 CPU 交换信息。

主存与 CPU、Cache、辅存都能交换信息。

Cache-主存层主要解决 CPU 和主存速度不匹配的问题。主存和 Cache 之间的数据调动是由硬件自动完成的，对所有程序员均是透明的。

主存-辅存层主要是解决存储系统的容量问题。主存和辅存之间的数据调用是由硬件和操作系统共同完成的，对应用程序员是透明的。

按存储介质分类

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

按存取方式分类

• 随机存储器/RAM

  存储器的任意一个存储单元都可以随机存取，并且存取时间和存储单元的物理位置无关。

• 只读存储器/ROM

  存储器的内容只能随机读出而不能写入。

  信息一旦写入存储单元，即使断电，内容也不会丢失。

  可与 RAM 共同作为主存的一部分，统一构成主存的地址域。

  一些类型的 ROM 存储器也可以进行反复重写，叫只读存储器只是叫习惯了。这种 ROM 的写入速度会比读取速度慢得多。

• 串行访问存储器

  对存储单元进行读/写操作的时候，需要先按物理位置的先后顺序寻址。又可以再分为两类：

  • 顺序存取存储器：磁带
  • 直接存取存储器：磁盘、光盘

按信息的可保存性分类

• 易失性：按断电后存储信息是否会消失，分为易失性存储器和非易失性存储器。
• 破坏性：按读取完某个存储单元存储的信息后，原存储信息是否被破坏，分为破坏性读出和非破坏性读出。对于破坏性读出的存储器，每次读出操作后必须再紧接着一个再生对的操作，以便恢复被破坏的信息。

1.2 性能指标

有如下的性能指标：

• $\text{存储容量} = \text{存储字数} \times \text{字长}$。其中存储字数表示存储器的地址空间大小，字长表示一次存取操作的数据量。

  1B = 8b，B 表示 byte 的意思，b 表示 bit 的意思

  注意，这里的字长指的是存储器的字长，也叫存储字，不同于 CPU 的字长。

• $\text{单位成本} = \text{位价} = \frac{\text{总成本}}{总容量}$

• $\text{存储速度} = \text{数据传输速率} = \text{主存带宽} = \frac{\text{字长}}{存取周期}$，即每秒从主存进出信息的最大数量，单位可以为 字/秒、字节/秒、位/秒。

• 存取时间：启动一次存储器操作到操作完成所经历的时间。

• 存取周期：存储器进行完一次存取操作之后可能不能立刻继续处理下一个请求，而是需要再等待一段时间。连续两次独立访问存储器的操作之间所需要的最小时间间隔就被称为存取周期。

  比如破坏性读出存储器在进行完存取操作之后，可能还要有一段时间来进行复原。

2. 内部存储

2.1 结构

整个存储器的结构分为如下几个层次：

• 存储器：是整个的一个概念。比如我们插多个内存条，那么这些内存条合起来称为内存这个存储器。
• 存储模块：是物理上的一个独立的实体，比如一根内存条就是一个内存模块。
• 存储芯片：一个存储模块可能由若干个存储芯片组成。比如内存条上的黑色颗粒就是存储芯片。

存储芯片的结构如下：

• 存放一个二进制位的物理器件称为存储元。多个存储元排列成二维，构成了一个位平面。多个存储矩阵的相同位置的存储元的地址码是相同的，构成一个存储单元。所有的位平面构成了一个存储体/存储矩阵。

  题目中经常会出现形如 $1024 \times 1024 \times 8$ 位这种对存储芯片的描述，表示的就是说这个存储芯片的存储矩阵的行数和列数为 $1024$，一个存储单元存储 $8$ 位。

  一般来说，每个存储元存放 1bit 数据。一个存储单元存放的是一个存储字的数据，一般是 1 个字节。

  一个存储芯片可能包含多个存储体/存储矩阵（上图中只画了一个）。

• 地址译码器用来在存储矩阵上定位要访问的存储单元的位置。

  地址译码器分为 $X$ 和 $Y$ 两个译码器，分别选中一个存储矩阵的一行和一列，将某个特定的存储单元取出。

  SRAM 是可以同时送入行列地址的。而 DRAM 需要先送行地址，再送列地址，但是行列地址线是复用的。

  这种地址译码器实际上是双译码法/二维译码，因为我们的存储体就是二维的。

  一些存储体是一维形状的，那么与之对应的就是单译码法/一维译码。相同容量，一维形状存储体的地址线宽度要比二维形状存储体的地址线宽度要大，所以二维形状存储体的存储矩阵叫法和双译码法更常见。

  王道上面说单译码法就是只有一个行译码器，同一行所有存储单元都被读写，我感觉说的不对。

• I/O 电路用来控制被选中的单元的读出或写入，同时具有信号放大的作用。

• 片选控制线：表示是否选中当前这个芯片。

• 读/写控制线：控制对被选中的存储单元是读还是写。

2.2 组合扩展

408 计组在这一部分的概念非常混乱（当然也可能是我自己没理清楚）。很多题目/辅导资料会把存储模块、存储芯片、存储体混用，字扩展、位扩展、多体存储、多模块存储这些也是混用的。做题的时候就别纠结了。

2.2.1 位扩展

有时候某个存储部分的存储字的位数小于 CPU 的总线宽度，此时需要位扩展。

以存储芯片的位扩展为例，我们需要把各芯片的地址线、片选控制线、读写控制线并联，然后各芯片的数据线分别引出，连接 CPU 的总线。

位扩展的总体思想就是把各个部分并联，然后每个部分负责一个区间。

位扩展在不同的地方都有使用，但是叫法可能不同：

• 存储芯片上，多个位平面就类似位扩展一样形成一个存储矩阵。

• 单体多字存储器相当于用类似的方法，扩大存储单元的容量。比如一个存储单元存储 $k$ 个字。CPU 在读一个字的时候，存储器直接主动响应 $k$ 个字，这种响应的比请求的还多，称为突发传输（Burst 传输）。

  优点是提高了存储器的吞吐率。缺点是如果 CPU 访问的地址不连续，很分散的话，提升不明显。

• 408 中也会把一些地方的位扩展叫做低位交叉编址/交叉存储器+同时启动，虽然我感觉和低位交叉编址没什么关系。

  如果我们在主板上插入多个内存条，比如两个内存条，就会开启双通道模式。每个通道都是一个总线宽度（比如 64 位），双通道就是把总线宽度扩大（变成 128 位），吞吐量也就增大。这就对应于低位交叉编址+同时启动。

2.2.2 容量扩展

有时候我们需要把多个存储部分给拼起来，以扩大总容量。扩展的方式大概有两种：

（1）在高位上区分不同的存储部分

这个也叫做片选。这个也分为两种：

• 高位上直接用位来表示选择哪个存储部分，这个也叫做片选里的线选法：

  比如上图，用 0 表示某个存储被选中，1 则表示没有被选中。显然只能有一个位为 0。

  优点：不需要译码器，线路简单。缺点：地址空间不连续，且存在地址空间的浪费。

• 用高位上表示的二进制数字表示选择哪个存储部分。这个也叫做片选里的译码片选法，也叫做字扩展、高位交叉编址的多体存储器。

  （上图的虚线表示一次只选择一个）

（2）在低位上区分不同的存储部分

这个也叫做低位交叉编址/交叉存储器+轮流启动。

低位交叉编址也叫做交叉存储器。其又分为轮流启动和同时启动。但是题目里一般提到低位交叉编址指的就是轮流启动的这个。

（上图的虚线表示一次只选择一个）

这种方式除了能扩大存储容量，还能使得读写操作变得流水线化。

比如，设模块的存取周期为 $T$，总线的周期为 $r$，存储部分的数量 $m$ 大于等于 $\frac{T}{r}$ 时，读完第一个字，在读取下一个字的时候，就换了一个部分读，当所有部分都读一遍，回到第一个部分，第一个部分恰好已经读完了，可以继续读，于是就变得流水线化：

这样，连续读 $n$ 个字的时间只需要 $T+(n-1)r$，而顺序方式读 $n$ 个字需要 $mT$ 的时间，可见交叉存储器的带宽大大提高。

不过有可能相邻的 $m$ 次访问请求中存在两次请求的地址对应到同一个部分，这就会发生访存冲突，需要推迟发生冲突的请求。

2.3 RAM

随机访问存储器（RAM）分为两种：SRAM，即静态存储器 和 DRAM，即动态存储器。

2.2.1 SRAM

原理

SRAM 将每个位存储在一个双稳态的触发器中。这个触发器是用一个六晶体管电路来实现的，其结构类似于一个倒转的钟摆，可以无限期地保持在两种电压状态之一，其他的所有状态都是不稳定的，并可以立刻由不稳定状态转移到稳定状态：

原则上，钟摆还可以在垂直位置一直保持平衡。但是这个状态是亚稳态的，一旦有任何细微的扰动也会使钟摆倒下，而且一旦倒下就不会恢复到垂直状态。

SRAM 这个双稳态的特性使得其只要有电，就能一直保持他的值，并且抗干扰的能力很强。干扰结束之后就能立刻恢复到原来的值。

特点

SRAM 是静态的随机访问寄存器。静态则意味着是非破坏性读出的。这也同时意味着 SRAM 的速度比 DRAM 快，常用作 CPU 内的缓存。

不过 SRAM 使用了六晶体管，这意味着 SRAM 的集成度低，功耗较大，价格较为昂贵。

2.2.2 DRAM

原理

DRAM 将每个位存储为对一个非常小的电容的充电，每个存储单元由一个电容和一个访问晶体管组成（所以 DRAM 也算半导体 RAM）。

DRAM 寻址时，需要先给行地址（这一步称为 RAS 请求），于是存储矩阵上的一整行都会被读取到内部的一个行缓冲区中（这个行缓冲区常用 SRAM 实现）。然后再给列地址（这一步称为 CAS 请求），就会直接从行缓冲区中将对应列的数据读出来。

值得注意的是，行缓冲区也为突发传输提供了基础。

由于 DRAM 需要分别对行和列进行寻址，所以 DRAM 的行列地址线是可以复用的，只需要整一个地址线，宽度只需要可以容纳行数和列数中较大的那个就可以了。

特点

DRAM 基本存储单元只使用一个晶体管，这意味着 DRAM 的集成度高，价位低，功耗小等优点。

DRAM 是动态存储器，这意味着是破坏性读出的，所以 DRAM 在读出之后还需要再把数据恢复。同时，DRAM 电容上的电荷一般只能维持 1 到 2 ms，所以需要定期在电荷消失之前将存储单元刷新（注意到 CPU 的时钟周期是以纳秒来衡量的，所以 DRAM 的数据保持时间相对来说还是比较长）。

同时，DRAM 存储单元对干扰非常敏感，电容的电压被扰乱之后就永远不会恢复了。

刷新

存储单元每隔一段时间就要刷新，这个时间间隔被称为刷新周期，DRAM 必须在刷新周期内完成对每个存储单元的刷新。

DRAM 的刷新只依赖于整个存储器的控制器，不依赖于外部如 CPU 设备。控制器应该是维护了一个统一的时钟。当需要刷新的时候，是所有芯片都同时被刷新。

我们知道 DRAM 读数据是可以直接把一行一口气全给读出来的。DRAM 的刷新就相当于是对存储单元读一下。所以 DRAM 的刷新是以行为单位进行的，耗时差不多为一个存取周期。

刷新的方式有如下几种：

• 集中刷新

  在一个刷新周期内的固定时间，专门把存储器的所有行逐一刷新，在此期间停止对存储器的读写操作，这段时间也叫死时间/访存死区。

• 分散刷新

  当对某一行进行读写的时候，读写完毕后顺便把这一行给刷新了。这样的话就相当于是把一个刷新周期内对每一行需要支付的刷新时间融入到了一个存取周期中。这样我们可以理解为是不存在死区了，但是存取周期被拉大。由于刷新时间基本上等于存取时间，所以这个方案可以认为是将存取周期扩大了一倍。

• 异步刷新

  比如刷新周期为 $T$，现在有 $N$ 行，那么异步刷新就是，每 $\frac{T}{N}$ 刷新一行。这样相当于是把集中刷新在最后聚集的死区均匀分布在了整个刷新周期中。这样可以避免让 CPU 连续等待过长时间。

更多类型

上面这是传统的 DRAM。而实际应用中更多使用改进后的 DRAM ：

• FPM DRAM（快页模式 DRAM）：传统的 DRAM 中，如果连续读写相同行的存储单元，DRAM 会反复载入内部行缓冲区。FPM DRAM 则会识别到如果某一行已经载入到内部行缓冲区中则不再重新载入。

• EDO DRAM（扩展数据输出 DRAM）：FPM DRAM 的加强版，允许 CAS 信号在时间上靠得更近一点。

• SDRAM（同步 DRAM）：

  DRAM、FPM DRAM、EDO RAM 都是异步的，也就是他们的控制信号和内存控制器的时钟信号的频率无关。这会导致 CPU 将地址和控制信号送至存储器后，需要经过一段延迟时间，数据才会被读出或者写入。在这个延迟的时间中，CPU 需要不断地采样 DRAM 的完成信号，并且在 DRAM 完成之前 CPU 不能做其他工作，这拖慢了 CPU 的效率。

  而 SDRAM 是同步的，会在 CPU 时钟的控制下进行数据的读出和写入，它将 CPU 发出的地址和控制信号锁存起来，经过指定的时钟周期数后再响应。尽管 CPU 还是要等待内存完成操作，但是等待的时间是可以被预测的，于是 CPU 可能会做一些优化，中间去干点别的什么的。总之带来的结果是比异步的 DRAM 速度要快。

• DDR SDRAM（双倍数据速率同步 DRAM）：是 SDRAM 的增强版，他使用两个时钟沿作为控制信号，使得 DRAM 的速度翻倍。

• VRAM（视频 RAM）：用在图形系统的帧缓冲区中。他基本思想和 FPM DRAM 类似，但有两个主要区别：首先是 VRAM 的输出是通过依次对内部缓冲区的整个内容进行移位得到的；其次是 VRAM 允许对内存进行并行读和写，这使得系统可以在写 VRAM 的同时，用 VRAM 中的数据更新屏幕。

2.4 ROM

ROM 和 RAM 一样都支持随机访问。并且 ROM 的结构简单，位密度比 RAM 要高。同时最重要的，ROM 是非易失的。

一些 ROM 既可以读又可以写，但是由于历史原因，习惯被称为只读存储器。

根据制造工艺的不同，ROM 可分为如下几类（下面的这些都属于半导体存储器）：

2.3.1 MROM

也被称为掩模式只读存储器，半导体制造厂商会按需求在芯片生产的过程中直接把数据写入，写入之后内容就无法改变了。

优点是可靠性高，集成度高，价格偏移。缺点是灵活性差。

2.3.2 PROM

也被称为一次可编程只读存储器。

每个存储器单元都一种熔丝，可被高电流熔断。用户也可以利用专门的设备写入自己的程序，写入一次之后内容就无法被改变。

比 MROM 稍微灵活了一点。

2.3.3 EPROM

也被称为可擦写可编程只读存储器。

每个存储单元有一个透明的石英窗口，允许光到达存储单元，当紫外线光照射窗口时，存储单元数据就被清零。

尽管 EPROM 支持重写，但是其重写次数是有限的，一般只能重写大概几千次。同时写入存储单元需要额外的特殊设备，且写入时间较长。

2.3.4 EEPROM

也被称为电子可擦除只读存储器。

类似 EPROM ，但不需要额外的设备进行写入，可以直接在 EEPROM 的电路卡上进行编程。EEPROM 能够被编程的次数的数量级可以达到 $10^5$ 次。

2.3.5 Flash

在 EEPROM 的基础上又进行了改进，成本更低，并且擦除重写的速度更高。

3. 外部存储

3.1 磁盘存储器

优点：

• 容量大，价格低
• 记录介质可以重复使用
• 记录信息保存时间长
• 非破坏性读出

缺点：

• 机械结构复杂，对工作环境要求高

3.1.1 结构

磁盘存储器由如下部分组成：

• 磁盘。结构如下：

  • 一个磁盘有若干个盘片。

  • 每个盘片有两面，称为记录面。每个记录面都会有一个对应的磁头。

  • 每个面上划分若干个同心圆，称为磁道。

  • 每个磁道被划分为一组扇区，每个扇区存储相等数量的数据（通常是 512 字节），是磁盘读写的最小单位。

    相邻扇区和相邻磁道之间会有一定的间隙分隔开，以避免精度错误。

  • 术语柱面指的是所有盘片表面上到主轴中心的距离相等的磁道集合。柱面数即一个记录面上面有多少个磁道。

• 磁盘驱动器：驱动磁盘转动，并在磁盘上通过磁头进行读写操作。

• 磁盘控制器：负责接收并解释 CPU 发来的命令，并向磁盘驱动器发出各种控制信号，同时检测磁盘驱动器状态。

一般文件系统会约定连续的几个扇区为一个簇（比如 ext 文件系统的块大小），操作系统在读写磁盘的时候是以簇为单位进行的。

操作系统会在内存中开辟一部分区域，用于缓冲将被送到磁盘上的数据，这个区域被称为磁盘高速缓存。

由于读写头距离盘面的高度只有 0.1 微米。因此哪怕是一粒微小的灰尘都会撞击到读写头。所以磁盘总是密封的。

3.1.2 读写

磁盘主要有三个操作：寻址、读盘、写盘。

每个操作都对应一个控制字。磁盘在工作时会反复取控制字和执行控制字。

磁盘属于机械式部件，所有的操作都是串行的。这也就意味着不可能在同一时刻既读又写，也不可能在同一时刻读两组或者是写两组数据。

在进行读写操作之前，需要先向磁盘控制器发送寻址信息，磁盘的地址的格式如下：

然后磁盘会先将磁头移动对应的柱面上，然后整个磁盘进行旋转，直到目标扇区到达读写头下。

然后磁头会将二进制数据，通过电磁转换，转变成从存储介质磁层中一个磁化翻转状态的序列。

3.1.3 性能指标

• 记录密度：指盘片单位面积上记录的二进制数据量，通常用下面三个指标来表示：

  • 道密度：沿磁盘半径方向单位长度上的磁道数。

  • 位密度：磁道单位长度上能记录的二进制数据量。

  • 面密度：道密度和位密度的乘积。

• 磁盘容量。分为如下两种：

  • 非格式化容量：

    $$\text{记录面数}\times\text{柱面数}\times\text{每条磁道的磁化单元数}$$

  • 格式化容量：

    $$\text{记录面数}\times\text{柱面数}\times\text{每道扇区数}\text{每个扇区的容量}$$

    格式化容量要比非格式化容量小。

• 存取时间，由如下三个部分构成：

  • 寻道时间：读写头移动到目标扇区所在的磁道的时间。

    平均寻道时间一般取从最外道移动到最内道时间的一半。

  • 旋转时间：旋转盘片使得目标扇区到达读写头下的时间（准确来说是读写头到达目标扇区开头的时间）。

    平均旋转时间一般取旋转半周的时间。

  • 传输时间：磁头读取一个扇区的时间。

  一般传输时间很小，可以忽略不记。平均寻道时间一般作为磁盘的参数由制造商公布。旋转时间和平均寻道时间近似。因此将平均寻道时间乘 2 可以用来估计磁盘的存取时间。

• 数据传输速率：如果磁盘的转数为 $r$ 转/秒，每条磁道容量为 $N$ 字节，则传输速率为 $D = rN$。

在之前，每个磁道上拥有的扇区数量都相同。但是由于磁道从内到外半径依次增大，这使得越外侧的磁道上扇区之间的间隙越来越大，会造成很严重的浪费。

现代大容量磁盘使用了一种称为多区记录的技术。我们把一些连续的磁道划分成一个区，同一个区内磁道上的扇区数量一致，由最靠近中心的磁道的扇区数量一致。不同区的磁道的扇区数量不一致。所以现代磁盘的一个参数是平均扇区数。

3.1.4 磁盘阵列

RAID（独立冗余磁盘阵列）指的是将多个独立的物理磁盘组成一个独立的逻辑盘，数据在多个物理盘上分割交叉存储，并行访问，具有更好的性能、可靠性、安全性。

RAID 有如下的分级：

• RAID0：无冗余和无校验磁盘阵列

  把连续多个数据块交替地放在不同物理磁盘中，几个磁盘交叉并行读写，即条带化技术，提高了存取速度。但是 RAID0 没有容错能力。

• RAID1：镜像磁盘阵列

  使两个磁盘同时读写，互为备份，把两个当一个用。

• RAID2：采用纠错的海明码磁盘阵列

• RAID3：位交叉奇偶校验的磁盘阵列

• RAID4：块交叉奇偶校验的磁盘阵列

• RAID5：无独立校验的奇偶校验磁盘阵列

其中除 RAID0 以外，其他的方案中，无论何时有磁盘损坏，都可以随时拔出受损的磁盘再插入好的磁盘，而数据不会损坏。

3.2 固态硬盘

基于闪存技术。固态硬盘和 U 盘无本质区别，只不过固态硬盘的容量会更大，性能更好。

一个固态硬盘由闪存翻译层和闪存两部分组成。其中闪存由若干个块组成，每个块又由若干个页组成。一个页的大小大概是 512 字节到 4KB 之间。一个块由 $32\sim 128$ 个页组成。

数据以页为单位进行读写。写入时，需要把一个块进行擦除才能写这个块内的页。一个块大约进行 $10^5$ 次擦写后就会被损坏。一个块被损坏之后就不能用了。当写操作试图修改一个已经包含数据的页时，这个页所属的块，整个都需要先复制到另一个已经被擦除的块中，然后再对目标页进行写。这也就使得固态硬盘的随机写速度很慢。闪存翻译层中实现了很复杂的逻辑，尽可能最小化写的代价，但是写的速度还是没读的速度快。

同时，为了延长 SSD 的寿命，有磨损均衡技术，大致有两种：

• 动态磨损均衡：写入数据时，优先选择擦除次数少的新闪存块。
• 静态磨损均衡：即使没有数据写入，SSD 也会主动检测并自动进行数据分配，让老的闪存块承担以读为主的存储任务，让新的闪存块腾出更多空间，承担更多以写为主的存储任务。

4. CPU 总线

CPU 通过总线与外部的设备进行交互。总线结构如下：

每个总线又包含了如下三种总线：

• 数据总线：数据总线的位数与工作频率的乘积正比于数据传输速率。
• 地址总线：地址总线的位数决定了可寻址的最大内存空间。

在读内存时，CPU 会将目标地址放到系统总线上，IO 桥将信号传递到内存总线，主存受到信号之后进行读取并将数据放到内存总线，IO 桥再将数据传回系统总线。写内存时同理。系统总线和内存总线与 CPU 相关。

其他的，如鼠标键盘、显卡、磁盘等，是连接到 IO 总线上的。IO 总线与 CPU 无关。IO 总线要比内存总线慢很多。

CPU 使用内存映射 IO 的技术来向 IO 设备发送命令。地址空间中有一块地址是用来与 IO 设备进行通信的，这被称为 IO 端口。一个设备可能会与一个或者多个 IO 端口相关联。

CPU 在操作 IO 设备时（如读磁盘），会向 IO 接口发送指令，表明要进行的操作、操作目标、参数等，IO 总线不会将对应的内存操作发送到内存总线，而是转而发送到相应的 IO 设备上。由于 IO 设备执行速度相比 CPU 的时钟周期来说相当慢，所以发完指令之后 CPU 继续做其他事情。IO 设备进行完操作之后会自行把数据放到内存中而并不需要 CPU 干涉（这也被称为 DMA（直接内存访问）技术）。数据完全准备完毕之后则会给 CPU 发送一个中断信号。

5. 缓存

5.1 结构

缓存的结构层次如下：

一般而言，上层的存储作为下层存储的缓存。

缓存既可以对数据进行缓存，又可以对指令进行缓存。前者称为 d-cache ，后者称为 i-cache。既缓存数据又缓存指令的缓存称为统一缓存。

5.2 放置策略

假设一个计算机系统每个存储器地址有 $m$ 位，形成 $M=2^m$ 个不同的地址。

一个缓存有 $S=2^s$ 个缓存组。

每个缓存组有 $E$ 个缓存行。

每个缓存行包含三部分：有效位、标记、$B=2^b$ 个缓存块。

从缓存中读一个地址的时候，我们把这个地址分成三部分。其中 $s$ 和 $b$ 是缓存的参数，$t=m-s-b$

根据取到的组索引选择相应的缓存组，然后在该组内的缓存行中搜索，找到有效位为 1 且标记部分和地址的标记部分相同的缓存行。找到了则说明缓存命中，并根据块偏移读取缓存行中相应的块。反之说明缓存不命中。

• 在最开始时，缓存中还没有缓存数据，此时任何访问请求都会触发缓存不命中，我们称这时的缓存叫冷缓存，这样的缓存不命中称为强制不命中或是冷不命中。
• 如果有两个地址都对应于同一个缓存行，那么来回读这两个地址就会使得缓存一直不命中。这种缓存不命中称为冲突不命中。
• 程序在运行过程中，可能会反复使用某个数据（比如循环反复访问一个数组），这个数据称为这个阶段的工作集，当工作集的大小超过缓存的大小时，会出现缓存不命中，这种被称为容量不命中。

5.2.1 直接映射缓存

当 $E=1$ 即每个缓存组只有一个缓存行时，我们将这种缓存称为直接映射缓存。

5.2.2 全相连缓存

缓存只有一个缓存组，称为全相连缓存：

缓存在硬件实现上，是并行地判断缓存行的标记和地址上的标记是否匹配。全相连缓存的缓存行非常多，这会使得标记匹配的电路的实现又贵又困难。全相连缓存只适合做小的缓存，如虚拟内存的快表（TLB）就是全相连缓存。

5.2.3 组相连缓存

除了上面两种情况的缓存就是组相连缓存。有 $E$ 个缓存组的缓存被称为 $E$ 路组相联缓存。

5.3 替换策略

像组相联缓存和全相连缓存，一个缓存组内有多个缓存行这种，在缓存不命中的时候，如果存在有效位为 0 的缓存行，我们就可以把新载入的数据放到这个缓存行中。如果没有的话，我们需要选择驱逐哪个缓存行，需要确定一个替换策略。有如下的替换策略：

• 随机：随机地替换缓存行。这种方案实现比较简单，但是可能会导致缓存命中率比较低。

• FIFO：选择最早被调入的缓存行进行替换。但是最早进入缓存的行可能也是要经常使用的，也可能导致缓存命中率比较低。

• LRU：替换最后一次访问时间最久远的缓存行

  LRU 算法对每个缓存行设置一个计数器（也被称为 LRU 替换位），用来统计缓存行的使用情况，并选择淘汰哪个块。计数器的位数和一个缓存组内的缓存行数量有关，如果有 $2$ 个缓存行，就设置 $1$ 位，如果有 $4$ 个缓存行，就设置 $2$ 位，以此类推。

  • 当缓存命中时，设命中的缓存行的计数器的值为 $x$，将所有计数器值小于 $x$ 的缓存行的计数器值加 $1$，并将命中的缓存行的计数器的值清零。
  • 当缓存未命中且还有空闲行的时候，新装入的行的计数器的值置为 $0$，其余缓存行的计数器的值加 $1$。
  • 当缓存未命中且没有空闲行的时候，替换计数器值为 $3$ 的缓存行。新装入的行的计数器的值置为 $0$，其余缓存行的计数器的值加 $1$。

  我们有时候可能要用高级语言手写 LRU 策略，一个单次操作 $O(1)$ 的实现如下：每个 Value 连在一个链表上。使用 HashMap，维护每个 Key 对应的 Value 的指针，这样就可以 $O(1)$ 判断 Value 是否存在以及在哪里。

  缓存命中时，将 Value 从链表中取出再插入到链表的头部。

  缓存不命中且需要替换时，选择替换链表最尾部的 Value。

• LFU：替换引用次数最少的缓存行

  单次操作 $O(1)$ 的实现：HashMap 的 key 维护访问次数，value 维护一个链表，链表元素为缓存的 Value。然后再有个 HashMap 维护每个缓存的 Key 对应的 Value 的指针，这样就可以 $O(1)$ 判断缓存是否存在以及存在哪里。维护一个当前最小访问次数。

  缓存命中时，将缓存的 Value 从链表中取出，然后放到访问次数 +1 的链表里。如果原来的链表为空了，则将其从 HashMap 中删掉，这样可以确保维护访问次数的 HashMap 中的元素个数不会超过缓存大小。

  缓存不命中时且需要替换时，选择当前最小访问次数对应的 HashMap 的链表中的元素进行替换。

5.4 一致性

当我们将对缓存进行修改时，需要使用合适的策略来确保缓存中的内容和主存内容保持一致。

在写入数据时，会出现两种情况：

• 要写入的位置已经位于缓存中，我们称之为写命中，此时又有两种策略：

  • 全写/直写：修改位于缓存中的块，然后立刻把这个块写回低一层。优点是简单，并且缓存行需要被替换的时候就不用再写回了。缺点是每次写都会引起总线的流量，降低了缓存的效率。

    一个优化是加一个写缓冲来解决缓存和内存写入速度不匹配的问题。但是如果出现频繁的写入，就会使得缓冲区饱和溢出：

  • 写回/回写：修改位于缓存中的块，但是不立刻写回到低一层，而是等该缓存被驱逐时，才会写回到低一层。优点是可以减少总线的流量。缺点是增加了复杂性，需要额外给每个缓存行设置一个修改位/脏位维护缓存是否被修改过。

• 要写入的位置没有在缓存中，即写不命中，此时也有两种策略：

  • 写分配：把要写入的位置加载到缓存中，再进行修改。写分配通常和写回配合。
  • 非写分配：避开缓存，直接修改低一层。非写分配通常和直写配合。

一般写回+写分配策略是比较常用的。因为对低一层的存储器直接进行写消耗的时间比较大，且写回+写分配与处理读的方式更加统一，且写回+写分配导致的电路复杂性在现代电路中已经不算障碍了。

5.5 缓存性能

有如下指标来衡量缓存的性能：

• 不命中率：$\frac{\text{不命中数量}}{\text{引用数量}}$
• 命中率：$1-\text{不命中率}$
• 命中时间：从缓存传送一个字到 CPU 所需要的时间，包含组选择、行确认、字选择、字传送的时间
• 不命中处罚：由于不命中所需要的额外时间，包含从下一层存储读数据、进行替换等时间

对于缓存大小，一方面，较大缓存大小可以提高缓存命中率。另一方面，大存储器的命中时间会长一点。因此层次越高的存储器大小越小。

对于单个缓存行的块数量，一方面，较多的块数量可以提高命中率。另一方面，也会增加不命中处罚。

对于相连度（即单个缓存组中缓存行的数量大小），一方面，相连度较大的话可以降低冲突不命中的抖动。另一方面，较高的相连度实现起来复杂又昂贵，这会增加命中时间，且选择被替换的行的复杂性也增加了，这会增加不命中时间。一般层次越高的缓存使用较低的相连度，层次较低的缓存使用较高的相连度。

5.6 程序利用缓存

一个良好的程序应当具有良好的局部性。局部性有两种形式：

• 空间局部性：如果一个内存位置被引用了一次，那么程序在不远的将来会引用这个内存位置附近的内存位置（这个内存位置被引用后必然存在缓存中，那么其附近的数据可能在同一个缓存行中）
• 时间局部性：某个内存位置被引用之后，后续还可能会多次引用这个内存位置（这个内存位置已经被载入缓存）

5.6.1 时间局部性

下表展示了时间局部性：

这表明，工作集越小，越能够放进更高层的缓存中，使得访问速度更快。我们应该考虑将访问频繁的数据放入 L1 缓存中。

步长为 1 进行访问时，即使访问的工作集已经远远超过 L1 缓存大小，但是测试会发现仍可以获得 L1 缓存的访问速率。这是因为现代的处理器有硬件级的预取机制，能够自动识别步长为 1 的访问模式，进而在下一次访问开始之前就把数据加入到缓存中。

5.6.2 空间局部性

下表展示了空间局部性：

吞吐量的降低是由于缓存不命中次数的增加。步长从 8 开始，每次访问都会导致缓存不命中，读吞吐量退化到和直接读取较低层存储器一样了。我们应该考虑尽可能让访问比较连续，以增加空间局部性。

如：

第三章学习过，多维数组在内存中的放置是按最后一个下标连续放置的，所以上面的代码会连续访问内存，代码有很好的空间局部性。但是没有很好的时间局部性，因为每个地址只会被访问一次。一般空间局部性和时间局部性有一个就可以。

其缓存命中情况如下：

而如果我们交换循环顺序：

代码会跳跃式地访问内存，空间局部性变得很差。缓存命中情况也很糟糕：

在一些机器上，前者会比后者快 25 倍。

7. 错题

RAM 只要电源不断电，所存信息就不会丢失。

首先可以更改的 ROM 也不算 RAM，支持随机存取的存储器并不一定是 RAM。其次 EPROM 的修改非常繁琐且耗时，并且能够改写的次数优先，因此不能作为需要频繁读写的 RAM 使用。

Ⅰ的意思应该是存储器内容会不会随着时间而发生改变，DRAM 有刷新机制，所以不会。

Ⅳ的一次完整刷新过程应该是指的刷新一行。

注意 DRAM 是行列地址线复用的，所以容量可以提高到原来的四倍。（虽然我觉得题面应该要写成“最多”）

首先这个题默认交叉存储器是轮流启动的。

首先这个题也是默认交叉存储器是轮流启动的。

并且还默认读取周期和总线周期的比例恰好就是模块数量。

对于 B，基本上所有存储字长和总线宽度不一致的情况，都可以说是用多模块交叉编址。

对于 C，注意 DRAM 的行列地址线复用。

后面那个译码输出为 1 才选择这个芯片，也就是为 1 才属于此译码空间。

存储器的 MAR 应该覆盖整个主存地址空间，和当前实际空间大小无关（应考虑到后续可能还会扩展）。