文档介绍：操作系统设计说明书
学院名称: 计算机与信息工程学院
班级名称: 计科 112班
学生姓名: 夏宗斌、柴远亮、王辉、王周军、陈敏
学号: 、、、
、
题目: 页面置换算法实现与分析
指导教师: 胡成祥
起止日期: 2013年6月3日~2013年6月30日
目录
3
3
任务分析 3
任务目的 3
方案设计 4
5
FIFO(先进先出) 5
LRU(最近最久未使用) 8
OPT(最佳置换算法) 10
14
14
18
19
参考文献 20
代码 20
随着计算机的普及人们的物质生活得到了极大的满足,人们在精神生活方面同样也需要提高,所以越来越多的人进行着各种各样的学****操作系统是计算机教学中最重要的环节之一,也是计算机专业学生的一门重要的专业课程。操作系统质量的好坏,直接影响整个计算机系统的性能和用户对计算机的使用。一个精心设计的操作系统能极大地扩充计算机系统的功能,充分发挥系统中各种设备的使用效率,提高系统工作的可靠性。
在各种存储器管理方式中,有一个共同的特点,即它们都要求将一个作业全部装入内存方能运行,但是有两种情况:(1)有的作业很大,不能全部装入内存,致使作业无法运行;(2)有大量作业要求运行,但内存容量不足以容纳所有这些作业。而虚拟内存技术正式从逻辑上扩充内存容量,将会解决以上两个问题。从内存中调出一页程序或数据送磁盘的对换区中,通常,把选择换出的页面的算法称为页面置换算法(Page-Replacement Algorithms)。进而页面置换算法模拟程序能客观的将其工作原理展现在我们面前。
任务分析
首先,定义宏变量,设置所占最大内存长度。编辑以时间为种子,初始化随即发生器。进行相关页面输入程序的编写以及页面的打印。然后,寻找最近最久未使用的页面、记录当前内存块中页面离下次使用间隔长度等相关程序的代码编写。最后,进行FIFO 、LRU、 OPT三种算法的编写。
任务目的
1. 通过模拟实现请求页式存储管理的几种页面置换算法,了解虚拟存储技术的特点。
2. 通过对页面、页表、地址转换和页面置换过程的模拟,加深对请求调页系统的原理和实现过程的理解。
3. 掌握虚拟存储请求页式存储管理中几种基本页面置换算法的基本思想和实现过程,并比较它们的效率。
方案设计
1. 用随机数方法产生页面走向,页面走向长度为L。
2. 根据页面走向,分别采用FIFO和LRU算法进行页面置换,统计缺页率;为简化操作,在淘汰一页时,只将该页在页表中抹去,而不再判断它是否被改写过,也不将它写回到辅存。
3. 假定可用内存块和页表长度(作业的页面数)分别为m和k,初始时,作业页面都不在内存。
随机数产生程序:
int i,j;
j=time(NULL);//取时钟时间
srand(j);//以时钟时间x为种子,初始化随机数发生器
cout<<"输出随机数: ";
for(i=0;i<m;i++){
p[i].num=rand( )%10+1;//产生1到10之间的随即数放到数组p中
p[i].time=0;
cout<<p[i].num<<" ";
}
~,稍另变化就可得到0~n-1之间的随机数。
程序开始时,应对变量Seed (实型)赋初值。
根据页面置换算法的理论操作及要求,首先要进行页面长度的确定,定义结构体用以储存数据,进行主界面代码及OPT、FIFO、LRU页面置换算法代码的编写。
FIFO(先进先出)
算法思想:需要进行页面置换,即把内存中装入最早的那个页面淘汰,换入当前的页面。
算法流程图:
FIFO算法流程图
核心代码:
if(c==1)//FIFO页面置换
{
n=0;
cout<<" ****************************************** "<<endl;
cout<<endl;
cout<<" FIFO算法页面置换情况如下: "<<endl;
cout<<endl;
cout<<" ****************************************** "<<endl;
while(i<m)
{
if(Search(p[i].num,page)>=0)//当前页面在内存中
{
cout<<p[i].num<<" ";//输出当前页p[i].num
c