要是在面试前刷到这篇就好了：页面置换算法

专业造轮子

发布于 2026-06-23 20:52:30

1000

"今天我们来聊聊虚拟内存管理。"面试官推过来一杯水，手指在笔记本触控板上滑动，"假设物理内存已满，进程需要加载新页面时该怎么办？"

我深吸一口气，指尖无意识地摩挲着牛仔裤上的纹路。这已经是第五轮技术面了，会议室的空调冷气正对着后颈吹，让本就紧绷的神经更加敏感。"这种情况需要把暂时不用的页面换出到磁盘，也就是页面置换。"我尽量让声音保持平稳，"关键在于选择置换哪个页面，这直接影响系统性能。"

面试官微微点头，在屏幕上打开一个文档："那硬件如何支持这个过程？页表需要哪些特殊设计？"

硬件基石：存在位与缺页中断

"页表必须包含存在位。"我拿起笔在草稿纸上画了个简单的页表项结构，"当存在位为0时，表示页面不在物理内存，此时访问会触发缺页中断——这是一种特殊的陷阱指令，会让操作系统介入处理。"

"具体处理流程呢？"面试官身体前倾，指尖轻叩桌面。

我在纸上补充步骤："首先保存当前进程上下文，然后检查中断原因是否为页面缺失。确认后查询页表找到页面在磁盘的位置，接着选择牺牲页面换出，最后将目标页面从磁盘加载到内存并更新页表。整个过程对用户进程透明。"

"为什么需要硬件支持而不是纯软件实现？"这突如其来的追问让我心跳漏了一拍，我盯着草稿纸上的存在位标记，突然意识到关键点："因为页面访问是高频操作，纯软件判断会导致每个内存访问都增加额外开销。硬件实现可以在地址转换阶段并行完成检查，效率更高。"

面试官嘴角扬起一丝弧度，在笔记本上记了些什么。

算法交锋：七种置换策略的优劣对决

"接下来我们聊聊算法。"面试官清了清嗓子，"你能说说常见的页面置换算法有哪些吗？各自的适用场景是什么？"

我在纸上列出清单，开始逐一分析：

最优置换：理想与现实的鸿沟

"最优置换理论上最优，它选择最远将来才会被访问的页面。"我画了个时间轴示意图，"但问题在于需要预知未来访问序列，这在实际系统中不可能实现，所以通常作为评估其他算法的基准。"

"就像预测彩票号码？"面试官打趣道。

"确实类似。"我笑了笑，"不过它揭示了一个重要原则：尽量保留短期内会频繁使用的页面。"

随机置换：最简单却最危险

"随机置换完全随机选择页面，实现简单但性能不稳定。"我摇摇头，"极端情况下可能连续置换活跃页面，导致严重的抖动现象。除非硬件不支持页表访问位，否则很少使用。"

最近未使用：时钟滴答间的抉择

"NRU算法将页面分为四类：未访问未修改、未访问已修改、已访问未修改、已访问已修改。"我画了个四象限图，"缺页时优先淘汰编号最小的类别，通常是最近一个时钟滴答（约20ms）内未被访问的页面。实现简单但精度较低，适合对性能要求不高的场景。"

FIFO与第二次机会：排队理论的应用与改进

"FIFO就像排队买咖啡，先进入内存的页面先被置换。"我画了个队列示意图，"但'Belady异常'是它的致命伤——增加物理页帧数反而可能导致缺页率上升。"

"所以有了第二次机会算法？"面试官追问。

"没错。"我在队列节点旁标注了R位，"当遇到R位为1的页面时，将R位清零并移到队尾，相当于给了第二次机会。这在一定程度上解决了FIFO的缺陷，但需要频繁移动链表节点，开销较大。"

时钟页面置换：环形队列的优雅优化

"时钟算法是第二次机会的改进版。"我画了个环形链表，用箭头表示当前指针位置，"把页面组织成环形队列，指针指向最老的页面。缺页时检查当前页面R位：为0直接置换，为1则清零后移动指针。无需移动节点，只需调整指针位置，实现更高效。"

"像老式唱片播放器？"面试官形象地比喻。

"非常贴切！"我点头赞同，"很多操作系统如Linux早期版本就采用这种算法，兼顾性能和实现复杂度。"

LRU：最接近最优的实用方案

"LRU（最近最少使用） 基于局部性原理，认为最近访问过的页面短期内仍会被访问。"我画了个访问序列，"实现方式有多种，软件层面常用哈希表+双向链表：哈希表快速定位节点，链表维护访问顺序，最近使用的移到表头，淘汰时移除表尾。"

"能具体说说实现细节吗？"面试官突然前倾身体，"比如get和put操作的流程。"

我立刻在纸上写下核心代码逻辑：

class LRUCache {  
public:  
    unordered_map<int, list<pair<int, int>>::iterator> m;  
    list<pair<int, int>> l;  
    int cap;  
    LRUCache(int capacity) {  
        this->cap = capacity;  
    }  

    int get(int key) {  
        if(!m.count(key)) return-1;  
        auto p = *(m[key]);  
        l.erase(m[key]);  
        l.push_front(p);  
        m[key] = l.begin();  
        return p.second;  
    }  

    void put(int key, int value) {  
        if(m.count(key)) {  
            l.erase(m[key]);  
        } else {  
           if(l.size() == this->cap) {  
               m.erase(l.back().first);  
               l.pop_back();  
           }   
        }  
        auto p = make_pair(key, value);  
        l.push_front(p);  
        m[key] = l.begin();  
    }  
};

"这个实现的时间复杂度是多少？"面试官追问。

"get和put都是O(1)。"我自信地回答，"但需要注意线程安全问题，多线程环境下需要加锁保护临界区。"

"如果硬件不支持维护访问顺序呢？"

"可以用近似LRU，比如增强型时钟算法，结合访问位和修改位进行多轮扫描。"我补充道，"Linux的CLOCK_V2就是这种思路。"

面试官满意地点点头，看了眼手表："最后一个问题，如何解决内存抖动？"