目的：
熟悉页面置换算法及其实现，引入计算机系统性能评价方法的概念。
内容：
编制页面置换算法的模拟程序。
要求：
- 用随机数方法产生页面走向，页面走向长度为L。
- 根据页面走向，分别采用FIFO和LRU算法进行页面置换，统计缺页率。
- 假定可用内存块和页表长度 (作业的页面数)分别为m和k，初始时，作业页面都不在内存。
随机数产生程序：
function random: real:
begin Seed: =125.0*(seed+1.0)
Seed: =Seed-8192.0*trunc (seed/8192)
random: = (Seed+0.5)/8192
end;
上述随机数发生函数产生的随机数为0.0~1.0，稍另变化就可得到0~n-1之间的随机数。
程序开始时，应对变量Seed (实型)赋初值。
#include <cstdio>
#include <iostream>
#include <algorithm>using namespace std;
#define MAX_L 1000
#define MAX_M 1000
int m,k;//可用内存块和作业的页面数分别为m和k
int ReqPage[MAX_L],L;//页面走向长度为Ldouble random() { static double Seed = 233; //随机种子，在此处可改变初值 Seed = 125.0 * (Seed + 1.0);Seed = Seed - 8192.0 * (int)(Seed/8192);return (Seed+0.5)/8192;
}void CALC_FIFO() {cout << "FIFO算法\n"; static int PageTable[MAX_M];int missNum = 0;for (int i = 0; i<m && i<L; i++) {PageTable[i] = ReqPage[i];missNum++;}int lastId = 0;if (L > m) {for (int i = m; i < L; i++) {int *pageIt = find(PageTable, PageTable+m, ReqPage[i]);if (pageIt != PageTable+m) continue;missNum++;printf("第%d次缺页，%d换入，%d换出\n",missNum,ReqPage[i],PageTable[lastId]);PageTable[lastId] = ReqPage[i]; lastId = lastId+1;if (lastId == m) lastId = 0;}}printf("缺页率%g\n", 1.0*missNum/L);
}void CALC_LRU() {cout << "LRU算法\n"; int PageTable[MAX_M];int LastVisitTime[MAX_M]; //记录最近访问时间 int missNum = 0;for (int i = 0; i<m && i<L; i++) {PageTable[i] = ReqPage[i];LastVisitTime[i] = i;missNum++;}if (L > m) {for (int i = m; i < L; i++) {int *pageIt = find(PageTable, PageTable+m, ReqPage[i]);if (pageIt != PageTable+m) {LastVisitTime[pageIt - PageTable] = i;continue;}missNum++;int *minLastVisitIt = min_element(LastVisitTime, LastVisitTime + m);int pageOutId = minLastVisitIt - LastVisitTime;printf("第%d次缺页，%d换入，%d换出\n",missNum,ReqPage[i],PageTable[pageOutId]);PageTable[pageOutId] = ReqPage[i]; LastVisitTime[pageOutId] = i;}}printf("\n缺页率%g\n", 1.0*missNum/L);
}int main() {cout << "请分别输入可用内存块m,作业的页面数k,页面走向长度为L\n";cin >> m >> k >> L;cout << "随机生成的页面走向为:\n";for (int i = 0; i < L; i++) {ReqPage[i] = static_cast<int>(random() * k);// random()生成0~1， random()*k 向零取整为0~k-1 cout << ReqPage[i]<< " ";}puts("");//！！！因为请求序列是随机生成的，不符合局部性原理，很多情况下LRU表现不比FIFO好 CALC_FIFO();CALC_LRU();return 0;
}