实验3页面调度算法Word文件下载.docx
《实验3页面调度算法Word文件下载.docx》由会员分享，可在线阅读，更多相关《实验3页面调度算法Word文件下载.docx（15页珍藏版）》请在冰点文库上搜索。
二、实验环境
三、实验内容
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<
iostream.h>
#defineBsize3
#definePsize20
structpageInfor
{
intcontent;
//页面号
inttimer;
//被访问标记
};
classPRA
public:
PRA（void）;
voidOptimal（void）;
//OPTIMAL算法
//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<
Bsize;
i++）
block[i].content=-1;
block[i].timer=0;
}
page=newpageInfor[Psize];
for（i=0;
Psize;
page[i].content=QString[i];
page[i].timer=0;
intPRA:
findSpace（void）
if（block[i].content==-1）
returni;
//找到空闲内存，返回BLOCK中位置
return-1;
findExist（intcurpage）
if（block[i].content==page[curpage].content）
//找到内存中有该页面，返回BLOCK中位置
findReplace（void）
intpos=0;
if（block[i].timer>
=block[pos].timer）
pos=i;
//找到应予置换页面，返回BLOCK中位置
returnpos;
voidPRA:
display（void）
if（block[i].content!
=-1）
cout<
<
block[i].content<
"
"
;
cout<
endl;
Optimal（void）
intexist,space,position;
{
exist=findExist（i）;
if（exist!
{cout<
不缺页"
}
else
{
space=findSpace（）;
if（space!
{
block[space]=page[i];
display（）;
for（intk=0;
k<
k++）
for（intj=i;
j<
j++）
if（block[k].content!
=page[j].content）
{block[k].timer=1000;
}//将来不会用，设置TIMER为一个很大数
block[k].timer=j;
break;
position=findReplace（）;
block[position]=page[i];
LRU（void）
block[exist].timer=-1;
//恢复存在的并刚访问过的BLOCK中页面TIMER为-1
for（intj=0;
block[j].timer++;
FIFO（void）
{cout<
//BLOCK中所有页面TIMER++
BlockClear（void）
voidmain（void）
|----------页面置换算法----------|"
|---powerbykangyan（1318064008）---|"
|-------------------------------------|"
页面号引用串:
7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1"
----------------------------------------------------"
选择<
1>
应用Optimal算法"
2>
应用FIFO算法"
3>
应用LRU算法"
0>
退出"
intselect;
PRAtest;
while（select）
cin>
>
select;
switch（select）
case0:
case1:
Optimal算法结果如下:
test.Optimal（）;
test.BlockClear（）;
----------------------"
case2:
FIFO算法结果如下:
test.FIFO（）;
case3:
LRU算法结果如下:
test.LRU（）;
default:
请输入正确功能号"
实验截图如如下图所示：
—键入1选择运行LRU算法的置换
—初始化信息：
3个页块，20个页面号引用串
—存入前三个页，有空闲内存，无需置换
—3，4页已经在内存中无需再写入
—因为3是最久的页面所以将其置换
下面原理一样
—所有命中的页面数
—
七、总结
页面置换算法的思想可以说比拟简单，易懂，但是在实现的时候，也遇到了很多的问题，比如说在找空闲物理块的时候，起初我是比拟物理块是否等于0，假如为0，如此直接把页面放入，后来发现不论什么时候都是把0替换出去，才恍然大悟，既然页面标号有0，就不能用0来表示空闲物理块，后来就换成用-1来表示物理块空闲了。
通过编写本实验，不仅理解了OS中页面置换算法，也锻炼编程能力，编程过程中会遇到些小问题，可以通过各种途径解决，另外，编程之前要做好整体规划，最好写出来，把各个模块的功能和主要变量都写成文档，这样效率很高。
升级会员 