C++ 实现内存页面调度置换算法之 FIFO 先进先出命中率模拟【实战】-C++-PHP中文网

FIFO模拟命中率偏低甚至为0，主因是页表未初始化或访问序列页号高度不重复导致频繁缺页，且未用哈希集合快速判重，造成漏判命中及“刚调入就淘汰”循环。

c++ 实现内存页面调度置换算法之 fifo 先进先出命中率模拟【实战】

为什么 FIFO 模拟结果总是命中率偏低甚至为 0

直接原因是页表未初始化或访问序列中存在大量不重复页号，导致每次访问都缺页。FIFO 不考虑访问局部性，纯按入队顺序淘汰，一旦工作集大小超过物理页帧数，就极易陷入“刚调入就淘汰”的循环。更隐蔽的问题是：模拟时用 std::queue 存页号，但没做“是否已在内存中”的快速判断，每次都要遍历帧数组查重——这不仅慢，还容易漏判已命中情况。

实操建议：

用 std::unordered_set 维护当前驻留页集合，O(1) 判断命中，避免遍历
物理页帧数组（如 std::vector）只存页号，不存状态位；是否在内存中由 set 冗余保证一致性
务必在访问前先查 page_set.find(page_id) != page_set.end()，命中则跳过入队和淘汰逻辑
若输入序列含非法页号（如负数、超大值），提前过滤，否则 page_set.insert() 无害但会干扰统计

如何用 std::queue 正确模拟 FIFO 入队/出队与缺页处理

std::queue 只负责记录调入顺序，不负责查重或更新帧内容。它的作用很窄：每次缺页时，把新页号 push() 进去；同时如果帧已满，从 front() 取出最老页号，从 page_set 中移除，并可选地清空对应帧位置（但帧数组本身无需擦写，下一次 push() 对应的 queue 操作自然覆盖）。

关键细节：

不要用 queue.pop() 后再取 front() —— 应先 int oldest = q.front(); q.pop();
帧数组大小固定为 frame_count，但 queue 长度可能长期大于 frame_count（比如持续缺页），此时每次只 pop 一个，push 一个，保持队列长度稳定
缺页计数器只在“未命中且完成入队+淘汰”后加 1；命中时不触发任何 queue 操作

示例片段：

if (page_set.find(pid) == page_set.end()) { // 缺页<br>  if (frames.size()     frames.push_back(pid);<br>  } else {<br>    int oldest = q.front(); q.pop();<br>    page_set.erase(oldest);<br>    // 更新 frames 中某个位置？不需要——用 vector 下标模拟帧，实际替换靠后续 push 覆盖<br>  }<br>  q.push(pid);<br>  page_set.insert(pid);<br>  page_faults++;<br>}

命中率计算必须避开的两个统计陷阱

第一个陷阱：把“初始空帧时的第一次访问”算作缺页没问题，但有人误把 page_faults / total_accesses 当成命中率，其实这是缺页率；命中率是 (total_accesses - page_faults) / total_accesses。

第二个陷阱更隐蔽：访问序列中存在连续重复页号（如 [1,1,1]），FIFO 下第二次、第三次访问必命中，但如果代码里没做“命中即跳过所有淘汰逻辑”，就可能错误地执行了出队/入队，导致 page_set 和 queue 状态错乱，最终命中数少计。

C++14

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

下载

验证建议：

手算小样例：frames=2, access=[1,2,3,2,4]，正确过程应为：1(缺)→2(缺)→3(缺,淘汰1)→2(命中)→4(缺,淘汰2)，共 4 次缺页，命中率 = 1/5 = 20%
在循环内加日志输出每次访问的 pid、是否命中、queue size、set size，比对中间态
用 assert(frames.size() 防止帧溢出