页面置换算法模拟_页面置换算法模拟设计
页面置换算法模拟由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“页面置换算法模拟设计”。
“计算机操作系统”课程设计大作业
一、题目: 页面置换算法模拟实验
二、目的分别采用最佳(Optimal)置换算法、先进先出(FIFO)页面置换算法和最近最少使用(LRU)置换算法对用户输入的页面号请求序列进行淘汰和置换，从而加深对页面置换算法的理解。
三、内容和要求
请用C/C++语言编一个页面置换算法模拟程序。用户通过键盘输入分配的物理内存总块数，再输入用户逻辑页面号请求序列，然后分别采用最佳(Optimal)置换算法、先进先出(FIFO)页面置换算法和最近最少使用(LRU)置换算法三种算法对页面请求序列进行转换，最后按照课本P150页图4-26的置换图格式输出每次页面请求后各物理块内存放的虚页号，并算出每种算法的缺页次数。最后评价三种页面置换算法的优缺点。
三种页面置换算法的思想可参考教材P149-P152页。
假设页面号请求序列为4、3、2、1、4、3、5、4、3、2、1、5，当分配给某进程的物理块数分别为3块和4块时，试用自己编写的模拟程序进行页面转换并输出置换图和缺页次数。
四、提交内容 本大作业每个人必须单独完成，大作业以WORD附件形式提交。最后需提交的内容包括：算法算法思路及流程图、数据结构说明、源程序（关键代码需要注释说明）、运行结果截图、心得体会及总结。
大作业严禁抄袭。发现抄袭一律以不及格论。
请大家严格按照大作业题目来编写程序，不要上交以前布置的大作业。如果提交的大作业题目与本文档要求不符，成绩一律为不及格。
请大家按时在网院网上系统里提交大作业，过了规定时间将无法再补交大作业。
页面置换算法模拟实验
算法算法思路
模拟FIFOOPTLRU这3种页面置换算法，先分配所需的内存空间，在根据已知的序列，分别根据不同的页面算法去访问已知序列，得出不同内存空间的置换算法的缺页数量。总体流程图
开始输入内存数执行页面置换FIFOLRUOPT显示结果结束
数据结构说明
源程序（关键代码需要注释说明）FIFO关键源码
LRU关键源码
OPT关键源码
程序源码
#include using namespace std;#define N 12 //默认序列12 #define M 4 // 默认开辟4 内存空间 struct page{ int pno;// 定义页号
int bno;//定义块号
int time;// 定义最近使用
int status;//定义命中状态
int order;//定义优先级 };
int list[12]={4,3,2,1,4,2,5,2,3,2,1,5};// 已知序列
// 输出方法
void output(int *a ,int n){ for(int i=0;i
cout
a++;} cout
void fifo(int *list,int mem_num){
page p[N];// 定义记录数组
int flag;int mem[M];// 定义内存
int index =0;// 默认下标
int lack=0;// 初始化内存
for(int i=0;i
mem[i]=0;} // 遍历序列
for(i=0;i
flag=0;// 设置默认命中 0
for(int j=0;j
if(list[i]==mem[j]){ // 检测序列与已知内存值，命中返回flag
flag=1;
break;
}
}
if(flag==1){ // 判断是否命中，则对 p 赋值
p[i].bno = j+1;
p[i].pno = list[i];
p[i].status =1;
}else{
p[i].pno = list[i];
p[i].status = 0;
mem[index] = list[i];
p[i].bno = index+1;// 赋予 页号
index =(index+1)%mem_num;// 每次取余
lack++;
} }
cout
cout
cout
cout
cout
}
struct mem{ int order;//内存优先级 主要用于识别是否不常用
int pno;// 内存页号
int time;// 记录是否最近使用 };
void lru(int *list,int mem_num){ page p[N];// 定义记录数组
int flag;mem m[M];// 定义内存
int index =0;// 默认下标
int lack=0;int temp;int max=0;// 内存赋值
for(int i=0;i
m[i].pno=0;
//默认初始优先级 0
m[i].order = 0;} for(i=0;i
flag=0;
for(int j=0;j
if(list[i]==m[j].pno){
flag=1;
index=j;
//m[j].order++;
p[i].order =m[j].order;
break;
}
}
if(flag==1){ //命中后，p[i].bno = index+1;
p[i].pno = list[i];
p[i].status = 1;
p[i].order--;
temp = p[i].order;
for(j=0;j
if(p[j].order
temp=p[j].order;
index = p[j].bno;
}
}
}else{
p[i].status=0;
p[i].pno = list[i];
m[index].pno = list[i];
m[index].order = p[i].order;
p[i].bno = index+1;
for(j=0;j
if(m[j].order>max){
index = j;
}
}
index =(index+1)%mem_num;// 每次取余有效的下标
//max++;
lack++;
} } cout
cout
cout
cout
void opt(int *list,int mem_num){ page p[N];//定义页面
mem m[M];int flag=0;int index = 0;//下标
int max = N;int lack=0;for(int i=0;i
m[i].pno=0;
m[i].time = 0;//设置内存使用频率
}
for(i=0;i
flag=0;
for(int j=0;j
if(list[i]==m[j].pno){
flag=1;
index = j;
break;
}
}
if(flag==1){
p[i].status =1;
p[i].bno = index+1;
p[i].pno = list[i];
for(j=0;j
for(int g=i;g
if(m[j].pno==list[g]){
m[j].time = N-g;//获取到 最近使用
p[i].time = m[j].time;
index = j;
}
}
}
}else{
p[i].status =0;
p[i].pno = list[i];
m[index].pno = list[i];
m[index].time = N;//设置默认不使用
p[i].bno =index+1;
for(j=0;j
if(m[j].time>max){
index = j;
}
}
index =(index+1)%mem_num;
lack++;
}
} cout
cout
cout
cout
cout
void main(){ int m;cout > m;cout
}
运行结果截图
FIFO、LRU、OPT运行截图（开辟3个内存空间）：
FIFO、LRU、OPT运行截图（开辟4个内存空间）：
心得体会及总结：
在开始做题目的时候，需要了解什么是FIOFOLRUOPT这3个页面置换的知识点，同时参考了网络上许多实现过程技巧，并在在纸上面简单画出页面如何记录如何与内存置换，这样子比较方便写出算法。由于这次设计的时间比较仓促，其中不免会有些纰漏，比如在程序的实现上还不够严谨，出错处理不够完善等多方面问题，这些都有进一步改善。同时，在这次编写3个页面算法的过程中，我学到了很多东西，无论在理论上还是实践中，都得到不少的提高，这对以后的工作中会有一定的帮助。
