分布页数量与缺页异常次数判定

是什么

• 定义：虚存跨页计算指确定一段连续数据（如数组）在虚拟地址空间中所覆盖的不同虚拟页面的集合；缺页异常次数是指访问该数据过程中，由于目标页面未调入主存而触发操作系统缺页中断处理的累计次数。

• 大白话：算跨几页就是看数据从头到尾占用的地址区间切穿了几个 4KB（或其它页大小）的格子；算缺页几次就是看程序在顺序跑的过程中，踩进了几个原本不在内存里的全新格子里。

核心内容

1. 数组地址区间的标准求解

设数组首地址为 $A_{\text{start}}$，数组元素个数为 $N$，单个元素大小为 $S=\text{sizeof}(T)$：

• 数据总字节数：

  $\text{TotalBytes}=N\times S$

• 起始字节地址：

  ${\text{Addr}}_{\text{first}}=A_{\text{start}}$

• 末尾字节地址（必须减 1 字节）：

  ${\text{Addr}}_{\text{last}}=A_{\text{start}}+\text{TotalBytes}-1$

2. 判定跨越页数的通用步骤

设页面大小为 $P$（如 $4\text{ KB}=2^{12}\text{ B}=1000\text{H}$），页内偏移占 $k$ 位（4KB 对应 $k=12$ 位）：

1. 求起始页号：

   ${\text{Page}}_{\text{start}}=\lfloor {\text{Addr}}_{\text{first}}/P\rfloor \text{（十六进制下直接截掉低 }k/4\text{ 位）}$

2. 求末尾页号：

   ${\text{Page}}_{\text{last}}=\lfloor {\text{Addr}}_{\text{last}}/P\rfloor \text{（十六进制下直接截掉低 }k/4\text{ 位）}$

3. 计算跨越的总页数：

   $\text{跨越页数}={\text{Page}}_{\text{last}}-{\text{Page}}_{\text{start}}+1$

3. 缺页次数判定法则

• 前提条件：

  • 若题目明确声明“执行前数据不在主存中，且执行期间不发生页面置换”；

  • 数组为顺序/线性访问遍历。

• 计算规则：

  • 程序首次进入每一个新页面时，必然发生 1 次冷缺页（Compulsory Page Fault）；

  • 只要页面进入主存后不再被置换出，后续对同页面内其余元素的访问全部命中，不再缺页；

  • 核心结论：==缺页异常次数 = 顺序访问所覆盖的不同页面总数==。

例题

• 题目（2025 统考 408 真题节选）：

  页面大小为 4KB，数组定义为 int d[2048];（sizeof(int) = 4）。数组 $d$ 的起始虚拟地址为 0180 0020H。若执行循环遍历前数组 $d$ 未调入主存，且遍历过程中不发生页面置换，求：

  1. 数组 $d$ 分布在几个页中？

  2. 访问数组 $d$ 所引起的缺页次数是多少？

• 分析：

  • 页面大小：$4\text{ KB}=2^{12}\text{ B}=1000\text{H}$，即虚拟地址的低 12 位（后 3 位十六进制）为页内偏移，高 20 位（前 5 位十六进制）为虚页号。

  • 数组总大小：$2048\times 4\text{ B}=8192\text{ B}=2000\text{H}$（恰好等于 2 个整页的大小）。

  • 起始字节地址：0180 0020H

  • 末尾字节地址：

    $\text{0180 0020H}+2000\text{H}-1\text{H}=\text{0180 201FH}$

  • 起始虚页号：取 0180 0020H 的高 20 位 $\to$ 01800H

  • 末尾虚页号：取 0180 201FH 的高 20 位 $\to$ 01802H

• 答案：

  1. 分布页数：

     数组占用的虚页号依次为 01800H、01801H、01802H。

     $\text{跨越页数}=\text{01802H}-\text{01800H}+1=3\text{ 个页}$

  2. 缺页次数：

     由于初始不在主存且不发生置换，线性遍历首次访问 d[0]（页 01800H）、跨入页 01801H 的首个元素、以及跨入页 01802H 的首个元素时各发生 1 次缺页异常。

     $\text{缺页次数}=3\text{ 次}$

⚠️ 易错点

Warning

• 只拿总字节数除以页大小 $\to$ 误认为 $8\text{ KB}/4\text{ KB}=2\text{ 页}$。这是最常见的致命陷阱！只有当首地址严格在页边界对齐（如 ...000H）时才成立；若首地址有偏移（如 ...020H），尾部必然会溢出切入第 3 个页。

• 末尾地址未减 1 字节 $\to$ 若误算末尾地址为 $\text{首地址}+\text{长度}$，当数组恰好填满某页边界时，会把下一页的第一个字节算进来，导致多算 1 页。

• 混淆代码缺页与数据缺页 $\to$ 注意题目是否注明“代码已在内存/Cache 中”。若代码不在内存中，取指令本身也会引起缺页；若题目仅问“访问数组引起”，则只需统计数据页。 这里面的“减 1”和“加 1”其实分别对应着日常计算中非常经典的“末尾字节边界”和“植树/闭区间计数”问题。

1. 算末尾地址时，为什么要「减 1」？（闭区间边界问题）

• 本质原理：从第 $1$ 个字节开始数，总共有 $L$ 个字节，那么最后一个字节的偏移量是 $L-1$。

• 生活中的直观例子：

  • 如果你要从第 100 页 开始读 1 页 书，你读的是哪一页？是第 100 页（即 $100+1-1=100$），而不是 $100+1=101$。

  • 如果读 3 页 书，你读的是 100、101、102 这三页，最后一页是 $100+3-1=102$。

• 不减 1 的致命后果：

  • 假设页大小是 4KB（1000H），数组首地址是 0000H，数组长度恰好是 4KB（1000H 字节）。

  • 正确的最后一个字节地址是：0000H + 1000H - 1 = 0FFFH（依然在第 0 页）。

  • 如果你不减 1：0000H + 1000H = 1000H。这个 1000H 已经是第 1 页的第 0 个字节了！你会误以为数据跨到了第 1 页，从而错误地多算了一页。

$\text{末尾字节真实地址}=\text{首地址}+\text{总字节数}-1$

2. 算跨越总页数时，为什么要「加 1」？（两端都包含的闭区间计数）

• 本质原理：两端都包含的连续整数个数公式为：$\text{个数}=\text{终点}-\text{起点}+1$。

• 生活中的直观例子：

  • 如果数据占用了 第 3 页、第 4 页、第 5 页，一共占了几页？

  • 显然是 3 页。但如果直接做减法：$5-3=2$ 页，就会少算起始的那一页。

  • 正确算法是：$5-3+1=3$ 页。

• 在 408 题目中的应用：

  • 起始页号：01800H

  • 末尾页号：01802H

  • 实际包含的页面有：01800H、01801H、01802H 这 3 个。

$\text{跨越页数}=\text{末尾页号}-\text{起始页号}+1$

一句话速记口诀

• 算末尾地址「减 1」：防溢出，保证抓到的是数据占用的最后一个字节，不把下一个无辜的字节算进来。

• 算页面总数「加 1」：闭区间计数，保证头尾两页都算在内。