存储器层次结构
存储器概述
存储器的分类
主存储器的组成和基本操作
层次化存储结构
程序访问的局部性
半导体随机存取存储器
存储基本元件
六管静态 MOS 管存储元件
单管动态 MOS 管存储元件
静态存储元件和动态存储元件的比较
DRAM 芯片
存储器芯片的内部结构
DRAM 芯片的刷新
SDRAM 芯片技术
SDRAM 芯片技术
DDR SDRAM 芯片技术
DDR2 SDRAM 芯片技术
DDR3 SDRAM 芯片技术
DDR4 SDRAM 芯片技术
DDR5 SDRAM 芯片技术
内存条及其与 CPU 的连接
存储器芯片的扩展
主存控制器
外部存储器
磁盘存储器的结构
磁盘存储器的性能指标
记录密度
存储容量
数据传输速率
平均存取事件
闪速存储器和 U 盘*
闪存存储元*
闪存的基本操作*
固态硬盘*
Cache
通过提高存储器芯片本身的速度或采用并行存储器结构，可以弥补 CPU 和主存之间的性能差距。除此之外，在 CPU 和主存之间添加 cache（高速缓冲存储器）也可以提高 CPU 访存的速度。
cache 的基本工作原理
「cache」是一种小容量高速缓冲存储器，由快速的 SRAM 存储元构成，直接集成在 CPU 芯片内，速度几乎与 CPU 一样快。在 CPU 和主存之间添加 cache，可以把程序频繁访问的活跃主存块装入 cache 中。由于程序的局部性特点，大多数情况下，CPU 能直接从 cache 中取得指令和数据，而不必访问慢速的主存。
为便于 cache 和主存交换信息，一般将 cache 和主存空间划分为大小相等的区域，主存中的区域称为「块」（block），也称为「主存块」，它是 cache 和主存之间的信息交换单位；cache 中存放一个主存块的区域称为「行」（line）或「槽」（slot）。
cache 的有效位
在系统启动或复位时，每个 cache 行都为空，其中的信息无效，只有装入了主存块后信息才有效。为了标识这一点，每个 cache 行都关联一个「有效位」（valid bit）。
有了有效位，就可以将有效位清零来淘汰某 cache 行中的主存块，这个操作称为「冲刷」（flush），装入一个新主存块时，再将有效位置一。
CPU 在 cache 中的访问过程
【这里有一张图，图 6.20】
如上凸所示，整个访存过程如下：
- 判断信息是否在 cache 中，若是，则直接从 cache 中取信息；
- 若否，则从主存取一个主存块到 cache.
- 如果对应 cache 行已满，则需要替换 cache 中的信息。
cache - 主存层次的平均访问时间
据图 6.20，访存过程中需要判断所访问信息是否在 cache 中。
若是，则称为 cache「命中」（hit）；若否，则称为「不命中」或「缺失」（miss）。二者次数与访问总次数之比分别称为「命中率」（hit rate）\(p\) 和「缺失率」（miss rate）（或「不命中率」）。
命中时，CPU 在 cache 中直接存取信息，所用时间即为 cache 访问时间 \(T_c\)，称为「命中时间」（hit time）；缺失是，需要从主存读取一个主存块送 cache，同时将所需信息送 CPU，所用时间为主存访问时间 \(T_m\) 和 cache 访问时间 \(T_c\) 之和，此处 \(T_m\) 称作「缺失损失」（miss penalty）【我觉得称为「不命中惩罚」或者「不命中罚时」更好】。
显然，CPU 在 cache - 主存层次的平均访问时间为： $$ T_a=pT_c+(1-p)(T_m+T_c)=T_c+(1-p)T_m $$ 由于程序访问的局部性特点，cache 的命中率可以很高而接近于 \(1\)，因此虽然有 \(T_m\gg T_c\)，但最终的平均访问时间仍可接近 \(T_c\)，这就很好。
cache 的映射方式
cache 行中的信息取自主存中的某块。在将主存块装入 cache 行时，主存块和 cache 行之间必须遵循一定的映射规则，这样，CPU 要访问某个主存单元时，可以依据映射规则直接到 cache 对应行中查找要访问的信息，而不用在整个 cache 中寻找。
根据不同的映射规则，主存块和 cache 行之间通常有以下三种映射方式：
- 「直接映射」（direct-mapped）：每个主存块映射到 cache 的固定行中。
- 「全组联」（fully associative）：每个主存块映射到 cache 的任意行中。
- 「组相联」（set associative）：每个主存块映射到 cache 的固定组的任意行中。
直接映射方式
直接映射的基本思想是将主存块映射到固定的 cache 行中，也称「模映射」，映射关系如下：
cache 行号 = 主存块号 mod cache 行数
通常 cache 行数是 2 的幂，假设 cache 有 \(2^c\) 行，主存有 \(2^m\) 块，套用上面公式，主存块号低 \(c\) 位即它要装入的 cache 行号，且主存块号低 \(c\) 位相同的主存块都会映射到同一个 cache 行。
为了让 cache 记录每行装入了哪个主存块，需要给每行分配一个 \(t\) 位长的「标记」（tag），此处 \(t=m-c\)，某主存块调入 cache 后，将其块号的高 \(t\) 位填入对应 cache 行的标记中。
根据以上做法，主存地址被分为三个字段：高 \(t\) 位的「标记」，中间 \(c\) 位的 cache「行号」（也称「行索引」），剩下的低位地址为「块内地址」，若主存块占 \(2^b\) 字节，则块内地址占 \(b\) 位。
【这里有一张图，图 6.21 b)】
流程如下：
- 根据访存地址中间 \(c\) 位，直接找到对应的 cache 行，比较该 cache 行中的标记和主存地址高 \(t\) 位。
- 若相等且有效位为 1，则访问 cache 命中，进而根据主存地址低 \(b\) 位的块内地址，在该 cache 行中存取信息。
- 若不等或有效位为 0，则缺失，此时，CPU 从主存中读出该地址所在主存块，根据块内地址存取信息后写入该 cache 行，并将有效位置一，且将地址高 \(t\) 位填入该 cache 行中的标记。这一步会造成 cache 行的替换。
访问 cache 行时，读操作比写操作简单。针对写操作，由于 cache 行中的信息是主存某块的副本，因此需要考虑如何使 cache 行中的数据与主存中数据保持一致，这将在之后介绍。
直接映射的优点是易实现，但由于映射方式不够灵活，无法充分利用 cache 空间，故而在某些访存模式下命中率较低。
全相联方式
全相联的基本思想是主存块可以被装入任意 cache 行，因此全相联 cache 需比较所有 cache 行标记才能判断是否命中，同时不需要 cache 行索引，即主存地址中只有标记和块内地址两个字段。
全相联方式下，只要有空闲 cache 行，就不会发生冲突，因而块冲突概率低。
为了判断是否命中，通常为每个 cache 行分别添加一个比较器，其位数等于标记字段的位数。
全相联方式下，cache 访存时根据标记字段的内容来查找相应的 cache 行，是一种「按内容访问方式」，因此，相应的电路是一种「相联存储器」。当比较器数量多时，相联存储器的电路延迟和所用元件开销都较大，因此全相联方式不适合容量较大的 cache.
组相联方式
直接映射方式和全相联方式的优缺点恰好相反，二者结合可取长补短，从而诞生了组相联方式。
组相联的主要思想是，将 cache 所有行分为 \(2^q\) 个大小相等的组，每组有 \(2^s\) 行，每个主存块映射到 cache 固定组中的任意一行，即组相联采用组间模映射，组内全相联的方式。映射关系如下：
cache 组号 = 主存块号 mod cache 组数
上述 \(2^q\) 组 \(\times 2^s\) 行/组的 cache 映射方式称为 \(2^s\) 路组相联。假设主存地址有 \(m\) 位，块内地址占 \(b\) 位，有 \(2^t\) 个组群，那么 \(m = t + q + b\)，也就是主存地址高 \(t\) 位为标记，中间 \(q\) 位为组号（组索引），低 \(b\) 位为块内地址。
\(s\) 的选取决定了块冲突的概率和相联比较的复杂性。\(s\) 越大，则 cache 发生块冲突的概率越低，相联比较电路越复杂。选取适当的 \(s\)，可使组相联的成本比全相联的成本低得多，而性能上仍可接近全相联方式。
早期 cache 容量不大，\(s\) 通常为 \(1\) 或 \(2\)，近年来 \(s=3\) 或 \(s=4\) 即 8 路或 16 路组相联方式很常用。
三种映射方式的比较
对于一个主存块来说，三种映射方式下所能映射到的 cache 行的数量不同，这种特性可用「关联度」度量。
直接映射是唯一映射，即关联度为 1；全相联是任意映射，关联度最高，为 cache 总行数；N 路组相联可映射到 N 行，关联度居中，为 N.
当 cache 大小、主存块大小一定是，关联度和命中率、命中时间、标记所占额外开销显然有如下关系：
- 关联度越低，命中率越低。
- 关联度越低，判断是否命中的电路开销越小。
- 关联度越低，每个 cache 行中的标记所占额外空间越少。
cache 的替换算法
cache 块数比主存块数少很多，多个主存快会映射到同一个 cache 行中。当一个新主存块装入 cache 时，可能 cache 中的对应行全部沾满，此时必须选择淘汰其中一个 cache 行中的主存块，使该行中能存放新主存块。
具体如何淘汰称为「淘汰策略问题」，也称为「替换算法」或「替换策略」。
常用的替换算法有「先进先出」（FIFO, first-in-first-out）算法、「最近最少用」（LRU, least-recently used）算法、「最不经常用」（LFU, least-frequency used）算法。
先进先出算法
FIFO 算法的基本思想是：总是替换最早进入 cache 的主存块。
FIFO 算法容易实现，但不能正确反映程序访问局部性，因为最先进入的主存块也可能是当前经常访问的，从而造成较大的缺失率。
最近最少用算法
LRU 算法的基本思想是：总是替换近期最少使用的主存块。
这种算法能比较正确地反映程序访问局部性，但实现比 FIFO 算法复杂。
显然，对于 LRU 算法，同一组中小关联度的块集合必然是大关联度的块集合之子集，满足这种特性的算法称为「栈算法」。
显然，当程序的「工作集」（即程序中某段时间集中访问的存储区）超过 cache 组的大小时，命中率可能变得很低。比如 cache 每组只有 \(4\) 行，而工作集大小为 \(5\)，当访存地址流为 \(1,2,3,4,5,1,2,3,4,5,\cdots\) 时命中率为零（开头 cache 为空，也是缺失），这种现象称为「颠簸」或「抖动」（thrashing）。
实际情况下，每个 cache 行有一个计数器，用计数值来记录主存块的使用情况，这个计数值称为「LRU 位」，其位数与 cache 组大小有关（\(2^s\) 路组相联时为 \(s\)）
【这里有一张图，图 6.27】
j计数值变化规则如下：
- 命中时，被访问行的计数器清零，比其低的计数器加一，其余不变。
- 缺失且该组还有空行时，将新装入行的计数器设为零，其余全加一。
- 缺失且该组无空行时，替换计数值为 \(2^s-1\) 的行中主存块，将新装入的计数值设为零，其余加一。
不难发现任意时刻没有两个计数器数值相等，进而推导出计数值不会超过 \(2^s-1\)，进而推导出组无空行时，必然存在计数值为 \(2^s-1\) 的行中主存块。
然而计数器硬件实现成本十分高昂，故通常采用「伪 LRU」（PLRU, pseudo-LRU）算法，主要思想如下：
PLRU：仅记录 cache 组内每个主存块的近似使用情况。
具体实现通常有两种方式：「计数器型伪 LRU」和「树型伪 LRU」。计数器型伪 LRU 只需为每个 cache 行维护 1 位计数器，而树型伪 LRU 只需为每个 cache 组维护 \(2^s-1\)（关联度减一）位的状态位。因近似效果良好，总体性能仍接近 LRU 算法，且实现成本较低。
最不经常用算法
LFU 算法的基本思想是：替换 cache 中访问次数最少的块。LFU 算法与 LRU 类似，也用计数器实现，但不完全相同。
随机替换方法
随机替换算法的基本思想是：随即替换组内的一个主存块，而和使用情况无关。
统计数据表明，随即替换方法在性能上只稍逊于基于使用情况的算法，但实现相当简单。
cache 的写策略
因 cache 中的内容时主存块副本，当更新 cache 内容时，就要考虑何时更新主存中相应内容，使两者保持一致，这称为「写策略」（write policy）问题，通常有「通写法」和「回写法」两种。
通写法
「通写法」（write through），也称为「全写法」、「直写法」、「写直达法」。
其基本思想是：若写命中，则同时写 cache 和主存，以保持两者一致；若写缺失，则先写主存，且有以下两种方式：
- 「写分配法」（write allocate）：分配一个 cache 行并装入更新后的主存块。
- 「非写分配法」（not write allocate）：不将主存块装入 cache.
写分配法可以充分利用空间局部性，且能充分保证 cache 和主存内容一致，但每次写缺失都要装入主存块，增加了写缺失的处理开销。非写分配法可以减少写缺失的处理时间，但没有充分利用空间局部性。
为了减少写主存的开销，通常在 cache 和主存之间加一个「写缓冲」（write buffer）。在 CPU 写 cache 的同时，也将内容写入写缓冲，此时 CPU 可继续工作，不必等待内容真正写入主存，而是由写缓冲将其内容写入主存。
写缓冲是一个 FIFO 队列，一般有 4 项，在写操作频率不高的情况下效果较好；若写操作频繁，则会使写缓冲饱和而阻塞，此时 CPU 需要等待。
回写法
「回写法」（write back）也称「一次性写」、「写回法」。
其基本思想是：若写命中，则只将内容写入 cache 而不写入主存；若写缺失，则分配一个 cache 行并装入主存块，然后更新该行的内容。
回写法通常与写分配法组合使用。CPU 执行写操作时，回写法不会更新主存单元，只有在替换 cache 行中的主存块时，才将该块内容一次性写回主存。回写法的好处是减少了写主存的次数，英雌可大大降低主存带宽需求。
此外，若 cache 行的主存块未被写过，替换时则无须将其写回主存，为记录该信息，每个 cache 行关联一个「修改位」，也称「脏位」（dirty bit）。
向 cache 行装入新主存块时，将该位清零；CPU 写入 cache 行时，将该位置一。替换 cache 行时检查其修改位，若为 1，则需要将该主存块写回主存；若为 0，则不需要。
由于回写法未即使将内容协会贮存，此时，若系统中的其他模块（如外设、其他 CPU 等）访问该主存块，将读出果实的内容，进而影响程序正确性。这通常需要其他同步机制来解决该问题。