C++ 实现内存页面置换算法之 FIFO 与 LRU 命中率对比模拟实战案例演练【实战】-C++-PHP中文网

必须构造含时间局部性的工作集模型访问序列才能真实暴露fifo与lru差距；采用std::mt19937均匀生成页号，冷启动阶段跳过前framecount次访问；通过pagereplacementalgo基类统一接口，fifo用queue+unordered_set或循环数组实现，lru用list+unordered_map实现，避免o(n)操作。

c++ 实现内存页面置换算法之 fifo 与 lru 命中率对比模拟实战案例演练【实战】

准备带局部性的访问序列

用纯随机数生成的页号序列无法暴露 FIFO 和 LRU 的真实差距，必须构造含时间局部性的访问流，否则两者命中率会趋近一致。

创建 std::mt19937 引擎并绑定 std::uniform_int_distribution dist(0, 99)，确保页号分布均匀且周期足够长；避免使用已被淘汰的 std::rand()。

采用“工作集模型”：维护一个当前窗口 vector window，初始填入 20 个连续页号；每次以 85% 概率从 window 中随机选页，15% 概率生成新窗口（清空 window 后填入下一批 20 个新页号）；总序列长度设为 1000，不低于页面总数的 10 倍。

【必须跳过前 frameCount 次访问不计入命中统计】——冷启动阶段全是缺页，若参与计算会系统性压低 LRU 优势，导致对比失真。

统一接口抽象与算法基类

不为每个算法写独立主循环，定义抽象基类 PageReplacementAlgo，含纯虚函数 access(int page_id) 和 get_hit_count()，强制所有实现遵循同一行为契约。

在构造函数中预分配 std::vector resident(total_pages, false)，用于 O(1) 查页是否驻留；禁止用线性扫描替代，否则单次 access 复杂度升至 O(m)，10 万次访问将明显卡顿。

所有子类（FIFOAlgo、LRUAlgo）必须在 access() 内部完成三件事：查 resident → 更新计数器 → 若缺页则执行置换逻辑；外部调用者只看到 for (int pg : trace) { algo->access(pg); } 这一行。

FIFO 算法实现要点

方法一：std::queue + std::unordered_set 协同

声明 queue q 和 unordered_set inMemory；每次 access 前先查 inMemory.find(page) != inMemory.end()，命中则 hit++ 并返回。

缺页时先 pageFaults++，再判断 if (q.size() == frameCount)，满则取 int victim = q.front(); q.pop(); inMemory.erase(victim)；最后 q.push(page); inMemory.insert(page)。

【调用 q.front() 前必须断言 !q.empty()，尤其 frameCount == 0 或 trace 极短时，否则未定义行为】

C++14

C++14 对 C++11 的修正与增强版本，适合旧系统维护和较老工具链兼容。

下载

方法二：手写循环数组模拟

用 std::vector frames(frameCount, -1) 存页号，int cur = 0 表示下次覆盖位置；首次装入阶段（frames 中 -1 数量 > 0）绝不更新 cur。

缺页且已满时：int victim = frames[cur]; frames[cur] = page; cur = (cur + 1) % frameCount；同步操作 inMemory.erase(victim); inMemory.insert(page)。

LRU 算法实现要点

用 std::list lru_list 维护访问时序，std::unordered_map::iterator> page_to_iter 映射页号到链表节点迭代器。

命中时：auto it = page_to_iter.find(page); lru_list.splice(lru_list.begin(), lru_list, it->second); page_to_iter[page] = lru_list.begin()；注意 splice 后原迭代器失效，必须重赋值。

缺页时：若已满，先 int victim = lru_list.back(); lru_list.pop_back(); page_to_iter.erase(victim)；再 lru_list.push_front(page); page_to_iter[page] = lru_list.begin()。

别用 std::vector 模拟 LRU：erase 中间元素是 O(n)，10 万次访问下性能断崖式下降。