# PageReplacementAlgorithm **Repository Path**: CodexploRe/PageReplacementAlgorithm ## Basic Information - **Project Name**: PageReplacementAlgorithm - **Description**: PageReplacementAlgorithm项目使用c++代码实现模拟操作系统采用OPT、FIFO和LRU算法进行页面置换的过程。 - **Primary Language**: Unknown - **License**: MIT - **Default Branch**: master - **Homepage**: None - **GVP Project**: No ## Statistics - **Stars**: 0 - **Forks**: 0 - **Created**: 2024-06-08 - **Last Updated**: 2025-03-29 ## Categories & Tags **Categories**: Uncategorized **Tags**: None ## README # 操作系统页面置换模拟 ## 概述本项目旨在模拟操作系统的页面置换过程，通过实现不同的页面置换算法（OPT、FIFO、LRU），加深对页式虚拟存储器实现原理的理解，并掌握页面置换的模拟方法。 ## 实验结果实验结果将展示不同页面序列和不同内存块数下(假设页面大小和内存块大小相同)，OPT、FIFO和LRU算法的流程和最终的缺页中断率。 ## 测试样例以下是程序的测试样例，展示了如何使用不同的页面置换算法处理给定的页号序列。 > 样例来自《操作系统教程》谢旭升等机械工业出版社 P146 ```cpp #include #include "BaseAlgorithm.h" #include "FIFO.h" #include "LRU.h" #include "OPT.h" using namespace std; void start(BaseAlgorithm* algo, const bool& verbose = false) { algo->start(verbose); // 启动算法，可以选择是否显示中间日志 cout << endl; } int main() { // 给定的页号序列 const vector pageList = {7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1}; // 内存块的最大数量 constexpr int maxSize = 3; // 创建页面置换算法实例 auto* fifo = new FIFO(pageList, maxSize); auto* lru = new LRU(pageList, maxSize); auto* opt = new OPT(pageList, maxSize); // 运行算法并打印结果 start(fifo, true); // 显示FIFO算法的中间日志 start(lru); // 不显示LRU算法的中间日志 start(opt); // 不显示OPT算法的中间日志 // 释放算法实例 delete fifo; delete lru; delete opt; return 0; } ``` ### 运行结果 - FIFO算法部分（显示了中间日志） ```shell --------------------------------------- --------------- FIFO ------------------ --------------------------------------- Try to insert page: 7 Limit! Total limit times now: 1 Insert page: 7 --------------------------------------- Try to insert page: 0 Limit! Total limit times now: 2 Insert page: 0 --------------------------------------- Try to insert page: 1 Limit! Total limit times now: 3 Insert page: 1 --------------------------------------- Try to insert page: 2 Limit! Total limit times now: 4 Exchange page: 7 ----> 2 --------------------------------------- Try to insert page: 0 No problem~ --------------------------------------- Try to insert page: 3 Limit! Total limit times now: 5 Exchange page: 0 ----> 3 --------------------------------------- Try to insert page: 0 Limit! Total limit times now: 6 Exchange page: 1 ----> 0 --------------------------------------- Try to insert page: 4 Limit! Total limit times now: 7 Exchange page: 2 ----> 4 --------------------------------------- Try to insert page: 2 Limit! Total limit times now: 8 Exchange page: 3 ----> 2 --------------------------------------- Try to insert page: 3 Limit! Total limit times now: 9 Exchange page: 0 ----> 3 --------------------------------------- Try to insert page: 0 Limit! Total limit times now: 10 Exchange page: 4 ----> 0 --------------------------------------- Try to insert page: 3 No problem~ --------------------------------------- Try to insert page: 2 No problem~ --------------------------------------- Try to insert page: 1 Limit! Total limit times now: 11 Exchange page: 2 ----> 1 --------------------------------------- Try to insert page: 2 Limit! Total limit times now: 12 Exchange page: 3 ----> 2 --------------------------------------- Try to insert page: 0 No problem~ --------------------------------------- Try to insert page: 1 No problem~ --------------------------------------- Try to insert page: 7 Limit! Total limit times now: 13 Exchange page: 0 ----> 7 --------------------------------------- Try to insert page: 0 Limit! Total limit times now: 14 Exchange page: 1 ----> 0 --------------------------------------- Try to insert page: 1 Limit! Total limit times now: 15 Exchange page: 2 ----> 1 FIFO process: [0] input: 7 7 + [1] input: 0 7 0 + [2] input: 1 7 0 1 + [3] input: 2 0 1 2 + [4] input: 0 0 1 2 [5] input: 3 1 2 3 + [6] input: 0 2 3 0 + [7] input: 4 3 0 4 + [8] input: 2 0 4 2 + [9] input: 3 4 2 3 + [10] input: 0 2 3 0 + [11] input: 3 2 3 0 [12] input: 2 2 3 0 [13] input: 1 3 0 1 + [14] input: 2 0 1 2 + [15] input: 0 0 1 2 [16] input: 1 0 1 2 [17] input: 7 1 2 7 + [18] input: 0 2 7 0 + [19] input: 1 7 0 1 + --------------------------------------- OutPageList: 7 0 1 2 3 0 4 2 3 0 1 2 Limit ratio: 0.750 --------------------------------------- ``` 参照课本内容： ![FIFO](README.assets/FIFO.jpg) - LRU算法部分 ```shell --------------- LRU ------------------ LRU process: [0] input: 7 7 + [1] input: 0 7 0 + [2] input: 1 7 0 1 + [3] input: 2 2 0 1 + [4] input: 0 2 0 1 [5] input: 3 2 0 3 + [6] input: 0 2 0 3 [7] input: 4 4 0 3 + [8] input: 2 4 0 2 + [9] input: 3 4 3 2 + [10] input: 0 0 3 2 + [11] input: 3 0 3 2 [12] input: 2 0 3 2 [13] input: 1 1 3 2 + [14] input: 2 1 3 2 [15] input: 0 1 0 2 + [16] input: 1 1 0 2 [17] input: 7 1 0 7 + [18] input: 0 1 0 7 [19] input: 1 1 0 7 --------------------------------------- OutPageList: 7 1 2 3 0 4 0 3 2 Limit ratio: 0.600 --------------------------------------- ``` 参照课本内容： ![LRU](README.assets/LRU.jpg) - OPT算法部分 ```shell --------------- OPT ------------------ OPT process: [0] input: 7 7 + [1] input: 0 7 0 + [2] input: 1 7 0 1 + [3] input: 2 2 0 1 + [4] input: 0 2 0 1 [5] input: 3 2 0 3 + [6] input: 0 2 0 3 [7] input: 4 2 4 3 + [8] input: 2 2 4 3 [9] input: 3 2 4 3 [10] input: 0 2 0 3 + [11] input: 3 2 0 3 [12] input: 2 2 0 3 [13] input: 1 2 0 1 + [14] input: 2 2 0 1 [15] input: 0 2 0 1 [16] input: 1 2 0 1 [17] input: 7 7 0 1 + [18] input: 0 7 0 1 [19] input: 1 7 0 1 --------------------------------------- OutPageList: 7 1 0 4 3 2 Limit ratio: 0.450 --------------------------------------- ``` 参照课本内容： ![OPT](README.assets/OPT.jpg) ## 代码结构 - `main.cpp`: 主程序文件，包含页面置换模拟的实现。 - `BaseAlgorithm.h`: 页面置换算法基类的声明。 - `OPT.h`: OPT算法的实现。 - `FIFO.h`: FIFO算法的实现。 - `LRU.h`: LRU算法的实现。 ## 许可本项目采用 [MIT 许可证](LICENSE)。