C++如何模拟FIFO页面置换算法并统计命中率？

FIFO页面置换算法在操作系统内存管理中属于最直观的一类策略：当进程请求的页面不在内存中时，触发一次缺页中断，如果内存中已经没有空闲页框，就必须从当前已加载的页面里挑一个淘汰出去。FIFO选择的是最早进入内存的页面，也就是在页框里停留时间最长的那个页面。要把这个策略模拟准确，关键不在于算法复杂，而在于是否严格区分了命中、缺页未满、缺页已满三种访问状态。下面这篇文章使用C++实现一个可运行的模拟器，并用几组引用串数据看看不同页框数量对命中率的影响。

一、FIFO算法与命中率计算模型

参考进程访问页面序列通常被称为引用串，例如7,0,1,2,0,3。内存里分配给该进程的页框数量固定为m，每个页框最多保存一个页面号。访问某个页面时，如果它已经位于任一页框内，算作一次命中，否则算作一次缺页。命中率就是命中次数除以总访问次数，缺页率则等于1减去命中率。FIFO的实现不需要参考未来的访问趋势，只需要一个有序结构记录页面进入内存的先后关系。每次淘汰队首页面即可。

在计算命中率时，最容易出错的地方是把缺页后的载入过程也算进访问次数。访问次数只统计引用串中每一个页面请求，不统计内部替换操作。比如引用串为7,0,1,2,0,3，如果页框数为3，前三次请求都是缺页，第四次请求2时替换掉7，第五次请求0时因为0还在内存中，所以算作命中。只有严格按照这个口径统计，最终得到的命中率才能和其他算法公平比较。

FIFO的另一个特征是完全依赖进入时间，不关心页面最近是否被使用过。即使某个页面刚刚被访问了很多次，只要它进入内存的时间最早，下一次缺页时仍然可能被淘汰。这个特性让FIFO实现起来非常简单，但也会造成一些不符合直觉的现象，比如后文会提到的Belady异常。

二、C++数据结构与模拟类设计

实现FIFO模拟器时，最自然的结构是用一个队列记录页面进入内存的先后顺序。C++标准库中的queue<int>可以满足需求，它只允许在队尾插入、在队首删除，刚好对应页面的载入和淘汰。页框本身可以用vector<int>来表示，因为它需要随机访问，方便查找某个页面是否已经存在。页面号统一使用整数，引用串则保存在一个普通数组中。

下面的类把页框数组、进入顺序队列、缺页次数和命中次数封装在一起。访问页面的核心方法accessPage会先判断页面是否已经在页框中，如果在则命中计数加一，否则进入缺页处理逻辑。缺页处理又分为两种情况：页框还有空闲位置时直接载入；页框已满时从队列头部取出淘汰页面，替换到页框数组中对应位置，并把这个新页面加入队尾。

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

class FIFOSimulator {
private:
    int frameCount;
    vector<int> frames;
    queue<int> enterOrder;
    int pageFaults;
    int pageHits;

public:
    FIFOSimulator(int count) : frameCount(count), pageFaults(0), pageHits(0) {
        frames.reserve(frameCount);
    }

    bool isInFrames(int page) {
        return find(frames.begin(), frames.end(), page) != frames.end();
    }

    void accessPage(int page) {
        if (isInFrames(page)) {
            pageHits++;
            return;
        }

        pageFaults++;
        if ((int)frames.size() < frameCount) {
            frames.push_back(page);
            enterOrder.push(page);
            return;
        }

        int victim = enterOrder.front();
        enterOrder.pop();

        for (size_t i = 0; i < frames.size(); ++i) {
            if (frames[i] == victim) {
                frames[i] = page;
                break;
            }
        }
        enterOrder.push(page);
    }

    void printStats() {
        cout << "缺页次数: " << pageFaults << endl;
        cout << "命中次数: " << pageHits << endl;
        int total = pageFaults + pageHits;
        double hitRate = total == 0 ? 0.0 : (double)pageHits / total * 100;
        cout << "命中率: " << hitRate << "%" << endl;
    }
};

int main() {
    int frames = 3;
    int refs[] = {7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1};
    FIFOSimulator sim(frames);
    for (int p : refs) {
        sim.accessPage(p);
    }
    sim.printStats();
    return 0;
}

这段代码的关键在于enterOrder队列始终与页框数组保持同一个页面集合，但队列只负责进入顺序，不负责查找。查找操作通过find在frames向量中线性扫描完成。当页框数量不大时，线性扫描的性能完全够用；如果页框数量很大，可以把页框改成哈希表来降低查找时间，但保留队列仍然是FIFO策略所必需的。

构造函数中调用frames.reserve(frameCount)是为了减少后续动态扩容带来的小开销。这里没有直接创建固定大小的数组，而是用一个空向量逐步填充，原因是这样更容易区分哪些页框已经被占用。如果使用固定大小数组并初始化为-1，逻辑上也可以，但在空页框处理上需要额外判断。

三、FIFO替换流程与边界处理

当页框未满时，缺页处理非常简单：页面直接加入页框向量，同时把这个页面号压入进入顺序队列。此时不需要淘汰任何页面，因为系统还有空闲物理页框。很多模拟程序在这里多写了一个替换指针或者单独维护一个队尾下标，实际上完全没有必要，直接用frames.size()和frameCount比较即可。

页框已满时的替换流程要格外注意顺序。先取出队首页面作为淘汰对象，再在页框数组中找到这个页面所在的下标，最后用新页面覆盖该位置。如果先把新页面压入队列再查找淘汰页面，会导致队列和页框数组不一致。重复访问已有页面时，队列不能发生任何变化，因为该页面进入内存的原始时间没有变。例如页面0在页框中，之后又多次访问0，这些命中不会改变0在队列中的位置。

页框数量为1是一个常见的边界情况。此时每次缺页都会淘汰当前唯一页面，队列中始终只有一个元素。查找命中时，isInFrames会返回真，直接命中返回；如果未命中，先淘汰队首，再载入新页面。整个过程不会出现越界或重复插入。另一个边界是页框数量大于引用串中不同页面的数量，这时可能永远不会触发淘汰，所有缺页都发生在初始化阶段，后续请求全部命中。

四、运行结果与不同页框数对比

上面main函数使用3个页框处理长度为20的引用串。运行后会输出缺页次数为15，命中次数为5，命中率为25%。这个结果并不理想，说明FIFO在页框数量较少时频繁淘汰还会用到的页面。把frames变量改成4后重新编译运行，命中率一般会有所提升，但提升幅度和访问序列的局部性密切相关。

FIFO还存在一个显著缺陷，就是Belady异常。通常情况下，增加页框数量应当减少缺页次数，但FIFO在部分引用串中反而会因为多出来的页框改变了淘汰顺序，导致缺页次数增加。经典引用串1,2,3,4,1,2,5,1,2,3,4,5在使用3个页框时缺页9次，而使用4个页框时缺页10次。出现这个现象的原因是FIFO完全不考虑页面使用频率，只按照进入时间机械淘汰。

从模拟结果可以看出，FIFO适合作为教学模型和基线对比，并不适合直接用在真实操作系统的主要页面置换策略中。它的优点是实现简单、代码量少、维护成本低，在页面访问序列近似顺序访问时表现尚可。遇到随机访问或强局部性负载时，FIFO的命中率会明显低于LRU、CLOCK等算法。通过修改上面的引用串和页框数，可以进一步观察不同负载下命中率的变化规律。

FIFO页面置换算法C++命中率模拟内存页面调度修改时间：2026-09-27 06:50:23