页面置换算法代码实现电子科大.docx
- 文档编号:4989906
- 上传时间:2023-05-07
- 格式:DOCX
- 页数:12
- 大小:45.80KB
页面置换算法代码实现电子科大.docx
《页面置换算法代码实现电子科大.docx》由会员分享,可在线阅读,更多相关《页面置换算法代码实现电子科大.docx(12页珍藏版)》请在冰点文库上搜索。
页面置换算法代码实现电子科大
电子科技大学
实验报告
学生姓名:
满博学号:
2823103017指导教师:
罗惠琼
一、实验室名称:
软件实验室A2412
二、实验项目名称:
内存页面置换算法的设计
三、实验原理:
在内存运行过程中,若其所要访问的页面不在内存而需要把他们调入内存,但内存已经没有空闲空间时,为了保证该进程能正常运行,系统必须从内存中调出一页程序或数据送磁盘的对换区中。
但应将那个页面调出,需根据一定的算法来确定。
通常,把选择换出页面的算法成为页面置换算法。
置换算法的好坏,将直接影响到系统的性能。
一个好的页面置换算法,应具有较低的页面更换频率。
从理论上讲,应将那些以后不再会访问的页面置换出,或者把那些在较长时间内不会在访问的页面调出。
目前存在着许多种置换算法(如FIFO,OPT,LRU),他们都试图更接近理论上的目标。
四、实验目的:
1.熟悉FIFO,OPT和LRU算法
2.比较三种算法的性能优劣
五、实验内容:
写出FIFO,OPT和LRU算法的程序代码,并比较它们的算法性能。
六、实验器材(设备、元器件):
1.基本环境要求
①宽敞整洁专用实验室
②必备的基本实验工具
2.最低设备要求
①计算机CPU不小于800MHZ;
②计算机内存不小于128M;
3.软硬件要求
①实验平台Visualc++6.0
七、实验步骤:
代码如下:
#include
#defineM4//物理页数
#defineN20//需要调入的页数
typedefstructpage
{
intnum;
inttime;
}Page;//物理页项,包括调入的页号和时间
Pagemm[M];//4个物理页
intqueue1[20],queue2[20],queue3[20];//记录置换的页
intK=0,S=0,T=0;//置换页数组的标识
intpos=0;//记录存在最长时间项
//初始化内存页表项及存储内存情况的空间
voidINIT(){
inti;
for(i=0;i mm[i].num=-1; mm[i].time=0; } } //取得内存中存在时间最久的位置 intGetMax(){ intmax=-1; inti; for(i=0;i if(mm[i].time>max){ max=mm[i].time; pos=i; } } returnpos; } //检查最长时间不使用页面 intlongesttime(intfold) { inti; intmax=-1; for(i=fold;i if(mm[0].num! =i){ mm[0].time++; } if(mm[1].num! =i){ mm[1].time++; } if(mm[2].num! =i){ mm[2].time++; } if(mm[3].num! =i){ mm[3].time++; } } for(i=0;i if(mm[i].time>max){ max=mm[i].time; pos=i; } } returnpos; } //检查某页是否在内存 intEquation(intfold){ inti; for(i=0;i if(mm[i].num==fold) returni; } return-1; } //检查物理内存是否已满,-1表满,其他不满 intCheck(){ inti; for(i=0;i if(mm[i].num==-1) returni; } return-1; } //先进先出 voidFIFO(intfold){ inti; inta,b,c; a=Equation(fold); //页已存在 if(a! =-1){} //页不存在 else{ b=Check(); //内存还有空闲 if(b! =-1){ mm[b].num=fold; } //内存已满,需要置换 else{ c=GetMax(); mm[c].num=fold; mm[c].time=0; } queue1[K++]=fold; } for(i=0;i if(mm[i].num! =-1){ mm[i].time++; } } } voidOPT(intfold) { inta,b,c; a=Equation(fold); if(a==-1){//页不在内存 b=Check(); //内存还有空闲 if(b! =-1){ mm[b].num=fold; } //内存已满,需要置换 else{ c=longesttime(fold); mm[c].num=fold; mm[c].time=0; } queue3[T++]=fold; } } voidLRU(intfold) { inti; inta,b; intp; a=Equation(fold); if(a! =-1)//页已在内存 { //把此项移动到链表最后一项 if(a==3)//此项已经在最后,不需要做任何改动 return; else { p=Equation(-1); if(p==-1)//链表是满的 { for(;a<3;a++) mm[a].num=mm[a+1].num; mm[3].num=fold; } elseif(p<=3)//链表不满 { for(;a mm[a].num=mm[a+1].num; mm[a].num=fold; } } } else { b=Check(); if(b! =-1)//不满 mm[b].num=fold; else { for(i=0;i<3;i++) mm[i].num=mm[i+1].num; mm[3].num=fold; } queue2[S++]=fold; } } voidmain() { intA[N],B[N]; inti; INIT(); printf("请依次输入%d个页面号: \n",N); for(i=0;i scanf("%d",&A[i]); } //FIFO for(i=0;i B[i]=A[i]; } for(i=0;i FIFO(B[i]); } printf("FIFO的"); printf("调入队列为: "); for(i=0;i printf("%3d",queue1[i]); printf("\n缺页次数为: %6d\n缺页率: %16.6f\n\n",K,(float)K/N); //LRU INIT(); for(i=0;i B[i]=A[i]; } for(i=0;i LRU(B[i]); } printf("LRU的"); printf("调入队列为: "); for(i=0;i printf("%3d",queue2[i]); printf("\n缺页次数为: %6d\n缺页率: %16.6f\n\n",S,(float)S/N); //OPT INIT(); for(i=0;i B[i]=A[i]; } for(i=0;i OPT(B[i]); } printf("OPT的"); printf("调入队列为: "); for(i=0;i printf("%3d",queue3[i]); printf("\n缺页次数为: %6d\n缺页率: %16.6f\n\n",T,(float)T/N); } 运行截图如下所示: 实例1 实例2 八、实验数据及结果分析: 显而易见,LRU算法的效率最高。 事实上,FIFO算法算法调度是依据各个页面的调入时间,而不是页面的使用情况;而OPT算法对今后要使用的页面进行估算,因此该算法无法预知今后页面的情况,故不符合实际,不能在常规中使用。 因此,LRU算法综合来说在三种算法中最高效且实用。 九、实验结论: 成功实现了FIFO,OPT和LRU算法,并了解了这些置换算法的原理和各自的优缺点。 十、总结及心得体会: 通过本次试验,我掌握了页面置换算法的基本原理,对于这些算法的性能优劣有了较为直观的理解,收获颇大。 十一、对本实验过程及方法、手段的改进建议: 程序可改进,使用户控制输入页块数及页面序列的个数,实验四给出改进。 报告评分: 指导教师签字:
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 页面 置换 算法 代码 实现 电子科