页面置换算法FIFO，结果

### FIFO 页面置换算法概述

FIFO（First-In-First-Out）页面置换算法是最简单的页面置换策略之一。其实质在于总是选择在主存中停留时间最长的页进行替换，即先进入内存的页最先被移除[^2]。

### FIFO 页面置换算法的特点

该算法通过维护一个队列来跟踪所有当前驻留在内存中的页面。每当发生缺页中断时，操作系统会将新请求的页面加载到内存中，并将其放置在队列的末端；与此同时，在队列头部的最旧页面会被淘汰出去。尽管这种方法易于理解和实现，但它并非最优解，因为较早进入系统的页面未必就是将来不会再访问的页面[^1]。

值得注意的是，FIFO 算法存在一种称为 Belady 异常的现象——随着分配给进程的工作集大小增大，缺页率却可能上升而不是下降[^3]。

### C语言下的FIFO页面置换算法实现

下面是一个基于C语言编写的简单版本的FIFO页面置换模拟器：

#include <stdio.h>
#define MAX_PAGES 10    /* 假设最大可容纳的页面数量 */
int fifo_queue[MAX_PAGES];     /* 存储当前缓存内的页面编号 */
int front = -1;                /* 队首指针初始化为无效位置 */
int rear = -1;                 /* 队尾指针同样设置 */

void enqueue(int value){
    if (rear >= MAX_PAGES - 1) {
        printf("Queue Overflow\n");
        return;
    }
    
    if(front == -1 && rear == -1){ // 如果队列为空，则更新front指向第一个元素的位置
        front++;
    }

    fifo_queue[++rear] = value;
}

// 函数用于判断某特定值是否存在于数组内
bool contains(int *arr, int size, int target){
    for(int i=0;i<size;++i){
        if(arr[i]==target)return true;
    }
    return false;
}

int main(){
    int pages[] = {7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2};   /* 测试用例序列 */
    int n = sizeof(pages)/sizeof(pages[0]);                  /* 获取测试数据长度 */
    int fault_count = 0;

    for(int i=0 ; i<n ; ++i){
        if(!contains(fifo_queue,rear+1,pages[i])){           /* 若不存在于缓存中...*/
            fault_count++;                                   /* ...则触发一次缺页错误*/

            if(rear>=MAX_PAGES-1){                           /* 当缓存已满时...*/
                front=(front+1)%MAX_PAGES;                   /* ...移动front以覆盖最早的项*/
                rear=(rear+1)%MAX_PAGES;                     /* 同样调整rear保持一致*/
                
                fifo_queue[rear]=pages[i];
            }else{
                enqueue(pages[i]);
            }
            
            printf("Page %d inserted into cache.\n", pages[i]);
        } else {
            printf("Hit on Page %d.\n", pages[i]);
        }
        
        for(int j=front;j<=rear;j++){
            printf("%d ", fifo_queue[j%MAX_PAGES]);
        }
        puts("");
    }

    printf("\nTotal number of page faults: %d\n",fault_count);
}

此程序展示了如何利用循环缓冲区结构来管理固定容量的页面帧集合，并计算在整个过程中发生的缺页次数。每次遇到新的未命中页面都会打印出来并显示当前状态，以便观察者可以清楚地看到每一步的变化情况。