页面置换模拟
一、实验目的和要求
（一）实验目的
通过模拟实现请求页式存储管理的基本几种页面置换算法，了解虚拟存储技术的特点，掌握虚拟存储请求页式存储管理中的基本页面置换算法的基本思想和实现过程，并比较他们的效率。
（二）实验内容
设计一个虚拟存储区和内存工作区，并使用下述算法访问命中率
1.最佳淘汰算法（OPT）。 2.先进先出算法（FIFO）。 3.最近最久未使用算法（LRU）。
（三）实验指导
1.假设分给一作业的内存块数为4，每条指令占一个存储单元，每个页面中可存放10条指令。
2.设计一个程序，模拟一作业的执行过程。设改作业共有160条指令，即他们的地址空间为16页，最初作业的所有页面都还未调入内存。在模拟过程中，如果所访问的指令都已经在内存，则显示其物理地址，并转吓一条指令。如果所访问的指令都未装入内存，则发生缺页，此时需要记录缺页的次数，并将相应页调入内存。如果4个内存块中均已装入该作业的虚页面，则需进行页面置换；在所有200条指令执行完毕后，请计算并显示作业运行过程中发生的缺页率。
3.作业中指令的访问次序要按如下原则生成。 具体实施的办法是：
（1）在[0,159]之间随机选举一条起始执行指令，其序号为 m ;
（2）顺序执行两条指令，即序号为 m+1 、m+2 的指令;
（3）通过随机数，跳转到前地址部分[0,m-1]中的某条指令处，其序号为 m1;
（4）顺序执行两条指令，即序号为 m1+1 、m1+2的指令;
（5）通过随机数，跳转到后地址部分[m1+3,159]中的某条指令处，其序号为 m2;
（6）顺序执行两条指令，即序号为 m2+1、m2+2 的指令;若m2+2>159 只执行一条指令;
（7）重复 “跳转到前地址部分、顺序执行、跳转到后地址部分、顺序执行”的过程，直至执行完全部200条指令。
二、实验环境
PC(Windows 10) Visual Studio 2015
三、实验步骤
流程图：
1.实现一个Random类，能按实验指导3的规则生成长度为200的指令的访问次序，并将其打印、输出。
/*
Random类：
按240页第三条要求生成[0,e](e默认为159)长度为n(默认为200)的随机数表
*/
class Random
{
public:
Random(int e = 159, int n = 200)
{
end = e; number = n;
srand(unsigned(time(0)));//将time(0)作为随机数种子
randomTable = new int[number];//创建一个长度为number(默认200)的数组
//按要求生成数列
int i = 0;
randomTable[i] = random(0, end);
int m = randomTable[i], m1;
i++; if (m == end) { goto A; }
randomTable[i] = m + 1;
i++; if (m == end - 1) { goto A; }
randomTable[i] = m + 2;
i++; if (m == 0) { m1 = 0; goto B; }
A:
for (; i < number; )
{
randomTable[i] = random(0, m - 1);
m1 = randomTable[i];
i++; if (i >= number) { break; } if (m1 == end - 1) { goto B; }
randomTable[i] = ++m1;
i++; if (i >= number) { break; } if (m1 == end - 2) { goto B; }
randomTable[i] = ++m1;
i++; if (i >= number) { break; }
B:
randomTable[i] = random(++m1, end);
m = randomTable[i];
i++; if (i >= number) { break; } if (m == end - 1) { goto A; }
randomTable[i] = m + 1;
i++; if (i >= number) { break; } if (m == end - 2) { goto A; }
randomTable[i] = m + 2;
i++;
}
//生成数列完成
}
//打印数列中的数字，每20个换一次行
void printAll()
{
for (int i = 0; i < 200; i++)
{
cout << setw(4) << randomTable[i] << " ";
if (i % 20== 19)
{
cout << endl;
}
}
}
//输出第i个随机数
int output(int &i)
{
return randomTable[i];
}
private:
int *randomTable;
int end, number;
//随机生成[start,end]中的一个数
int random(int start, int end)
{
return start + rand() % (end + 1 - start);
}
};
2．实现一个页面置换（pageReplace）类，该类需包含3个成员函数OPT，FIFO，LRU分别实现最佳淘汰算法、先进先出算法、最近最久未使用算法。
数据成员：
int pageLength;//每页可以放指令的数量
int *pageInRam;//该指针指向一个长度为内存块数ramLength的数组，数组中的数依次记录该内存块中存放的页的页号
int ramLength;//内存块数
int pageUsed;//即将使用的页的页号
int t;//FIFO算法中，t为下一个被置换的内存的下标
int count;//计数器，记录缺页的次数
int number;//需要执行指令的数量
Random *R;
int *timeTable;//LRU算法中，页在内存中已经持续的时间
int *timeTable2;//OPT算法中，页在内存中到下次再被访问的时间
（1）OPT函数
为实现OPT算法，需创建一个长度为4的表timeTable2 = new int[ramLength]用来分别记录4个内存块中的页从此时到下次置换所需要的时间。每读取一个新的指令时，timeTable2中所有的元素都减1；如果该指令需要页面置换，则对从此时到下次置换所需要的时间最长的页进行置换；无论是否发生置换，都要重新计算该指令所在的页从此时到下次置换所需要的时间，并记录在timeTable2相应位置中。
实现方法如下：
//最佳淘汰
void OPT()
{
for (int i = 0; i < ramLength; i++)//初始化pageInRam，ramLength值为0表示未放入任何页，timeTable2[i] = 9999999表示永远不会使用
{
pageInRam[i] = 0;
timeTable2[i] = 9999999;
}
count = 0;
for (int i = 0; i < number; i++)//执行最佳淘汰（单步）number次
{
cout << "No." << setw(3) << i + 1 << ": " << "第" << setw(5) << R->output(i) << "条指令,在第" << setw(5) << (pageUsed = R->output(i) / pageLength + 1) << "页";
oneStepOPT(i);
cout << endl;
}
cout << "OPT缺页率" << count*100.0 / number << "%" << endl;
}
//最佳淘汰（单步）
void oneStepOPT(int &i)
{
int a = Max(timeTable2);//a为最长时间内不再访问的页的下标
int JUD = judge();
for (int j = 0; j < ramLength; j++)//所有页在内存中到下次再被访问的时间减1
{
timeTable2[j]--;
}
if (JUD == -1)//如果需要置换
{
pageInRam[a] = pageUsed;//页到下次再被访问的时间最长的那个页被置换
timeTable2[a] = 1;
for (int p = i + 1; p < number; p++)//计算这个页多久后会被再次使用
{
if (pageInRam[a] == R->output(p) / pageLength + 1)
{
break;
}
timeTable2[a]++;
}
cout << setw(10) << " 缺页";
count++;
}
else//如果不需要置换
{
timeTable2[JUD] = 1;
for (int p = i + 1; p < number; p++)//计算这个页多久后会被再次使用
{
if (pageInRam[JUD] == R->output(p) / pageLength + 1)
{
break;
}
timeTable2[JUD]++;
}
cout << setw(10) << " 不缺页";
}
printPageInRam();
}
（2）FIFO函数
实现该算法，需要一个指针t，该指针永远指向下一个最先进入的页。若发生置换，则将指针t中的页置换出，并使t重新指向下一个最先进入的页。
实现方法如下：
//先进先出
void FIFO()
{
for (int i = 0; i < ramLength; i++)//初始化pageInRam，值为0表示未放入任何页
{
pageInRam[i] = 0;
}
count = 0;//记录 进行页面置换次数 的计数器清零
for (int i = 0; i < number; i++)//执行先进先出（单步）number次
{
cout << "No." << setw(3) << i + 1 << ": " << "第" << setw(5) << R->output(i) << "条指令,在第" << setw(5) << (pageUsed = R->output(i) / pageLength + 1) << "页";
oneStepFIFO();
cout << endl;
}
cout << "FIFO缺页率" << count*100.0 / number << "%" << endl;
}
//先进先出（单步）
void oneStepFIFO()
{
int JUD = judge();
if (JUD == -1)
{
pageInRam[t] = pageUsed;//下标为t的内存块中的页被置换
t = (t + 1) % ramLength;//t指向下一个要被置换的（最先进入的）内存块
cout << setw(10) << " 缺页";
count++;
}
else
{
cout << setw(10) << " 不缺页";
}
printPageInRam();
}
（3）LRU函数
为实现LRU算法，需创建一个长度为4的表timeTable = new int[ramLength]用来分别记录4个内存块中的页在内存中没有被访问的时间。每读取一个新的指令时，timeTable中所有的元素都加1；如果该指令需要页面置换，则对在内存中没有被访问的时间最长的页进行置换；无论是否发生置换，都要将该指令所在的页对应的timeTable中的值清零。
//最近最久未使用
void LRU()
{
for (int i = 0; i < ramLength; i++)//初始化pageInRam，ramLength值为0表示未放入任何页，timeTable值为0表示刚被使用过
{
pageInRam[i] = 0;
timeTable[i] = 0;
}
count = 0;
for (int i = 0; i < number; i++)//执行最近最久未使用（单步）number次
{
cout << "No." << setw(3) << i + 1 << ": " << "第" << setw(5) << R->output(i) << "条指令,在第" << setw(5) << (pageUsed = R->output(i) / pageLength + 1) << "页";
oneStepLRU();
cout << endl;
}
cout << "LRU缺页率" << count*100.0 / number << "%" << endl;
}
//最近最久未使用（单步）
void oneStepLRU()
{
int JUD = judge();
for (int i = 0; i < ramLength; i++)//所有内存块未使用时间增加1
{
timeTable[i]++;
}
int a = Max(timeTable);
if (JUD == -1)
{
pageInRam[a] = pageUsed;//未使用时间最长的内存块被置换
timeTable[a] = 0;//该内存块未使用时间清零
cout << setw(10) << " 缺页";
count++;
}
else
{
timeTable[JUD] = 0;
cout << setw(10) << " 不缺页";
}
printPageInRam();
}