扫码获取 VIP 码
添加管理员微信获取 VIP 码
摘要：页面置换算法是软考操作系统板块的高频考点，每年都换着花样出题。但多数考生只会背几个名词，一到考试就翻车。这篇文章从虚拟存储的底层原理讲起，把四种置换算法的执行流程、命中判定、Belady异常现象和CLOCK改进机制掰开揉碎，再对照历年真题逐题拆解。读完这篇文章，你能闭着眼睛算出任何一道页面置换的缺页次数，拿到这几分稳稳的。
现代操作系统都采用虚拟内存技术，它让程序员觉得自己拥有一片连续的、容量巨大的地址空间，而实际上物理内存可能只有几个GB，远远装不下所有进程的代码和数据。虚拟内存的精妙之处在于按需调页——程序运行时，只有当前即将执行的指令和数据所在的页面才被加载到物理内存中，其余全部留在磁盘上。磁盘上存放这些页面的区域称为交换区或对换空间，扮演着物理内存后备仓库的角色。
当CPU要访问的指令或数据不在物理内存中时，就会触发缺页中断，操作系统暂停当前进程，从磁盘上把缺失的页面调入内存。但内存是有限的——假设物理内存只能容纳四个页面，而进程有十个页面，当四个物理页框全部被占满、第五个页面又要进来时，操作系统必须做出选择：把哪个旧页面踢出去？这个"踢谁"的决策就是页面置换算法的全部内涵。选得好，缺页次数少，系统运行流畅；选得不好，刚踢出去的页面下一秒又要访问，性能断崖式下跌。
理解这个场景的关键在于认识页面置换的"被动性"——只有在物理页框满载且新页面必须进入时才触发。如果页框有空位，直接放进去就行了，根本不需要置换。软考命题人经常在此挖坑，很多考生把"有空位时直接装入"误算成一次页面置换，全题崩盘。记住：只有满载时才置换，有空位时只算装入不算置换。
从宏观机制来看，页面置换算法就是一个决策函数，输入是内存当前状态和访问序列，输出是被淘汰页面的编号。当一个逻辑地址被CPU访问时，硬件先查快表TLB，TLB命中则直接翻译出物理地址；未命中则查内存中的页表。如果页表项中的存在位显示该页在内存中，把页号加载到TLB中继续访问。如果存在位显示该页不在内存中——这就是缺页——CPU触发缺页异常，控制权交给操作系统。
操作系统首先检查是否有空闲页框。如果有，直接从磁盘读入所需页面，更新页表项，返回被中断的指令重新执行。如果没有空闲页框，置换算法正式登场。算法选出一个"牺牲页"之后，需要判断这个牺牲页是否被修改过。如果修改位是脏的，说明内存副本与磁盘不一致，必须先写回磁盘交换区才能腾出位置。如果修改位是干净的，直接覆盖即可，省去一次磁盘写入。这个"脏页写回"的细节看似微小，对置换效率影响却很大，这也是改进型CLOCK算法多维护一个修改位的根本原因。
牺牲页处理完毕后，新页面从磁盘调入空闲出来的页框，页表项被更新。值得留意的是，页表项中通常还维护一个访问位——每次页面被读或写，硬件自动将该位置为1。这个访问位是LRU和CLOCK家族算法的核心信息来源。反过来讲，FIFO完全不理访问位，只看谁先来后到，这也是它表现糟糕的根源。OPT则更离谱，它需要知道未来的访问序列，在真实系统中根本无法实现，纯属理论标杆。
整个置换流程中最耗时的环节是磁盘读写。一次磁盘I/O的延迟通常在几毫秒级别，而CPU执行一条指令只需要零点几纳秒，差距在百万倍以上。缺页率每升高一个百分点，程序运行时间就可能延长数秒。所以缺页次数直接量化了算法好与坏。软考反复考察的就是给定一个页面走向序列和固定数量的物理页框，手算OPT、FIFO、LRU三种算法的缺页次数并比较优劣。
最佳置换算法的逻辑一句话概括：淘汰在未来最长时间内不再被访问的页面。假设内存中有页面零、一、三，即将到来的访问序列是零、二、零、一、三、二。OPT逐一审视内存中每个页面，分别找出它们下一次被访问的位置。页面零下一次在第一位被访问，页面一在第四位，页面三在第五位。那么页面三就是"下一次访问最晚到来"的那个，被选中淘汰。如果某个页面从此再也不会被访问了，"下次访问位置"视为无穷大，必然优先淘汰。
为什么OPT无法实现？因为它需要预知整个访问序列，等于要求操作系统知道程序未来每一步将访问哪个地址。程序的访存行为受输入数据、分支预测等多重因素影响，没人能提前知道。OPT的真正价值在于提供了置换效率的上界：没有任何算法可以比OPT产生更少的缺页次数。在考试中，OPT的计算结果用作评判其他算法的基准，命题人最爱让你先算出OPT的缺页数，再比较FIFO和LRU比OPT多缺了多少页。
FIFO算法的逻辑和食堂排队一模一样：谁最早进来谁最早出去。操作系统维护一个队列，每当新页面装入时把它挂在队尾，需要置换时把队首的页面踢出去。这个队列可以用链表实现，也可以用数组加头尾指针实现，时间复杂度是常数级别的，在四种算法中实现成本最低。每个页框不再需要维护访问位、修改位以外的任何额外信息，页表结构最简洁。
但FIFO的致命缺陷在于完全不考虑页面的使用频率。一个刚刚被频繁访问的热页，如果它不幸是"最早进来的"，下一秒就会被无情踢出。更糟糕的是Belady异常——操作系统理论中最违反直觉的现象之一。直觉上，给进程更多物理页框应该降低缺页率。但FIFO偏偏不是：在某些访问序列下，增加页框不仅不降缺页数，反而让它上升。这个现象由Belady等人在1969年发现，根本原因是FIFO的置换决策与页面访问的局部性完全不挂钩，多出来的页框给了FIFO更多"犯错的空间"——它可能保留了一堆永不再用的旧页面，而把马上要用的热页踢出去。
软考命题人对Belady异常情有独钟，逢FIFO必考。典型题目是给一个访问序列——比如三、二、一、零、三、二、四、三、二、一、零、四——让你分别用三个和四个物理页框计算FIFO的缺页次数。三个页框时缺页九次，四个页框反而缺页十次，Belady异常实锤。关键在于：多出来的那个页框让FIFO在早期多保留了一个后来不再使用的页面，连锁反应推高了缺页数。LRU和OPT永远不会出现Belady异常——它们的决策基于"将来是否还会用"或"最近是否被用过"，增加页框总是帮助而非阻碍保留有用页面。
LRU算法的核心思想来自程序访存的局部性原理。时间局部性告诉我们，一个内存地址如果刚刚被访问过，那么它在不久的将来极有可能再次被访问。空间局部性则告诉我们，如果一个地址被访问，它附近的地址也很可能被访问。LRU利用的是时间局部性——它把"最近最久没有被访问过的页面"当作"未来最不可能被访问的页面"来淘汰。这和OPT的理念一脉相承，只是OPT看的是未来，LRU看的是过去，用过去推测未来。
实现真正的LRU需要为每个页面记录它最后一次被访问的时间戳。每次访问发生时更新对应页面的时间戳，需要置换时扫描所有页面的时间戳找出最小值。如果系统有N个物理页框，这个扫描操作的复杂度就是O(N)，对于页框数很大的系统来说开销不小。另一种实现方式是用一个栈——每当页面被访问，就把它从栈中原来位置抽出来压到栈顶。栈底永远是那个最久未被访问的页面，置换时直接淘汰栈底就行。但栈操作涉及链表的节点移动，对于硬件实现的TLB而言不够简洁。
在考试中，LRU缺页次数的计算有两种约定，考生必须看清题干。一种是严格LRU，即基于完整的历史信息，把距离上次访问时间最久的页面淘汰。另一种是近似LRU，以访问位为核心，定期清零访问位再查看。软考多数真题采用严格LRU，但也会在描述中做提示。手算LRU时的技巧是：从当前时刻倒着扫访问序列，内存中最晚出现在倒扫序列的那个页面就是LRU要淘汰的对象。这个技巧把"找最小时间戳"转化成了直观的视觉比对，在考场上能省不少时间。
CLOCK算法的出现就是为了解决LRU实现成本过高的问题。它不维护时间戳，不维护栈，只依赖每个页面自带的一个访问位。所有物理页框被组织成一个环形链表，类似于钟面，一根指针在环上顺时针转动。当需要置换时，指针检查指向页面的访问位。如果访问位是零，说明自从上次检查以来这个页面没有被访问过，它被选中淘汰，新页面填入这个位置，指针移到下一个位置。如果访问位是一，说明这个页面近期被访问过，算法把访问位清零，给这个页面"第二次机会"，指针继续前进，直到找到一个访问位为零的页面为止。
这个算法的直观理解是：页面被访问时硬件自动把访问位置为一。指针转过来看到一，就给你一次机会同时清零——下次再转过
本篇完！