问题描述：
设计程序模拟先进先出FIFO，最佳置换OPI和最近最久未使用LRU页面置换算法的工作过程。假设内存中分配给每个进程的最小物理块数为m，在进程运行过程中要访问的页面个数为n，页面访问序列为P1, … ,Pn，分别利用不同的页面置换算法调度进程的页面访问序列，给出页面访问序列的置换过程，计算每种算法缺页次数和缺页率。程序要求如下：
1）利用先进先出FIFO，最佳置换OPI和最近最久未使用LRU三种页面置换算法模拟页面访问过程。
2）模拟三种算法的页面置换过程，给出每个页面访问时的内存分配情况。
3）输入：最小物理块数m，页面个数n，页面访问序列P1, … ,Pn，算法选择1-FIFO，2-OPI，3-LRU。
4）输出：每种算法的缺页次数和缺页率
要求：复习页面置换算法，熟悉FIFO，OPI，LRU三种页面分配和置换算法的过程；
实验用例：假定系统为某进程分配了三个物理块，并按以下的页面号引用串测试这三种算法：
7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1。
实验开发环境
clion
程序主要构成部分及其算法说明
主函数里调用了四个函数Input()、FIFO()、OPI()、LRU();、Input():引导用户输入物理、页面数、页面号引用串。FIFO()算法中对第一个页面单独拿出来放进物理块，然后之后的页面进行是否相同检查与物理块是否满了的检查，用LongPageloc来记录在物理块里待的最长时间的页面下标，查找后进行置换或进行下一个页面，输出当前物理块情况，记录缺页数，计算缺页率，并进行输出。OPI()算法中也对第一个页面单独拿出来放进物理块，然后之后的页面进行是否相同检查与物理块是否满了的检查，在三个物理块里比较在之后最晚要使用的页面，记录下标进行置换。输出当前物理块情况，记录缺页数，计算缺页率，并进行输出。LRU()算法中同样也是对第一个页面单独拿出来放进物理块，然后对页面进行是否相同检查与物理块是否满了的检查，在三个物理块里比较在之前中最久没有被访问的，从算法里体现就是在当前物理块里与之前使用过的相同页面距离最远的，如果没有距离就是0，记录下标进行置换。输出当前物理块情况，记录缺页数，计算缺页率，并进行输出。
调试过程和运行结果
附完整代码：
#includeusing namespace std; const int MaxNumber = 100; int PageOrder[MaxNumber]; int OPIBlock[MaxNumber];//OPI算法使用的数组 int LRUBlock[MaxNumber];//LRU算法使用的数组 int BlockOrder[MaxNumber]; //FIFO算法使用的数组 int FarPageloc[MaxNumber]; //OPI算法中储存Block的距离 int OldPageloc[MaxNumber]; //LRU算法中储存Block使用过最近 int PageNum; int BlockNum; //物理块数 bool found; void Input() { cout << "物理块数："; cin >> BlockNum; cout << "页面数："; cin >> PageNum; cout << "页面号引用串："; for (int i = 0; i < PageNum; i++) { cin >> PageOrder[i]; } } void FIFO() { int LackNum = 0; double LackPageRate; cout << "FIFO:" << endl; int LongPageloc = 0, Blockloc = 0; BlockOrder[0] = PageOrder[0]; //放入第一个 cout << PageOrder[0] << " " << BlockOrder[0] << endl; Blockloc += 1; //装满物理块的判定 LongPageloc = 0; //待时间最长的页面下标 for (int i = 1; i < PageNum; i++) { found = false; if (Blockloc < BlockNum) { for (int j = 0; j < Blockloc; j++) { if (PageOrder[i] == BlockOrder[j]) { found = true; break; } } if (!found) { BlockOrder[Blockloc] = PageOrder[i]; Blockloc += 1; } cout << PageOrder[i] << " "; for (int temp = 0; temp < Blockloc; temp++) { cout << BlockOrder[temp] << " "; } cout << endl; } else { for (int j = 0; j < BlockNum; j++) { if (PageOrder[i] == BlockOrder[j]) { found = true; break; } } if (!found) { BlockOrder[LongPageloc] = PageOrder[i]; LongPageloc += 1; if (LongPageloc == 3) { LongPageloc = 0; } LackNum += 1; } cout << PageOrder[i] << " "; for (int temp = 0; temp < BlockNum; temp++) { cout << BlockOrder[temp] << " "; } cout << endl; } } LackNum = LackNum+BlockNum; LackPageRate = (double)LackNum / PageNum; cout << "缺页数：" << LackNum << "缺页率：" << LackPageRate * 100 << "%" << endl; } void OPI() { cout << "OPI:" << endl; int Blockloc = 0;//装满物理块的判定 int LackNum = 0; double LackPageRate; OPIBlock[0] = PageOrder[0]; cout << PageOrder[0] << " " << OPIBlock[0] << endl; Blockloc += 1; for (int i = 1; i < PageNum; i++) { found = false; if (Blockloc < BlockNum) { for (int j = 0; j < Blockloc; j++) { if (PageOrder[i] == OPIBlock[j]) { found = true; break; } } if (!found) { OPIBlock[Blockloc] = PageOrder[i]; Blockloc += 1; } cout << PageOrder[i] << " "; for (int temp = 0; temp < Blockloc; temp++) { cout << OPIBlock[temp] << " "; } cout << endl; } else { for (int j = 0; j < BlockNum; j++) { if (PageOrder[i] == OPIBlock[j]) { found = true; break; } } if (!found) { for (int j = 0; j < BlockNum; j++) { bool farFound = false; for (int k = i + 1; k < PageNum; k++) { if (OPIBlock[j] == PageOrder[k]) { FarPageloc[j] = k; farFound = true; break; } } if (!farFound) { FarPageloc[j] = PageNum; } } int FarMax = FarPageloc[0]; int Farloc = 0; //找出未来最晚使用的下标 for (int j = 1; j < BlockNum; j++) { if (FarPageloc[j] > FarMax) { FarMax = FarPageloc[j]; Farloc = j; } } OPIBlock[Farloc] = PageOrder[i]; LackNum += 1; } cout << PageOrder[i] << " "; for (int temp = 0; temp < BlockNum; temp++) { cout << OPIBlock[temp] << " "; } cout << endl; } } LackNum = LackNum+BlockNum; LackPageRate = (double)LackNum / PageNum; cout << "缺页数：" << LackNum << "缺页率：" << LackPageRate * 100 << "%" << endl; } void LRU() { cout << "LRU:" << endl; int Blockloc = 0;//装满物理块的判定 int OldBlockloc; int LackNum = 0; double LackPageRate; LRUBlock[0] = PageOrder[0]; OldBlockloc = 0; cout << PageOrder[0] << " " << LRUBlock[0] << endl; Blockloc += 1; for (int i = 1; i < PageNum; i++) { found = false; if (Blockloc < BlockNum) { for (int j = 0; j < Blockloc; j++) { if (PageOrder[i] == LRUBlock[j]) { found = true; break; } } if (!found) { LRUBlock[Blockloc] = PageOrder[i]; Blockloc += 1; } cout << PageOrder[i] << " "; for (int temp = 0; temp < Blockloc; temp++) { cout << LRUBlock[temp] << " "; } cout << endl; } else { for (int j = 0; j < BlockNum; j++) { if (PageOrder[i] == LRUBlock[j]) { found = true; break; } } if (!found) { for (int j = 0; j < BlockNum; j++) { for (int k = i - 1; k >= 0; k--) { if (LRUBlock[j] == PageOrder[k]) { OldPageloc[j] = k; break; } } } int OldMax = OldPageloc[0]; int Oldloc = 0; for (int j = 1; j < BlockNum; j++) { if (OldPageloc[j] < OldMax) { OldMax = OldPageloc[j]; Oldloc = j; } } LRUBlock[Oldloc] = PageOrder[i]; LackNum += 1; } cout << PageOrder[i] << " "; for (int temp = 0; temp < BlockNum; temp++) { cout << LRUBlock[temp] << " "; } cout << endl; } } LackNum = LackNum+BlockNum; LackPageRate = (double)LackNum / PageNum; cout << "缺页数：" << LackNum << "缺页率：" << LackPageRate * 100 << "%" << endl; } int main() { //7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 测试数据 Input(); FIFO(); OPI(); LRU(); //system("pause"); //int temp; //cout << "请输入想选择的算法"; //cin >> temp; }
