1. 页面置换算法基础概念当物理内存不足时操作系统需要将部分页面换出到磁盘为新的页面腾出空间。这个决策过程就是页面置换算法要解决的问题。想象你有一个只能放3本书的书架现在要放入第4本就必须决定替换掉哪本旧书——这就是页面置换算法的生活化类比。四种经典算法各有特点OPT是理论最优但无法实现的先知算法FIFO简单粗暴但性能不稳定LRU基于时间局部性原理LFU则统计访问频率。在实际系统开发中理解这些算法的差异对内存调优至关重要。比如数据库缓冲池就常采用LRU的变种算法。2. 最佳置换算法(OPT)实现2.1 算法原理OPT算法选择未来最长时间不会被访问的页面进行置换这需要预知未来的页面访问序列。虽然无法实际应用但它的缺页率是所有算法中最低的常作为性能评估的基准。测试用例假设页框数n3访问序列为2,3,2,1,5,2,4,5,3,2,5,2。OPT处理过程如下访问2: [2, , ] 缺页 访问3: [2,3, ] 缺页 访问2: [2,3, ] 命中 访问1: [2,3,1] 缺页 访问5: [2,5,1] 替换3(因为3在未来最晚被访问)2.2 C核心实现int findReplaceIndex(vectorint frames, vectorint future, int current) { int farthest -1, index -1; for (int i 0; i frames.size(); i) { int j; for (j current; j future.size(); j) { if (frames[i] future[j]) break; } if (j future.size()) return i; // 未来不再访问 if (j farthest) { farthest j; index i; } } return index; } void OPT(vectorint pages, int frameCount) { vectorint frames; int faults 0; for (int i 0; i pages.size(); i) { if (find(frames.begin(), frames.end(), pages[i]) frames.end()) { faults; if (frames.size() frameCount) { frames.push_back(pages[i]); } else { int idx findReplaceIndex(frames, pages, i1); frames[idx] pages[i]; } } // 打印当前帧状态 } cout OPT缺页次数: faults endl; }3. 先进先出算法(FIFO)剖析3.1 算法特点FIFO维护一个队列总是淘汰最早进入内存的页面。这种实现简单但性能较差可能出现Belady异常——增加页框数反而导致缺页率上升的现象。同一个测试序列下FIFO的表现访问2: [2, , ] 访问3: [2,3, ] 访问2: [2,3, ] 命中 访问1: [2,3,1] 访问5: [5,3,1] 替换最早进入的23.2 C实现要点void FIFO(vectorint pages, int frameCount) { queueint q; unordered_setint s; int faults 0; for (int page : pages) { if (s.find(page) s.end()) { faults; if (s.size() frameCount) { int oldest q.front(); q.pop(); s.erase(oldest); } s.insert(page); q.push(page); } // 打印状态 } cout FIFO缺页次数: faults endl; }4. 最近最久未使用算法(LRU)详解4.1 算法优势LRU基于时间局部性原理认为最近使用的页面很可能再次被使用。实际测试中它的性能最接近OPT算法。常见的实现方式有计数器法为每个页表项添加时间戳栈结构将访问的页面移到栈顶测试序列处理示例访问2: [2, , ] 访问3: [3,2, ] 访问2: [2,3, ] 访问1: [1,2,3] 访问5: [5,1,2] 替换最久未使用的34.2 基于双向链表的实现class LRUCache { listint dq; // 存储页号 unordered_mapint, listint::iterator ma; int csize; // 页框数 public: LRUCache(int capacity) : csize(capacity) {} void refer(int page) { if (ma.find(page) ma.end()) { if (dq.size() csize) { int last dq.back(); dq.pop_back(); ma.erase(last); } } else { dq.erase(ma[page]); } dq.push_front(page); ma[page] dq.begin(); } void display() { for (auto it dq.begin(); it ! dq.end(); it) cout *it ; cout endl; } };5. 最不经常使用算法(LFU)实现5.1 算法特点LFU统计页面的历史访问频率淘汰访问次数最少的页面。适合访问模式相对稳定的场景但对突发访问模式不敏感。修改后的测试序列2,3,2,1,2,1,5,4,2,4,4,6访问2: [2(1), , ] 访问3: [2(1),3(1), ] 访问2: [2(2),3(1), ] 访问1: [2(2),3(1),1(1)] 访问2: [2(3),3(1),1(1)] 访问5: [2(3),5(1),1(1)] 替换访问次数最少的35.2 C实现方案void LFU(vectorint pages, int frameCount) { unordered_mapint, int freq; // 页面对应访问频率 unordered_mapint, int time; // 最近访问时间 settupleint, int, int s; // (频率,时间,页面) unordered_setint inMemory; int faults 0, timestamp 0; for (int page : pages) { if (inMemory.count(page)) { auto it s.find({freq[page], time[page], page}); s.erase(it); freq[page]; time[page] timestamp; s.insert({freq[page], time[page], page}); } else { faults; if (inMemory.size() frameCount) { auto [f, t, p] *s.begin(); inMemory.erase(p); s.erase(s.begin()); } freq[page] 1; time[page] timestamp; inMemory.insert(page); s.insert({1, timestamp, page}); } } cout LFU缺页次数: faults endl; }6. 性能对比与算法选择6.1 测试数据对比使用统一测试序列2,3,2,1,5,2,4,5,3,2,5,2n3时的表现算法缺页次数缺页率OPT650%FIFO975%LRU758.3%LFU758.3%6.2 适用场景建议嵌入式系统常选择FIFO实现简单开销小数据库系统多采用LRU变种如PostgreSQL的clock-sweepJava虚拟机年轻代用FIFO老年代用LRUWeb服务器LFU适合热点内容缓存实际项目中Linux内核采用的CLOCK算法是LRU的近似实现通过访问位模拟最近使用情况在性能和实现复杂度间取得平衡。