分页存储管理

概念

分页存储管理指把进程的逻辑地址空间切成等长的"页"，把物理内存切成同样大小的"页框"，页可以装进任意空闲页框里，不必连续。

一句话说清它是什么：分页就是"把程序拆成等长的页，随便塞进内存的空位里，再用一张表记下'第几页放在哪个页框'"——它用"一张映射表"换掉了上一章那个"必须连续"的硬约束（回顾 os/20-contiguous.md：外部碎片就是连续分配的代价）。

⚠️ 三个术语必须先分清：

术语	属于哪一侧	含义
页（page）/ 页面	逻辑（虚拟）侧	进程地址空间被切成的等长块
页框（page frame）/ 物理块 / 存储块	物理侧	内存被切成的同样大小的块
页表项（PTE）	页表的一项	记录**"某虚页 → 哪个页框"**及若干标志位

⚠️ 页是"虚"的、页框是"实"的，两者大小必须相等（否则搬不进去）。页大小由硬件/系统定，是 2 的整数次幂（4096 B、8192 B 等）——这是"页内偏移位数 = log₂(页大小)"成立的前提。

原理

一、逻辑地址的两段划分

分页下，一个逻辑地址被硬件自动切成两段：

  ← 页号 P (高位) → ← 页内偏移 W (低位) →
  ┌───────────────┬──────────────────────┐
  │      页号       │       页内偏移         │
  └───────────────┴──────────────────────┘
  位数 = 虚址位数 - log₂(页大小)      位数 = log₂(页大小)

  若虚址 32 位、页 4KB(2^12):  页号 20 位 | 偏移 12 位

物理地址 = 页框号 × 页大小 + 页内偏移，或者按位写：

  ┌───────────────┬──────────────────────┐
  │     页框号      │       页内偏移         │   ← 偏移原样复制
  └───────────────┴──────────────────────┘

★ 铁律：页内偏移在地址变换中"一个比特都不变"——因为整页搬动，页内相对位置永远不动（arch/13-virtual.md 也强调过这条）。所以地址变换的本质只有一件事：把"页号"翻译成"页框号"。

二、页表与页表项

页表（page table）是一个数组：下标 = 页号，内容 = 页表项。

        页表 (由页表基址寄存器 PTBR 指向)
  ┌──────┬──────────────────────────────────────────┐
  │ 页号  │  页表项                                    │
  ├──────┼──────────────────────────────────────────┤
  │  0   │  页框号 | 有效位V | 修改位D | 访问位A | 保护位 │
  │  1   │  ...                                     │
  │  ⋮   │  ...                                     │
  └──────┴──────────────────────────────────────────┘

字段	作用
页框号（PPN）	变换的结果：该页在内存里的位置
有效位 / 状态位 V	该页是否在内存（= 0 → 缺页，见 os/23-virtual.md）
修改位 / 脏位 D	是否被写过（写过 → 换出时必须写回磁盘）
访问位 A	是否被访问过（给置换算法用，如 CLOCK）
保护位	读 / 写 / 执行权限

⚠️ 页表本身也放在内存里——所以"查页表"这件事本身就要访问一次内存（除非有快表缓存）。这就是下面"访存次数"那条口径的根源。

三、基本地址变换机构

没有快表时，一次访存要访问两次内存：

   ①CPU 给出逻辑地址 → 硬件拆成 (页号 P, 偏移 W)
             │
             ▼
   ②检查 P 是否越界 ── 越界 ──▶ 产生"越界中断"
             │ 不越界
             ▼
   ③用 P 查页表 (★ 第 1 次访存, 位置 = 页表基址 + P × 页表项大小)
             │
             ▼
   ④取出页框号 → 拼成物理地址 = 页框号 × 页大小 + W
             │
             ▼
   ⑤按物理地址取数据 (★ 第 2 次访存)

⚠️ 检查什么、用什么检查（易漏）：

• 页号越界检查：页号 ≥ 页表长度 → 越界中断（这是"内存保护"的实现方式之一）。
• 注意区分"页表长度"与"页大小"：页表长度 = 页表有多少项（能表示多少页）；页大小 = 每页多少字节——两个数完全不同，别写错。

四、具有快表（TLB）的地址变换机构

快表（TLB，translation lookaside buffer，也叫"联想存储器""相联存储器"）是一个容量极小、极快、通常全相联的硬件表，缓存最近用过的页表项。

  逻辑地址 → (页号 P, 偏移 W)
                │
       ┌────────┴────────┐
       ▼                 ▼
   查快表 TLB          TLB 未命中
       │命中              │
       │                  ▼
       │            查内存中的页表 (1 次访存)
       │                  │
       │                  ▼
       │            把这一项填入 TLB (替换掉一项)
       ▼                  │
       └────────┬─────────┘
                ▼
        拿到页框号 → 物理地址 → 取数据 (1 次访存)

有效访问时间 EAT（必考公式）：设查快表需 $t_{TLB}$、访存一次需 $t_{mem}$、快表命中率为 $a$：

$$EAT=a(t_{TLB}+t_{mem})+(1-a)(t_{TLB}+t_{mem}+t_{mem})$$

⚠️ 三点口径：

1. 命中时：查快表 + 取数据 = 2 个动作（查快表通常不计入"访存"，但公式里要加上它的时间）。
2. 未命中时：查快表 + 查页表 + 取数据 = 3 个动作（多出的一次访存就是"查页表"）。
3. 若题目说"查快表时间可忽略"，则 $t_{TLB}=0$，答案必须按题目给的参数算——这是最容易失分的一处。

⚠️ 与 arch/13-virtual.md 的口径区别：那一章把"两级页表"计入未命中代价（多 2 次访存），得到 EAT = 101 + (1-a)×200 + c×1e6；本章按操作系统教材口径只计"一次页表访存"。两处参数不同，不是矛盾——看清题目给的是单级还是两级页表、快表时间算不算。

五、两级页表与多级页表

为什么需要多级：以 32 位虚址、4KB 页、页表项 4B 为例——

$$\text{虚页号}=32-12=20\text{位}\Rightarrow \text{页表项数}=2^{20}=1048576\Rightarrow \text{页表大小}=1048576\times 4\text{B}=\boxed{{\displaystyle 4\text{MB}}}$$

每个进程都要一张 4MB 的页表，而且必须连续存放——这不可接受。于是把页表本身也分页：

    32 位逻辑地址（两级页表：10 + 10 + 12）
  ┌───────────┬───────────┬──────────────┐
  │ 一级页号   │  二级页号  │   页内偏移     │
  │  10 位     │  10 位    │   12 位       │
  └─────┬─────┴─────┬─────┴──────────────┘
        │           │
        ▼           ▼
   一级页表      二级页表          最终页框
   (页目录)    (共 1024 张,
    1024 项      按需分配)

• 一级页表（页目录）：1024 项 × 4B = 4KB = 恰好 1 页，必须常驻。
• 二级页表：每张 1024 项 = 4KB，1024 张，只为"用到的"段分配。
• 好处：不必为整个 4GB 空间准备 4MB+4KB 的连续页表，只需常驻 4KB——用"多一层间接"换"按需分配"。
• 代价：访存次数从 2 次变成 3 次（查一级 → 查二级 → 取数据），TLB 未命中的代价更高。

⚠️ 两级页表并没有减少"页表项总数"（上限仍是 4MB + 4KB），它减少的是"必须常驻的那部分"——这句话是概念题的采分点。

示例

例 1：地址变换手算

页大小 4KB，某进程页表的前几项为：页号 0→页框 5、1→1、2→3、3→（不在内存）、4→7、5→0、6→2、7→6。求逻辑地址 12345、16384、30000 的物理地址。

第一步：确定划分位数

$$\text{页内偏移}={\log }_{2}4096=12\text{位}\Rightarrow \text{一页}=4096\text{字节}$$

第二步：逐个拆分与拼接

逻辑地址	页号 = 地址 ÷ 4096	偏移 = 地址 mod 4096	页框号	物理地址 = 页框号 × 4096 + 偏移
12345	$\lfloor 12345/4096\rfloor =3$	$12345-3\times 4096=12345-12288=\mathbf{57}$	缺页	不存在（触发缺页中断）
16384	$16384/4096=4$	$16384-16384=\mathbf{0}$	7	$7\times 4096+0=\mathbf{28672}$
30000	$\lfloor 30000/4096\rfloor =7$	$30000-7\times 4096=30000-28672=\mathbf{1328}$	6	$6\times 4096+1328=24576+1328=\mathbf{25904}$

⚠️ 手算的三个着力点：

1. 除 4096 就是右移 12 位，取余就是取低 12 位——心算时先找 4096 的倍数（$4096\times 3=12288$、$4096\times 4=16384$、$4096\times 7=28672$）。
2. 12345 落在第 3 页（$12288\le 12345<16384$），而第 3 页不在内存 → 缺页——地址变换本身没法"算"下去，必须先进缺页处理。
3. 物理地址与逻辑地址数值上毫无关系——别指望"接近"或"成比例"。

例 2：页表容量与两级页表

32 位逻辑地址、页大小 4KB、页表项 4 字节。求单级页表的容量；再改为两级页表（10+10），求划分与各级容量。

第一步：单级页表

页内偏移位数 = log₂(4096) = 12 位
虚页号位数   = 32 - 12 = 20 位
页表项数     = 2^20 = 1048576 项
单级页表大小 = 1048576 × 4 B = 4194304 B = 4096 KB = 4 MB

$$\boxed{{\displaystyle \text{单级页表}=4\text{MB}}}$$

第二步：两级页表（10 + 10 + 12）

项目	计算	结果
一级页号	10 位	$2^{10}=1024$ 项
二级页号	10 位	每张二级表 $2^{10}=1024$ 项
一级页表大小	$1024\times 4$ B	4096 B = 4KB（必须常驻）
二级页表单张大小	$1024\times 4$ B	4096 B = 4KB（按需分配）
常驻最小	只留一级	4KB
最坏情况	一级 + 全部二级	$4096+1024\times 4096=4198400$ B ≈ 4 MB

对照上一章的连续分配：单级页表要 4MB 连续内存，两级页表只要常驻 4KB——这正是"多级页表"存在的唯一理由。

例 3：C 实现——地址变换（含缺页判定）

#include <stdio.h>

#define PAGE_SIZE  4096        /* 页大小 4KB */
#define PT_ENTRIES 8           /* 演示用的页表长度(只放 8 项) */

/* 页表: 下标 = 页号, 内容 = 页框号; -1 表示该页不在内存(缺页) */
static int page_table[PT_ENTRIES] = {5, 1, 3, -1, 7, 0, 2, 6};

/* 逻辑地址 -> 物理地址; 返回 -1 = 缺页, -2 = 页号越界 */
static long translate(unsigned long vaddr) {
    unsigned long pageno = vaddr / PAGE_SIZE;
    unsigned long offset = vaddr % PAGE_SIZE;
    long frame;

    if (pageno >= PT_ENTRIES) return -2;        /* ① 页号越界检查 */
    frame = page_table[pageno];                 /* ② 查页表 */
    if (frame < 0) return -1;                   /* ③ 有效位为 0 -> 缺页 */
    return frame * PAGE_SIZE + offset;          /* ④ 拼物理地址 */
}

int main(void) {
    unsigned long addr[4] = {0, 12345, 16384, 30000};
    int i;

    printf("页大小 = %d B, 页表项 = %d 个\n", PAGE_SIZE, PT_ENTRIES);
    for (i = 0; i < PT_ENTRIES; i++)
        printf("  页号 %d -> 页框号 %d\n", i, page_table[i]);

    printf("\n逻辑地址 -> 页号/偏移 -> 物理地址\n");
    for (i = 0; i < 4; i++) {
        long pa = translate(addr[i]);
        printf("  %5lu -> 页号 %lu 偏移 %lu -> ",
               addr[i], addr[i] / PAGE_SIZE, addr[i] % PAGE_SIZE);
        if (pa == -1)      printf("缺页 (该页不在内存)\n");
        else if (pa == -2) printf("页号越界\n");
        else               printf("物理地址 %ld\n", pa);
    }
    return 0;
}

c 本站为静态站，不提供在线运行；可复制到本地用 gcc / python 执行

预期输出：

页大小 = 4096 B, 页表项 = 8 个
  页号 0 -> 页框号 5
  页号 1 -> 页框号 1
  页号 2 -> 页框号 3
  页号 3 -> 页框号 -1
  页号 4 -> 页框号 7
  页号 5 -> 页框号 0
  页号 6 -> 页框号 2
  页号 7 -> 页框号 6

逻辑地址 -> 页号/偏移 -> 物理地址
      0 -> 页号 0 偏移 0 -> 物理地址 20480
  12345 -> 页号 3 偏移 57 -> 缺页 (该页不在内存)
  16384 -> 页号 4 偏移 0 -> 物理地址 28672
  30000 -> 页号 7 偏移 1328 -> 物理地址 25904

⚠️ 三点说明：

1. -1 与 -2 两种返回值对应"缺页"与"越界"——这正是地址变换机构要处理的两类异常；现实中缺页交给操作系统（os/23-virtual.md），越界直接报错终止。
2. vaddr / PAGE_SIZE 与 vaddr % PAGE_SIZE 就是"取高位"与"取低 12 位"——编译器对 2 的幂会优化成移位/掩码，但语义上就是除法与取余。
3. 本机无 C 编译器：此段代码逐行人工审查，并用等价的 Python 实现（下例同一组地址）实跑核对过输出——两边结果完全一致。

例 4：Python——页表容量、地址变换与快表 EAT

import math

PAGE = 4096

print('=== ① 单级页表容量 ===')
for va_bits, page, pte in [(32, 4096, 4), (32, 4096, 8), (46, 8192, 8)]:
    off = int(math.log2(page))
    vpn = va_bits - off
    n = 2 ** vpn
    tot = n * pte
    print('虚址 %d 位 / 页 %d B / 页表项 %d B:' % (va_bits, page, pte))
    print('  偏移 %d 位, 虚页号 %d 位 -> 页表项 %d 个, 单级页表 %d B = %.2f MB'
          % (off, vpn, n, tot, tot / 1024 / 1024))

print()
print('=== ② 两级页表(32 位 / 4KB 页 / 页表项 4 B) ===')
off = 12
hi = lo = (32 - off) // 2
print('  划分: 一级 %d 位 + 二级 %d 位 + 偏移 %d 位' % (hi, lo, off))
print('  一级页表(页目录): %d 项 x 4 B = %d B  <- 必须常驻'
      % (2 ** hi, 2 ** hi * 4))
print('  二级页表: 一张 %d 项 x 4 B = %d B  <- 按需分配' % (2 ** lo, 2 ** lo * 4))
print('  常驻最小 = %d B; 最坏 = 一级 + 全部二级 = %d B = %.2f MB'
      % (2 ** hi * 4, 2 ** hi * 4 + 2 ** hi * 2 ** lo * 4,
         (2 ** hi * 4 + 2 ** hi * 2 ** lo * 4) / 1024 / 1024))

print()
print('=== ③ 地址变换 ===')
pt = {0: 5, 1: 1, 2: 3, 3: None, 4: 7, 5: 0, 6: 2, 7: 6}
for va in [0, 12345, 16384, 30000]:
    p, w = divmod(va, PAGE)
    fr = pt.get(p)
    if fr is None:
        print('  逻辑 %5d -> 页号 %d 偏移 %4d -> 缺页' % (va, p, w))
    else:
        print('  逻辑 %5d -> 页号 %d 偏移 %4d -> 物理 %d' % (va, p, w, fr * PAGE + w))

print()
print('=== ④ 快表(TLB) 有效访问时间 ===')
MEM, TLB = 100.0, 10.0
print('  无快表(每次都查内存中的页表): EAT = 2 x %.0f = %.1f ns' % (MEM, 2 * MEM))
for a in [0.90, 0.98, 1.0]:
    eat = a * (TLB + MEM) + (1 - a) * (TLB + MEM + MEM)
    tag = '  <- 全命中' if a == 1.0 else ''
    print('  命中率 %3.0f%%: EAT = %6.2f ns, 相对无快表加速 %.3f 倍%s'
          % (a * 100, eat, 2 * MEM / eat, tag))
print('  说明: 命中时 = 查快表 + 取数据; 未命中时 = 查快表 + 查页表 + 取数据')

python 本站为静态站，不提供在线运行；可复制到本地用 gcc / python 执行

输出对照（真实运行结果）：

=== ① 单级页表容量 ===
虚址 32 位 / 页 4096 B / 页表项 4 B:
  偏移 12 位, 虚页号 20 位 -> 页表项 1048576 个, 单级页表 4194304 B = 4.00 MB
虚址 32 位 / 页 4096 B / 页表项 8 B:
  偏移 12 位, 虚页号 20 位 -> 页表项 1048576 个, 单级页表 8388608 B = 8.00 MB
虚址 46 位 / 页 8192 B / 页表项 8 B:
  偏移 13 位, 虚页号 33 位 -> 页表项 8589934592 个, 单级页表 68719476736 B = 65536.00 MB

=== ② 两级页表(32 位 / 4KB 页 / 页表项 4 B) ===
  划分: 一级 10 位 + 二级 10 位 + 偏移 12 位
  一级页表(页目录): 1024 项 x 4 B = 4096 B  <- 必须常驻
  二级页表: 一张 1024 项 x 4 B = 4096 B  <- 按需分配
  常驻最小 = 4096 B; 最坏 = 一级 + 全部二级 = 4198400 B = 4.00 MB

=== ③ 地址变换 ===
  逻辑     0 -> 页号 0 偏移    0 -> 物理 20480
  逻辑 12345 -> 页号 3 偏移   57 -> 缺页
  逻辑 16384 -> 页号 4 偏移    0 -> 物理 28672
  逻辑 30000 -> 页号 7 偏移 1328 -> 物理 25904

=== ④ 快表(TLB) 有效访问时间 ===
  无快表(每次都查内存中的页表): EAT = 2 x 100 = 200.0 ns
  命中率  90%: EAT = 120.00 ns, 相对无快表加速 1.667 倍
  命中率  98%: EAT = 112.00 ns, 相对无快表加速 1.786 倍
  命中率 100%: EAT = 110.00 ns, 相对无快表加速 1.818 倍  <- 全命中
  说明: 命中时 = 查快表 + 取数据; 未命中时 = 查快表 + 查页表 + 取数据

四条结论：

1. 同一份地址数据，C 与 Python 两边结果完全一致（20480 / 缺页 / 28672 / 25904）——地址变换的算法就是"除、查、乘、加"四步，没有别的分支。
2. 单级页表 4MB 在 32 位系统上还能忍，到 46 位就是 64GB（$8589934592\times 8$ B = 68719476736 B）——这就是 64 位系统必须用 4 级甚至 5 级页表的原因。
3. 两级页表把"必须常驻"从 4MB 压到 4KB（是 4MB 的 1/1024）——代价是访存从 2 次涨到 3 次。
4. 快表是"用硬件缓存换访存次数"：命中率 90% 时 EAT 从 200ns 降到 120ns（快 1.667 倍）；98% 时到 112ns——注意"全命中"也要 110ns（查快表 10ns + 取数据 100ns），快表不是免费的。

考点

考点

1. 必背结论

• 地址划分：页号位数 = 虚址位数 − log₂(页大小)；页内偏移位数 = log₂(页大小)。
• 页内偏移在变换中不变（唯一不变的量）；变换的本质是页号 → 页框号。
• 物理地址 = 页框号 × 页大小 + 页内偏移。
• 页表项四类信息：页框号 + 有效位 V + 修改位 D + 访问位 A（+ 保护位）。
• 页表项数 = 2^(虚页号位数)；页表大小 = 页表项数 × 页表项大小（与页大小无关！）
• 访存次数三档：无快表 2 次（查页表 + 取数据）；快表命中 1 次（取数据）；两级页表且快表未命中 3 次。
• EAT = a·(t_TLB + t_mem) + (1−a)·(t_TLB + 2·t_mem)；例 4 锚点：90% → 120ns、98% → 112ns、全命中 110ns、无快表 200ns。
• 两级页表 32 位/4KB/4B：10 + 10 + 12 划分；一级 1024 项 = 4KB（常驻）；二级每张 4KB（按需）；常驻最小 4KB。
• 页表长度（多少项）≠ 页大小（多少字节）——两个完全不同的量。
• 分页 vs 连续分配：分页只可能产生"页内碎片"（最后一页装不满），不会产生外部碎片。

2. 高频陷阱

• 把"页表大小"算成"页大小 × 页表项数"：错。是用"页表项数 × 页表项大小"，页表项通常是 4B 或 8B，不是 4096B。
• 忘了"页内偏移不变"：错。只有页号被翻译，偏移原样拼接——这是全章唯一一条铁律。
• EAT 公式里把"未命中时多出的一次访存"漏掉：错。未命中 = 查快表 + 查页表 + 取数据，比命中多一次访存。
• 把"查快表的时间"当成 0 而不看题目：错。题目给了就要算；说"可忽略"才取 0。
• 说"两级页表减少了页表项总数"：错。总上限没变（4MB+4KB），减少的是"必须常驻的部分"。
• 把"页表寄存器（PTBR）"与"页表长度寄存器（PTLR）"混用：错。前者存页表起始地址，后者存页表长度（用于越界检查）。
• 以为"页大小越大越好"：错。页大 → 页内碎片大、缺页时多读无用数据；页小 → 页表项数暴增、页表占内存多——是权衡，不是单调越好。
• 说"分页有外部碎片"：错。分页的进程页可以任意离散存放，外部碎片为 0（只有"最后一页装不满"的页内碎片）。
• 把"页框号位数"算成"物理地址位数"：错。页框号位数 = 物理地址位数 − log₂(页大小)（例：物理地址 30 位、页 4KB → 页框号 18 位、共 262144 个页框）。
• 混淆"页号位数"与"页表长度"：页表长度是"项的个数"，而按位数理解时它是 $2^{\text{页号位数}}$——题目问"页表有多少项"答 $2^{20}$，问"位"答 20。

3. 解题模板（"分页地址变换题"）

① 先算两个位数: 页内偏移位数 = log2(页大小); 页号位数 = 虚址位数 - 偏移位数
② 逻辑地址 -> 页号 = 地址 // 页大小 ; 偏移 = 地址 % 页大小  (2 的幂就用移位/掩码)
③ 查页表(或快表): 拿页框号; 若有效位 0 -> 答"缺页"
④ 物理地址 = 页框号 * 页大小 + 偏移
⑤ 若问访存次数/EAT: 先判"单级还是两级页表、快表命中率、快表时间算不算",
   再套 EAT = a(t_TLB+t_mem) + (1-a)(t_TLB+2 t_mem)
⑥ 若问页表容量: 项数 = 2^页号位数; 大小 = 项数 * 页表项大小

4. 与相邻章节的接口

• os/20-contiguous.md（连续分配）：分页的动机就是消灭那章的外部碎片；代价是引入页内碎片与页表开销。
• os/22-segment.md（分段）：分页是"物理等分"，分段是"逻辑不等分"——段内仍要求连续，所以分段又带回了外部碎片。
• os/23-virtual.md（虚拟内存）：本章的有效位 = 0 只是"报缺页"，真正"怎么处理缺页、怎么置换"在那一章；本章的页表项到那里要再加"外存地址"字段。
• arch/13-virtual.md（虚拟存储器）：同一套机制的硬件侧——那里的 EAT 含两级页表与缺页，本章只看页表与快表，参数口径不同，别互相套公式。
• os/10-process.md（进程与线程）："线程切换比进程切换快 5 倍"差的就是"换页表 + 刷 TLB"——因为每个进程有自己的页表与 TLB。
• arch/12-cache.md 与 arch/13-virtual.md 的 TLB/Cache 分工：TLB 缓存"地址映射"，Cache 缓存"数据"——两者都命中才是最快路径。

小结

• 分页 = 逻辑空间等分成"页"、物理空间等分成"页框"，页可放入任意空闲页框——用页表换掉"必须连续"。
• 地址结构：页号 | 页内偏移；偏移位数 = log₂(页大小)，变换中偏移不变。
• 页表项 = 页框号 + 有效位 + 修改位 + 访问位（+ 保护位）；页表本身在内存 → 查表也是一次访存。
• 访存次数：无快表 2 次 / 快表命中 1 次 / 两级页表且快表未命中 3 次。
• EAT 锚点（快表 10ns、访存 100ns）：0% → 200ns、90% → 120ns、98% → 112ns、100% → 110ns。
• 例 1 锚点：页 4KB 时 12345 → 页 3 偏移 57 → 缺页；16384 → 页 4 偏移 0 → 物理 28672；30000 → 页 7 偏移 1328 → 物理 25904。
• 例 2 锚点：32 位/4KB/4B → 单级页表 4MB；两级 10+10 → 一级 1024 项 = 4KB 常驻、二级每张 4KB 按需；常驻从 4MB 压到 4KB。
• 分页只有"页内碎片"，没有外部碎片——这是它相对连续分配最大的进步。

下一篇：分段与段页式管理