操作系统实验--虚拟存储管理-最佳置换先进先出最近最久未使用.docx
《操作系统实验--虚拟存储管理-最佳置换先进先出最近最久未使用.docx》由会员分享，可在线阅读，更多相关《操作系统实验--虚拟存储管理-最佳置换先进先出最近最久未使用.docx（14页珍藏版）》请在冰点文库上搜索。
学号 P71514032 专业 计算机科学与技术 姓名
实验日期 2017/11/30 教师签字 成绩
实验报告
【实验名称】 虚拟存储管理
【实验目的】
模拟请求分页虚拟存储管理技术中的硬件地址变换、缺页中断以及页式淘汰算法，处理缺页中断。
清楚认识请求分页管理。
采用最佳置换算法实现分页管理的缺页调度。
采用先进先出算法实现分页管理的缺页调度。
采用LRU算法实现分页管理的缺页调度。
【实验原理】
C语言程序设计
数据结构
最佳置换算法：
其所选择的淘汰页面将是以后永不使用的，或许是在最长（未来）时间内不再被访问的页面。
采用最佳置换算法通常可保证获得最低的缺页率。
先入先出置换算法：
该算法总是淘汰最先进入内存的页面。
最近最久未被访问算法：
选取过去中最久未被访问的页面进行替换。
【实验内容】
数据结构和符号说明
a）数据结构
②structPAGE_LIST
③{
④ intid;//块号
⑤ intflag;//自适应标志
⑥}page_list[MAX];
⑦intN=0;//页面表大小
⑧intorder[MAX];//调用串
⑨ //调用长度
⑩intM=0;//定义输出内容
⑪intG[MAX][MAX];//输出置换图
⑫intI,J;//置换图扫描指针
⑬intLL[MAX];//缺页序列
⑭intLI;//缺页序列扫描指针
⑮intRL[MAX];//置换序列
⑯ //置换序列扫描指针
⑰intRI;
函数说明：
voidinit（）;//初始化函数
voidprint（）;//输出函数
voidOptimal（）;//最佳置换算法
voidFIFO（）//先进先出算法
voidLRU（）;//最近最久未使用算法
流程图
最佳置换算法：
先进先出置换算法：
最近最久未被访问算法：
代码：
#include
#defineMAX100
structPAGE_LIST
{
intid;//块号
intflag;//自适应标志
}page_list[MAX];
intN=0;//页面表大小
intorder[MAX];//调用串
//调用长度
intM=0;//定义输出内容
intG[MAX][MAX];//输出置换图
intI,J;//置换图扫描指针
intLL[MAX];//缺页序列
intLI;//缺页序列扫描指针
intRL[MAX];//置换序列
//置换序列扫描指针
intRI;
//初始化函数
voidinit（）
{
inti;
I=0;
J=0;
LI=0;
RI=0;
for（i=0;i<100;i++）
{
page_list[i].id=-1;
page_list[i].flag=999;
}
printf（"请输入页表的大小：
"）;
scanf（"%d",&N）;
printf（"请输入调用长度：
"）;
scanf（"%d",&M）;
printf（"请输入调用串：
\n"）;
for（i=0;i scanf（"%d",&order[i]）;
}
//输出函数
voiddisplay（）
{
inti,j;
floatx;
printf（"置换图为：
\n"）;
for（i=0;i {
printf（"\n"）;
for（j=0;j printf（"==="）;
printf（"\n"）;
for（j=0;j printf（"%3d",G[i][j]）;
printf（"\n"）;
}
printf（"\n缺页序列为：
\n"）;
for（i=0;i printf（"%3d",LL[i]）;
printf（"\n置换序列为：
\n"）;
for（i=0;i printf（"%3d",RL[i]）;
x=（float）J/（float）M;
x*=100;
printf（"\n缺页率为：
\n%3.2f%%\n",x）;
}
//判断页是否在页表内
intIsExist（intx）
{
inti;
for（i=0;i {
if（page_list[i].id==x）
{
return1;
}
}
return0;
}
//最佳置换算法
//此算法中自适应标志代表后面序列中是否访问到了此位置
voidOptimal（）
{
inti,j,k;
intcou;
init（）;
for（i=0;i {
page_list[i].id=order[i];
for（j=0;j {
G[I][J]=page_list[j].id;
I++;
}
I=0;
J++;
LL[LI]=order[i];
LI++;
}
for（;i {
if（!
IsExist（order[i]））
{
cou=0;
for（j=i+1;j {
if（cou==N-1）
break;
for（k=0;k if（page_list[k].id==order[j]&&page_list[k].flag!
=0）
{
page_list[k].flag=0;
cou++;
}
}
for（j=0;j if（page_list[j].flag!
=0）
{
page_list[j].id=order[i];
break;
}
for（j=0;j {
G[I][J]=page_list[j].id;
I++;
}
I=0;
J++;
LL[LI]=order[i];
LI++;
RL[RI]=order[i];
RI++;
}
for（j=0;j page_list[j].flag=999;
}
}
//先进先出算法
//此算法中自适应标志不需要使用
voidFIFO（）
{
inti,j;
intpos=0;
init（）;
for（i=0;i {
if（!
IsExist（order[i]））
{
page_list[pos].id=order[i];
pos=（pos+1）%N;
for（j=0;j {
G[I][J]=page_list[j].id;
I++;
}
I=0;
J++;
LL[LI]=order[i];
LI++;
if（i>=N）
{
RL[RI]=order[i];
RI++;
}
}
}
}
//最近最久未使用算法
//此算法中自适应标志为起未被使用的次数
voidLRU（）
{
inti,j;
intpos,max;
init（）;
for（i=0;i {
if（!
IsExist（order[i]））
{
pos=0;
max=0;
for（j=0;j {
if（page_list[j].flag>max）
{
pos=j;
max=page_list[j].flag;
}
}
page_list[pos].id=order[i];
page_list[pos].flag=0;
for（j=0;j {
G[I][J]=page_list[j].id;
I++;
}
I=0;
J++;
LL[LI]=order[i];
LI++;
if（i>=N）
{
RL[RI]=order[i];
RI++;
}
}
else
{
for（j=0;j if（page_list[j].id==order[i]）
{
page_list[j].flag=0;
break;
}
}
for（j=0;j if（page_list[j].id==order[i]）
continue;
else
page_list[j].flag++;
}
}
intmain（）
{
intselect;
do
{
printf（"页面置换算法\n"）;
printf（"1.最佳置换算法（Optimal）\n2.先进先出算法（FIFO）\n"）;
printf（"3.最近最久未使用算法（LRU）\n4.退出程序\n"）;
printf（"请输入您想要执行的操作：
"）;
scanf（"%d",&select）;
switch（select）
{
case1:
Optimal（）;
display（）;
break;
case2:
FIFO（）;
display（）;
break;
case3:
LRU（）;
display（）;
break;
case4:
return0;
default:
printf（"输入有误，请重新输入！
\n"）;
}
}while
（1）;
return0;
}
结果截图
最佳置换算法
先进先出算法:
最近最久未使用算法：
【小结或讨论】
三种算法的主要区别是确定替换物理块的方式不同：
1、对于先进先出置换算法，设置一个指针，循环从block的首元素指到block的尾元素，就是物理块置换顺序
2、对于LRU置换算法，遍历页表中的页号，根据这些页号最近被引用的顺序，找到最久未被引用的页号，即在输入序列中向前查找离当前页最远的页号，将其所在的物理块置换掉。
3、对于LRU置换算法，遍历输入序列中的页号，根据这些页号将来被引用的顺序，找到将来最长时间未被引用的页号，即在输入序列中向后查找离当前页最远的页号，将其所在的物理块置换掉。
4、通过本次实验，我对于虚拟存储中的分页管理有了更加深入的了解。
理解了最佳页面置换算法、先入先出页面置换算法以及最近最久未被使用页面置换算法的中心思想。
同时发现，最佳页面置换算法得到的缺页率最低，但其要求也更加严格，必须要求知道未来调用的所有序列。
先进先出算法最为简单，但是缺页率最高。
最近最久未被访问算法居中。
升级会员 