题目

某 32 位系统采用基于二级页表的请求分页存储管理方式，按字节编址，页目录项和页表项长度均为 4 字节，虚拟地址结构如下：

某 C 程序中数组 a[1024][1024] 的起始虚拟地址为 1080 0000H，数组元素占 4 字节。该程序运行时，其进程的页目录起始物理地址为 0020 1000H。请回答下列问题：

(1) 数组元素 a[1][2] 的：

• 虚拟地址是什么？
• 对应的页目录号和页号分别是什么？
• 对应的页目录项的物理地址是什么？
• 若该目录项中存放的页框号为 00301H，则 a[1][2] 所在页对应的页表项的物理地址是什么？

(2) 数组 a 在虚拟地址空间中所占区域是否必须连续？在物理地址空间中所占区域是否必须连续？

(3) 已知数组 a 按行优先方式存放，若对数组 a 分别按行遍历和按列遍历，哪一种遍历方式的局部性更好？

解析

准备工作：算页大小 + 一行的字节数

• 页大小 = B = 4 KB = 4096 B
• 每个数组元素 4 B
• 一行 1024 个元素 × 4 B = 4096 B = 1 页

关键观察：数组的每一行恰好占 1 页！ 这是本题最关键的几何关系。

（1）求 a[1][2] 的各种地址

Step 1：求虚拟地址

数组按行优先存放，a 的起始地址（即 a[0][0]）= 0x10800000。

a[1][2] = 起始地址 + 第 1 行偏移 + 第 2 个元素偏移：

Step 2：求页目录号 + 页号

把 0x10801008 转成二进制并按 (10, 10, 12) 切：

字段	二进制	十六进制
页目录号（高 10）	0000010000
页号（中 10）	1000000001 错	...

让我精确按位拆：

比特位置	内容
[31:22] 页目录号	0001000010 = 0x042
[21:12] 页号	0000000001 = 0x001
[11:0] 页内偏移	000000001000 = 0x008

→ 页目录号 = 0x042（66），页号 = 0x001（1）。

Step 3：求页目录项的物理地址

页目录起始物理地址 = 0x00201000，每项 4 B：

Step 4：求 a[1][2] 所在页的页表项物理地址

页目录项给出的页框号 = 0x00301 → 该二级页表起始物理地址：

a[1][2] 所在页的页号是 0x001，所以页表项位于：

答案汇总

量	值
a[1][2] 虚拟地址	10801008H
页目录号	042H
页号	001H
页目录项物理地址	00201108H
页表项物理地址	00301004H

（2）虚拟空间 / 物理空间是否必须连续？

空间	是否必须连续	理由
虚拟地址空间	✅ 必须	C 数组按下标随机存取——a[i][j] = base + (i * 1024 + j) * 4 这条公式要求连续
物理地址空间	❌ 不必	数组占 1024 页，相邻虚页不必映射到相邻物理页框——分页机制就是来解决"虚连续 / 物离散"的

编者注（核心概念）：分页机制的最大价值就是"打破物理连续性约束"——程序员看到的连续虚地址在物理上可能散落各处，但通过页表"翻译"后，访问体验仍是连续的。这是为什么大数组、大 buffer 在分页系统下没有"分配不出连续物理空间"的烦恼。

（3）行遍历 vs 列遍历，谁的局部性更好？

关键事实

由 (1) 知：数组的每一行正好占 1 页。

行遍历

for (int i = 0; i < 1024; i++)
  for (int j = 0; j < 1024; j++)
    访问 a[i][j];

固定 i、j 从 0 跑到 1023 → 访问的所有元素都在同一页（第 i 行的 1024 个元素都在第 i 页里）→ 一页内访问完才换下一页。

行遍历	缺页次数
每行 1024 个元素只触发 1 次缺页（首次访问那一页时）	1024 行 → 1024 次缺页

列遍历

for (int j = 0; j < 1024; j++)
  for (int i = 0; i < 1024; i++)
    访问 a[i][j];

固定 j、i 从 0 跑到 1023 → 每访问一个元素跨一页（a[0][j] 在第 0 页、a[1][j] 在第 1 页、...）→ 一列遍历完后再下一列。

如果工作集（驻留集）小于 1024 页，第 1024 次访问后第 0 页很可能已被换出，下一列又重新缺页：

列遍历	缺页次数
最坏情况下每个元素都缺页 → 总共可达 1024 × 1024 ≈ 100 万次缺页

结论

按行遍历局部性更好——缺页率比按列遍历低约 1000 倍。

编者注（核心规律 + 工程意义）：

1. 存储顺序与遍历顺序匹配 = 局部性最优：

   • C / Java：行优先 → 行遍历快
   • Fortran / MATLAB：列优先 → 列遍历快 搞反就掉性能。

2. 本题的极端性：每行 = 1 页恰好，所以行 / 列遍历的缺页率差异可达千倍。在真实代码里也会反映到 cache miss、内存带宽利用率上。

3. 优化技巧（超出 408 范围但加分）：处理大矩阵时常用 blocking / tiling 技术——把大数组切成小块，让一块全部在 cache 里再处理，列优先访问也能优化。这是数值计算的核心技巧。

4. 本题考的"局部性"包括两类：

   • 空间局部性：访问相邻地址的元素（行遍历好）
   • 时间局部性：短时间内重复访问同一地址（本题不涉及）

   本题主要考"空间局部性"，列遍历每访问一个元素就跨一页，几乎没有空间局部性可言。