存储系统概述

概念

存储系统（memory system）不是"一块内存"，而是用多种速度、容量、价格都不同的存储器拼出来的一个整体，让使用者感觉它是一个"又大又快又便宜"的存储器。

这个整体靠两条腿站立：

1. 层次结构（memory hierarchy）——上面快而小，下面慢而大。
2. 局部性原理（principle of locality）——程序访问的地址不是均匀分布的，而是"扎堆"的。

没有局部性，层次结构就毫无意义：每次访问都要到最底层去取，上面的快存储器就是摆设。

一句话抓住核心：层次结构提供"可能快"，局部性把它变成"真的快"。

原理

一、三个不可兼得的指标

指标	含义	矛盾
速度	存取时间	越快的器件越贵
容量	能存多少	容量越大越慢
价格	每位成本	越快越贵

三种存储器（如 SRAM、DRAM、磁盘）无法同时满足三者，于是分层堆叠：用少量昂贵的快速存储器挡住大部分访问，让海量廉价存储器只承接少量访问。

二、层次结构全貌

   CPU
    │
    ▼
┌──────────┐  寄存器        速度最快、容量最小（几百字节）、在 CPU 内
├──────────┤
│  L1 Cache│  数十 KB，与 CPU 同频
│  L2 Cache│  数百 KB
│  L3 Cache│  数 MB ~ 数十 MB
├──────────┤
│  主存     │  DRAM，数 GB，可与 CPU 直接交换数据
├──────────┤
│  辅存     │  磁盘 / SSD，数百 GB ~ TB，需经 I/O 接口
├──────────┤
│  三级存储 │  磁带、光盘、网络存储，容量近乎无限
└──────────┘
      速度 ↓        容量 ↑        位价 ↓

层	典型容量	典型速度	谁管理
寄存器	数百 B	< 1 ns	编译器 / 程序员
Cache	KB ~ 数十 MB	1 ~ 10 ns	硬件自动，对程序员透明
主存	GB 级	数十 ns	硬件 + 操作系统
辅存	TB 级	毫秒 ~ 微秒	操作系统 + 用户程序

三、局部性原理

类型	含义	典型来源
时间局部性（temporal locality）	刚被访问过的信息，不久后还会被访问	循环体、循环变量、反复调用的函数
空间局部性（spatial locality）	刚被访问过的信息的邻近地址很快会被访问	数组顺序遍历、指令顺序执行

int sum = 0;
for (int i = 0; i < n; i++)      /* i 反复被访问 → 时间局部性 */
    sum += a[i];                 /* a[i] 与 a[i+1] 相邻 → 空间局部性 */

数组按行访问与按列访问的差异，是局部性原理最经典的考题——同样的数据、同样的访问次数，只因顺序不同，性能可以差几十倍。

四、两层"缓存"的分工必须分清

层次结构里有两处"快的挡慢的"，但它们目的不同、机制不同，这是选择题的高频陷阱：

对比项	Cache — 主存 层	主存 — 辅存 层
要解决的问题	速度匹配	容量不足
实现者	纯硬件	硬件 + 操作系统
对应用程序员	透明（不用管）	不透明（要管换页、缺页）
数据传送单位	块 / 行（几十字节）	页 / 段（几 KB）
未命中处理	硬件自动调块，CPU 暂停若干周期	触发缺页异常，换页后重执行指令
地址空间	同一物理地址空间	虚地址 → 实地址的映射
典型命中率	90% ~ 99%	99.9% 以上

记忆钩子：Cache 是硬件管家，页表是软件管家。 "对程序员透明"这五个字只属于 Cache 层。

五、性能指标：命中率与平均访问时间

设访问次数为 $N$，其中命中 $N_c$ 次、未命中 $N_m$ 次，则

$$H=\frac{N_c}{N_c+N_m},M=1-H$$

平均访问时间有两种口径，看清题目是"同时访问"还是"逐级访问"：

口径 A（同时访问）——Cache 与主存同时启动，命中就用 Cache 的结果，未命中就用主存的结果（主存直接供数）：

$$T_a=H{T}_c+(1-H)T_m$$

口径 B（逐级访问）——先查 Cache，未命中再访问主存，时间叠加：

$$T_a=T_c+(1-H)T_m$$

访问效率（efficiency）：

$$e=\frac{T_c}{T_a}\times 100\mathrm{\%}$$

多级 Cache 逐级展开（先 L1、未命中查 L2、再未命中查主存）：

$$T_a=H_1{T}_1+(1-H_1)H_2{T}_2+(1-H_1)(1-H_2)T_3$$

六、存取时间与存取周期（别混为一谈）

术语	含义
存取时间（access time, $T_a$）	从发出读写命令到数据可用/写入完成的时间
存取周期（memory cycle time, $T_m$）	两次独立访问之间必须间隔的最小时间，$T_m>T_a$

为什么 $T_m>T_a$：DRAM 是破坏性读出——读出后存储元电荷被破坏，必须重写恢复，再等读出放大器复位。所以 DRAM 的存取周期明显大于存取时间。SRAM 用触发器保存数据，读出非破坏性，$T_m\approx T_a$。

主存带宽（bandwidth）：

$$\text{带宽}=\frac{\text{一次传送的数据位数}}{\text{存取周期}}$$

注意分母是存取周期而不是存取时间——用错就高估一倍。

示例

例 1：两级 Cache 的平均访问时间与效率

某系统 Cache 存取时间 $T_c=1\text{ns}$，主存存取时间 $T_m=100\text{ns}$，命中率 $H=95\mathrm{\%}$。分别按两种口径求平均访问时间与访问效率。

完整计算过程：

第一步，明确已知：$H=0.95$，未命中率 $M=1-H=0.05$，$T_c=1$ ns，$T_m=100$ ns。

第二步，口径 A（同时访问）：

$$T_a=H{T}_c+(1-H)T_m=0.95\times 1+0.05\times 100=0.95+5=5.95\text{ns}$$

第三步，口径 B（逐级访问）：

$$T_a=T_c+(1-H)T_m=1+0.05\times 100=1+5=6.00\text{ns}$$

第四步，算访问效率（以口径 A 为例）：

$$e=\frac{T_c}{T_a}\times 100\mathrm{\%}=\frac{1}{5.95}\times 100\mathrm{\%}\approx 16.81\mathrm{\%}$$

结论：平均访问时间约 $5.95$ ns（口径 A）/ $6.00$ ns（口径 B），访问效率约 $16.81\mathrm{\%}$。

第五步，做个直观对照：不用 Cache 时访问时间是 $100$ ns，用 Cache 后降到 $5.95$ ns，加速比

$$S=\frac{100}{5.95}\approx 16.8$$

即整个存储系统的速度提升了近 17 倍，靠的只是 5% 的未命中率差距。

例 2：三级存储的平均访问时间

L1 存取时间 $1$ ns，命中率 $90\mathrm{\%}$；L2 存取时间 $10$ ns，对 L1 未命中的请求命中率 $90\mathrm{\%}$；主存 $100$ ns。求平均访问时间。

完整计算过程：

第一步，明确各层"条件命中率"的含义：$H_2$ 是在 L1 未命中的前提下，L2 的命中率。

第二步，列三级公式：

$$T_a=H_1{T}_1+(1-H_1)H_2{T}_2+(1-H_1)(1-H_2)T_3$$

第三步，逐项代入：

项	含义	计算	值
第 1 项	L1 命中	$0.9\times 1$	$0.90$ ns
第 2 项	L1 未命中、L2 命中	$0.1\times 0.9\times 10$	$0.90$ ns
第 3 项	两级都未命中、访主存	$0.1\times 0.1\times 100$	$1.00$ ns

第四步，求和：

$$T_a=0.90+0.90+1.00=2.80\text{ns}$$

结论：平均访问时间 $2.80$ ns。

注意最后一项的比重：三级都未命中的概率只有 $1\mathrm{\%}$，但它贡献了 $1.00$ ns——占总额的 $35.7\mathrm{\%}$。这就是"尾部延迟"的由来：概率极低的事件，因为代价极高，反而主导平均值。

例 3：反推命中率要求

上题参数不变（$T_c=1$ ns，$T_m=100$ ns），要求平均访问时间不超过 $2$ ns，命中率至少要多少？

完整计算过程：

第一步，按口径 A 列不等式：

$$H\times 1+(1-H)\times 100\le 2$$

第二步，展开整理：

$$H+100-100H\le 2$$$$100-99H\le 2$$$$99H\ge 98$$

第三步，解出：

$$H\ge \frac{98}{99}\approx 0.9899$$

结论：命中率必须达到 $98.99\mathrm{\%}$ 以上。

直觉解读：命中率从 $95\mathrm{\%}$ 提到 $98.99\mathrm{\%}$，看起来只是多挡了 4 个百分点，但平均访问时间从 $5.95$ ns 掉到 $2$ ns——因为未命中率从 $5\mathrm{\%}$ 降到了约 $1\mathrm{\%}$。平均值被未命中这条尾巴拖着走，这就是为什么 Cache 设计宁可加容量、加层级，也要把命中率往 99% 推。

例 4：主存带宽——为什么会用错分母

SRAM 存取时间 $5$ ns、存取周期 $5$ ns；DRAM 存取时间 $50$ ns、存取周期 $100$ ns。数据总线宽度均为 $32$ 位。分别求带宽。

完整计算过程：

第一步，算一次传送的数据量：$32$ 位 $=4$ B。

第二步，算 SRAM 带宽（$T_m=5$ ns）：

$${\text{带宽}}_{\text{SRAM}}=\frac{4\text{B}}{5\text{ns}}=\frac{4}{5\times {10}^{-9}}\text{B/s}=800\text{MB/s}$$

第三步，算 DRAM 带宽（$T_m=100$ ns）：

$${\text{带宽}}_{\text{DRAM}}=\frac{4\text{B}}{100\text{ns}}=40\text{MB/s}$$

第四步，如果错用存取时间做分母（$50$ ns），会得到：

$$\frac{4\text{B}}{50\text{ns}}=80\text{MB/s}$$

——比真值高一倍。DRAM 那 50 ns 的恢复时间是躲不掉的。

结论：SRAM 带宽 $800$ MB/s，DRAM 带宽 $40$ MB/s，相差 20 倍。这正是"必须用 Cache 挡住 CPU"的数量级依据：CPU 每秒能发上亿次访问，主存根本顶不住。

例 5：局部性的威力——同一个数组，两种遍历顺序

数组 int a[1024][1024]（按行存储，共 4 MB），Cache 容量 32 KB，块大小 64 B，采用直接映射。分别按行优先和列优先遍历，求命中率。

完整计算过程：

第一步，算基本参数：

• 数组总大小 $=1024\times 1024\times 4\text{B}=4\text{MB}$
• 一个块能装 $64÷4=16$ 个 int
• 一行 $1024$ 个 int $=4096$ B $=64$ 个块
• Cache 共 $32\text{KB}÷64\text{B}=512$ 行（每行一个块）

第二步，按行优先遍历（for i { for j { a[i][j] } }）：

访问顺序是完全连续的地址。每调入一个块，紧接着的 16 次访问全部命中，也就是每 16 次访问只缺失 1 次：

$$H_{\text{行}}=1-\frac{1}{16}=93.75\mathrm{\%}$$

更直接地算一遍：

$$\text{缺失次数}=\frac{\text{数组总字节}}{\text{块大小}}=\frac{4194304}{64}=65536$$$$\text{总访问次数}=1024\times 1024=1048576$$$$H_{\text{行}}=1-\frac{65536}{1048576}=1-\frac{1}{16}=93.75\mathrm{\%}$$

第三步，按列优先遍历（for j { for i { a[i][j] } }）：

此时相邻两次访问的地址间隔是一行的长度：

$$\text{步长}=1024\times 4\text{B}=4096\text{B}=64\text{个块}$$

而这个步长造成两个后果：

1. 块内没有复用：调入一个块取到 a[i][j] 后，块里剩下 15 个元素属于别的列，本次循环根本不用。一次调入只用 1 个元素。
2. Cache 装不下：列遍历需要同时在 Cache 里保留 1024 行（每行一个块），但 Cache 只有 512 行，容量直接不够；即使够，步长为 64 个块时，第 $i$ 行与第 $i+8$ 行的块会映射到同一 Cache 行（$8\times 64=512\equiv 0(\mathrm{mod}512)$），互相淘汰。

结果：每一次访问都缺失，命中率 $H_{\text{列}}\approx 0\mathrm{\%}$。

第四步，对照：

遍历方式	缺失次数	命中率
按行	65536	93.75%
按列	1048576	≈ 0%

结论：同样的数据、同样的访问次数，只因遍历顺序不同，命中率从 93.75% 掉到 0%。 这不是 Cache 设计的问题，是程序没有利用空间局部性。工程上的对策很简单：把循环交换过来，或者分块（blocking）处理。

例 6：C 代码——实测两种遍历顺序

本机不提供代码运行能力，runnable 标记仅为将来接入运行件预留；请自行在本地编译验证。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define N 1024

static int a[N][N];

/* 按行遍历：地址连续，空间局部性最好 */
static long sum_row(void) {
    long s = 0;
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            s += a[i][j];
    return s;
}

/* 按列遍历：地址步长 = 一整行，空间局部性极差 */
static long sum_col(void) {
    long s = 0;
    for (int j = 0; j < N; j++)
        for (int i = 0; i < N; i++)
            s += a[i][j];
    return s;
}

int main(void) {
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            a[i][j] = 1;

    clock_t t0 = clock();
    long s1 = sum_row();
    clock_t t1 = clock();
    long s2 = sum_col();
    clock_t t2 = clock();

    printf("按行: sum=%ld  用时 %.3f s\n", s1, (double)(t1 - t0) / CLOCKS_PER_SEC);
    printf("按列: sum=%ld  用时 %.3f s\n", s2, (double)(t2 - t1) / CLOCKS_PER_SEC);
    printf("两次结果相同(校验局部性不影响正确性): %s\n", s1 == s2 ? "是" : "否");
    printf("提示: 实际比值取决于 Cache 参数, 典型为 3~20 倍\n");
    return 0;
}

c 本站为静态站，不提供在线运行；可复制到本地用 gcc / python 执行

说明：两个函数的求和结果一定相同（都遍历全部元素），差别只在访存模式。按列版本通常会慢几倍到几十倍，具体倍数取决于本机 Cache 容量、块大小与替换算法——这正是"局部性不改变算法复杂度，只改变常数因子"的直观体现。

例 7：Python 对照——用模型算出命中率

# 用直接映射 Cache 模型计算两种遍历顺序的缺失次数（对应例 5）
N, SZ, BLK, CS = 1024, 4, 64, 32 * 1024
LINES = CS // BLK                      # 512 行
addr = lambda r, c: (r * N + c) * SZ   # 行优先存储

def simulate(order):
    tag = [None] * LINES
    miss = 0
    for r, c in order:
        block = addr(r, c) // BLK
        line, tg = block % LINES, block // LINES
        if tag[line] != tg:
            tag[line] = tg
            miss += 1
    return miss

rows = [(r, c) for r in range(N) for c in range(N)]
cols = [(r, c) for r in range(N) for r in range(N)]

for name, order in (('按行', rows), ('按列', cols)):
    m = simulate(order)
    print('%s: 缺失 %d / 总访问 %d -> 命中率 %.2f%%'
          % (name, m, len(order), (1 - m / len(order)) * 100))

python 本站为静态站，不提供在线运行；可复制到本地用 gcc / python 执行

输出对照：

按行: 缺失 65536 / 总访问 1048576 -> 命中率 93.75%
按列: 缺失 1048576 / 总访问 1048576 -> 命中率 0.00%

与例 5 的手算完全一致（$65536/1048576=1/16$）。

考点

考点

1. 必背公式

• 命中率 $H=N_c/(N_c+N_m)$，未命中率 $M=1-H$
• 口径 A（同时访问）：$T_a=H{T}_c+(1-H)T_m$
• 口径 B（逐级访问）：$T_a=T_c+(1-H)T_m$
• 访问效率 $e=T_c/T_a$
• 三级：$T_a=H_1{T}_1+(1-H_1)H_2{T}_2+(1-H_1)(1-H_2)T_3$
• 主存带宽 = 数据位数 / 存取周期

2. 高频陷阱

• 两种口径别混。题目说"Cache 与主存同时访问"用口径 A；说"未命中时再访问主存"用口径 B。同一组参数，两口径答案不等（例 1：$5.95$ vs $6.00$）。
• 多级 Cache 的 $H_2$ 是条件命中率（在 L1 未命中的前提下），不是全局命中率。把它当全局命中率算会得到荒谬结果。
• 带宽的分母是存取周期，不是存取时间。DRAM 有恢复时间，用错分母高估一倍。
• "对程序员透明"只属于 Cache—主存层。主存—辅存层（虚拟存储器）对程序员不透明——缺页、页面置换是能感知的。
• 不要混淆两类"未命中代价"：Cache 缺失由硬件自动处理，CPU 停顿几个周期；缺页由操作系统处理，代价是毫秒级。
• 局部性不改变算法的时间复杂度，只改变常数因子。按行和按列求和都是 $O(n^2)$，但实测耗时可能差 10 倍以上。
• 存储层次的"上"是靠近 CPU，别把方向搞反。越往上越快、越小、越贵。
• 寄存器不属于主存，也不属于 Cache。题目问"CPU 能直接访问的存储器"要看清选项：Cache 和主存都能被 CPU 直接访问（通过总线），但寄存器在 CPU 内部。

3. 归属判断题速查

说法	正误
Cache 由硬件管理，对程序员透明	✓
虚拟存储器对应用程序员透明	✗（不透明）
硬盘属于主机的一部分	✗（I/O 设备）
主存—辅存层解决的是速度问题	✗（解决容量）
Cache—主存层解决的是容量问题	✗（解决速度）
局部性原理是层次结构有效的前提	✓

4. 与后续章节的接口

• 例 4 的"主存顶不住 CPU"直接引出第 11 篇的多模块交叉存储与第 12 篇的 Cache 映射。
• 主存—辅存层展开成第 13 篇的虚拟存储器（页表、TLB、地址变换）。
• 与操作系统交叉命题：本篇的"主存—辅存层"就是 OS 里内存管理的硬件基础。

小结

• 存储层次结构要同时解决容量、速度、价格三者的矛盾；它的有效性建立在局部性原理之上。
• 时间局部性靠"刚用过的还会用"，空间局部性靠"附近的会被用"。
• 两处"快的挡慢的"分工不同：Cache—主存解决速度、硬件管理、对程序员透明；主存—辅存解决容量、软硬结合、不透明。
• 平均访问时间有两个口径，先看题目说"同时"还是"逐级"；访问效率 $e=T_c/T_a$。
• 存取周期 ≥ 存取时间（DRAM 破坏性读出需恢复），带宽的分母必须是存取周期。
• 局部性的威力可以用例 5 记住：同一数组，按行 93.75%、按列 0%。

下一篇：主存储器