页面置换算法详解：从LRU到Clock，操作系统内存优化的核心

内存不够用的时候，操作系统到底在忙什么？很多时候你盯着一个无响应的小球转圈，背后极有可能就是操作系统在内存和磁盘之间疯狂搬运页面，也就是在做页面置换（淘汰）算法该干的事。在内存管理这摊事里，页面置换算法是那种平时看不见、一卡顿就背锅的角色。这期我就围绕页面置换算法，从原理到代码到实际踩坑，一次说透，给做操作系统实验的、考研复习的、或者单纯想搞懂内存机制的兄弟们一份能直接用的参考。

1. 为什么操作系统要把页面“请”出内存

1.1 从一次内存不够说起

先想一个场景：你开着一台16G内存的电脑，IDE里挂着三四个服务，浏览器开了二十多个标签页，后台还跑着微信和音乐播放器。内存总量是有限的，但程序要的内存是无上限的，这时候操作系统就得想办法让“看起来不卡”。

它想出来的办法就是虚拟内存。每个进程都有自己的虚拟地址空间，按固定大小切成页，比如4KB一页；物理内存也切成同样大小的页框。进程真正运行的时候，并不需要把所有页都加载到内存里，只需要加载正在用的那一部分。这就是“按需调页”。

问题来了：物理内存被占满之后，你还要去访问一个不在内存里的页，操作系统必须从磁盘把这一页读进来。可是内存已经没有空位了，它就必须先挑一个已经在内存里的页，把它写回磁盘或者干脆丢掉（如果这页没被修改过），腾出地方给新页用。这个“挑一个页踢出去”的动作，就叫做页面置换，也叫页面淘汰。

被踢出去的页如果之后又被访问到了，就得再一次从磁盘读进来。频次一高，系统就会一直处于“等磁盘”的状态，CPU空转，用户感知就是卡成PPT。这就是“抖动”（Thrashing）。所以页面置换算法最核心的KPI只有一个：尽量降低缺页率。谁能让缺页率更低，谁就是好算法。

1.2 页面置换的终极目标不是“换出去”，是“少换”

很多初学者会理解错方向，以为页面置换算法是在比“怎么把页面换出去换得更快”。其实不是。页面置换真正的目标，是预测哪一个页面在未来最长时间内不会被访问，或者叫“最不可能被用到”的页面。把这种页面踢出去，未来很长时间都不需要把它调回来，缺页的次数自然少了。

这里面有个理论基础叫“局部性原理”，分两个层面。时间局部性：如果一个页面刚刚被访问过，那么它在不远的将来很可能再次被访问。典型例子就是循环体里的代码和数据，一直在反复用。空间局部性：如果一个页面被访问了，那么它邻近地址的页面很可能在不久的将来也会被访问。典型例子是数组遍历、顺序执行的代码。所有的置换算法，本质上都是在用“过去”和“现在”的信息，去猜测“未来”的访问规律。有的猜得准，有的猜得糙，差别就是缺页率。

所以就有一个很重要的认知：不存在一个能在所有访问序列下都最优的在线算法。你只能根据访问模式挑最合适的。

2. 四大经典置换算法的原理与取舍

2.1 最好也是最难的：最佳置换（OPT）

最佳置换算法是一个理想化的算法。它的思想很直接：当需要淘汰页面时，选择将来最长时间不会被访问的页面淘汰。

这个算法如果真能实现，缺页率一定是最低的。它就像是你知道未来所有彩票号码之后再去买彩票，思路无敌。但问题也恰恰在这里，操作系统预知不了未来。你根本不知道每个页面下一次访问是什么时候，除非你提前跑一遍整个程序，记录完整的访问序列，但那意味着你得先把整个程序完整执行一遍，这本身就不现实。

所以，OPT算法在实操中是不能直接实现的。但它有一个不可替代的价值：用来做基准测试。你在实验环境里跑一组访问序列，记录下OPT的缺页次数，拿这个数字当“理论最低值”，再看你实际实现的算法离这个最优值差了多远。如果你的LRU和OPT差不多，说明这组数据的局部性很好；如果差很多，说明你的算法在应对这组数据时有明显短板。

2.2 简单到不行的：先进先出（FIFO）

FIFO是最简单的置换算法，思路就是谁先进来谁先走。用一个队列就能实现，新页面从队尾入队，淘汰的时候从队头出队。

FIFO实现代价极低，但它的缺陷也很致命。它完全无视了访问频率和访问时间。一个被访问了一万次的热门页面，只要它是最先进来的，也会被第一个踢出去。踢出去之后马上又要用，又得从磁盘调回来，系统就来回折腾，缺页率拉满。更离谱的是，FIFO还有一个著名的反直觉现象——Belady异常：增大物理内存块数，缺页次数反而增加。后面我单独说这个问题。

现在的操作系统里几乎不会直接用FIFO做置换算法，但FIFO的思想在各种缓存淘汰里还是有身影的，尤其在一些实现成本受限的嵌入式场景里，偶尔能看见它的变体。

2.3 最常用的标尺：最近最少使用（LRU）

LRU（Least Recently Used）是目前最广为人知、也被研究得最透的置换算法。它的规则很符合直觉：当需要淘汰页面时，选择最长时间没有被访问的页面淘汰。

它的依据是“过去的一段历史时间中，最久没被使用的页，在未来最不可能立刻被用”。这依据的是时间局部性原理。你想想自己平时开软件的习惯：最近一直用的Word，你不可能马上关掉它；反而是那个一个月前打开过一次、之后再没碰过的PS，最可能被关掉。LRU就是在干这件事。

理论上说，如果用“完美LRU”，也就是每次访问都精确记录时间戳，淘汰时找最老的那个，那么在模拟环境下它的缺页率非常接近OPT，而且不会出现Belady异常。但问题在于，完美LRU的实现开销极大。每次内存访问都要更新时间戳，每次淘汰都要遍历所有页面找最小值，这在真正的操作系统里是不可接受的。所以工业界普遍用“近似LRU”来替代完美LRU，最经典的就是Clock算法。

2.4 工业界的常客：Clock（第二次机会）算法

Clock算法，也叫第二次机会算法，是操作系统教科书和真实内核里出镜率最高的置换算法。它的原理是这样的：把物理页框想象成一个环形缓冲区，每个页框都有一个“访问位”（referenced bit）。页面被访问时，硬件会把访问位置为1。当需要淘汰页面时，指针从当前位置开始循环扫描：

• 如果访问位为1，表示这个页面最近被用过，把它改成0，指针继续往下走；
• 如果访问位为0，表示这个页面最近没被用过，选它淘汰。

这一圈下来，每个页面其实都有“第二次机会”。第一次被指针扫到的时候，如果它被访问过，就只把访问位清零、不淘汰它，相当于“缓刑”一次。如果它在下一轮扫描之前又被访问了，那访问位又会变成1，继续缓刑。

这就是“近似LRU”的精髓：它没有精确记录每个页面最后访问的时间，只用一位二进制数来区分“最近被用过”和“最近没被用过”。牺牲了一定的精确度，换来了极低的实现开销。你可以把访问位想象成“最近过得好不好”的一个粗略标记，1是好，0是一般。CLOCK挑的一般是那些“最近过得最一般”的页面。

在Linux内核里，早期版本用的是一个叫“第二次机会”的变体，后来演变成了更精细的多队列近似LRU。但无论怎么变，核心思想都是Clock的环形扫描。

2.5 差点被遗忘的：最不经常使用（LFU）

LFU（Least Frequently Used）的核心思想是：淘汰访问次数最少的页面。它的逻辑也不是没道理，如果一个页面被访问的次数很少，说明它大概率不是热点，淘汰它对性能影响最小。

实现上，LFU需要给每个页面维护一个计数器，每被访问一次就加一，淘汰的时候选计数器最小的。听起来简单，但有两个麻烦的问题：

第一，计数器可能会溢出。一个页面如果从进程启动开始就被反复访问，计数可以涨到很大，得考虑如何处理溢出的情况。第二，历史权重大高的问题。一个页面早期被访问了1000次，但最近已经完全不用了，它的计数还是很高的，导致它永远不会被淘汰，白白占着内存，这就叫“陈旧热点”问题。

解决陈旧热点问题的办法也有，比如定期把计数器减半，或者用滑动窗口记录“最近一段时间内的访问次数”，但这又增加了实现复杂度。所以LFU在操作系统内核的页面置换场景里反而用得不多，更多的出现在数据库缓存、Redis缓存淘汰里，而且通常要配衰减策略一起用。

2.6 一张表看清各算法的脾气

3. 实现层的关键细节与数据结构的选择

3.1 LRU的真正难点：时间戳怎么记录才不贵

很多人在实验课里实现LRU，第一反应是给每个页框加一个时间戳字段，每次访问时记录下当前时间（或者一个自增计数），淘汰时线性扫描所有页框，找到时间戳最小的那个淘汰。

这个方法在页框数量少的时候没问题。比如只有32个页框，每次淘汰前遍历一遍，32次比较，完全可以接受。但你想一下真实系统的场景：物理内存可能有几十GB，按4KB一页算就是几百万甚至上千万个页框。每次淘汰都遍历一遍几百万个条目找最小值，这个代价是不可接受的。页面置换是发生在缺页异常处理路径里的，这个路径本身就是系统最关键的路径，任何多余操作都会放大延迟。

所以完美LRU在真实系统里是不会实现的。它只存在于模拟环境或教学实验里。你在实验课里写一个纯模拟的LRU，线性扫表没问题，但要心里清楚，这只是在数据量小的场景下成立的做法。

如果你真的要在工程里实现一个接近LRU的效果，常见的做法是维护一个双向链表加哈希表。哈希表负责O(1)时间定位到某个页面对应的链表节点，双向链表负责维护页面访问的“新旧顺序”。每次访问某个页面，就把这个节点从当前位置摘下来，移到链表的头部。淘汰的时候，直接淘汰链表尾部的节点，时间复杂度只有O(1)。这其实是“最近最久未使用”这个语义的精确实现方式，但代价是每次内存访问都必须维护链表结构，这在硬件Cache这类场景里不合适，在软件缓存（比如Redis的近似LRU）里倒是很常见。

3.2 Clock算法为什么用“近似LRU”而不是精确LRU

完美的LRU需要知道所有页面“谁新谁旧”的完整顺序，这个顺序信息量是很大的。你每访问一次页面，这个顺序就得变一次。如果要精确维护，开销和复杂度都会很高。

Clock算法的聪明之处在于它只问一个问题：这个页面在最近的一个扫描周期里有没有被访问过？只需要一位二进制数来回答。这一位由硬件的访问位提供，操作系统在页面被加载时把访问位清零，后续CPU访问这个页面的时候，硬件会自动把访问位置1，操作系统完全不需要额外插手。只有在发生缺页的时候，Clock算法才需要启动扫描，平时是完全无开销的。

这就体现了工程上的一个核心折衷思路：与其追求完美的信息量，不如用足够好且代价低的信息做决策。你可以把Clock算法理解成一个“粗粒度”的LRU：它不是精确记得每个页面最后访问的时间点，而是粗略判断“最近这一圈里你有没有被用过”。这个粗糙判断在绝大多数场景下，效果已经足够接近精确LRU了，但实现代价差了不止一个数量级。

3.3 访问位的位数、脏页位与回写时机

真实系统中的页表项里，除了访问位，还有一个很重要的“脏位”（dirty bit）。如果一个页面被修改过，也就是脏位为1，那么它在被淘汰的时候必须把内容写回磁盘，这个操作是昂贵的。反之，如果页面是干净的（读入后从未被修改），那淘汰的时候可以直接丢弃，不需要写回磁盘，相当于省了一次磁盘写操作。

这一点对置换算法的设计影响很大。在Clock扫描时，如果你遇到一个访问位为0、脏位也为0的页面，那是最理想的淘汰目标——它不用回写磁盘，直接释放页框就行。如果遇到访问位为0、但脏位为1的页面，淘汰它需要先把内容写回磁盘，代价更贵。

为了处理这种差异，有些改进型算法会做两轮扫描：第一轮优先找“干净且未访问”的页面；如果找不到，再降级找“脏但未访问”的页面。这就是所谓的Enhanced Clock算法，它把访问位和脏位组合成四种状态，优先淘汰状态最好的页面。这在实际系统里是很有价值的优化，因为“淘汰一个干净页面”比“淘汰一个脏页面”快得多，毕竟后者要等磁盘写完成才敢释放页框。

4. 手写一遍：页面置换算法的代码级实现

4.1 LRU：用一个双向链表加哈希表

先看一个精确LRU的工程化实现思路。我用C++写了一个极简版，展示核心数据结构与逻辑。这个思路你在很多地方都能看到，比如现在各大厂面试的LRU Cache题，考的就是这个。

#include <iostream> #include <list> #include <unordered_map> #include <vector> class LRUCache { private: int cap; // 链表存页面号（也可以存实际数据），链表头表示最近使用，链表尾表示最久未使用 std::list<int> lruList; // 哈希表映射：页面号 -> 链表中的迭代器 std::unordered_map<int, std::list<int>::iterator> mp; public: explicit LRUCache(int capacity) : cap(capacity) {} void access(int pageNum) { auto it = mp.find(pageNum); if (it != mp.end()) { // 页面已在内存中：把它移到链表头部，表示刚被访问过 lruList.erase(it->second); lruList.push_front(pageNum); it->second = lruList.begin(); } else { // 页面不在内存中：缺页，得调页进来 if (lruList.size() == (size_t)cap) { // 内存已满，淘汰链表末尾页面 int victim = lruList.back(); lruList.pop_back(); mp.erase(victim); } lruList.push_front(pageNum); mp[pageNum] = lruList.begin(); } } void printStatus() { for (int page : lruList) { std::cout << page << " "; } std::cout << std::endl; } };

这个实现的核心就是：链表维护“最近使用顺序”，哈希表维护“页面号到链表节点的定位”。每次访问都能在O(1)时间内完成定位和调整。淘汰的时候删链表尾部就能得到“最久没用过的页面”。

你可以用下面这个简单的访问序列测试：

int main() { LRUCache cache(3); std::vector<int> requests = {1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5}; for (int r : requests) { std::cout << "访问 " << r << " -> "; cache.access(r); cache.printStatus(); } return 0; }

观察一下 4 访问之后，1 被淘汰了，因为它是当前最久没被访问的。这就是LRU的直观淘汰行为。

4.2 Clock：一个环形指针的优雅实现

Clock算法用代码实现起来更贴近真实操作系统。它的核心结构是一个页框数组加一个环形指针。我写一个可运行的简化版本：

#include <iostream> #include <vector> class ClockAlgorithm { private: struct Frame { int pageNum; // 存储的页面号，-1 表示空 bool referenced; // 访问位 bool dirty; // 脏位，这里就简化成一起管理了 }; std::vector<Frame> frames; int hand; // 环形指针 public: explicit ClockAlgorithm(int frameCount) : frames(frameCount), hand(0) { for (auto &f : frames) { f.pageNum = -1; f.referenced = false; f.dirty = false; } } bool isHit(int pageNum) { for (auto &f : frames) { if (f.pageNum == pageNum) return true; } return false; } void access(int pageNum, bool dirtyWrite) { // 检查是否命中 for (auto &f : frames) { if (f.pageNum == pageNum) { f.referenced = true; if (dirtyWrite) f.dirty = true; std::cout << "命中页面 " << pageNum << std::endl; return; } } // 缺页，需要找到一个victim while (true) { Frame &f = frames[hand]; if (f.pageNum == -1) { // 空页框，直接使用 f.pageNum = pageNum; f.referenced = true; f.dirty = dirtyWrite; std::cout << "缺页，装入空页框 " << hand << "，页面 " << pageNum << std::endl; hand = (hand + 1) % frames.size(); return; } if (f.referenced) { // 有访问位，给它第二次机会 f.referenced = false; hand = (hand + 1) % frames.size(); std::cout << "页面 " << f.pageNum << " 被暂停淘汰（访问位清零）" << std::endl; } else { // 访问位为0，淘汰 int oldPage = f.pageNum; f.pageNum = pageNum; f.referenced = true; f.dirty = dirtyWrite; std::cout << "淘汰页面 " << oldPage << "（第 " << hand << " 个页框），装入 " << pageNum << std::endl; hand = (hand + 1) % frames.size(); return; } } } void print() { for (int i = 0; i < (int)frames.size(); ++i) { std::cout << "[" << i << "] 页面=" << frames[i].pageNum << " 访问位=" << frames[i].referenced << " 脏位=" << frames[i].dirty << std::endl; } } };

clock的核心在于“转圈”的指针。每次扫描到过访问位的页面，只清零不淘汰，这个页面就获得了第二次机会。这也解释了为什么这个算法叫“第二次机会”算法——它不会因为你过去访问过就让你一直占着坑，但也不会因为你仅仅一次没被访问就马上把你踢出去。

有一说一，这个算法在面试里也很常考，重点是你要理解指针的移动方式，以及访问位清零的意义。

5. 实战中我踩过的坑和常见问题排查

5.1 Belady异常：FIFO的反直觉表现

有些算法存在一个很反直觉的现象：物理内存的页框数增加，按理说缺页应该更少，但FIFO在某些访问序列下，缺页反而更多。这就是Belady异常。

举个例子。假设访问序列是：1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5。在页框数=3时，FIFO会缺页9次；把页框数增加到4，FIFO反而缺页10次。是的，你没看错，加了内存，缺页反而变多了。

原因是FIFO不了解页面的访问频率，只按进内存的先后顺序淘汰。增加页框数可能让某个本应该被淘汰的页面多待了一段时间，反而把热门的顶掉了。这正是“呆板”的代价。

对比来看，LRU和Clock这类基于访问历史的算法，都具备“栈特性”，严格满足“多分配内存不缺页更多”的性质，不会出现Belady异常。这也是为什么它们更适合做通用置换算法。

5.2 LRU在扫描场景下的退化

LRU在大多数场景下表现很好，但有一种场景会让它非常难受，就是顺序扫描，也叫全表扫描。想象一个数据库要做一个全表扫描，它会依次访问表里的每一个页。假设内存只能装下10个页，而表有1000个页。LRU会把内存里的页面按最近访问时间排好序，新读进来的页不断成为“最新”，而之前读进来的页很快就成了“最旧”，结果就是每个新页面都会挤掉一个未来的页面。也就是说，每一页都只被使用一次，然后就再也没有被访问的机会了。

这种情况下，LRU的缺页率几乎是灾难性的——每次访问都缺页，内存形同虚设。这不是LRU逻辑错了，而是它假设“最近访问的很可能再次访问”，但顺序扫描恰恰不满足这个假设。

实际应对策略有几种：把LRU换成LFU变体，让高频页面留下来；或者对扫描行为进行检测，识别出顺序访问并直接用预取策略；或者用Clock这种粗糙的近似算法，因为它在扫描场景下反而不会那么极端。所以做系统设计时，你必须知道你面对的工作负载长什么样，没有银弹。

5.3 抖动（Thrashing）与工作集模型

如果你机器上开了一堆应用，每个都占很多内存，总需求远超物理内存，那系统就会陷入一个恶性循环：页面刚被换出去，马上又要使用，又得调回来；调回来同时又把另一个正在用的页面挤出去。CPU大量时间花在等待磁盘I/O上，利用率反而暴跌。这就是抖动。

抖动不是单个置换算法能解决的，它是一个系统级的问题。解决抖动的经典思路是“工作集模型”。工作集是一个进程在最近一段时间内实际访问过的页面集合。如果每个进程的工作集总大小不超过物理内存，系统就能稳定运行；如果超过了，就需要把某个进程挂起或者交换出内存，宁可牺牲一个进程，也保住其余进程。

所以你看，页面置换算法管的是“在内存满了选谁淘汰”，但真正解决系统性问题的，是在更高维度做内存调度和准入控制。这两者要配合才能发挥效果。

5.4 想清楚你的访问特征再选算法

经过上面这些分析，你会得到一个实际项目里非常重要的教训：选置换算法之前，先分析你的访问模式。

如果访问序列以循环为主，热点集中，LFU或增强型Clock效果不错；如果访问序列有很强的突发性，LRU的近似实现会更好；如果有大量的顺序扫描，你得考虑预取策略，纯粹靠置换算法是兜不住的；如果Cache被用在数据库里，还得考虑访问频率和访问时间两者的权衡，这时候可能要多级队列混合算法。

我在接手一个内存系统调优任务的时候，第一步永远是把访问日志拉出来，统计页面的访问频次分布、相邻访问的时间间隔、重复访问的最大间隔。有了这些数据，再选算法，基本不会跑偏。盲目套一个看起来很高级的算法，最后效果可能还不如一个简简单单的Clock。

6. 页面置换算法在现代系统里的活法

6.1 操作系统内核是怎么做的

现代Linux内核早就不是单一的Clock算法，而是用了一套更复杂的方案。早期2.4内核用过Clock，后来演进到2.6，用LRU链表的方式管理内存页，把物理页框分成active链表和inactive链表，页面在两个链表之间移动。页面在inactive链表被访问，会晋升到active；在active链表里长期没被访问，会降级到inactive。淘汰的时候优先从inactive链表的尾部挑。

再后来，内存页管理又加入了“每个NUMA节点独立管理”“文件页与匿名页分类处理”等机制。文件页可以干净释放，匿名页可能需要回写。这些细节让真实系统的内存管理变得非常复杂，但底层的逻辑还是那些基础算法的组合变体。

换句话说，你在课本上学到的FIFO、LRU、Clock、LFU，并不是过时知识，而是为理解真实系统打底的基础。真正工程系统里的算法，都是在这些基础上的扩展和组合。

6.2 Redis、数据库、浏览器都在用

页面置换的思想不只存在于操作系统里，几乎每一个有“缓存”概念的系统都在用它。Redis的缓存淘汰策略里就有近似LRU、LFU两种可选。Redis的近似LRU抽样部分key来模拟LRU排序，而不是全量排序，这样可以节省大量内存和时间。Redis 4.0之后提供的LFU策略，则是在LRU基础上增加了访问频次的概念，适合某些特定热度的负载。

数据库缓冲池的页面管理也是一个典型的置换算法应用场。数据库不会让每一脏页立刻落盘，而是在Buffer Pool里维护一批页面，满了就按LRU或改进算法淘汰。数据库的经典问题“随机I/O变成顺序I/O”，很大程度上靠的就是页面置换算法帮忙把频繁使用的页面留在Buffer Pool里。再往宏观了说，CDN的缓存淘汰、浏览器的磁盘缓存，底层都是这套思想。

6.3 算法选型背后最核心的判断维度

如果我只给你一条判断算法好坏的标准，我会说：请先定义你的成本函数。淘汰一个干净页面和淘汰一个脏页面的成本差距很大，查找一个LRU节点的成本在不同数据结构下的差距也很大，而你能够容忍多少额外开销来维持淘汰的准确度，决定了算法选型的最终答案。

如果你在做嵌入式设备，内存极小，CPU性能也弱，Clock这种低开销近似算法可能比复杂ML算法靠谱得多。如果你在做数据库缓存表，内存够大，热点集中，LFU再加衰减反而效果更好。如果你在写一个内存池、自研Cache，那完美的LRU配合哈希表加链表可能是最稳妥的选择。

在硬件越来越快、内存容量越来越大的今天，有的朋友会觉得页面置换算法不重要了。其实恰恰相反，内存越来越大，但软件跑得也越来越重，虚拟化、容器、大模型推理都会对内存管理提出更高要求。在内存稀缺到不能再稀缺的场景里，置换算法依然是决定用户体验的核心杠杆之一。

我自己在实际项目里做过一轮缓存命中率调优，把原来的纯LRU改成了带脏页优先淘汰的Clock变体，命中率提升了大概3到5个百分点，别小看这3个百分点，在数据库场景里直接省下了好几个G的I/O压力。踩过几次坑之后，我对页面置换算法的态度一直很明确：先理解访问特征，再动手选算法，不要拿着最火的算法硬套。