操作系统 设计说明书.docx
《操作系统 设计说明书.docx》由会员分享，可在线阅读，更多相关《操作系统 设计说明书.docx（26页珍藏版）》请在冰点文库上搜索。
操作系统设计说明书
操作系统设计说明书
学院名称：
计算机与信息工程学院
班级名称：
计科112班
学生姓名：
夏宗斌、柴远亮、王辉、王周军、陈敏
学号：
2011211227、2011211173、2011211212、
2011211222、2011211175
题目：
页面置换算法实现与分析
指导教师：
胡成祥
起止日期：
2013年6月3日~2013年6月30日
目录
1.选题背景3
2.方案论证3
2.1任务分析3
2.2任务目的3
2.3方案设计4
3.过程论述5
3.1FIFO（先进先出）5
3.2LRU（最近最久未使用）8
3.3OPT（最佳置换算法）10
4.结果分析14
4.1实现结果14
4.2程序测试18
5.结论19
参考文献20
代码20
1.选题背景
随着计算机的普及人们的物质生活得到了极大的满足，人们在精神生活方面同样也需要提高，所以越来越多的人进行着各种各样的学习。
操作系统是计算机教学中最重要的环节之一，也是计算机专业学生的一门重要的专业课程。
操作系统质量的好坏，直接影响整个计算机系统的性能和用户对计算机的使用。
一个精心设计的操作系统能极大地扩充计算机系统的功能，充分发挥系统中各种设备的使用效率，提高系统工作的可靠性。
在各种存储器管理方式中，有一个共同的特点，即它们都要求将一个作业全部装入内存方能运行，但是有两种情况：
（1）有的作业很大，不能全部装入内存，致使作业无法运行；
（2）有大量作业要求运行，但内存容量不足以容纳所有这些作业。
而虚拟内存技术正式从逻辑上扩充内存容量，将会解决以上两个问题。
从内存中调出一页程序或数据送磁盘的对换区中，通常，把选择换出的页面的算法称为页面置换算法（Page-ReplacementAlgorithms）。
进而页面置换算法模拟程序能客观的将其工作原理展现在我们面前。
2.方案论证
2.1任务分析
首先，定义宏变量，设置所占最大内存长度。
编辑以时间为种子，初始化随即发生器。
进行相关页面输入程序的编写以及页面的打印。
然后，寻找最近最久未使用的页面、记录当前内存块中页面离下次使用间隔长度等相关程序的代码编写。
最后，进行FIFO、LRU、OPT三种算法的编写。
2.2任务目的
1.通过模拟实现请求页式存储管理的几种页面置换算法，了解虚拟存储技术的特点。
2.通过对页面、页表、地址转换和页面置换过程的模拟，加深对请求调页系统的原理和实现过程的理解。
3.掌握虚拟存储请求页式存储管理中几种基本页面置换算法的基本思想和实现过程，并比较它们的效率。
2.3方案设计
1.用随机数方法产生页面走向，页面走向长度为L。
2.根据页面走向，分别采用FIFO和LRU算法进行页面置换，统计缺页率；为简化操作，在淘汰一页时，只将该页在页表中抹去,而不再判断它是否被改写过，也不将它写回到辅存。
3.假定可用内存块和页表长度（作业的页面数）分别为m和k，初始时，作业页面都不在内存。
随机数产生程序：
inti,j;
j=time（NULL）;//取时钟时间
srand（j）;//以时钟时间x为种子，初始化随机数发生器
cout<<"输出随机数:
";
for（i=0;ip[i].num=rand（）%10+1;//产生1到10之间的随即数放到数组p中
p[i].time=0;
cout<}
上述随机数发生函数产生的随机数为0.0～1.0，稍另变化就可得到0～n-1之间的随机数。
程序开始时，应对变量Seed（实型）赋初值。
根据页面置换算法的理论操作及要求，首先要进行页面长度的确定，定义结构体用以储存数据，进行主界面代码及OPT、FIFO、LRU页面置换算法代码的编写。
3.过程论述
3.1FIFO（先进先出）
算法思想：
需要进行页面置换，即把内存中装入最早的那个页面淘汰，换入当前的页面。
算法流程图：
图3.1FIFO算法流程图
核心代码：
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<<"缺页次数：
"<"<}
3.2LRU（最近最久未使用）
算法思想：
当需要淘汰某一页时，选择离当前时间最近的一段时间内最久没有使用过的页先淘汰该算法的主要出发点是，如果某页被访问了，则它可能马上还要被访问。
或者反过来说如果某页很长时间未被访问，则它在最近一段时间也不会被访问。
算法流程图：
图3.2LRU算法流程图
核心代码：
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<<"缺页次数：
"<"<}
3.3OPT（最佳置换算法）
算法思想：
需要进行页面置换，把内存中以后一段时间都不使用或是使用时间离现在最远的页面换出。
算法流程图：
图3.3OPT算法流程图
核心代码：
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<<"缺页次数：
"<"<}
4.结果分析
4.1实现结果
程序在运行的情况下，进入主界面输入菜单，如图4.1所示：
输入11：
图4.1输入11的输出图
输入24：
图4.2输入24的输出图
输入16：
图4.3输入16的输出图
输入2：
图4.4输入2的输出图
输入6：
图4.5输入6的输出图
输入3：
图4.6输入3的输出图
选1，进入FIFO页面置换：
图4.7FIFO的输出图
选2，进入LRU页面置换：
图4.8LRU的输出图
输入3，进入OPT页面置换：
图4.9OPT的输出图
4.2程序测试
设计测试数据：
A112416；B263；
B1
C2
D3
测试结果及分析：
1）测试A结果及分析
进入主菜单后输入11、24，显示输入不满足要求。
输入16显示相关信息;
输入2、6不满足要求，输入3显示出相关信息。
2）测试B结果及分析：
显示出FIFO页面置换算法的缺页信息及缺页率。
3）测试C结果及分析：
显示出LRU页面置换算法的缺页信息及缺页率。
4）测试D结果及分析：
显示出OPT页面置换算法的缺页信息及缺页率
5.结论
这次实验的目的是模拟虚拟存储的页面置换算法，请求页式虚存管理是常用的虚拟存储管理方案之一。
通过请求页式虚存管理中对页面置换算法的模拟，有助于理解虚拟存储技术的特点，并加深对请求页式虚存管理的页面调度算法的理解。
这次实验我采用的是先进先出算法。
在程序中主要是设计了如下几个数据结构：
pv_type——用来表示虚页的有关信息，pf_type——用来表示内存中实页的有关信息。
同时还用到了两个链表——free和busy，分别用来表示空闲实页面和已经存有虚页的忙页面。
在进行页面置换时，要同时更改free和busy链表中的虚页号和实页号，free链表中的虚页号应该改到默认状态。
当内存中不存在下一个要调入内存的虚页且内存中已经没有空闲页面时，那么将发生页面置换。
通过这次实验使我对页面置换算法有了进一步的了解，加强了自己的动手能力和编程的能力，巩固了课堂上所学的知识。
参考文献
计算机操作系统第三版，编著人：
梁小兵，梁晓丹，唐子瀛等。
C++语言程序设计第四版，编著人：
董渊，何江舟等。
代码
#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;
system（"cls"）;
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;
}
升级会员 