假设你经营一家小小的奶茶店，后厨只有一个三层货架，用来放各种原料：珍珠、椰果、奶盖、茶冻……客人点什么，你就要用到什么。货架满了的时候，新买的原料没地方放，就得先扔掉一箱旧的。问题是——扔哪一箱？扔错了，下一单立刻又得去仓库补货，客人等得心焦。你需要的，就是一套“扔东西的智慧”，这正是操作系统在物理内存不够用时面临的难题，我们叫它“页面置换算法”。内存就是货架，页面就是一箱箱原料，缺货就是“缺页”。这篇文章带你看看：FIFO 的机械、LRU 的精细、Clock 的偷懒、LFU 的记仇，以及 Linux 内核真正的“扔货”手段。

岗位关联

掌握页面置换算法，你才能真正理解缓存为何命中、数据库为何抖动、大模型推理为何卡顿——这是所有高性能系统的底层密码。

目录
  1. 可视化演示
  2. 内存危机来临
  3. FIFO先入先出
  4. LRU最近最少
  5. Clock时钟扫描
  6. LFU频率计数
  7. Belady异常
  8. 内核实战折衷
  9. AI 应用场景
  10. Python 演示
  11. 常见误区
  12. 面试题

可视化演示

本节配有交互动效（进入视口后自动加载，约 3KB）。

页面置换算法与Belady异常对比 FIFO按入队顺序换出页面，可能产生Belady异常：增加帧数反而命中率下降 LRU淘汰最久未访问页面，是栈式算法，不会出现Belady异常 Clock用访问位给页面二次机会，是LRU的高效近似，Linux用双链表实现 命中率 = 命中次数 / 总访问次数 LRU和Clock无Belady异常，FIFO和LFU可能异常

内存危机来临

你的奶茶店越开越火，后厨货架却永远只有三层。客人点单的速度远超你补货的速度，每隔一会儿就有一箱原料“放不下了”。这时候你才意识到：货架（物理内存）是有限的，而菜单上的原料种类（虚拟页面）远不止三层能装下。一旦客人点到的原料不在货架上，你就得暂停出杯，跑去仓库搬货——这一趟趟搬运，就是操作系统的“缺页中断”。

技术上讲，CPU 访问的每个地址都属于某个“页面”。当页面不在物理内存中时，硬件会触发缺页中断，操作系统暂停当前进程，从磁盘把页面读入内存，再重新执行刚才的指令。如果内存已满，就必须先“扔一箱”——选择一个页面换出，腾出位置。这个选择过程，就是页面置换算法要解决的问题。而你服务客人时经常用到的“那几箱原料的组合”，专业术语叫“工作集”。

置换算法的好坏，直接决定系统会不会频繁卡顿。衡量指标就是缺页率：访问 100 次页面，有几次需要去磁盘搬货。搬得越少，系统越快。

回到奶茶店：缺页率就是你“跑去仓库补货”占全部出杯操作的比例。这个比例越低，说明你的货架摆放策略越懂客人的口味——而这正是接下来每一种置换算法比拼的舞台。

缺页率=缺页次数总访存次数×100%\displaystyle \text{缺页率} = \frac{\text{缺页次数}}{\text{总访存次数}} \times 100\%
缺页率就像奶茶店的“缺货率”：缺货越少，客人等待越少，出杯越快。
  1. 总访存次数CPU 执行程序时发出的所有内存访问请求，都会记录到一个引用序列里，这个序列的长度就是总访存次数。
    NtotalN_{\text{total}}
  2. 缺页次数每次访问的页面不在物理内存中，就触发一次缺页中断，同时计数器加一。
    NfaultN_{\text{fault}}
  3. 求比值用缺页次数除以总访存次数，再乘以 100%，就得到缺页率。
    P=NfaultNtotal×100%\displaystyle P = \frac{N_{\text{fault}}}{N_{\text{total}}} \times 100\%

FIFO先入先出

最直觉的扔货策略是什么？小智脱口而出：“哪箱原料最早进货，就先扔哪箱！”他把货架想象成一条传送带：新原料从一头放进来，旧原料从另一头被挤出去。谁先进来谁先走，公平得像排队打饭——这就是 FIFO（First In First Out，先进先出）。

操作系统里，FIFO 为每个页框维护一个队列，队首是最早进入的页面，队尾是最新进入的。缺页时直接把队首踢出去，新页面排到队尾。实现起来只需要一个环形数组和两个指针，比任何算法都省事，硬件开销几乎为零。

但它有个致命的“眼瞎”：它完全不看页面最近有没有被用到。哪怕一箱原料刚刚被客人疯狂点单，只要它排在最前面，照样被扔。于是你可能刚扔掉珍珠，下一单就是珍珠奶茶，只能灰溜溜跑去仓库补货。

传送带策略最大的优点是省心，最大的缺点是“不识时务”。它给了我们一个教训：扔货不能只看进店时间，还得看“最近有没有人点”。这个教训，直接催生了下一个更聪明的算法。

pout=Qhead,Q←Q∖{pout}∪{pnew}\displaystyle p_{\text{out}} = Q_{\text{head}}, \qquad Q \leftarrow Q \setminus \{p_{\text{out}}\} \cup \{p_{\text{new}}\}
队首出队、队尾入队，这就是 FIFO 的全部策略——简单，但可能“好心办坏事”。
  1. 队首出队队列头部存放的是最早进入内存的页面，缺页时直接选它作为换出对象。
    pout=Qheadp_{\text{out}} = Q_{\text{head}}
  2. 集合删旧加新从队列中移除队首页面，再把新调入的页面追加到队尾。
    Q←Q−{pout}+{pnew}\displaystyle Q \gets Q - \{p_{\text{out}}\} + \{p_{\text{new}}\}
  3. 命中不调整如果访问的页面已经在队列中，FIFO 不做任何位置调整——它不在乎“最近使用过”这个信息。
    if p∈Q:no-op\text{if } p \in Q: \text{no-op}

LRU最近最少

小智学乖了。他给每箱原料贴了一张便签，记录“最后一次被取用的时间”。货架满时，他不扔最先进来的，而是扔“最久没被碰过”的那箱——这才是真正的懂人心：你很久没点椰果了，那椰果就先让位给新来的茶冻吧。这就是 LRU（Least Recently Used，最近最少使用）。

LRU 的依据是“时间局部性”：程序刚刚访问过的页面，很可能马上还会被访问。所以它给每个页面记录最近访问时刻，缺页时选时间戳最小的页面淘汰。与 FIFO 最大的区别在于：一个页面即使很早就进入内存，只要它持续被访问，LRU 就会一直保着它，永不淘汰。

LRU 还有一个漂亮的理论性质：它是“栈式算法”。栈式算法的驻留页面集合始终是更大内存时驻留集合的子集，这意味着——加内存一定不会让情况变差。这个性质在后面的 Belady 异常一节会大放异彩。不过 LRU 的代价也很高：每次访问都要更新时间戳，每次缺页都要扫描所有页框找最小值，硬件实现需要昂贵的电路支持。

LRU 就像一位记性极好的店长，清楚每箱原料上一次被碰的时间。可问题是，精确记时间太贵了——每箱原料都要贴标签、每次取用都要更新，货一多就手忙脚乱。于是，小智想出了一个“偷懒”但够用的办法。

p∗=arg⁡min⁡p∈S  tlast(p)\displaystyle p^* = \underset{p \in S}{\arg\min} \; t_{\text{last}}(p)
在所有驻留页面中，挑出“最久没被访问”的那个淘汰——LRU 的公式就这么简单，难的是如何低成本地维护时间信息。
  1. 候选集合当前占住页框的所有页面构成候选集，置换时只能从这里面选。
    S={p1,p2,…,pm}S = \{p_1, p_2, \dots, p_m\}
  2. 时间戳记录每个页面维护一个变量，保存它最近一次被访问的时刻。
    tlast(p)t_{\text{last}}(p)
  3. 取最小时间戳缺页时遍历候选集，找到 $t_{\text{last}}$ 最小的页面换出，这就是“最久未用”。
    p∗=arg⁡min⁡p  tlast(p)\displaystyle p^* = \underset{p}{\arg\min} \; t_{\text{last}}(p)

Clock时钟扫描

小智想：我不用记精确时间，给每箱原料贴一张便利贴就行。客人点过一次，我就打个勾（访问位置 1）。货架满了要扔东西时，我沿货架一圈一圈地走，看到有勾的，擦掉勾继续走——相当于给它一次“缓刑”；看到没勾的，直接扔掉。这就像钟表指针扫过一圈，所以叫 Clock 算法，也叫“二次机会算法”。

Clock 算法是 LRU 的工程近似：每个页面维护一个“访问位”，页面被访问时硬件自动置 1。缺页时，系统维护一个环形指针，沿页框循环扫描：遇到访问位为 1 的页面，把它清为 0 并跳过；遇到访问位为 0 的页面，说明它自上次扫描以来从未被访问，直接换出。如果指针转了一圈都没找到，就退化为把“第一圈的起点”换出——此时它约等于 FIFO。

这个算法的精妙之处在于“二次机会”：一个刚被访问过的页面，指针扫到它时会得到一次豁免。被频繁访问的页面，访问位总在清 0 前又被置 1，因此永远存活。它不需要精确的时间戳，只需要一个位，硬件成本极低。Linux、Windows 至今仍在用它的变体。

便利贴方案省下了精确计时的高昂成本，效果却接近 LRU。但小智很快发现另一种“记仇”的策略：有人提议按“总使用次数”扔货——用过最少的先扔。这个思路听起来合理，却也藏着陷阱。

指针沿环扫描:{a=1⇒a←0, 继续移动a=0⇒换出该页\displaystyle \text{指针沿环扫描}:\quad \begin{cases} a = 1 \Rightarrow a \leftarrow 0,\ \text{继续移动} \\ a = 0 \Rightarrow \text{换出该页} \end{cases}
便利贴上的勾，就是页面的“免死金牌”；没有勾的页面，就是被遗忘的原料，活该被清出货架。
  1. 访问位置 1每次页面被访问，硬件自动把该页的访问位置为 1，表示“最近用过”。
    a=1a = 1
  2. 扫描清位指针扫过访问位为 1 的页面时，不清除它，而是把位改成 0 并继续前进——相当于“再给你一次机会”。
    a←0, 指针→下一页\displaystyle a \leftarrow 0,\ \text{指针} \to \text{下一页}
  3. 遇到 0 换出当指针遇到访问位本来就是 0 的页面，说明上一轮扫描后它从未被使用，此时选择换出。
    换出 a=0 的页面,a←1 放入新页\text{换出 } a = 0 \text{ 的页面}, \quad a \leftarrow 1 \text{ 放入新页}

LFU频率计数

小智雇了一位新店员小周，他提议：“别管最近用没用，统计每箱原料一共被用过多少次，次数最少的先扔！”这就是 LFU（Least Frequently Used，最少使用频次）。乍一听很有道理：珍珠用了 100 次，桂花冻只用了 1 次，要扔当然扔桂花冻。

LFU 的实现是给每个页面配一个计数器，每次被访问就加一，缺页时选计数值最小的页面换出。它的直觉是“频率代表长期价值”：常被访问的页面应该长期留在内存。在访问模式非常稳定的系统里，LFU 确实表现优异，能比 LRU 更精准地识别“长期热页”。

但 LFU 有个著名的缺陷——“冷启动”问题：一个页面可能刚刚开始流行，比如新出的“柿子冻”，只被点过两次，却即将在下一单大爆发。LFU 一看它次数最少，直接扔掉，结果下一秒就后悔。同时，长期不衰减的计数器会让“过气网红”霸占货架：某个曾经很火的原料早没人点了，但历史计数很高，永远不会被淘汰。

记仇的 LFU 在稳定场景下很聪明，但“新晋爆款”总是被它误伤。小智们逐渐意识到：没有完美的算法，每一种策略都有反例。更邪门的是，有些算法还隐藏着一个“反直觉”的陷阱——货架变大，缺货反而更严重。

p∗=arg⁡min⁡p∈S  f(p)\displaystyle p^* = \underset{p \in S}{\arg\min} \; f(p)
LFU 用计数器记住每箱原料的历史辉煌，但辉煌属于昨天，不代表明天还被需要。
  1. 访问加一每个页面维护计数器 $f(p)$，每次被访问时计数器加一。
    f(p)←f(p)+1f(p) \leftarrow f(p) + 1
  2. 淘汰最小频次缺页时找出计数器值最小的页面作为换出对象。
    p∗=arg⁡min⁡p  f(p)\displaystyle p^* = \underset{p}{\arg\min} \; f(p)
  3. 平局处理若多个页面计数相同，通常借用 FIFO 或 LRU 规则打破平局。
    tie⇒按进入顺序淘汰\text{tie} \Rightarrow \text{按进入顺序淘汰}

Belady异常

小智一直以为“货架越大越好”，直到他亲眼看到诡异的一幕：在某个固定点单序列下，三层货架缺货 9 次，把货架加到四层，缺货次数反而升到 10 次！多了一个货位，缺货反而更多？这不科学！这个怪现象，就是著名的 Belady 异常，而元凶正是 FIFO 算法。

为什么 FIFO 会闹这种笑话？因为它“没有记忆”。四层货架时，它可能把某个“即将被点单”的原料提前挤走，导致后续一连串补货；而三层货架反而阴差阳错地避开了这个节奏。缺页率与内存大小不成单调关系，说明 FIFO 的置换决策与程序的访问模式完全脱节。

要杜绝 Belady 异常，算法必须是“栈式算法”——即页框数为 m 时的驻留集合，始终是页框数为 m+1 时驻留集合的子集。LRU 和 OPT（Optimal，理论最优）都是栈式算法。OPT 是一个“开了上帝视角”的算法：它事先知道整个访问序列，置换时永远选择“未来最久才会被用到”的页面。OPT 的缺页率是所有算法里最低的，但它需要预知未来，现实中无法实现，只能作为理论上限来参照。

Belady 异常让小智明白了一个道理：扔货策略必须“懂未来”或“懂历史”，机械地按先后顺序扔，迟早被命运捉弄。然而，现实中没人能预知未来，精确的 LRU 又太昂贵。Linux 内核给出的答案，是一种务实的折衷方案。

Sm(t)⊆Sm+1(t)⇒缺页次数随页框数增加而单调不增\displaystyle S_m(t) \subseteq S_{m+1}(t) \quad \Rightarrow \quad \text{缺页次数随页框数增加而单调不增}
栈式算法就像“越大的仓库越不会缺货”的保证书；FIFO 没有这份保证，所以会出现“仓库变大反而更缺货”的怪事。
  1. 栈式条件任意时刻，m 个页框的驻留页面集合必须是 m+1 个页框时驻留集合的子集，这是栈式算法的定义。
    Sm(t)⊆Sm+1(t)S_m(t) \subseteq S_{m+1}(t)
  2. FIFO 违反FIFO 的驻留集合不满足包含关系，因此存在某个时刻它的集合结构会“错位”，导致异常发生。
    ∃t:  Sm(t)⊈Sm+1(t)\exists t: \; S_m(t) \nsubseteq S_{m+1}(t)
  3. 单调结论栈式算法保证页框越多、缺页越少，缺页次数关于页框数是单调不增的。
    faults(m+1)≤faults(m)\text{faults}(m+1) \leq \text{faults}(m)

内核实战折衷

小智最终采纳了一套融合方案：把货架分成两个区——“热门区”和“冷门区”。新进的原料先放冷门区；被点过两次以上的，就“晋升”到热门区；需要腾地方时，优先从冷门区里扔。这样既不用给每箱原料精确计时，又能保证常客原料稳稳待在架上。这就是 Linux 内核著名的“活跃/非活跃链表”设计。

Linux 把物理页面分成两条链表：活跃链表（active list）和非活跃链表（inactive list）。页面首次调入时进入非活跃链表；在非活跃链表期间再次被访问，页面会“晋升”到活跃链表。活跃链表内的页面若长期未被访问，会逐渐“老化”并被降级回非活跃链表。当内存不足需要换页时，内核只从非活跃链表的尾部摘页——那里的页面既没被晋升，又最久未被访问，扔了最不心疼。

与教科书算法相比，这套机制是“近似 LRU”的工程实现：它不追求每个页面的精确访问时间，而是用“链表位置 + 访问位”粗粒度地区分冷热。内核还会周期性扫描整条链表，调整页面位置，模拟时钟指针的效果。代价是链表维护有额外开销，但换来了极好的扩展性——面对海量页面，它不会像精确 LRU 那样需要昂贵的硬件支持。

小智的热门/冷门双区货架，最终让奶茶店在有限的货架空间里，把补货次数降到了最低。从 FIFO 到 Linux 双链表，你看到的不仅是算法的演进，更是一个朴素的道理：资源有限时，真正的智慧不是记住一切，而是用最省力的方式，留住最有可能被需要的东西。

pout=tail(inactive_list)\displaystyle p_{\text{out}} = \text{tail}(\text{inactive\_list})
换出目标永远从非活跃链表尾部选取——那里是“既没晋升又最久没被碰”的页面，扔了损失最小。
  1. 非活跃链表尾部非活跃链表按访问时间排序，尾部存放的是最久未被访问且未晋升的页面，是换出的首选。
    pout=tail(inactive_list)p_{\text{out}} = \text{tail}(\text{inactive\_list})
  2. 晋升条件非活跃链表中的页面若发生第二次访问，就移动到活跃链表头部，获得长期驻留资格。
    ref(p)≥2⇒p→active_list\text{ref}(p) \geq 2 \Rightarrow p \to \text{active\_list}
  3. 降级老化活跃链表中的页面若在长时间内未被访问，会逐步移回非活跃链表，等待被淘汰。
    old_in_active⇒p→inactive_list\text{old\_in\_active} \Rightarrow p \to \text{inactive\_list}

AI 应用场景

vLLM 的 KV Cache 页面置换

阶段：大模型推理部署与优化

解决的问题：大模型推理时，每生成一个 token 都要读取全部历史 KV（键值）缓存，显存有限时缓存放不下，传统做法是整段预分配，导致显存碎片化、吞吐低下。vLLM 借鉴操作系统“分页”思想，把 KV Cache 切成固定大小的页，用类 LRU/前缀缓存的策略决定哪些页留在显存、哪些换出到 CPU 内存。

具体案例：运行 Llama-2-70B 服务的团队发现，同时服务 32 个请求时显存频繁溢出。接入 PagedAttention 页面管理后，KV 缓存按需分页分配，长期未命中的历史页被换出，热点前缀页被保留，吞吐量提升 2-4 倍。这里的“页命中率”优化，本质就是 LRU 置换思想在 AI 推理引擎中的重生。

Redis 缓存淘汰策略

阶段：AI 服务的特征缓存与结果缓存

解决的问题：AI 在线服务把特征向量、模型中间结果缓存到 Redis，内存耗尽时希望“扔最没价值的 key”。Redis 提供的 allkeys-lru 和 allkeys-lfu 策略，就是 LRU 与 LFU 的工业级应用：一个是“最久未访问先淘汰”，适合访问模式波动大的场景；一个是“访问次数最少先淘汰”，适用于访问分布稳定的推荐特征。

具体案例：某推荐系统把用户特征缓存进 Redis，初始用 allkeys-lru，热门用户特征频繁命中；后来发现有些小众但稳定的长尾特征频繁被挤掉，切换 allkeys-lfu 后缓存命中率提升 18%，平均延迟下降 40%。选 LRU 还是 LFU，取决于你的访问分布是“时间相关”还是“频率稳定”。

数据库 Buffer Pool 的冷热分区

阶段：训练与推理数据的存储访问

解决的问题：MySQL 的 InnoDB Buffer Pool 直接采用“改进版 LRU”：链表分为年轻区（young）和旧区（old），新读入的页面先进旧区，只有再次被访问才会晋升到年轻区。这能防止一次全表扫描把真正的热数据全部挤出缓存——对应文章里 Linux 活跃/非活跃链表的设计思想。

具体案例：某 AI 训练平台每天跑数据清洗任务，大表扫描频繁污染缓存，导致在线推理服务读取特征时磁盘 IO 飙升。调大 Buffer Pool 旧区比例后，扫描页被限制在旧区，热特征页稳定留在年轻区，查询 P99 延迟从 800ms 降到 120ms。

Python 演示

python58 行
def sim(name, refs, frames):    pages = []    last = {}    freq = {}    faults = 0    ptr = 0    refbits = {}    for t, p in enumerate(refs):        if p in pages:            last[p] = t            freq[p] += 1            if name == "Clock":                refbits[p] = 1            continue        faults += 1        if len(pages) < frames:            pages.append(p)        else:            if name == "FIFO":                old = pages.pop(0)            elif name == "LRU":                old = min(pages, key=lambda x: last[x])            elif name == "LFU":                old = min(pages, key=lambda x: (freq[x], last[x]))            else:  # Clock                while True:                    cur = pages[ptr]                    if refbits.get(cur, 0) == 0:                        old = pages.pop(ptr)                        break                    refbits[cur] = 0                    ptr = (ptr + 1) % len(pages)                ptr = ptr % frames            pages.remove(old)            pages.append(p)            if name == "Clock":                refbits.pop(old, None)        last[p] = t        freq[p] += 1        ptr = 0    return faults  def main():    refs = [7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1]    for name in ["FIFO", "LRU", "Clock", "LFU"]:        print(name, "faults:", sim(name, refs, 3))     belady = [1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5]    f3 = sim("FIFO", belady, 3)    f4 = sim("FIFO", belady, 4)    print("Belady FIFO frames=3:", f3, "frames=4:", f4)    if f4 > f3:        print("Belady anomaly reproduced: more frames, more faults!")  if __name__ == "__main__":    main()
目的：用同一段访存序列模拟 FIFO、LRU、Clock、LFU 四种页面置换算法，统计缺页次数，并复现著名的 Belady 异常。
  1. pages.append(p)新页面调入内存（货架有空位时直接上架）。
  2. old = pages.pop(0)FIFO 无情地把队首页面踢出，不管它最近是否被用过。
  3. old = min(pages, key=lambda x: last[x])LRU 挑“最久没被访问”的页面淘汰，这就是时间戳投票。
  4. refbits.get(cur, 0) == 0Clock 扫描时发现便利贴（访问位）为空，立刻换出。
  5. refbits[cur] = 0遇到有勾的页面先擦掉勾，再给一次机会，这就是“二次机会”的兑现。
  6. old = min(pages, key=lambda x: (freq[x], last[x]))LFU 先比访问次数，再比最近访问时间，破平局。
  7. if f4 > f3: print("Belady anomaly...")检测到 4 个页框的缺页数反而大于 3 个页框，复现非栈式算法的反直觉现象。

常见误区

误区总以为加内存条一定能提升一切性能，缺页率必然下降。既然页框多了能装更多页面，怎么可能更差？

正解这对栈式算法（LRU、OPT）成立，但对 FIFO 不成立。Belady 异常表明，FIFO 在页框从 3 增加到 4 时，缺页次数可能从 9 涨到 10。因为 FIFO 的驻留集不满足“栈包含关系”，多出来的页框反而扰乱了淘汰节奏。就像奶茶店多加一层货架，却因为机械的先进先出规则，把更需要的原料挤走了。

为何常见：直觉上“空间多总比少好”，大多数人没意识到置换策略本身可能违背单调性，只有学习 Belady 具体反例后才会真正理解。

误区看到 LRU 的“Least Recently Used“，以为它淘汰的是”用得最少的页面”，用次数多少来判断。

正解LRU 看的不是次数，而是“最近一次访问的时间”——哪怕一个页面被访问过 1000 次，只要它最近一分钟没被碰，就可能被淘汰；相反，一个刚被访问的页面哪怕只被用过两次，也会被保全。数次数的是 LFU。两者的区别就像“谁最后离开座位”（LRU）与“谁来得最少”（LFU）。

为何常见：中文翻译“最近最少使用”有歧义，容易让人联想到“频率最少”；而人们日常生活中也更习惯用“次数”衡量价值。

误区看到 Clock 用环形队列扫描，觉得它只是把 FIFO 的直线队列弯成一个圈，本质还是先进先出。

正解Clock 的访问位机制提供了“第二次机会”，完全改变了淘汰逻辑：访问位为 1 的页面会被清位并跳过，相当于被访问过的页面能活过至少一轮扫描。它的命中率明显高于 FIFO，更接近 LRU。如果所有页面访问位都为 0，Clock 才退化为 FIFO。

为何常见：初学者容易只看到“环”的外形，忽略“访问位”这个核心机制；同时 Clock 的实现确实沿用了 FIFO 的指针结构，容易造成误解。

误区LFU 记录了长期频次，听起来比 LRU 的“一时记忆”更全面，所以一定更优。

正解LFU 的计数器是“历史包袱”：一个曾经高频、如今冷门的页面会永远霸占货架；而一个即将爆发的“新晋页面”因为计数值低，会在爆发前被提前淘汰。LFU 还需要计数器溢出处理和定期老化，复杂度高。实际效果取决于访问模式：稳定分布下 LFU 好，突发热点下 LRU 好。没有绝对的王者。

为何常见：“频率”比“时间”听起来更有统计意义，人们容易忽略程序访问的“时间局部性”才是最重要的规律。

面试题

Q1. 当进程访问的页面不在物理内存中，且内存已满时，操作系统会执行什么操作？

单选题 · easy

  • A.直接终止进程
  • B.触发缺页中断并执行页面置换← 正确答案
  • C.增大物理内存
  • D.忽略这次访问

答案：B。页面不在内存时硬件触发缺页中断，内存已满则先执行页面置换换出一个旧页，再调入新页。就像奶茶店货架满了需要先扔一箱原料才能放新货。终止进程或忽略访问都会导致程序出错，增大物理内存不是操作系统运行时能做的事。

Q2. FIFO 页面置换算法选择哪个页面作为换出对象？

单选题 · easy

  • A.最近最少使用的页面
  • B.使用次数最少的页面
  • C.最早进入内存的页面← 正确答案
  • D.未来最久才用到的页面

答案：C。FIFO 按进入内存的先后顺序排队，队首是最早进入的页面，缺页时直接换出队首。它不关心访问时间和频率，就像传送带上最先放上货架的商品最先被挤下去。

Q3. LRU 算法淘汰页面的依据是？

单选题 · easy

  • A.页面进入内存的时间
  • B.页面被访问的总次数
  • C.页面最近一次被访问的时间← 正确答案
  • D.页面在磁盘上的位置

答案：C。LRU 全称 Least Recently Used，记录每个页面最近一次被访问的时间戳，缺页时淘汰时间戳最小（最久未使用）的页面。它讲的是“谁最久没被碰过”，而不是“谁来得最早”或“谁用得最少”。

Q4. 以下哪种算法可能出现 Belady 异常（页框增加反而缺页增多）？

单选题 · mid

  • A.LRU
  • B.OPT
  • C.FIFO← 正确答案
  • D.所有栈式算法

答案：C。Belady 异常的本质是算法不是栈式的，驻留集不满足包含关系，FIFO 是最著名的例子。LRU 和 OPT 都是栈式算法，保证缺页次数随页框增加单调不增，不可能出现“货架变大反而更缺货”的怪现象。

Q5. 下列哪些属于栈式页面置换算法？

多选题 · mid

  • A.LRU← 正确答案
  • B.OPT← 正确答案
  • C.FIFO
  • D.LFU

答案：AB。栈式算法要求 m 个页框的驻留集是 m+1 个页框驻留集的子集，LRU 和 OPT 满足这一性质，因此不会出现 Belady 异常。FIFO 和 LFU 不满足包含关系，页框增加时缺页次数可能不降反升。

Q6. Clock 算法扫描页面时，遇到访问位为 1 的页面会怎么处理？

单选题 · mid

  • A.立即换出该页面
  • B.将该页访问位清 0 并继续扫描← 正确答案
  • C.将该页访问位置 1 并继续扫描
  • D.直接跳过但不修改访问位

答案：B。访问位为 1 表示该页最近被访问过，Clock 会把它清成 0 并继续向前扫描，相当于多给一次机会。只有遇到访问位为 0 的页面才会换出，这就是“二次机会算法”名称的由来。

Q7. 关于缺页率，下列说法正确的有哪些？

多选题 · mid

  • A.缺页率 = 缺页次数 / 总访存次数← 正确答案
  • B.FIFO 算法下增加页框数一定能降低缺页率
  • C.程序局部性越好，缺页率通常越低← 正确答案
  • D.缺页率与置换算法无关

答案：AC。缺页率就是缺页中断次数占总访存次数的比例；程序的时间局部性越好，热页越集中，置换算法越容易保命中。FIFO 可能触发 Belady 异常，增加页框不一定降低缺页率；置换算法直接决定缺页率高低，不能选 D。

Q8. Linux 的活跃/非活跃链表设计中，页面从活跃链表回到非活跃链表的过程叫什么？

单选题 · hard

  • A.晋升
  • B.老化降级← 正确答案
  • C.换出
  • D.缺页

答案：B。活跃链表中的页面若长时间未被访问，会被逐步“老化”并移回非活跃链表，等待后续换出。晋升恰好相反，是页面从非活跃链表升入活跃链表的过程。换出是最终把页面写回磁盘，缺页是页面不在内存的触发事件。

Q9. 关于 LFU 算法的缺陷，以下说法正确的有？

多选题 · hard

  • A.新晋热门页面可能因计数值低而被提前淘汰← 正确答案
  • B.计数器需要处理溢出问题← 正确答案
  • C.时间局部性强的程序下 LFU 永远优于 LRU
  • D.LFU 不需要记录任何访问信息

答案：AB。LFU 的计数器从 0 起步，新晋页面频次低容易被误杀，这是“冷启动问题”；计数器持续累加会溢出，需要定期衰减或特殊处理。LFU 适合稳定访问分布，对突发热点反而吃亏，不能说永远优于 LRU；LFU 必须维护计数器，D 明显错误。

Q10. 在同一个访问序列上比较 OPT 与 LRU 的缺页次数，下列关系恒成立的是？

单选题 · extreme

  • A.OPT 的缺页次数总是小于等于 LRU← 正确答案
  • B.LRU 的缺页次数总是小于等于 OPT
  • C.两者总是相等
  • D.两者无法比较

答案：A。OPT（Optimal）拥有“预知未来”的能力，每次替换都选择未来最久才被用到的页面，它是所有置换算法的理论下界，任何算法（包括 LRU）的缺页次数都不可能少于 OPT。因此 OPT 的缺页次数恒小于等于 LRU。它是理论标杆，现实中无法实现。