FIFO（First In First Out）先进先出页面置换算法是操作系统中最经典的内存页面调度策略之一，也是学习操作系统课程时几乎绕不开的实验题目。它的核心思想非常直观：操作系统为进程分配若干个内存物理块，当需要调入新页面而内存已满时，就淘汰最早进入内存的那个页面。本文将通过一个完整的C++程序，模拟整个页面调度过程，统计缺页次数和命中率，并分析这个算法的特性和缺陷。
一、FIFO算法的基本原理
要理解FIFO算法，首先要明白几个基本概念。进程运行时访问的是逻辑地址空间，操作系统把逻辑空间划分成固定大小的页面，同时把物理内存划分成同样大小的物理块。进程的页面只有装入物理块才能被CPU实际执行，当进程访问的页面不在内存中时，就会产生一次缺页中断，操作系统必须把该页面从外存调入内存。
问题在于物理块是有限的。假设系统只给进程分配了3个物理块，而进程已经装入了页面1、2、3，此时又要访问页面4，内存已满，就必须选择一个老页面淘汰出去。FIFO的策略是：谁最先进入内存，谁就最先被淘汰。这非常类似于排队买票，排在队伍最前面的人最先被服务离开。
实现FIFO的关键数据结构是队列。每次装入新页面时，把页号追加到队尾；发生置换时，取出队头的页号将其淘汰。需要注意的一点是，FIFO只关心页面进入内存的先后顺序，完全不考虑页面是否被频繁访问。一个刚被访问过的热点页面，只要它进内存的时间早，照样会被淘汰，这也是FIFO命中率不高的根本原因。
二、C++实现页面调度模拟器
下面给出完整的C++实现。程序使用STL的queue维护装入顺序，用vector记录当前驻留在内存中的页面，方便判断命中与否。每次访问页面时，先查找内存中是否存在该页，存在则命中；不存在则缺页，若内存已满就执行FIFO置换。
#include <iostream>
#include <queue>
#include <vector>
#include <cstdlib>
#include <ctime>
using namespace std;
// 模拟FIFO页面置换算法
// refString: 页面访问序列 blockNum: 分配的物理块数
void simulateFIFO(const vector<int>& refString, int blockNum) {
vector<int> memory; // 当前内存中的页面
queue<int> loadOrder; // 页面装入顺序队列
int hitCount = 0; // 命中次数
int missCount = 0; // 缺页次数
for (size_t i = 0; i < refString.size(); i++) {
int page = refString[i];
bool found = false;
// 查找页面是否已在内存中
for (int p : memory) {
if (p == page) { found = true; break; }
}
cout << "第" << i + 1 << "次访问页面 " << page << " : ";
if (found) {
hitCount++;
cout << "命中" << endl;
} else {
missCount++;
if ((int)memory.size() < blockNum) {
// 内存未满，直接装入
memory.push_back(page);
loadOrder.push(page);
cout << "缺页，装入页面 " << page << endl;
} else {
// 内存已满，执行FIFO置换
int victim = loadOrder.front();
loadOrder.pop();
// 从内存中移除被淘汰页面
for (auto it = memory.begin(); it != memory.end(); ++it) {
if (*it == victim) { memory.erase(it); break; }
}
memory.push_back(page);
loadOrder.push(page);
cout << "缺页，淘汰页面 " << victim
<< "，装入页面 " << page << endl;
}
}
}
double total = refString.size();
double hitRate = hitCount / total * 100;
cout << "\n===== 统计结果 =====" << endl;
cout << "总访问次数: " << total << endl;
cout << "命中次数: " << hitCount << endl;
cout << "缺页次数: " << missCount << endl;
cout << "命中率: " << hitRate << "%" << endl;
}
int main() {
srand((unsigned)time(nullptr));
int pageSize, blockNum;
cout << "请输入页面总数: ";
cin >> pageSize;
cout << "请输入分配的物理块数: ";
cin >> blockNum;
// 随机生成页面访问序列
vector<int> refString(pageSize);
for (int i = 0; i < pageSize; i++) {
refString[i] = rand() % 9 + 1; // 页号范围 1~9
cout << refString[i] << " ";
}
cout << endl << endl;
simulateFIFO(refString, blockNum);
return 0;
}</code>代码中有几个设计细节值得注意。第一，命中判断采用的是线性查找，物理块数量通常很少（几个到几十个），线性查找的性能完全够用，如果页面较多可以换成unordered_set来优化。第二，队列中存放的是页号而不是内存下标，这样逻辑更直观。第三，淘汰页面时需要同时在vector和queue中做删除，两个容器必须保持同步，这是最容易出错的地方。
假设访问序列为 7 0 1 2 0 3 0 4，物理块数为3，程序运行过程是：前三次访问7、0、1依次装入内存；第四次访问2时发生缺页，淘汰最早进入的7；第五次访问0时命中；后续依次类推。整个过程中缺页6次、命中2次，命中率为25%。手动推演一遍这个过程，对理解算法执行流程非常有帮助。
三、FIFO的缺陷与Belady异常
FIFO最著名的问题就是Belady异常：一般情况下，增加物理块数应该减少缺页次数，但FIFO在某些访问序列下，物理块增多反而导致缺页次数上升。最经典的例子是访问序列 1 2 3 4 1 2 5 1 2 3 4 5：分配3个物理块时缺页9次，而分配4个物理块时缺页竟然达到10次。这种现象违背直觉，也说明FIFO算法不符合栈式访问规律。
读者可以把上面的程序稍作修改，用固定序列分别测试3块和4块的情况，验证这个反常现象。这也是实验报告中常见的加分点。相比之下，LRU算法属于栈式算法，物理块增加时缺页次数一定不会增加，因此不会出现Belady异常。
四、与LRU、OPT算法的命中率对比
为了客观评价FIFO的性能，可以在同一份访问序列上分别运行三种算法。OPT（最佳置换算法）淘汰未来最长时间不再被访问的页面，它是理论上的性能上限，实际无法实现，只作为对比基准。LRU（最近最久未使用）淘汰最长时间未被访问的页面，性能接近OPT但开销较大。三者复杂度对比大致为：OPT实现最难且不可实用，LRU需要维护访问时间戳或双向链表加哈希表，FIFO实现最简单、开销最小。
典型测试数据表明，在随机访问序列下，FIFO的命中率通常明显低于LRU，差距可达10%到20%；而在局部性较强的真实程序访问序列下，LRU的优势会更明显。FIFO的价值在于实现简单、硬件开销为零，适合作为教学示例或对性能要求不高的场景。如果读者想进一步扩展，可以在本程序基础上增加LRU模拟函数，将三种算法的统计结果放在同一张表中输出，直观比较命中率的差异。
总结来说，FIFO页面置换算法虽然简单，却完整体现了操作系统在有限资源下做取舍的核心思想。通过这个C++模拟器，读者不仅能掌握队列这一数据结构在实际问题中的应用，还能深入理解缺页中断、命中率计算以及Belady异常等操作系统核心概念，为后续学习LRU、Clock等更复杂的置换算法打下扎实基础。