1. 效果展示

2. 程序流程图

（1）程序总流程

（2） FIFO策略

（3） LRU策略

（4） OPT策略

3. 数据结构设计

//页面数据结构
    struct PageInfo {
        int id;
        int visit;
    };

    PageInfo* Block;  // 物理块
    PageInfo* Page;  // 页面

4. 功能函数设计

序号	函数	功能说明
1	void init();	从data.txt文件中读取数据进行初始化
2	int findSpace();	查找是否有空闲物理块
3	int findExist(int curren);	查找物理块中是否存在该页面
4	int findReplace();	查找应予以置换的页面
5	int showSingle(int curren);	打印每一个序列号的结果
6	void FIFO();	替换最早进入的页面
7	void LRU();	淘汰上次使用距当前最远的页面
8	void OPT();	淘汰下一次访问距当前最远的页面中序号最小的一页
9	int main();	主函数，控制程序的整个流程

5. 代码实现

/// 页面替换策略 FIFO、OPT、LRU
#include <bits/stdc++.h>
using namespace std;

class Pager {
public:
    //页面数据结构
    struct PageInfo {
        int id;
        int visit;
    };

    PageInfo* Block;  // 物理块
    PageInfo* Page;  // 页面

    int BlockNum;
    int PageNum;

    int LockPageCnt;  //缺页次数
    int ChangePageCnt;  //置换次数

public:
    /// 从data.txt文件中读取数据，并初始化
    void init() {
        cout<<"正在进行数据读取..."<<endl;
        ifstream readData;
        readData.open("data.txt");

        readData>>BlockNum;
        Block = new PageInfo[BlockNum];
        for (int i = 0; i < BlockNum; ++i) {
            Block[i].id = -1;
            Block[i].visit = 0;
        }
        readData>>PageNum;
        Page = new PageInfo[PageNum];
        for (int i = 0; i < PageNum; ++i) {
            readData>>Page[i].id;
            Page[i].visit = 0;
        }
        readData.close();

        cout<<"数据读取结果如下："<<endl;
        printf("物理块数为：%d\n", BlockNum);
        printf("页面个数为：%d\n", PageNum);
        cout<<"页面序列如下："<<endl;
        for (int i = 0; i < PageNum; ++i) {
            printf("%d  ", Page[i].id);
        }
        cout<<endl;
        cout<<"数据读取完毕！"<<endl;
    }

    /// 查找是否有空闲块
    int findSpace() {
        for (int i = 0; i < BlockNum; ++i) {
            if (Block[i].id == -1) {
                return i;
            }
        }
        return -1;
    }

    /// 查找内存中是否存在该页面
    int findExist(int curren) {
        for (int i = 0; i < BlockNum; ++i) {
            if(Block[i].id != -1 && Block[i].id == curren) {
                return i;
            }
        }
        return -1;
    }

    /// 查找应予以置换的页面
    int findReplace() {
        int pos = 0;
        for (int i = 1; i < BlockNum; i++) {
            if(Block[i].id != -1 && Block[i].visit > Block[pos].visit) {
                pos = i;
            }
        }
        return pos;
    }

    /// 显示置换一次后的Block
    void showSingle(int curren) {
        printf("%d : ", curren);
        for (int i = 0; i < BlockNum; ++i) {
            if(Block[i].id != -1) {
                printf(" %d ", Block[i].id);
            }
        }
        cout<<endl;
    }

    /// FIFO
    void FIFO() {
        int exist, space, position;
        double fifo_missRate;
        LockPageCnt = 0;
        ChangePageCnt = 0;
        printf("\n----FIFO策略-start----\n");
        for (int i = 0; i < PageNum; ++i) {
            exist = findExist(Page[i].id);
            // 当前页面号不在内存中
            if (exist == -1) {
                LockPageCnt++;
                space = findSpace();
                // 当前内存已满，需置换
                if(space == -1) {
                    ChangePageCnt++;
                    position = findReplace();
                    Block[position] = Page[i];
                }
                // 当前内存未满，直接加入
                else {
                    Block[space] = Page[i];
                }

            }

            showSingle(Page[i].id);

            for (int j = 0; j < BlockNum; ++j) {
                if (Block[j].id != -1) {
                    Block[j].visit++;  // Block中的页面停留时间+1
                }
            }
        }
        fifo_missRate = (double) LockPageCnt / PageNum;
        printf("缺页次数：%d\n", LockPageCnt);
        printf("置换次数：%d\n", ChangePageCnt);
        printf("FIFO缺页率：%lf%%\n", fifo_missRate*100);
        printf("----FIFO策略-end----\n");
    }

    /// OPT
    void OPT() {
        int exist, space, position;
        double opt_missRate;
        LockPageCnt = 0;
        ChangePageCnt = 0;
        printf("\n----OPT策略-start----\n");
        for (int i = 0; i < PageNum; ++i) {
            exist = findExist(Page[i].id);
            // 当前页面号不在内存中
            if (exist == -1) {
                LockPageCnt++;
                space = findSpace();
                // 当前内存已满，需置换
                if(space == -1) {
                    ChangePageCnt++;
                    for (int k = 0; k < BlockNum; k++) {
                        for (int j = i+1; j < PageNum; j++) {
                            if (Block[k].id != Page[j].id) {
                                Block[k].visit = 1000;
                            } else {
                                Block[k].visit = j-i;
                                break;
                            }
                        }
                    }
                    position = findReplace();
                    Block[position] = Page[i];
                }
                // 当前内存未满，直接加入
                else {
                    Block[space] = Page[i];
                }
            }
            showSingle(Page[i].id);
        }
        opt_missRate = (double) LockPageCnt / PageNum;
        printf("缺页次数：%d\n", LockPageCnt);
        printf("置换次数：%d\n", ChangePageCnt);
        printf("OPT缺页率：%lf%%\n", opt_missRate*100);
        printf("----OPT策略-end----\n");
    }

    /// LRU
    void LRU() {
        int exist, space, position;
        double lru_missRate;
        LockPageCnt = 0;
        ChangePageCnt = 0;
        printf("\n----LRU策略-start----\n");
        for (int i = 0; i < PageNum; ++i) {
            exist = findExist(Page[i].id);
            // 当前页面号不在内存中
            if (exist == -1) {
                LockPageCnt++;
                space = findSpace();
                // 当前内存已满，需置换
                if(space == -1) {
                    ChangePageCnt++;
                    position = findReplace();
                    Block[position] = Page[i];
                }
                    // 当前内存未满，直接加入
                else {
                    Block[space] = Page[i];
                }
            }
            // 当前页面在内存中
            else {
                Block[exist].visit = 0;
            }
            showSingle(Page[i].id);

            for (int j = 0; j < BlockNum; ++j) {
                if (Block[j].id != -1) {
                    Block[j].visit++;  // Block中的页面停留时间+1
                }
            }
        }
        lru_missRate = (double) LockPageCnt / PageNum;
        printf("缺页次数：%d\n", LockPageCnt);
        printf("置换次数：%d\n", ChangePageCnt);
        printf("LRU缺页率：%lf%%\n", lru_missRate*100);
        printf("----LRU策略-end----\n");
    }
};

int main() {
    Pager page;
    int chooseAlgorithm;
    while(true)
    {
        printf("\t-------------------------------------\n");
        printf("\t||                                  ||\n");
        printf("\t||       页面替换策略模拟程序           ||\n");
        printf("\t||           1. FIFO                ||\n");
        printf("\t||           2. LRU                 ||\n");
        printf("\t||           3. OPT                 ||\n");
        printf("\t||           0. 退出程序             ||\n");
        printf("\t||                                  ||\n");
        printf("\t-------------------------------------\n");

        printf("请输入序号进行选择：");
        cin>>chooseAlgorithm;
        switch(chooseAlgorithm)
        {
            case 1:
                page.init();
                page.FIFO();
                break;
            case 2:
                page.init();
                page.LRU();
                break;
            case 3:
                page.init();
                page.OPT();
                break;
            case 0:
                cout<<"正在退出程序..."<<endl;
                system("pause");
                return 0;
            default:
                cout<<"请输入正确的序号进行选择！"<<endl;
        }
    }
}