题目

已知计算机 M 字长为 32 位，按字节编址，采用请求调页策略的虚拟存储管理方式，虚拟地址为 32 位，页面大小为 4KB；数据 Cache 采用 4 路组相联映射，数据区大小为 8KB，主存块大小为 32B。现有 C 语言程序段如下：

for (i = 0; i < 24; i++)
    for (j = 0; j < 64; j++) a[i][j] = 10;

已知二维数组 a 按行优先存放，在虚拟地址空间中分配的起始地址为 0042 2000H，sizeof(int)=4，假定在 M 上执行上述程序段之前数组 a 不在主存，且在该程序段执行过程中不会发生页面置换。请回答下列问题。

(1) 数组 a 分为几个页面存储？对于数组 a 的访问，会发生几次缺页异常？页故障地址各是什么？

(2) 不考虑变量 i 和 j，该程序段的数据访问是否具有时间局部性？为什么？

(3) 计算机 M 的虚拟地址（A31~A0）中哪几位用作块内地址？哪几位用作 Cache 组号？a[1][0] 的虚拟地址是多少？其所在主存块对应的 Cache 组号是多少？

(4) 数组 a 占用多少主存块？假设上述程序段执行过程中数组 a 的访问不会和其他数据发生 Cache 访问冲突，则数组 a 的 Cache 命中率是多少？若将循环中 i 和 j 的次序按如下方式调换：

for (j = 0; j < 64; j++)
    for (i = 0; i < 24; i++) a[i][j] = 10;

则数组 a 的 Cache 命中率又是多少？

解析

本题在二维数组遍历的基础上同时考查 页式管理（缺页判定）+ 4 路组相联 Cache（命中率分析）+ 局部性原理。

注意："局部性"和"命中率"虽然相关但不是一回事。本题中循环交换后命中率不变，是因为 4 路组相联给了"额外宽容度"——即使空间局部性被破坏，每个 Cache 组放得下"3 行的工作集"，于是没有替换发生。

(1) 数组 a 占的页数与缺页次数 [3 分]

Step 1. 数组占多少字节。

数组从 00422000H 开始，恰好页对齐（2000H 是 4KB 倍数）→ 横跨 2 个页：

• 第 1 页：00422000H ~ 00422FFFH（4KB）；
• 第 2 页：00423000H ~ 00423FFFH（剩余 2KB 在此页前半）。

Step 2. 缺页次数与故障地址。

数组初始不在主存。访问 a[i][j] 是按行优先（i 慢、j 快），第一次跨页发生在 00423000H：

缺页次序	触发访问	故障地址
1	第一次访问 a[0][0]	00422000H
2	第一次跨入第 2 页	00423000H

总缺页次数 = 2。

易错点： 故障地址是"触发缺页的虚拟地址"，不一定是页起始地址（如果数组首地址不页对齐就不是）。本题恰好对齐才使两个故障地址都恰是页起始。

(2) 时间局部性判定 [2 分]

没有时间局部性。

理由： 时间局部性 = "刚访问的数据近期还会再访问"。本程序段每个 a[i][j] 只被访问 1 次（写入 10 后就不再读 / 写）→ 任何元素都没有"再访问"→ 没有时间局部性。

但有 空间局部性——按行优先访问相邻元素，命中率分析全依赖这一点。

(3) Cache 字段拆分 + a[1][0] 地址与 Cache 组号 [3 分]

Step 1. 算 Cache 字段位数。

• 块大小 32B → 块内偏移 = 位 → 占虚拟地址 [A₄:A₀]；
• Cache 组数 = → 组号 = 位 → 占 [A₁₀:A₅]。

字段	位数	地址位
块内偏移	5	A₄ ~ A₀
Cache 组号	6	A₁₀ ~ A₅
Tag	21	A₃₁ ~ A₁₁

Step 2. 算 a[1][0] 的虚拟地址。

数组按行优先存放，每行 64 个 int，每个 int 4 字节：

Step 3. 算 a[1][0] 的 Cache 组号。

二进制 00422100H 的低 11 位：

按 [A₁₀:A₅ 组号 | A₄:A₀ 偏移] 切：

• 组号（A₁₀:A₅）= 001000B = 8；
• 块内偏移（A₄:A₀）= 00000B = 0。

(4) 数组 a 占用的主存块数 + 两种循环顺序的命中率 [5 分]

主存块数：

每块容纳 个 int。

(4.1) 原循环（i 外、j 内）的命中率。

行优先访问 + 行优先存放 → 每访问 a[i][0] 触发 miss 装载整块（含 a[i][0..7]），随后 a[i][1..7] 全 hit。每 8 次访问 1 miss + 7 hit：

(4.2) 交换后（j 外、i 内）的命中率分析。

交换后访问顺序：a[0][0], a[1][0], ..., a[23][0], a[0][1], a[1][1], ...

• 内层 i 改变 → 每次访问的是不同行，但仍然是不同主存块（因为每行 256B = 8 块，相邻行差 8 个块）；
• a[0][0]、a[1][0]、...、a[23][0] 各属于不同的主存块，但 块映射到的 Cache 组只有 8 种（块号 = i × 8，组号 = (i × 8) mod 64 = (i mod 8) × 8）。

因此，固定 j 的内层循环 24 次访问 → 24 个不同主存块 → 8 种 Cache 组（每组 3 个块）。

关键：每组只有 3 块，4 路组相联可装下 → 不会发生替换。

跟踪一次完整 (j → i) 扫描：

• j = 0: 访问 a[0..23][0]，24 个 miss（首装），但分布到 8 组 × 3 块，cache 占满 24 个 cache line（每组 3/4 用）；
• j = 1: 访问 a[0..23][1]，全在同一批主存块内（块未变），全 hit；
• ...
• j = 7: 全 hit。
• j = 8: a[0..23][8] 进入下一批 24 块（不同组号偏移），miss；j=9..15 hit；
• 依此类推，每 8 个 j 触发 24 次 miss。

每块共 8 次访问（每次 j 落在该块覆盖的 8 个 j 之一）：1 miss + 7 hit。

易错点（关键洞察）： 交换后空间局部性按"列"看似乎被破坏，但 4 路组相联给的容量足够装下"工作集" → 实际命中率不下降。如果换成 1 路（直接映射）或减小 Cache 容量，结果会完全不同——这是本题最有意思的地方。

编者注（生僻术语）： "工作集（working set）"指程序在某一时间窗口内访问的数据集合。命中率本质上取决于"工作集 vs Cache 容量 / 关联度"的对比。本题工作集 = 24 块的某一批，恰好≤ 64 组 × 4 路 = 容量上限。