Runguo Li

Runguo Li

M.S. student in Information Science @ UIUC, advised by Prof. Minjia Zhang. Working on ML systems for large-scale models: MoE inference and expert streaming, distributed training and rollout, GPU compiler correctness.

Lecture 16–17: 请求调页（Demand Paging）

目录 · ← l12 · l14 →

Lecture 16–17: 请求调页（Demand Paging）

概述

真正的”虚拟”内存允许程序不把所有信息装入内存也能运行：用到的页在内存，闲置的页在磁盘（交换区/backing store），按需搬移。本讲讲解缺页机制（page fault）、取页策略（按需取页 vs 预取）、页面置换策略（随机/FIFO/MIN/LRU/时钟算法），以及内存过载导致的抖动（thrashing）——这是 Assign5/Assign6 的理论核心。

核心概念与系统机制图解

为什么能这么做？——局部性（Locality of Reference）

  • 大多数程序大部分时间只使用其代码和数据的一小部分。
  • 内存（DRAM）比磁盘快约 10 万倍、比 SSD 快约 1000 倍；磁盘/SSD 每比特成本低约 100 倍。理想：像磁盘一样便宜、像 DRAM 一样快的”虚拟内存”。

缺页机制（Page Fault）

  • 页表条目中的 Present 位 = 0 表示该页在 backing store（交换空间/分页文件）。
  • CPU 访问 present 位为 0 的虚拟地址 → 缺页陷阱（page fault trap） → OS 处理：
    1. 检查访问是否合法(否则 → 段错误, 终止进程)
2. 找一个空闲物理页(若无, 先按置换策略淘汰一页)
3. 从 backing store / 可执行文件读入该页
4. 更新页表条目: 指向新物理页, 置 Present 位
5. 恢复执行触发缺页的指令(指令必须可重启!)
  • 硬件支持：x86-64 把出错地址锁存到特权寄存器 CR2；指令需可重启（如 push 会先改 SP 再写内存，缺页时要能回滚）。

取页策略（Fetching Policy）

| 策略 | 做法 | 评价 | | :— | :— | :— | | 按需取页（Demand Fetching） | 进程启动时一页都不加载，引用到才取 | 简单；只读代码页从可执行文件取、未初始化数据/栈返回零页、脏数据页写回 backing store | | 预取（Prefetching） | 预测未来需要的页提前加载 | 需预测未来，难；折中：缺页时多读几页（顺序访问时有效）。磁盘缺页 5–10ms，预取 .04ms |

页面置换策略（Replacement Policy）

  • 内存满后每次缺页都必须淘汰一页： | 策略 | 做法 | 评价 | | :— | :— | :— | | Random | 随机选页 | 简单、出乎意料地有效 | | FIFO | 淘汰在内存最久的页 | 简单、对页公平；可能淘汰常用页 | | MIN（最优） | 淘汰未来最久才被访问的页 | 理论最优，需预知未来，不可实现 | | LRU | 淘汰最久未使用的页 | 用过去预测未来，应近似 MIN |

  • Lecture 16 的对比实验（引用序列 A..E 各若干次，3 个页框）：

    • FIFO：10 次缺页；MIN（最优）：6 次；LRU：8 次——LRU 明显优于 FIFO，接近最优。

LRU 的实现难题与时钟算法（Clock Algorithm）

  • 精确 LRU 需要硬件记录每页的访问时间戳——成本过高，不实用。
  • 实用硬件支持：页表条目中两个位——引用位（referenced/accessed）：页被读/写时由 CPU/MMU 置位；脏位（dirty）：页被修改时置位。
  • 时钟算法（Clock / 第二机会 Second Chance）——LRU 的近似：
    把物理页排成圆环, 一个"指针(hand)"指向某页:
缺页需要淘汰页时:
while (true):
  若 当前页引用位 = 1:  清除引用位(给第二次机会), 指针前移
  若 当前页引用位 = 0:  选中该页淘汰!
                        (若脏位=1, 先写回磁盘)
                        指针前移
╭───────────────────────────────╮
│  P1 ── P2 ── P3 ── P4 ── P5  │   ← 环形链表 + hand
╰───────────────────────────────╯
  • hand 速度的含义：慢 = 内存充足、缺页少；快 = 内存不足、缺页频繁（Assign6 直接实现该算法）。

全局 vs 每进程置换

  • 全局置换：所有进程的页放进同一个置换池，彼此竞争（无性能隔离；大多数系统采用）。
  • 每进程置换：每进程独立页框池，互不干扰（需决定每进程分多少页框）。

抖动（Thrashing）

  • 定义：活动工作集（working set）超过物理内存 → 每次缺页淘汰的都是活跃页 → 立刻又缺页 → 几乎所有时间都在换页。
  • 数学感受（Lecture 16）：DRAM 100ns，磁盘 10ms。若内存仅差 1%（每 100 次访问 1 次缺页）：0.99×100ns + 0.01×10ms ≈ 100,099ns —— 慢了 1000 倍！
  • 对策：OS 暂停部分进程（调度器只调度”装得下”的作业集）；个人电脑上用户可自行关闭程序；内存便宜 → 买够内存。

代码示例与系统调用解说

示例：用 mprotect + SIGSEGV 模拟缺页（Assign5 的核心思路）

#include <csignal>
#include <cstdio>
#include <cstdlib>
#include <sys/mman.h>
#include <unistd.h>

char* region;

void faultHandler(int, siginfo_t* si, void*) {
    // 捕获访问受保护页的 SIGSEGV —— 用户态版本的"缺页中断"
    char* faultAddr = (char*)si->si_addr;
    long page = ((long)faultAddr - (long)region) / 4096;
    printf("[page fault] loading page %ld from backing store\n", page);
    // (Assign5 中这里: 分配物理页→解密读入→mprotect 置可读写)
    mprotect(region + page * 4096, 4096, PROT_READ | PROT_WRITE); // 模拟"置 Present 位"
}

int main() {
    region = (char*)mmap(nullptr, 4 * 4096, PROT_NONE,
                         MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
    struct sigaction sa{};
    sa.sa_sigaction = faultHandler;
    sa.sa_flags = SA_SIGINFO;
    sigaction(SIGSEGV, &sa, nullptr);

    region[0] = 'A';          // 首次访问 → 故障 → 按需"取页"
    region[5000] = 'B';       // 第二页 → 再次故障
    printf("done: %c %c\n", region[0], region[5000]);
    return 0;
}

【代码做了什么？】 用 PROT_NONE 映射 4 页，任何访问都触发 SIGSEGV；处理器把页”加载”出来并 mprotect 为可读写，然后程序继续——完美模拟”缺页 → 取页 → 继续执行”。

【系统机制透视】

  • 真实内核的缺页处理与这段代码同构：内核在缺页陷阱里分配物理页、从 backing store 读入、更新页表（置 Present）、恢复指令执行。
  • mprotect 用页表保护位制造”伪缺页”——这正是 Assign5 在用户态模拟内核特性的技巧（讲义明确说”本应在内核里写的代码，我们用 mmap 在用户态实现”）。
  • 注意”指令可重启”：真实硬件保证缺页返回后重新执行同一指令；用户态模拟里，SIGSEGV 处理器返回后也会重试出错指令。

关键要点

  1. 请求调页让程序无需全部装入内存即可运行：Present 位 + 缺页陷阱是核心机制。
  2. 取页策略：按需取页（默认）vs 预取（赌顺序访问）。
  3. 置换策略：MIN 最优但不可实现；LRU 近似 MIN；时钟算法用引用位近似 LRU（Assign6 实现）。
  4. 引用位/脏位是页表条目中的关键硬件支持。
  5. 抖动 = 工作集超内存 → 换页风暴 → 千倍减速；需控制并发度或加内存。

常见陷阱与注意事项

  • 忘记检查缺页地址合法性：非法访问（如空指针）会无限缺页或错误地”取页”。
  • 脏页不写回：淘汰脏页前必须写回 backing store，否则数据丢失。
  • 置换掉正在使用的页：会导致立即再次缺页（抖动前兆）。
  • 时钟算法中忘记清除引用位：指针将永远找不到可淘汰页。
  • 把 backing store 与文件系统缓存混淆：backing store 是页的”影子”，独立于文件缓存。

思考题

  1. 问题：为什么 LRU 比 FIFO 更好？它为何无法精确实现？
    • 答案：LRU 淘汰”最久未使用”的页，利用时间局部性预测未来，近似 MIN；精确实现需为每页记录访问时间戳（硬件代价过高），因此用引用位做近似（时钟算法）。
  2. 问题：时钟算法中”清除引用位”的作用是什么？
    • 答案：给”最近被引用过”的页第二次机会——若在下一轮扫描前它又被引用，引用位重新置 1 继续存活；清除引用位是把”过去”的引用记录重置，让算法只考察”最近一轮”的访问。
  3. 问题：内存只差 1% 为什么会导致 1000 倍变慢？
    • 答案：每 100 次访问就有 1 次缺页（10ms 磁盘 I/O），平均访问时间从 100ns 恶化到约 100μs；且每次淘汰的往往是活跃页，缺页相互触发，形成换页风暴。