Skip to content

Chapter 5 Virtual Memory

虚拟内存（Virtual Memory）是在 paging 基础上进一步建立的内存管理机制。它让进程看到一个连续、私有、可扩展的虚拟地址空间，而实际物理内存只需要保存当前真正会被访问的那部分页面。

Virtual Memory 的核心目标

  • 分离逻辑地址与物理地址：程序使用 virtual address，硬件和内核负责映射到 physical frame
  • 突破物理内存容量限制：程序的虚拟地址空间可以大于实际物理内存
  • 提高并发度：每个进程只装入当前需要的页，更多进程可以同时驻留
  • 减少 I/O：不必一次性把整个程序装入内存
  • 支持共享与保护：共享库、共享内存、权限控制都可以通过页映射完成
  • 优化 fork()：通过 copy-on-write 避免立即复制整个父进程地址空间

1 Virtual Address Space

一个进程的虚拟地址空间通常按程序逻辑组织为 code、data、heap、shared library、stack 等区域。虽然这些区域在虚拟地址上看起来有固定布局，但它们不一定都已经占用物理内存。

典型虚拟地址空间布局
  • code / text：程序指令，通常只读、可执行
  • data / bss：全局变量、静态变量
  • heap：动态分配区域，通常向高地址增长
  • shared library：共享库映射区域，可以被多个进程共享
  • stack：函数调用栈，通常从高地址向低地址增长
  • heap 与 stack 中间的大量未使用地址是 hole

为什么虚拟地址空间可以很稀疏

虚拟地址只是进程可能访问的地址范围。只有当某个虚拟页真的被访问，并且内核认为该访问合法时，才需要给它分配或映射物理 frame。

因此 heap 和 stack 中间的 hole、尚未使用的大数组、很少触发的错误处理代码，都不必提前占用物理内存。

共享库也是虚拟内存的重要应用。多个进程可以把同一份只读库代码映射到各自的虚拟地址空间中，但底层指向同一批物理页。

虚拟内存为什么能支持共享库

每个进程都有自己的 page table。只要不同进程的 PTE 指向同一个物理 frame，它们就能共享同一份物理页。

对只读代码页而言，这种共享很安全；对可写页而言，则需要额外机制保证进程之间不会互相破坏。

2 Demand Paging

Demand paging（请求分页）的思想是：页面不在进程启动时全部装入，而是在第一次真正被访问时才装入物理内存。

Demand Paging 的基本流程

  • 进程访问某个 virtual address
  • MMU 查页表，发现对应 PTE 不 present / invalid
  • MMU 触发 page fault
  • OS 判断该访问是否合法
    • 非法访问：终止访问，向进程发送异常 / 信号
    • 合法但页面不在内存：分配 frame，并建立映射
  • 更新 page table / TLB
  • 重新执行触发 page fault 的指令
Demand paging 和 page fault 的关系
  • Demand paging 是一种内存管理策略：需要时才装入页面。
  • Page fault 是实现该策略的硬件异常机制：访问一个当前不可直接访问的虚拟页时，MMU 把控制权交给 OS。
Page Fault 的三类常见原因
  1. 地址未映射：访问了不属于该进程地址空间的区域
  2. 权限不足：例如用户态访问内核页、写只读页、执行不可执行页
  3. 合法但不在内存：页面被换出，或尚未为 lazy allocation 分配物理 frame

在 Linux 中，page fault 进入内核后，内核会先查该地址是否落在某个合法的 VMA（Virtual Memory Area） 中。若地址不属于任何 VMA，则是非法访问；若属于合法 VMA，则根据 fault 类型完成映射、分配、换入或 COW。

Page Fault Handling

处理一次合法的缺页大致包括：

  1. 进入内核，保存用户态上下文
  2. 判断异常类型确实是 page fault
  3. 检查访问是否合法：地址范围、访问权限、VMA 属性
  4. 找到或分配一个空闲 physical frame
  5. 从磁盘、文件或零页初始化该 frame
  6. 更新 page table entry
  7. 恢复进程上下文，重新执行出错指令

Zero-fill-on-demand

对匿名内存（如 heap / stack）而言，内核常在第一次访问时才分配物理页，并把页内容清零后交给进程。

这既避免泄露旧数据，也避免进程申请了大量内存但从未使用时浪费物理内存。

2. 1 Pure Demand Paging

极端情况下，一个进程启动时可以没有任何用户页在内存中。第一条指令、第一次访问数据、第一次访问栈，都可能触发 page fault。

Pure demand paging 的代价
  • 第一次访问每个页面都会 fault
  • 一条指令可能同时涉及多个页面
    • 指令所在页
    • 数据所在页
    • 页表本身需要访问的页
  • 若程序局部性不好，page fault 开销会非常大

Demand paging 之所以可行，是因为程序通常具有很强的 locality（局部性）。一段时间内，进程往往集中访问少量页，而不是均匀访问整个虚拟地址空间。

2. 2 Effective Access Time

Page fault 的代价远高于普通内存访问，因此即使很小的 fault rate 也会显著影响平均访问时间。

Demand Paging 的 EAT

设 page fault rate 为 \(p\)，普通 memory access time 为 \(M\)，一次 page fault 的平均处理时间为 \(F\)，则：

\[ EAT = (1-p) \times M + p \times F \]

更完整地看，\(F\) 可能包括：

  • page fault trap 开销
  • 查找 backing store
  • 必要时换出 victim page
  • 换入目标 page
  • 更新页表与 TLB
  • instruction restart
EAT 示例

假设普通内存访问为 \(200 \, ns\)，平均 page fault service time 为 \(8 \, ms\)：

\[ EAT = (1-p) \times 200 + p \times 8{,}000{,}000 = 200 + p \times 7{,}999{,}800 \]

若每 1000 次访问有 1 次 page fault，即 \(p=0.001\)，则：

\[ EAT \approx 8200 \, ns = 8.2 \, \mu s \]

平均访问时间会比 \(200 \, ns\) 慢约 \(41\) 倍。若要把额外开销控制在 10% 内，fault rate 必须低到约每 400,000 次访问不到 1 次 fault。

2. 3 Prepaging and Swap

请求分页只在访问时装页，而 prepaging 会提前装入一些预测即将使用的页。

策略 做法 风险
Demand paging 访问时才装入 初次访问会 fault
Prepaging 提前装入一批可能使用的页 若预测错误，会浪费 I/O 和内存
Prepaging 的判断

若提前装入 \(s\) 个页面，其中只有比例 \(\alpha\) 真的被使用：

  • \(\alpha\) 越接近 1，prepaging 越可能有收益
  • \(\alpha\) 越接近 0，prepaging 基本是在浪费 I/O 和 frame

Swap space 通常比普通文件系统 I/O 管理成本更低，因为 swap 区域分配更连续、元数据更少。但现代移动系统通常不采用传统 swapping，而是倾向于回收只读文件页、压缩内存，或直接终止后台进程。

3 Copy-on-Write

Copy-on-Write（COW）用于优化 fork()。父进程创建子进程时，内核并不立刻复制父进程的所有物理页，而是让父子进程暂时共享这些页，并把相关页标成只读。

当某一方尝试写共享页时，会触发 page fault。内核确认这是 COW fault 后，再复制该页，让写入方得到自己的私有副本。

COW 的意义

  • fork() 不必立即复制整个地址空间
  • 若子进程很快调用 exec()，多数页根本不用复制
  • 只有真正被写过的页才会产生复制成本
  • 只读代码页、共享库页可以继续共享
vfork()

vfork() 是早期没有 COW 或 COW 成本较高时的优化。它让子进程直接共享父进程地址空间，并挂起父进程直到子进程 exec() 或退出。

因为子进程共享父进程的 heap 和 stack，所以 vfork() 使用非常脆弱，子进程不应从调用函数返回，也不应调用普通 exit()，通常应尽快调用 exec() 或 _exit()。

4 Page Replacement

Demand paging 需要空闲 frame 才能把缺失页装入内存。若没有空闲 frame，OS 就必须选择某个当前在内存中的页作为 victim page，把它换出或丢弃，再把目标页装入该 frame。

Page Replacement 的目标

选择未来最不可能被访问的页面作为 victim，从而降低后续 page fault 次数。

由于 OS 无法知道未来访问序列，所有实际算法本质上都是在根据过去访问历史预测未来。

带 page replacement 的 page fault handler
  1. 找到目标页在 backing store / 文件中的位置
  2. 寻找空闲 frame
  3. 若没有空闲 frame，运行 replacement algorithm 选择 victim
  4. 若 victim 是 dirty page，则先写回磁盘
  5. 把目标页读入 frame
  6. 更新目标进程 page table
  7. 重新执行触发 fault 的指令

Dirty bit 的作用

若 victim page 没有被修改过，可以直接丢弃；如果之后还需要，重新从文件或 swap 读入即可。

若 dirty bit = 1，则说明内存中的内容比磁盘新，换出前必须写回，否则会丢数据。

5 Page Replacement Algorithms

评估页替换算法时，通常给定一个 reference string，只记录访问的 page number，然后计算在固定 frame 数下会发生多少次 page fault。

课件参考串 
7,0,1,2,0,3,0,4,2,3,0,3,0,3,2,1,2,0,1,7,0,1

连续访问同一个已经在内存中的页不会产生新的 page fault。

算法 Victim 选择 主要特点
FIFO 最早进入内存的页 简单，但可能出现 Belady's anomaly
OPT 未来最久不用的页 理论最优，只能作为比较基准
LRU 最久没有被访问的页 常用思想，不会出现 Belady's anomaly
Second Chance / Clock FIFO + reference bit LRU 的低成本近似
Enhanced Clock reference bit + dirty bit 同时考虑近期访问和写回成本
LFU / MFU 按访问次数选择 实际系统较少直接使用

5. 1 FIFO

FIFO（First-In-First-Out）总是替换最早装入内存的页面。它不关心页面最近是否被频繁访问，因此实现简单但效果不稳定。

Belady's Anomaly

对某些访问序列，FIFO 在 frame 数增加时反而可能产生更多 page fault，这称为 Belady's anomaly。

例如参考串 1,2,3,4,1,2,5,1,2,3,4,5 下，FIFO 可能出现 3 个 frame 比 4 个 frame fault 更少的反常情况。

5. 2 Optimal

OPT（Optimal replacement）替换未来最长时间不会再被访问的页。

OPT 的意义

OPT 需要知道未来访问序列，因此无法在线实现。

但它给出了某个 reference string 上的最小 page fault 数，可用来衡量其他算法离理论最优还有多远。

对课件中的 Belady anomaly 示例，OPT 可以做到 9 次 page faults。

5. 3 LRU

LRU（Least Recently Used）替换最久没有被访问的页。它的依据是 locality：最近被访问过的页，很可能近期还会再次被访问。

LRU 的性质

  • 通常比 FIFO 更符合程序局部性
  • 不会出现 Belady's anomaly
  • 精确实现成本较高
  • 对课件参考串，3 个 frames 下 LRU 产生 12 次 page faults，介于 FIFO 和 OPT 之间
LRU 的两种精确实现
实现 做法 代价
Counter-based 每次访问把当前时钟写入 PTE counter，替换时找 counter 最小的页 每次替换需要搜索，硬件 / OS 成本高
Stack-based 用链表维护访问顺序，每次访问把页移到栈顶，栈底是 victim 每次访问都要更新链表

5. 4 LRU Approximation

精确 LRU 代价太高，因此真实系统常使用 reference bit 做近似。reference bit 由硬件在页面被访问时置 1，OS 周期性检查并清零。

Additional-reference-bits algorithm

可以为每个页维护一个多位历史寄存器，例如 8 bits：

  • 每隔固定时间右移一位
  • 若该周期内 reference bit = 1，则把最高位置 1
  • 清除 reference bit，进入下一周期

例如：

  • 00000000：最近 8 个周期都没被访问
  • 11111111：最近 8 个周期都被访问
  • 11000100 比 01110111 更新，因为最高位代表最近周期

5. 5 Second Chance / Clock

Second-chance 在 FIFO 队列基础上加入 reference bit：

  • 若队首页 reference bit = 0，直接替换
  • 若 reference bit = 1，说明近期访问过，把它清 0 并移动到队尾 / 跳过
  • 继续检查下一个页

Clock algorithm 用一个环形队列和指针实现 second-chance，因此成本更低。

5. 6 Enhanced Second Chance

增强版 second-chance 同时使用 reference bit 和 modify / dirty bit，把页面分成四类：

类别 含义 替换优先级
(0, 0) 最近未访问，且未修改 最适合替换
(0, 1) 最近未访问，但已修改 可替换，但要写回
(1, 0) 最近访问过，未修改 不太适合
(1, 1) 最近访问过，且已修改 最不适合

算法优先选择编号最低的非空类别，必要时可能绕 clock queue 多圈。

5. 7 LFU / MFU and Buffering

LFU（Least Frequently Used）替换访问次数最少的页，但问题是某些页可能在初始化阶段被频繁访问，之后再也不用，计数却仍然很高。

MFU（Most Frequently Used）则基于相反假设：访问次数少的页可能刚刚被装入，还没来得及被充分使用。但这类 counting-based 算法实际并不常作为主流页替换策略。

Page-buffering algorithms

OS 可以长期维护一批 free frames：

  • fault 时先把目标页读入 free frame，让进程尽快恢复
  • victim page 的写回可以延后到磁盘空闲时做
  • 被释放 frame 的旧内容可暂时保留，若很快又被访问，等价于一次 cache hit
Applications and Page Replacement

OS 的页替换算法是在预测程序未来访问模式，但有些应用比 OS 更了解自己的访问规律，例如数据库。

这类应用若同时使用 OS buffer cache 和自己的 buffer pool，可能出现 double buffering：同一份磁盘页在 OS 和应用中各存一份，浪费内存。某些系统允许应用通过 raw disk mode 绕过 OS buffering、locking 等机制，让应用自己管理缓存。

6 Allocation of Frames

页替换算法决定“换掉哪个页”，而 frame allocation 决定“每个进程最多 / 至少能用多少 frame”。

Minimum number of frames

每个进程需要满足指令语义要求的最小 frame 数。

例如 IBM 370 的 SS MOVE 指令可能需要 6 个页面：

  • 指令本身可能跨 2 页
  • source operand 可能跨 2 页
  • destination operand 可能跨 2 页
分配策略 做法 特点
Equal allocation 每个进程分到相同数量 frame 简单，但忽略进程大小差异
Proportional allocation 按进程大小比例分配 frame 更合理，但需要动态调整
Global vs Local Replacement
策略 Victim 来源 优点 缺点
Global replacement 所有进程的 frame 系统吞吐通常更高，内存利用率更好 一个进程会影响另一个进程的性能
Local replacement 本进程已分配 frame 单个进程性能更稳定 可能导致全局内存利用不足

多数通用系统更偏向 global replacement，但会配合优先级、工作集、cgroup / quota 等机制限制互相干扰。

6. 1 Reclaiming Pages

OS 通常不会等 free-frame list 完全耗尽才开始回收页面，而是设置高低阈值：

  • free memory 低于 minimum threshold：开始积极 reclaim
  • 回收到 maximum threshold：暂停 reclaim

低内存时的最后手段

如果 reclaim 仍无法得到足够内存，系统可能触发 OOM 处理，按 OOM score 选择进程终止。

OOM score 反映进程在低内存情况下被杀掉的可能性，通常与内存占用、进程重要性等因素有关。

6. 2 Major and Minor Page Faults

类型 含义 是否需要磁盘 I/O
Major page fault 页面不在内存中，必须从磁盘读取 是
Minor page fault 当前映射不存在，但物理页已经在内存中 否

Minor fault 的例子包括共享库页已经在内存中、页面被 reclaim 但还没真正释放等。

6. 3 NUMA

在 NUMA（Non-Uniform Memory Access）系统中，不同 CPU 访问不同内存节点的延迟不同。为了提高性能，OS 应尽量：

  • 把线程调度到靠近其内存的 CPU 上
  • 从当前 CPU 所在 NUMA node 的 free-frame list 分配内存
  • 减少线程跨 NUMA domain 迁移

7 Thrashing

Thrashing 指进程把大量时间花在页面换入换出上，而不是实际执行指令。

Thrashing 的形成过程

  1. 某进程可用 frame 不足
  2. 它访问一个新页时必须换入，同时换出当前仍会很快用到的页
  3. 很快又需要刚换出的页，于是再次 page fault
  4. CPU 利用率下降
  5. OS 误以为需要增加 multiprogramming degree
  6. 更多进程进入内存，frame 更紧张，thrashing 更严重

Demand paging 能工作，是因为程序访问有 locality；thrashing 出现，是因为系统无法给所有活跃 locality 提供足够 frame。

8 Working-Set Model

Working set 描述进程在最近一段时间内真正活跃使用的页面集合。

Working-Set Model

设 working-set window 为 \(\Delta\)，表示最近 \(\Delta\) 次内存引用。

进程 \(p_i\) 的工作集大小：

\[ WSS_i = \text{最近 } \Delta \text{ 次引用中出现过的不同页面数} \]

系统总需求：

\[ D = \sum_i WSS_i \]

若 \(D > m\)，其中 \(m\) 是可用 physical frames 数，则系统可能发生 thrashing。

\(\Delta\) 应该如何选择
  • \(\Delta\) 太小：无法覆盖完整 locality，低估工作集
  • \(\Delta\) 太大：覆盖多个 locality，高估工作集
  • \(\Delta = \infty\)：等于整个程序曾经访问过的全部页面，失去动态意义
近似维护 Working Set

精确记录最近 \(\Delta\) 次引用成本很高，OS 可用 timer + reference bit 近似：

  • 硬件在页被访问时设置 reference bit
  • OS 每隔一段时间扫描并保存 reference bit
  • 清零 reference bit，进入下一轮统计
  • 若某页在最近几个周期内至少被标记过一次，则认为它属于 working set

例如 \(\Delta = 10{,}000\) 个时间单位，timer 每 5,000 个时间单位中断一次，则可以为每页保存 2 个历史 bit。若任一 bit 为 1，就近似认为该页在 working set 中。

这种方法不完全精确，因为它只知道某页在某个区间内被访问过，无法知道访问发生在区间内的具体时刻。若改成 10 个历史 bit、每 1,000 个时间单位中断一次，精度会更高。

8. 1 Page-Fault Frequency

Page-Fault Frequency（PFF）比 working-set model 更直接：根据实际 page fault rate 调整 frame 分配。

情况 调整
fault rate 太高 给进程更多 frame
fault rate 太低 回收部分 frame
没有空闲 frame 可给 挂起 / 换出某些进程

9 Other Considerations

9. 1 Kernel Memory Allocation

内核内存分配和用户内存分配不同。内核经常需要为各种数据结构分配小块对象，也可能需要为 DMA / device I/O 分配物理连续内存。

Kernel memory allocation 的特殊要求

  • 分配大小变化多
  • 需要减少碎片
  • 某些场景要求 physically contiguous
  • 分配 / 释放路径必须很快

9. 2 Page Size

页大小是内存系统中的重要折中。

倾向 原因
小页 内部碎片少、保护粒度细、locality 表达更精确
大页 页表更小、I/O 批量更大、TLB reach 更大、TLB miss 更少

TLB Reach

\[ TLB\ reach = TLB\ entries \times page\ size \]

若 working set 超出 TLB reach，即使数据都在内存中，也可能频繁发生 TLB miss。大页可以提高 TLB reach，但会增加内部碎片。

9. 3 Program Structure

程序访问顺序会直接影响 page fault 次数。

数组访问顺序

假设 int data[128][128]，每行刚好存放在一个 page 中，系统有 127 个 frames。

按列访问：

for (j = 0; j < 128; j++)
    for (i = 0; i < 128; i++)
        data[i][j] = 0;

每次内层循环都会跨页访问，可能造成 \(128 \times 128 = 16{,}384\) 次 page faults。

按行访问：

for (i = 0; i < 128; i++)
    for (j = 0; j < 128; j++)
        data[i][j] = 0;

每行只 fault 一次，约 \(128\) 次 page faults。

9. 4 I/O Interlock

用于 I/O 的页面有时必须被锁定在内存中，不能被 page replacement 选为 victim。例如设备正在把数据 DMA 到某个物理页时，该页不能被换出或重新分配。

9. 5 Windows XP Example

Windows XP 使用 demand paging，并通过 clustering 在缺页时顺带读入 faulting page 附近的页面，以利用空间局部性。

Working set trimming

每个进程有 working set minimum 和 maximum：

  • wsmin：进程保证能保留的最小页数
  • wsmax：进程最多可拥有的页数

当系统 free memory 低于阈值时，Windows 会自动 trim working set，从拥有超过 wsmin 的进程中回收页面。

10 Linux Virtual Memory

第二份课件主要说明 Linux 中虚拟内存如何落到实际地址空间、页表和内核分配器上。

10. 1 Flat Memory vs Virtual Memory

早期或简单系统可能使用 flat memory：所有程序、OS、外设共享同一个地址空间。

常见 flat memory 系统
  • 8086-80286 时代的早期 x86
  • ARM Cortex-M
  • 很多 8-bit / 16-bit IoT 芯片

Flat memory 的问题

  • 没有内存保护
  • 用户程序可能破坏内核内存
  • 进程之间难以隔离
  • 外设与 RAM 混在同一物理地址空间中，管理复杂
  • 旧 x86 中 RAM 还会被 DOS area、extended memory、硬件映射区域切开，访问方式更复杂

虚拟内存则为每个进程建立独立映射：

  • 同一个 virtual address 在不同进程中可以指向不同 physical frame
  • 用户态看不到内核内存
  • 权限位阻止非法读 / 写 / 执行
  • 物理页可以被移动、换出、共享或映射到外设

10. 2 Linux Address Spaces

Linux 中软件通常使用 virtual address，包括用户态和内核态。地址空间按架构分成用户区和内核区。

32-bit Linux

经典 32-bit Linux 通常采用 3G/1G 分割：

  • 0x00000000 ~ 0xBFFFFFFF：user space，约 3GB
  • 0xC0000000 ~ 0xFFFFFFFF：kernel space，约 1GB
  • CONFIG_PAGE_OFFSET 默认常为 0xC0000000

每个进程有自己的 user-space 映射；context switch 时，内核通过类似 switch_mm() 的路径切换当前进程的地址空间。

64-bit / ARM64

64-bit 系统的虚拟地址空间远大于物理内存，kernel / user split 依架构而定。

ARM64 常见配置：

  • 48-bit VA：四级页表，\(9 + 9 + 9 + 9 + 12\)
  • 39-bit VA：三级页表，\(9 + 9 + 9 + 12\)
  • TTBR0 通常用于 user space
  • TTBR1 通常用于 kernel space
  • 中间大片区域不映射，访问会 fault

10. 3 Three Kinds of Linux Virtual Addresses

Linux 设备驱动和内核内存管理中常区分三类虚拟地址：

类型 含义 映射特点
User virtual address 用户进程使用的虚拟地址 每个进程私有，通常虚拟连续、物理不连续
Kernel logical address 线性映射物理内存的内核地址 virtual 与 physical 有固定偏移，转换快
Kernel virtual address vmalloc() 等非连续映射区域 虚拟连续，但物理可不连续

Kernel logical address

在经典 32-bit 低内存系统中，PAGE_OFFSET 以上的一段 kernel logical address 线性映射低端物理内存。

例如：

\[ Virt: 0xC0000000 \rightarrow Phys: 0x00000000 \]

因此可以用类似 pa(x) / va(x) 的宏在二者之间转换。

Large physical RAM

32-bit kernel address space 只有约 1GB，且顶端还要保留一部分给 vmalloc() 等非连续映射。因此当物理内存超过约 1GB 时，不可能把所有 RAM 都线性映射进 kernel logical address space。

结果是：只有底部一部分物理 RAM 有直接 kernel logical address，其他高端内存需要额外映射机制访问。64-bit 系统一般没有这个问题。

10. 4 Page Tables, TLB and Faults in Linux

Linux 必须长期保存完整映射信息，因为 TLB 只能缓存少量最近使用的翻译结果。

MMU / TLB 在 Linux 中做什么
  • MMU 位于 CPU core 和内存系统之间，负责把 virtual address 翻译成 physical address
  • TLB 是 MMU 内部或旁边的高速缓存，保存最近使用的地址翻译和权限位
  • 若 TLB miss，硬件或软件需要进行 page table walk
  • 若页表项不存在、权限不满足或页面被换出，则触发 page fault
常见 page size
  • ARM：4KB
  • ARM64：4KB 或 64KB
  • x86：4KB
  • MIPS：配置更灵活

页大小通常在 kernel build time 或体系结构配置中决定。

Linux 中的关键结构
  • mm_struct：描述进程地址空间
  • mm_struct.pgd：指向顶级页表
  • vm_area_struct：描述一段连续虚拟区域及其权限 / 映射来源
  • switch_mm()：context switch 时切换地址空间
  • do_page_fault()：体系结构相关的 page fault 入口
  • __handle_mm_fault()：执行主要 fault 处理和 page table walk

Lazy allocation in Linux

用户进程申请内存时，内核可以只建立 VMA 记录，而不立刻分配物理页，也不立即更新 TLB。

当进程第一次访问该区域时，MMU 触发 page fault；内核发现地址合法后，再分配物理页、清零、更新页表，然后返回用户态继续执行。

对实时性敏感的程序，可以在启动阶段主动触碰相关内存，或使用 mlock() / mlockall() 降低运行中首次访问带来的 page fault 风险。

10. 5 Shared Memory and mmap()

共享内存可以通过把同一个 physical frame 映射进不同进程实现。不同进程中的 virtual address 不一定相同。

共享内存中的指针问题

若共享区域内部保存的是绝对指针，那么不同进程必须把该区域映射到相同 virtual address，否则指针值在另一个进程中没有意义。

mmap() 允许用户请求一个目标 virtual address，但内核不一定能满足；若地址冲突或不合法，映射会失败或被安排到其他位置。

10. 6 Swapping in Linux

当内存紧张时，Linux 可以把某些页面写入 swap，释放对应 physical frame。之后进程再次访问该页时，MMU 会因为 PTE 不 present 而触发 page fault，内核再把页面从 swap 读回。

换入后不必回到原 frame

页面从 swap 读回时，不需要回到原来的物理 frame。只要更新 page table，让原来的 virtual address 指向新的 frame，用户程序就感知不到变化。

这也是用户态普通内存通常不能直接用于 DMA 的原因之一：设备使用 physical address，而 OS 可能移动或换出该页。

11 Buddy System and Slab Allocator

11. 1 Buddy System

Linux 内核使用 buddy system 管理物理页框。它按 \(2^n\) 大小分配连续页块，并通过 buddy 关系快速拆分和合并。

Buddy system 示例

若当前只有一个 256KB 空闲块，而内核申请 21KB：

  1. 256KB 拆成两个 128KB buddy
  2. 一个 128KB 再拆成两个 64KB buddy
  3. 一个 64KB 再拆成两个 32KB buddy
  4. 分配一个 32KB 块给 21KB 请求

这样会产生内部碎片，但释放时容易按 buddy 关系向上合并。

Buddy System 的特点

  • 优点：快速找到连续物理页；释放后容易合并成大块
  • 缺点：按 \(2^n\) 向上取整，可能造成 internal fragmentation

11. 2 Slab Allocator

Buddy system 适合分配连续页块，但内核中还有大量固定大小的小对象，如 task_struct、inode、dentry 等。频繁向 buddy system 申请 / 释放这些小对象会很慢，也容易产生碎片。

Slab allocator 为每类常用对象维护 cache。一个 cache 由多个 slab 组成，每个 slab 包含若干连续页，并被切成多个等大小对象。

Slab 的三种状态
  • Full：slab 中所有对象都已分配
  • Partial：部分对象已分配，部分空闲
  • Empty：全部对象空闲

分配对象时，优先从 partial slab 中取空闲对象；若没有 partial slab，再使用 empty slab；若还没有，就新建 slab。

Slab Allocator 的优点

  • 分配 / 释放固定大小对象很快
  • 减少小对象碎片
  • 对象字段可能复用，减少初始化成本
  • 与 buddy system 分工明确：buddy 管页块，slab 管内核对象
SLAB / SLOB / SLUB
  • SLAB：早期 Linux slab allocator
  • SLOB：面向小内存系统的 simple list of blocks
  • SLUB：现代 Linux 常用的高性能 slab allocator，简化队列结构，把更多元数据放入 page structure

12 Summary

本章主线

  • Virtual memory 把进程看到的地址空间和物理内存分离
  • Demand paging 让页面在第一次使用时才进入内存
  • Page fault 是正常内存管理机制的一部分，不一定代表程序错误
  • COW 通过“先共享、写时复制”优化 fork()
  • Page replacement 在 frame 不足时决定换出谁
  • Working set 和 PFF 用来识别并缓解 thrashing
  • Linux 通过 VMA、page table、mm_struct、lazy allocation、swap 等机制实现虚拟内存
  • Buddy system 管理物理页块，slab allocator 管理内核小对象
本章常见考点
  • page fault 的原因、处理流程和 EAT 计算
  • demand paging 与 prepaging 的取舍
  • COW 的触发条件和 fork() 优化
  • FIFO / OPT / LRU / Clock 的 victim 选择与 Belady's anomaly
  • global replacement 与 local replacement 的区别
  • working set、PFF 与 thrashing 的关系
  • TLB reach 与 page size 的折中
  • Linux 三类虚拟地址：user virtual、kernel logical、kernel virtual
  • buddy system 与 slab allocator 的职责区别