是什么

  • 定义:将高级语言中的多维数组(如 C 语言行优先数组)映射到基于二级页表的虚拟内存与物理内存中,综合考查虚拟地址合成、二级页表两级物理寻址(PDE/PTE)以及矩阵遍历顺序对 Cache/TLB 局部性与命中率的影响。

  • 大白话:数组在虚拟世界里是一整条排得整整齐齐的糖葫芦;但在物理内存里被切成一小段一小段(页),随处乱塞。要想找到某个元素,得先根据下标算出它在整条糖葫芦的哪个虚拟位置,再通过两级目录顺藤摸瓜找到它住的物理格子。

==这道题同时给出了页表的起始虚拟地址和起始物理地址。算虚拟地址用虚拟基址加偏移,算物理地址用物理基址加偏移,千万别串位。==

核心内容

1. 第(1)小问深度剖析:四步无死角推导流水线

题目核心参数提取:

  • 数组定义:a[1024][1024],元素大小 ,行优先存放。

  • 数组首虚拟地址:1080 0000H。

  • 虚拟地址格式:页目录号(10位) + 页号(10位) + 页内偏移量(12位)。

  • 页目录起始物理地址:0020 1000H。

  • 页目录项(PDE)与页表项(PTE)大小均为 。

步骤一:求元素 a[1][2] 的虚拟地址

  • 数组线性下标偏移量公式(行优先存储,行号从 0 计):

    • :当前元素行号()。

    • :矩阵每行总元素个数()。

    • :当前元素列号()。

    • 代入:。

  • 字节偏移量计算:

  • 快速转十六进制技巧:

  • 目标虚拟地址合成:

步骤二:剥离出页目录号(10位)和页号(10位)

虚拟地址十六进制为 1080 1008H(共 32 位):

  • 低 12 位(低 3 个 Hex 字符):直接判定为页内偏移量 。

  • 剩余高 20 位(前 5 个 Hex 字符:10801H):由“页目录号 10 位 + 页号 10 位”组成。

  • 二进制切片速拆法:

    Plaintext

    高 20 位 Hex:       1          0          8          0          1
    转二进制(20位):  0 0 0 1 | 0 0 0 0 | 1 0 0 0 | 0 0 0 0 | 0 0 0 1
    -------------------------------------------------------------
    前 10 位(页目录号): 0 0 0 1 0 0 0 0 1 0  --> 42H (十进制 66)
    后 10 位(页号):                      0 0 0 0 0 0 0 0 0 1  --> 1H  (十进制 1)
    
  • 结论:页目录号 = 66(42H),页号 = 1。

步骤三:求对应的页目录项(PDE)物理地址

  • 核心定位公式:

    • 页目录起始基地址:0020 1000H。

    • 页目录号:。

    • PDE 大小:。

  • 偏移字节与 Hex 转换:

  • 计算结果:

步骤四:求所在页对应的页表项(PTE)物理地址

  • 二级页表基地址推导:

    • 题目给出该目录项中存放的页框号为 00301H。

    • 该页框中存放的是进程的某一张具体的二级页表。

    • 物理页面大小为 ,末尾补 3 个十六进制 0:

  • PTE 物理地址计算公式:

    • 页号为 ,PTE 大小为 :

2. 第(3)小问进阶剖析:按行/按列访问与 Cache 命中率终极陷阱

第 3 小问只问了“哪种局部性更好”,但 408 极高频的变式追问是:“按列访问时的 Cache / 页面命中率是多少?” 很多同学在此处会掉入“零命中率”的直觉陷阱。

(1) 遍历与空间跨度关系

  • 数组一行包含 。

  • 一行刚好填满一个完整的物理页面(4KB)!

  • 按行遍历 a[i][j]:

    • 先访问 a[0][0], a[0][1], a[0][2]...,地址连续递增。

    • 属于极致的空间局部性。若 Cache 行大小为 64B(可容纳 16 个元素),则每 16 次访问仅第 1 次缺失,后 15 次命中,Cache 命中率高达 ;整个 4KB 页面只需调页 1 次。

  • 按列遍历 a[i][j](外层 j 内层 i):

    • 访问顺序为:a[0][0] a[1][0] a[2][0] …

    • 相邻两次访问的地址跨度为整整一行:4096 字节(4KB)。

(2) ⚠️ 核心考点陷阱:按列访问的命中率到底是不是 0%?

当题目给出具体硬件参数(如 Cache 容量、页框数)时,必须区分两种极端情况:

  • 陷阱情况 A:容量不足引发颠簸(命中率确实为 0%)

    • 条件:若分配给进程的页框数(或 Cache 组数/容量)小于 1024。

    • 现象:访问 a[0][0] 装入第 0 页;访问 a[1][0] 装入第 1 页……访问到后面时,由于容量已满,把前面的页面全部淘汰了。等下一列访问 a[0][1] 时,第 0 页又不在了!

    • 结果:缺页率 100%,命中率 0%。

  • 陷阱情况 B:容量充足或全相联(后几列开始全部命中!)

    • 条件:若分配给进程的物理页框数大于等于 1024(能容下整个数组),或者在针对第二列访问提问。

    • 现象:虽然第 1 列(a[0][0] 到 a[1023][0])访问了 1024 个不同的页面发生 1024 次缺页,但这 1024 个页面此时全部留在了内存/大容量 Cache 中!

    • 当循环进入第 2 列访问 a[0][1] 到 a[1023][1] 时,这些元素所处的页面全都在内存中!

    • 结果:只有第一列发生缺失,后续 1023 列全部命中,整体命中率依然极高!

审题铁律:

凡是问按列访问的命中率,先看题目给的 Cache/页框容量能不能装下一整个矩阵(或者至少装下多少行),切忌脱离硬件容量直接下结论说“按列访问必定全部脱靶”。

例题

  • 题目:

    【2020 统考真题】某 32 位系统采用基于二级页表的请求分页存储管理方式,按字节编址,页目录项和页表项长度均为 4B,虚拟地址结构为:页目录号(10位) + 页号(10位) + 页内偏移量(12位)。

    某 C 程序中数组 a[1024][1024] 的起始虚拟地址为 1080 0000H,数组元素占 4B,该程序运行时,其进程的页目录起始物理地址为 0020 1000H。请回答:

    1. 数组元素 a[1][2] 的虚拟地址是什么?对应的页目录号和页号分别是什么?对应的页目录项的物理地址是什么?若该目录项中存放的页框号为 00301H,则 a[1][2] 所在页对应的页表项的物理地址是什么?

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

    3. 已知数组 a 按行优先方式存放,若对数组 a 分别按行遍历和按列遍历,则哪种遍历方式的局部性更好?

  • 分析:

    • a[1][2] 偏移量 ,虚拟地址加首地址得到 1080 1008H。

    • 截断低 12 位得到高 20 位 10801H,展开二进制拆分为前 10 位(66)和后 10 位(1)。

    • 页目录项物理地址:基址 0020 1000H 加上 得到 0020 1108H。

    • 页表项物理地址:二级页表基址 0030 1000H 加上 得到 0030 1004H。

    • 数组在虚拟空间必须连续,物理空间不必连续。

    • 行优先数组按行访问具备极优的空间局部性。

  • 答案:

    1. 计算结果如下:

      • a[1][2] 的虚拟地址:

      • 对应的页目录号和页号:

        高 20 位十六进制为 10801H,其二进制为 。

        • 页目录号:高 10 位为 (或 )

        • 页号:低 10 位为 (或 )

      • 页目录项的物理地址:

      • a[1][2] 所在页对应的页表项物理地址:

        二级页表基地址为 。

    2. 数组 a 在虚拟地址空间中必须连续;在物理地址空间中不必连续。

    3. 按行遍历方式的局部性更好。

      因为数组按行优先连续存放,按行遍历时相邻访问的元素在空间上连续(相邻元素均在同一个 Cache 行或同一物理页内),具有良好的空间局部性;按列遍历相邻访问跨越一整行(4KB),每次均跨越不同页面,空间局部性差。

⚠️ 易错点

Warning

  • 二维数组偏移量公式漏乘数据类型大小:

    • 算出跨越 1026 个元素后,直接把十进制 1026 当成字节偏移加到地址上。必须乘单个元素大小(本题每个元素占 4B,偏移为 4104B)。

  • 由页框号推二级页表基地址时错算位数:

    • 目录项里给的是页框号 00301H(20位),二级页表物理基地址必须是页框号左移 12 位(低位补 3 个 Hex 0,即 0030 1000H),再以此基地址去加 页号 * 4B。

  • 页目录项偏移十六进制换算错位:

    • 。。千万不要口算粗心错写成 168H 或 264H。 分清“页表项的虚拟地址”与“页表项的物理地址”: