操作系统学习笔记 · 第 17 课 · 页面置换——内存不够怎么办

上一课我们学了缺页中断：访问的页不在内存，内核就把它从磁盘换进来。但这里藏着一个前提——物理内存是满的。要换新页进来，就得先踢掉一个旧页。踢谁？这一脚的选择，直接决定系统是丝滑流畅还是卡成幻灯片。这一课，我们就看操作系统怎么"挑倒霉蛋"，也就是页面置换（Page Replacement）。

从"内存只能装 3 本书"说起

假设你的书架（内存）只能放 3 本书，但你要按顺序读 1、2、3、4 这几本书：

读 1、2、3，正好放下；
要读 4 了，书架满了，得踢掉一本腾位置——踢 1、还是 2、还是 3？

踢错了代价很大：如果踢掉的是"马上又要读"的那本，等下又得去仓库取，白忙一场。

"踢哪本"这个策略，就是页面置换算法。 它直接影响缺页次数，进而影响系统性能。

17.1 页面置换解决什么问题

一句话理解：物理内存不够，又要加载新页时，必须把某个旧页写回磁盘腾地方。选哪个旧页，直接影响性能。

核心矛盾一句话：内存容量有限，程序要用的页无限。 置换算法的目标，就是尽量踢掉"以后最不可能马上用到"的那页，从而减少缺页次数。

评判标准很简单：同一段访问序列，缺页次数越少，算法越好。 我们这一课就用"缺页次数"来PK各算法。

17.2 三种置换算法

算法	规则	优点	缺点
FIFO	最早进来的先换出	简单	可能换掉常用页（Belady 异常）
LRU	最久没用的先换出	效果好	需记录访问历史，实现贵
Clock	近似 LRU，用"访问位"转圈找	实现简单、接近 LRU	是近似，非最优

① FIFO（First In First Out，先进先出）

规则最简单：谁先进来，谁先出去，像排队。

优点：实现极简单，记个队列就行；
缺点：完全不看"这页还用不用"。可能把最常用的页踢掉，留下没用的页。

② LRU（Least Recently Used，最近最少使用）

规则更聪明：最久没被用过的页，先换出去。

直觉依据：最近用过的页，接下来很可能还会用；很久没用的页，接下来大概也不会用（这叫"局部性原理"）。所以踢"最久没用"的，最合理。

优点：效果接近最优；
缺点：要记录每页的访问历史（时间戳或链表维护"最近使用顺序"），实现开销大、贵。

③ Clock（时钟算法）

LRU 效果好但实现贵。Clock 是它的"平民版"：

给每页加一个访问位（reference bit），被访问过就置 1；
换页时，指针像钟的指针一样转圈扫，遇到访问位=1 的，就把它清 0 放过（给它一次机会）；遇到访问位=0 的，踢掉它。

一句话理解 Clock："转圈找，给一次机会，抓个'没被访问过'的倒霉蛋。" 它用极小的开销（一个 bit + 转圈扫描），近似达到了 LRU 的效果，是真实操作系统最常用的算法（比如 Linux 的改进版）。

17.3 Belady 异常

FIFO 有个反直觉的现象，值得单独拿出来说：

一句话理解：FIFO 有个反直觉现象——内存变大了，缺页反而变多。LRU 则不会。

正常直觉是"内存越大，缺页越少"。但 FIFO 会违背这个直觉：在特定访问序列下，3 页框的缺页次数反而比 4 页框更少。

这个反常现象叫 Belady 异常（以发现者命名）。

为什么 LRU 不会？因为 LRU 这类算法属于"栈算法"——内存越多，能保留的"最近用过的页"就越多，绝不会更差。而 FIFO 的"先进先出"和"是否常用"无关，所以可能越帮越忙。
一句话记：FIFO 会 Belady 异常，LRU 不会。 这也是"简单≠可靠"的又一例证。

17.4 工作集与抖动

最后，把"置换"放大到整个系统的视角，两个重要概念：

① 工作集（Working Set）

一句话理解：进程"最近正在用"的那组页，就是工作集。工作集都在内存里，进程才跑得顺。

一个进程在某段时间内，真正频繁访问的页其实不多，这一小撮页就是它的工作集。只要工作集能装进内存，进程就运行流畅。

② 抖动（Thrashing）

一句话理解：内存太小，进程的页刚换进来又被换出去，CPU 大量时间耗在换页上，系统慢到像死机。

当内存小到连工作集都装不下，就会发生灾难：进程要用的页，刚换进来，马上又要别的页，只好又换出去……换页本身成了主要工作，CPU 没空干正事。系统的表现是：磁盘疯狂读写、CPU 反而空闲（在等磁盘）、响应慢到像死机。

一句话：抖动 = 换页成了主业，正经活儿干不了。 解决办法通常是"减少同时跑的进程数"或"加内存"。

动手实验：C 语言写 LRU 置换模拟器

// lesson17.c —— LRU 页面置换模拟
#include <stdio.h>

#define FRAMES 3

int main(void) {
    int refs[] = {1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5};  // 访问序列
    int n = sizeof(refs) / sizeof(refs[0]);
    int frames[FRAMES] = {-1, -1, -1};   // -1 表示空
    int last_used[FRAMES] = {0};         // 记录每个框最近被用时刻
    int faults = 0;

    for (int t = 0; t < n; t++) {
        int page = refs[t];
        int hit = -1;
        for (int i = 0; i < FRAMES; i++)
            if (frames[i] == page) hit = i;   // 命中

        if (hit >= 0) {
            last_used[hit] = t;   // 更新最近使用时刻
            printf("访问 %d：命中\n", page);
        } else {
            // 找最久未用的框
            int victim = 0;
            for (int i = 1; i < FRAMES; i++)
                if (last_used[i] < last_used[victim]) victim = i;
            frames[victim] = page;
            last_used[victim] = t;
            faults++;
            printf("访问 %d：缺页，置换框 %d\n", page, victim);
        }
    }
    printf("总缺页次数：%d\n", faults);
    return 0;
}

编译运行：

gcc lesson17.c -o lesson17 && ./lesson17

观察输出：哪些访问命中、哪些缺页、最后总共缺页几次。

进阶玩法：

把 #define FRAMES 3 改成 4 再跑，对比缺页次数——通常内存变大缺页变少；
试着把算法改成 FIFO（记录每页"进来时间"，踢最早进来的），并构造一个能触发 Belady 异常的访问序列，亲眼看看"内存变大、缺页反而变多"的反常现象。

深入点：两个进阶话题

① 脏页（Dirty Page）

换出时，被换的页分两种：

脏页：这页在内存里被改过。换出前必须先写回磁盘（慢，因为要等磁盘写）；
干净页：这页和磁盘上的一致，没改过。直接丢弃即可（快，因为磁盘上已有副本）。

所以内核换页时，尽量先挑干净页换出，省得写磁盘。这也是"为什么写过的数据要及时落盘"的底层原因之一。

② 交换区（Swap）

换出去的页，放哪？放在磁盘的交换分区或交换文件（swap）里。

swap 太小：内存一紧张就无页可换，直接触发抖动；
swap 太大：浪费磁盘空间，还容易让系统"误以为"内存够用而过度换页。

所以 swap 要"平衡"：够用即可，不是越大越好。这也是服务器调优里的常见话题。

小结与思考题

这一课，我们回答了"内存不够怎么办"：

页面置换：内存满时踢掉旧页腾位置，踢哪个决定性能；
三种算法：FIFO（简单但蠢）、LRU（效果好但贵）、Clock（近似 LRU、最常用）；
Belady 异常：FIFO 会"内存越大缺页越多"，LRU 不会；
工作集与抖动：工作集装不进内存 → 抖动，系统慢到像死机。

留三个问题：

FIFO 和 LRU 各按什么规则选"倒霉页"？
什么是 Belady 异常？哪种算法不会发生？
系统"抖动"时你会观察到什么现象？（提示：CPU、内存、磁盘）

到这里，内存管理已经讲了三课：地址、虚拟内存、置换。还剩最后一块拼图——安全。前面反复出现的"段错误"、那些"只读不可执行"的权限位，到底在防什么？黑客又是怎么利用"写越界"攻破程序的？下一课，我们走进内存与系统的防线，看清操作系统如何保护自己、也保护你。