虚拟内存与数组（对齐 or 非对齐）缺页计算

• 时间局部性：某数据被访问后，不久后是否会被再次访问。

• 空间局部性：某数据被访问后，其临近的数据是否很快被访问。

是什么

• 定义：在分页存储管理中，数组在虚拟地址空间中分配时，其首地址在页内的偏移量决定了它是否与物理/虚拟页面边界对齐。当按线性顺序访问未调入内存的数组时，数组跨越的虚拟页数即为发生的缺页异常次数，每次跨入新页面的第一个访问地址即为缺页故障地址。

• 大白话：页就像固定容量的箱子（比如 $4\text{ KB}$ 一个）。数组对齐就是刚好从箱子开头装；不对齐就是从箱子中间装。从中间装会导致前一个箱子装不满，原本 2 个箱子能装下的东西可能被挤到第 3 个箱子里，从而多产生一次缺页。

核心内容

1. 虚拟地址划分

对于页面大小为 $4\text{ KB}=2^{12}\text{ B}$ 的系统：

• 页内偏移量（Offset）：虚拟地址的低 $12\text{ 位}$（十六进制后 3 位）。

• 虚拟页号（VPN）：虚拟地址的高位部分（右移 12 位）。

2. 数组跨越页数计算公式

通用首尾页号法（最稳妥，不易出错）

• 起始虚拟页号：

  $VP{N}_{start}=\lfloor \frac{Add{r}_{start}}{PageSize}\rfloor =Add{r}_{start}\gg 12$

• 末尾字节地址（必须减 1，指向最后一个有效字节）：

  $Add{r}_{end}=Add{r}_{start}+Siz{e}_{total}-1$

• 末尾虚拟页号：

  $VP{N}_{end}=\lfloor \frac{Add{r}_{end}}{PageSize}\rfloor =Add{r}_{end}\gg 12$

• 跨越总页数 $N$：

  $N=VP{N}_{end}-VP{N}_{start}+1$

向上取整公式法

设页面大小为 $P$，起始页内偏移量为 $Offse{t}_{start}=Add{r}_{start}\mathrm{mod}P$：

• 页对齐（$Offse{t}_{start}=0$）：

  $N=\lceil \frac{Siz{e}_{total}}{P}\rceil$

• 非页对齐（$Offse{t}_{start}\ne 0$）：

  $N=\lceil \frac{Offse{t}_{start}+Siz{e}_{total}}{P}\rceil$

3. 缺页次数与故障地址判定规则

前提条件：数组初始均不在主存、访问过程不发生页面置换，且按内存地址顺序线性递增访问。

• 总缺页次数：==$\text{缺页次数}=N$==

• 第 1 次缺页故障地址：发生在访问数组首个元素时，==地址为起始虚拟地址 $Add{r}_{start}$==（带起始偏移）。

• 第 $k$ 次缺页故障地址 ($2\le k\le N$)：发生在跨入新页面的第一个访问地址处。由于是线性连续扫描，该地址必然是新页面的页首对齐地址（低 12 位全为 0）：

  $FaultAdd{r}_k=(VP{N}_{start}+k-1)\times 4\text{ KB}=(VP{N}_{start}+k-1)\ll 12$

例题

• 题目：

  已知某分页虚拟存储管理系统中，页面大小为 $4\text{ KB}$。一个二维整型数组 A[24][64] 每个元素占 $4\text{ B}$，数组按行优先顺序存储。程序执行前该数组完全不在内存中，访问过程不发生页面置换。

  （1）若数组起始虚拟地址为 0042 2000H，计算线性遍历该数组发生的缺页次数及各次缺页的虚拟地址。

  （2）若数组起始虚拟地址为 0042 2A00H，计算线性遍历该数组发生的缺页次数及各次缺页的虚拟地址。

• 分析：

  数组总字节大小为 $Siz{e}_{total}=24\times 64\times 4\text{ B}=6144\text{ B}=6\text{ KB}=1800\text{H}$。

  页面大小为 $4\text{ KB}=1000\text{H}$。

  通过计算起始虚拟页号与末尾字节所在的虚拟页号，即可确定跨越页数及各次缺页触发的地址。

• 答案：

  （1）起始地址为 0042 2000H 时（页对齐）：

  末尾字节地址为：

  $Add{r}_{end}=\text{0042 2000H}+\text{1800H}-1=\text{0042 37FFH}$

  起始页号 $VP{N}_{start}=\text{00422H}$，末尾页号 $VP{N}_{end}=\text{00423H}$。

  跨越页数 $N=\text{00423H}-\text{00422H}+1=2$。

  因此，发生缺页次数为 2 次。

• 第 1 次缺页故障地址：0042 2000H

• 第 2 次缺页故障地址：0042 3000H

（2）起始地址为 0042 2A00H 时（非页对齐）：

末尾字节地址为：

$Add{r}_{end}=\text{0042 2A00H}+\text{1800H}-1=\text{0042 41FFH}$

起始页号 $VP{N}_{start}=\text{00422H}$，末尾页号 $VP{N}_{end}=\text{00424H}$。

跨越页数 $N=\text{00424H}-\text{00422H}+1=3$。

因此，发生缺页次数为 3 次。

• 第 1 次缺页故障地址：0042 2A00H

• 第 2 次缺页故障地址：0042 3000H

• 第 3 次缺页故障地址：0042 4000H

⚠️ 易错点

Warning

• 末尾地址未减 1 导致误判多跨一页（差一错误） $\to$ 计算末尾字节地址时，公式必须是 $Add{r}_{end}=Add{r}_{start}+Size-1$。如果数组恰好占满某一页（如末尾在 ...3FFFH），不减 1 会算成 ...4000H，导致虚拟页号多进位 1，从而错误地多算一次缺页。

• 后续缺页故障地址误带初始页内偏移 $\to$ 第 1 次缺页地址是带偏移的 $Add{r}_{start}$，但==第 2 次及以后的缺页地址必然落在新页的首字节（低 12 位为 000H）==，切勿把起始偏移量加到后续页面上。

• 十六进制容量换算进位错误 $\to$ $4\text{ KB}=1000\text{H}$，$6\text{ KB}=4\text{ KB}+2\text{ KB}=1000\text{H}+800\text{H}=1800\text{H}$。切忌把十进制的 $6\text{ KB}$ 直接当作 $6000\text{H}$ 或 $1600\text{H}$ 参与十六进制地址运算。