是什么
-
定义:将高级语言中的多维数组(如 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。请回答:-
数组元素
a[1][2]的虚拟地址是什么?对应的页目录号和页号分别是什么?对应的页目录项的物理地址是什么?若该目录项中存放的页框号为00301H,则a[1][2]所在页对应的页表项的物理地址是什么? -
数组 a 在虚拟地址空间中所占的区域是否必须连续?在物理地址空间中所占的区域是否必须连续?
-
已知数组 a 按行优先方式存放,若对数组 a 分别按行遍历和按列遍历,则哪种遍历方式的局部性更好?
-
-
分析:
-
a[1][2]偏移量 ,虚拟地址加首地址得到1080 1008H。 -
截断低 12 位得到高 20 位
10801H,展开二进制拆分为前 10 位(66)和后 10 位(1)。 -
页目录项物理地址:基址
0020 1000H加上 得到0020 1108H。 -
页表项物理地址:二级页表基址
0030 1000H加上 得到0030 1004H。 -
数组在虚拟空间必须连续,物理空间不必连续。
-
行优先数组按行访问具备极优的空间局部性。
-
-
答案:
-
计算结果如下:
-
a[1][2]的虚拟地址: -
对应的页目录号和页号:
高 20 位十六进制为
10801H,其二进制为 。-
页目录号:高 10 位为 (或 )
-
页号:低 10 位为 (或 )
-
-
页目录项的物理地址:
-
a[1][2]所在页对应的页表项物理地址:二级页表基地址为 。
-
-
数组 a 在虚拟地址空间中必须连续;在物理地址空间中不必连续。
-
按行遍历方式的局部性更好。
因为数组按行优先连续存放,按行遍历时相邻访问的元素在空间上连续(相邻元素均在同一个 Cache 行或同一物理页内),具有良好的空间局部性;按列遍历相邻访问跨越一整行(4KB),每次均跨越不同页面,空间局部性差。
-
⚠️ 易错点
Warning
二维数组偏移量公式漏乘数据类型大小:
算出跨越 1026 个元素后,直接把十进制 1026 当成字节偏移加到地址上。必须乘单个元素大小(本题每个元素占 4B,偏移为 4104B)。
由页框号推二级页表基地址时错算位数:
目录项里给的是页框号
00301H(20位),二级页表物理基地址必须是页框号左移 12 位(低位补 3 个 Hex 0,即0030 1000H),再以此基地址去加页号 * 4B。页目录项偏移十六进制换算错位:
- 。。千万不要口算粗心错写成
168H或264H。 分清“页表项的虚拟地址”与“页表项的物理地址”: