页面置换算法课程设计.docx
《页面置换算法课程设计.docx》由会员分享，可在线阅读，更多相关《页面置换算法课程设计.docx（19页珍藏版）》请在冰点文库上搜索。
页面置换算法课程设计
操作系统课程设计报告
题目：
页面置换算法模拟程序
一、设计目的………………………………………………………3
二、设计题目…………………………………………………………3
2.1设计内容………………………………………………………………………3
2.2设计要求………………………………………………………………………3
三、设计过程…………………………………………………………4
3.1FIFO（先进先出）……………………………………………………………4
3.2LRU（最近最久未使用）………………………………………………………5
3.3OPT（最佳置换算法）…………………………………………………………6
3.4随机数发生器……………………………………………………………………7
四、完整代码……………………………………………………………7
五、运行结果演示………………………………………………………13
六、设计心得……………………………………………………………16
七、参考文献……………………………………………………………16
一、设计目的
操作系统是计算机教学中最重要的环节之一，也是计算机专业学生的一门重要的专业课程。
操作系统质量的好坏，直接影响整个计算机系统的性能和用户对计算机的使用。
一个精心设计的操作系统能极大地扩充计算机系统的功能，充分发挥系统中各种设备的使用效率，提高系统工作的可靠性。
由于操作系统涉及计算机系统中各种软硬件资源的管理，内容比较繁琐，具有很强的实践性。
要学好这门课程，必须把理论与实践紧密结合，才能取得较好的学习效果。
本课程设计是学生学习完《计算机操作系统》课程后，进行的一次全面的综合训练，通过课程设计，让学生更好地掌握操作系统的原理及实现方法,加深对操作系统基础理论和重要算法的理解，加强学生的动手能力。
熟悉页面置换算法及其实现，引入计算机系统性能评价方法的概念。
二、设计题目：
页面置换算法模拟程序
2.1设计内容
编制页面置换算法的模拟程序。
2.2设计要求
1）.用随机数方法产生页面走向，页面走向长度为L（15<=L<=20）,L由控制台输入。
2）.根据页面走向，分别采用Optinal、FIFO、LRU算法进行页面置换，统计缺页率。
3）.假定可用内存块为m（3<=m<=5），m由控制台输入，初始时，作业页面都不在内存。
4）.要求写出一份详细的设计报告。
课程设计报告内容包括：
设计目的、设计内容、设计原理、算法实现、流程图、源程序、运行示例及结果分析、心得体会、参考资料等。
3．设计过程
3.1FIFO（先进先出）
设计原理：
需要进行页面置换，即把内存中装入最早的那个页面淘汰，换入当前的页面。
算法流程图：
3.2LRU（最近最久未使用）
设计原理：
当需要淘汰某一页时，选择离当前时间最近的一段时间内最久没有使用过的页先淘汰。
该算法的主要出发点是，如果某页被访问了，则它可能马上还要被访问。
或者反过来说，如果某页很长时间未被访问，则它在最近一段时间也不会被访问。
算法流程图：
3.3OPT（最佳置换算法）
设计原理：
需要进行页面置换，把内存中以后一段时间都不使用或是使用时间离现在最远的页面换出。
开始
页面走向存入数组p[]中，内存块用page[]表示初始化为0
当前p[]中第i个元素是否已在内存
Page[]是否有空
把p[i]的内容直接装入最上面一个空内存块，i++
把page[]中以后一段时间都不使用或是使用时间离现在最远的换出.i++
输出当前内存块状态
结束
N
i++
Y
流程图
Y
3.4随机数发生器
#include
#include//准备用时钟函数调用库函数
t=time（NULL）;//取时钟时间并存入t调用库函数
srand（t）;//用时间t初始化随机数发生器调用库函数
x=rand（）%10+1;//返回一个1~10之间的随机数
四．完整代码
#include
#include
#include
#include
#defineL20//页面走向长度最大为20
intM;//内存块
structPro//定义一个结构体
{
intnum,time;
};
Input（intm,Prop[L]）//打印页面走向状态
{
cout<<"请输入实际页面走向长度L（15<=L<=20）：
";
do
{
cin>>m;
if（m>20||m<15）cout<<"实际页面长度须在15～20之间;请重新输入L：
";
elsebreak;
}while
（1）;
inti,j;
j=time（NULL）;//取时钟时间
srand（j）;//以时钟时间x为种子，初始化随机数发生器
cout<<"输出随机数:
";
for（i=0;i{
p[i].num=rand（）%10+1;//产生1到10之间的随即数放到数组p中
p[i].time=0;
cout<}
cout<returnm;
}
voidprint（Pro*page1）//打印当前的页面
{
Pro*page=newPro[M];
page=page1;
for（inti=0;icout<cout<}
intSearch（inte,Pro*page1）//寻找内存块中与e相同的块号
{
Pro*page=newPro[M];
page=page1;
for（inti=0;ireturn-1;
}
intMax（Pro*page1）//寻找最近最长未使用的页面
{
Pro*page=newPro[M];
page=page1;
inte=page[0].time,i=0;
while（i{
if（ei++;
}
for（i=0;ireturn-1;
}
intCount（Pro*page1,inti,intt,Prop[L]）//记录当前内存块中页面离下次使用间隔长度
{
Pro*page=newPro[M];
page=page1;
intcount=0;
for（intj=i;j{
if（page[t].num==p[j].num）break;//当前页面再次被访问时循环结束
elsecount++;//否则count+1
}
returncount;//返回count的值
}
intmain（）
{
intc;
intm=0,t=0;
floatn=0;
Prop[L];
m=Input（m,p）;//调用input函数，返回m值
cout<<"请输入可用内存页面数m（3～5）:
";
do
{
cin>>M;
if（M>5||M<3）
cout<<"内存块m须在3～5之间，请重新输入m：
";
elsebreak;
}while
（1）;
Pro*page=newPro[M];
do{
for（inti=0;i{
page[i].num=0;
page[i].time=m-1-i;
}
i=0;
cout<<"1:
FIFO页面置换"<cout<<"2:
LRU页面置换"<cout<<"3:
OPT页面置换"<cout<<"按其它键结束程序；"<cin>>c;
if（c==1）//FIFO页面置换
{
n=0;
cout<<"******************************************"<cout<cout<<"FIFO算法页面置换情况如下:
"<cout<cout<<"******************************************"<while（i{
if（Search（p[i].num,page）>=0）//当前页面在内存中
{cout<cout<<"不缺页"<i++;//i加1
}
else//当前页不在内存中
{
if（t==M）t=0;
else
{
n++;//缺页次数加1
page[t].num=p[i].num;//把当前页面放入内存中
cout<print（page）;//打印当前页面
t++;//下一个内存块
i++;//指向下一个页面
}
}
}
cout<<"缺页次数：
"<"<}
if（c==2）//LRU页面置换
{
n=0;
cout<<"******************************************"<cout<cout<<"LRU算法页面置换情况如下:
"<cout<cout<<"******************************************"<while（i{
inta;
t=Search（p[i].num,page）;
if（t>=0）//如果已在内存块中
{
page[t].time=0;//把与它相同的内存块的时间置0
for（a=0;aif（a!
=t）page[a].time++;//其它的时间加1
cout<cout<<"不缺页"<}
else//如果不在内存块中
{
n++;//缺页次数加1
t=Max（page）;//返回最近最久未使用的块号赋值给t
page[t].num=p[i].num;//进行替换
page[t].time=0;//替换后时间置为0
cout<print（page）;
for（a=0;aif（a!
=t）page[a].time++;//其它的时间加1
}
i++;
}
cout<<"缺页次数：
"<"<}
if（c==3）//OPT页面置换
{
n=0;
cout<<"******************************************"<cout<cout<<"OPT算法置换情况如下:
"<cout<cout<<"******************************************"<while（i{
if（Search（p[i].num,page）>=0）//如果已在内存块中
{
cout<cout<<"不缺页"<i++;
}
else//如果不在内存块中
{
inta=0;
for（t=0;tif（page[t].num==0）a++;//记录空的内存块数
if（a!
=0）//有空内存块
{
intq=M;
for（t=0;tif（page[t].num==0&&q>t）q=t;//把空内存块中块号最小的找出来
page[q].num=p[i].num;
n++;
cout<print（page）;
i++;
}
else
{
inttemp=0,s;
for（t=0;tif（temp{
temp=Count（page,i,t,p）;
s=t;
}//把找到的块号赋给s
page[s].num=p[i].num;
n++;
cout<print（page）;
i++;
}
}
}
cout<<"缺页次数：
"<"<}
}while（c==1||c==2||c==3）;
return0;
}
五．运行结果演示
六.设计心得
通过这次课程设计，不仅让我了解了三种页面置换算法，即FIFO（先进先出）、LRU（最近最久未使用）、OPT（最佳置换）算法。
开始我对源代码一味的进行调试，但发现总是有点错误，于是调试了若干次还是没有编译成功。
又重新分析了几次设计要求，发现自己事先没有完全弄清楚这三种算法的做法，接着便是暂时停下程序的编译，将学习资料仔细地将这三种不同的算法研究了一下，待到基本弄懂它们具体怎么实现的时候，我才再一次去研究当初总是有问题的代码，结合课本知识与详细的流程图分析，经过不断的调试，多次尝试后，编译成功了，运行后发现此功能正是本次课程设计所需要的。
本次课程设计不仅让我对操作系统这门课程有了更深入的研究、对很多重要的概念有了巩固和掌握。
通过努力，三个页面置换算法程序都已经完成。
虽然自己所做的很少也不够完善，但毕竟也是努力的结果。
主要有以下几点收获：
1.通过对上网和看书查阅相关资料，使自己对VC++语言的基本框架有新的了解，加深了对可视化程序的认识。
2.在使用VC++语言来实现功能时，不像以往用的其他语言，它比较简练，更容易理解，实用性很强。
3.先进先出页面置换和LRU以及OPT算法各有特点，但是实践起来却很大，使自己对页面置换算法有了新的认识。
一周半的课程设计就要结束了，不但对专业知识有了更深的理解，更使的自己认识到实践的重要性，理论、实践相结合才能达到很好的学习效果，特别是程序语言的学习。
7．参考文献
《计算机操作系统教程》徐甲同等编著
《操作系统》罗宇等编著
《操作系统实验教程》张丽芬,刘利雄,王全玉编著
《计算机操作系统》梁红兵、哲风屏、汤子瀛编著
升级会员 