虚拟内存页面置换算法实验报告
软 件 学 院
上 机 实 验 报 告
课程名称： 操作系统原理
实验项目： 虚拟内存页面置换算法
实 验 室： 地狱018
姓 名： 死神 学 号：
专业班级： 实验时间： 2015/12/13
一、 实验目的及要求
通过这次实验，加深对虚拟内存页面置换概念的理解，进一步掌握先进先出FIFO最佳置换OPI和最近最久未使用LRU页面置换算法的实现方法。结合Linux的内层的分析方法查看内存的分配过程及linux kernel的内存管理机制
二、 实验性质
设计性
三、 实验学时
4学时
四、 实验环境
实验环境1.实验环境： C与C++程序设计学习与实验系统
2.知识准备：
（1）使用Linux的基本命令；
（2）了解Linux vmstat、free、top等命令查看linux系统的内存
分配情况；
（3） 掌握虚拟内存页面置换算法FIFO等基本算法理论。
五、 实验内容及步骤
假设有n个进程分别在T1, … ,Tn时刻到达系统，它们需要的服务时间分别为S1, … ,Sn。分别采用先来先服务FCFS和短作业优先SJF进程调度算法进行调度，计算每个进程的完成时间、周转时间和带权周转时间，并且统计n个进程的平均周转时间和平均带权周转时间。
步骤
通过已知最小物理块数、页面个数、页面访问序列、及采用置换方式可以得出页面置换的缺页次数和缺页率，及每次缺页时物理块中存储。
1．输入的形式
int PageOrder[MaxNumber];//页面序列
int PageNum,LackNum=0,BlockNum;//页面个数，缺页次数，最小物理块数
2. 输出的形式
double LackPageRate//缺页率
缺页个数
每次缺页时物理块中存储
程序所能达到的功能
模拟先进先出FIFO、最佳置换OPI和最近最久未使用LRU假设内存中分配给每个进程的最小物理块数为m，在进程运行过程中要访问的页面个数为n，页面访问序列为P1, … ,Pn，分别利用不同的页面置换算法调度进程的页面访问序列，给出页面访问序列的置换过程，计算每种算法缺页次数和缺页率。测试数据，包括正确的输入及其输出结果和含有错误的输入及其输出结果。
程序中用到的所有抽象数据类型的定义、主程序的流程以及各程序模块之间的层次(调用)关系。
int PageOrder[MaxNumber];//页面序列
int PageCount[MaxNumber]={0};//计算内存内数据离下一次出现的距离
int PageNum,LackNum=0,BlockNum;//页面个数，缺页次数，最小物理块数 double LackPageRate=0;
bool found=false;
六、实验数据及结果分析
运行截图：
图6.1
图6.2
图6.3
七、实验总结
这次试验，让我加深了对虚拟内存页面置换算法的理解，进一步掌握先进先出FIFO最佳置换OPI和最近最久未使用LRU页面置换算法的实现方法。熟悉Linux需要经过大量的实验、改进与思考，在编写代码的过程中遇到了一些问题要积极面对并通过讨论上网或者问老师解决。通过这次试验我了解了虚拟内存置换算法的一些知识，是我对于所学习的专业知识得到了更好的巩固和提升。
附录 源程序清单
#include
using namespace std;
#define MaxNumber 100
void OPI(int PageOrder[MaxNumber],int PageCount[MaxNumber],
found)
{
int module[MaxNumber];
int sum=0;
int i,j,k,m;
for(i=0;i
{
module[i]=PageOrder[i];
sum++; int PageNum,int LackNum,int BlockNum, double LackPageRate,bool
for(j=0;j
cout
cout
}
LackNum=BlockNum;
for(i=BlockNum;i
{
found=false;
for(j=0;j
}
if(found==false)//缺页，选择替换
{ for(j=0;j
PageCount[j]=0;
for(k=i+1;k
{ if(module[j]!=PageOrder[k]) PageCount[j]++; else break; }
} int max=PageCount[0];
int kind=0;
for(j=0;j
{
if(PageCount[j]>max) { } max=PageCount[j]; kind=j;
}
module[kind]=PageOrder[i];
LackNum++; for(m=0; m
LackPageRate=(LackNum*1.0)/PageNum;
cout
cout
}
/******************************
*************************************/
void FIFO(int PageOrder[MaxNumber],int PageCount[MaxNumber],
found)
{ int PageNum,int LackNum,int BlockNum, double LackPageRate,bool 先进先出置换算法
int module[MaxNumber];
int sum=0;
int i,j,m;
for(i=0;i
{
module[i]=PageOrder[i];
sum++;
PageCount[i]=3-i;
for(j=0;j
cout
cout
}
LackNum=BlockNum;
for(i=BlockNum;i
{
found=false;
for(j=0;j
}
if(found==false)//缺页，选择替换
{ int max=PageCount[0];
int kind=0; for(j=0;jmax) { } max=PageCount[j]; kind=j; } for(int k=0;k
PageCount[k]++;
}
module[kind]=PageOrder[i];
PageCount[kind]=0;// 替换之后已经查询的次数改为0
LackNum++; for(m=0; m
LackPageRate=(LackNum*1.0)/PageNum;
cout
cout
}
/******************************最近最久未使用置换算法*************************************/
void LRU(int PageOrder[MaxNumber],int PageCount[MaxNumber],
found)
{ int PageNum,int LackNum,int BlockNum, double LackPageRate,bool
int module[MaxNumber];
int sum=0;
int i,j,m;
for(i=0;i
{
module[i]=PageOrder[i];
sum++;
PageCount[i]=3-i;
for(j=0;j
cout
cout
}
LackNum=BlockNum;
for(i=BlockNum;i
{
found=false;
for(j=0;j
PageCount[j]=0;//查询后，更改次数
for(int k=0;k
PageCount[k]++;
} break; }
}
if(found==false)//缺页，选择替换
{ int max=PageCount[0];
int kind=0;
for(j=0;j
{
if(PageCount[j]>max) { } max=PageCount[j]; kind=j;
}
for(int k=0;k
{ if(k!=kind)
PageCount[k]++;
}
module[kind]=PageOrder[i];
PageCount[kind]=0;// 替换之后未查询的次数改为0
LackNum++;
for(m=0; m
cout
} }
LackPageRate=(LackNum*1.0)/PageNum;
cout
cout
}
int main ()
{
int PageOrder[MaxNumber];//页面序列
int PageCount[MaxNumber]={0};//计算内存内数据离下一次出现的距离 int PageNum,LackNum=0,BlockNum;//页面个数，缺页次数，最小物理块数 double LackPageRate=0; bool found=false; int chioce1=0,chioce2,chioce3;
int i=0;
while(chioce1==0) { cout>chioce2; if(chioce2==1) {
cout
cin>> PageNum; cout>BlockNum; cout>PageOrder[i]; }
cout>chioce3;
if(chioce3==1)
FIFO(PageOrder,PageCount,PageNum,LackNum,
LackPageRate, found);
else
{
if(chioce3==2) BlockNum,
OPI(PageOrder,PageCount,PageNum,LackNum, BlockNum, LackPageRate, found);
else BlockNum, LRU(PageOrder,PageCount,PageNum,LackNum,
LackPageRate, found);
} cout
} cout>chioce1; }