实验3页面调度算法.docx
- 文档编号:3290847
- 上传时间:2023-05-05
- 格式:DOCX
- 页数:15
- 大小:185.51KB
实验3页面调度算法.docx
《实验3页面调度算法.docx》由会员分享,可在线阅读,更多相关《实验3页面调度算法.docx(15页珍藏版)》请在冰点文库上搜索。
实验3页面调度算法
实验报告
院〔系〕:
专业班级:
学号:
姓名:
实验地点:
实验日期:
课程名称
实验项目名称
实验学时
实验类型
计算机操作系统
页面调度算法
2
验证型
一、实验目的与要求
通过本实验可以加深理解有关虚拟存储器的工作原理,进一步体会和了解页面替换算法的具体实现方法。
二、实验环境
三、实验内容
1实现三种算法:
先进先出;OPT;LRU
2页面序列从指定的文本文件〔TXT文件〕中取出
3输出:
第一行:
每次淘汰的页面号,第二行:
显示缺页的总次数
四、实验步骤
1.先进先出(FIFO)置换算法的思路
该算法总是淘汰最先进入内存的页面,即选择在内存中驻留时间最久的页面予以淘汰。
该算法实现简单,只需把一个进程已调入内存的页面,按照先后次序连接成一个队列,并设置一个替换指针,使它总指向最老的页面。
2.最近久未使用(LRU)置换算法的思路
最近久未使用置换算法的替换规如此,是根据页面调入内存后的使用情况来进展决策的。
该算法赋予每个页面一个访问字段,用来记录一个页面自上次被访问以来所经历的时间,当需淘汰一个页面的时候选择现有页面中其时间值最大的进
行淘汰。
3.最优〔OPT〕置换算法的思路
其所选择的被淘汰的页面,将是以后不使用的,或者是在未来时间内不再被访问的页面,采用最优算法,通常可保证获得最低的缺页率。
4、流程图如如下图所示:
五、调试过程
程序结构分析:
程序共有以下九个局部:
intfindSpace(void);//查找是否有空闲内存
intfindExist(intcurpage);//查找内存中是否有该页面
intfindReplace(void);//查找应予置换的页面
voiddisplay(void);//显示
voidFIFO(void);//FIFO算法
voidLRU(void);//LRU算法
voidOPT(void);//OPT算法;
voidBlockClear(void);//BLOCK清空,以便用另一种方法重新演示
intmain()//主程序
六、实验结果与分析
程序源代码:
#include
#defineBsize3
#definePsize20
structpageInfor
{
intcontent;//页面号
inttimer;//被访问标记
};
classPRA
{
public:
PRA(void);
intfindSpace(void);//查找是否有空闲内存
intfindExist(intcurpage);//查找内存中是否有该页面
intfindReplace(void);//查找应予置换的页面
voiddisplay(void);//显示
voidFIFO(void);//FIFO算法
voidLRU(void);//LRU算法
voidOptimal(void);//OPTIMAL算法
voidBlockClear(void);//BLOCK恢复
pageInfor*block;//物理块
pageInfor*page;//页面号串
private:
};
PRA:
:
PRA(void)
{
intQString[20]={7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1};
block=newpageInfor[Bsize];
for(inti=0;i { block[i].content=-1; block[i].timer=0; } page=newpageInfor[Psize]; for(i=0;i { page[i].content=QString[i]; page[i].timer=0; } } intPRA: : findSpace(void) { for(inti=0;i if(block[i].content==-1) returni;//找到空闲内存,返回BLOCK中位置 return-1; } intPRA: : findExist(intcurpage) { for(inti=0;i if(block[i].content==page[curpage].content) returni;//找到内存中有该页面,返回BLOCK中位置 return-1; } intPRA: : findReplace(void) { intpos=0; for(inti=0;i if(block[i].timer>=block[pos].timer) pos=i;//找到应予置换页面,返回BLOCK中位置 returnpos; } voidPRA: : display(void) { for(inti=0;i if(block[i].content! =-1) cout< cout< } voidPRA: : Optimal(void) { intexist,space,position; for(inti=0;i { exist=findExist(i); if(exist! =-1) {cout<<"不缺页"< else { space=findSpace(); if(space! =-1) { block[space]=page[i]; display(); } else { for(intk=0;k for(intj=i;j { if(block[k].content! =page[j].content) {block[k].timer=1000;}//将来不会用,设置TIMER为一个很大数 else { block[k].timer=j; break; } } position=findReplace(); block[position]=page[i]; display(); } } } } voidPRA: : LRU(void) { intexist,space,position; for(inti=0;i { exist=findExist(i); if(exist! =-1) { cout<<"不缺页"< block[exist].timer=-1;//恢复存在的并刚访问过的BLOCK中页面TIMER为-1 } else { space=findSpace(); if(space! =-1) { block[space]=page[i]; display(); } else { position=findReplace(); block[position]=page[i]; display(); } } for(intj=0;j block[j].timer++; } } voidPRA: : FIFO(void) { intexist,space,position; for(inti=0;i { exist=findExist(i); if(exist! =-1) {cout<<"不缺页"< else { space=findSpace(); if(space! =-1) { block[space]=page[i]; display(); } else { position=findReplace(); block[position]=page[i]; display(); } } for(intj=0;j block[j].timer++;//BLOCK中所有页面TIMER++ } } voidPRA: : BlockClear(void) { for(inti=0;i { block[i].content=-1; block[i].timer=0; } } voidmain(void) { cout<<"|----------页面置换算法----------|"< cout<<"|---powerbykangyan(1318064008)---|"< cout<<"|-------------------------------------|"< cout<<"页面号引用串: 7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1"< cout<<"----------------------------------------------------"< cout<<"选择<1>应用Optimal算法"< cout<<"选择<2>应用FIFO算法"< cout<<"选择<3>应用LRU算法"< cout<<"选择<0>退出"< intselect; PRAtest; while(select) { cin>>select; switch(select) { case0: break; case1: cout<<"Optimal算法结果如下: "< test.Optimal(); test.BlockClear(); cout<<"----------------------"< break; case2: cout<<"FIFO算法结果如下: "< test.FIFO(); test.BlockClear(); cout<<"----------------------"< break; case3: cout<<"LRU算法结果如下: "< test.LRU(); test.BlockClear(); cout<<"----------------------"< break; default: cout<<"请输入正确功能号"< break; } } } 实验截图如如下图所示: <—键入1选择运行LRU算法的置换 <—初始化信息: 3个页块,20个页面号引用串 <—存入前三个页,有空闲内存,无需置换 <—3,4页已经在内存中无需再写入 <—因为3是最久的页面所以将其置换 下面原理一样 <—所有命中的页面数 <— 七、总结 页面置换算法的思想可以说比拟简单,易懂,但是在实现的时候,也遇到了很多的问题,比如说在找空闲物理块的时候,起初我是比拟物理块是否等于0,假如为0,如此直接把页面放入,后来发现不论什么时候都是把0替换出去,才恍然大悟,既然页面标号有0,就不能用0来表示空闲物理块,后来就换成用-1来表示物理块空闲了。 通过编写本实验,不仅理解了OS中页面置换算法,也锻炼编程能力,编程过程中会遇到些小问题,可以通过各种途径解决,另外,编程之前要做好整体规划,最好写出来,把各个模块的功能和主要变量都写成文档,这样效率很高。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 实验 页面 调度 算法
![提示](https://static.bingdoc.com/images/bang_tan.gif)