页面置换算法(Page Replacement)

页面置换算法(Page Replacement Algorithm)是虚拟内存管理中,当物理内存已满而又需要调入新页面时,用来决定淘汰(换出)哪一个已在内存中的页面的策略。好的置换算法能有效降低缺页率,提高系统整体性能。

概述

在按需分页系统中,进程访问的页面不一定都在物理内存里。当发生缺页且没有空闲页帧时,操作系统必须选择一个内存中的页面换出到磁盘,再把需要的页面换入。选择哪个页面淘汰,直接决定了后续会不会很快又要把它换回来,因此置换算法是虚拟内存性能的关键。

常见算法

• 最优置换(OPT):淘汰未来最长时间不会被访问的页面,缺页率最低,但需预知未来,仅作理论基准。
• 先进先出(FIFO):淘汰最早进入内存的页面,实现简单,但可能淘汰常用页面,还会出现分配帧越多缺页反而增多的 Belady 异常。
• 最近最少使用(LRU):淘汰最久未被访问的页面,基于时间局部性,效果接近最优,但精确实现开销大。
• 时钟算法(Clock):用一个访问位近似 LRU,页面环形排列,指针扫描时清除访问位并淘汰访问位为零者,是实际系统常用的折中方案。

应用场景

Linux 内核采用改进的 LRU 变体,将页面组织为活跃(active)与不活跃(inactive)两个链表,并结合访问位近似实现;此外还引入了工作集与页面老化机制。数据库缓冲池也常用类似 LRU 或时钟的策略管理缓存页。

常见问题

问:为什么不直接用最优置换算法?答:最优算法需要预知每个页面未来的访问时刻,现实中无法做到,因此它只能作为衡量其他算法优劣的理论上界。

问:什么是抖动(Thrashing)?答:当分配给进程的页帧太少,系统频繁地换入换出页面,CPU 大量时间耗在缺页处理上而非真正计算,这种恶性循环称为抖动。