页面置换算法地实验报告材料.docx

页面置换算法地实验报告材料.docx

《页面置换算法地实验报告材料.docx》由会员分享，可在线阅读，更多相关《页面置换算法地实验报告材料.docx（19页珍藏版）》请在冰点文库上搜索。

页面置换算法地实验报告材料

操作系统

课程设计报告

院（系）：

衡阳师范学院

专业：

计算机科学与技术

姓名:

陈建元齐欢　　

班级：

＿1103班＿　

学号:

1119030111190316

题目：

页面置换算法

指导教师:

王玉奇

2013年12月10日至12月28日

摘要

操作系统（英语；OperatingSystem，简称OS）是一管理电脑硬件与软件资源的程序，同时也是计算机系统的内核与基石。

操作系统身负诸如管理与配置内存、决定系统资源供需的优先次序、控制输入与输出设备、操作网络与管理文件系统等基本事务。

操作系统是管理计算机系统的全部硬件资源包括软件资源及数据资源;控制程序运行;改善人机界面;为其它应用软件提供支持等，使计算机系统所有资源最大限度地发挥作用，为用户提供方便的、有效的、友善的服务界面。

操作系统是一个庞大的管理控制程序，大致包括5个方面的管理功能:

进程与处理机管理、作业管理、存储管理、设备管理、文件管理。

在地址映射过程中，若在页面中发现所要访问的页面不再内存中，则产生缺页中断。

当发生缺页中断时操作系统必须在内存选择一个页面将其移出内存，以便为即将调入的页面让出空间。

而用来选择淘汰哪一页的规则叫做页面置换算法（Page-ReplacementAlgorithms）。

关键词：

操作系统；OPT页面置换算法；FIFO先进先出的算法；LRU最近最久未使用夜面置换算法

第一章设计任务和需求

1.1课程设计任务

深入掌握内存调度算法的概念原理和实现方法。

编写程序实现：

（1）先进先出页面置换算法（FIFO）

（2）最近最久未使用页面置换算法（LRU）

（3）最佳置换页面置换算法（OPT）

设计一个虚拟存储区和内存工作区，编程序演示以上三种算法的具体实现过程，并计算访问命中率。

演示页面置换的三种算法。

通过随机数产生一个指令序列，将指令序列转换成为页地址流。

计算并输出各种算法在不同内存容量下的缺页率。

1.2课程设计需求

在各种存储器管理方式中，有一个共同的特点，即它们都要求将一个作业全部装入内存方能运行，但是有两种情况：

（1）有的作业很大，不能全部装入内存，致使作业无法运行；

（2）有大量作业要求运行，但内存容量不足以容纳所有这些作业。

而虚拟内存技术正式从逻辑上扩充内存容量，将会解决以上两个问题。

从内存中调出一页程序或数据送磁盘的对换区中，通常，把选择换出的页面的算法称为页面置换算法（Page-ReplacementAlgorithms）。

进而页面置换算法程序能客观的将其工作原理展现在我们面前。

第二章概要设计

2.1系统分析

由于分区式管理尽管实现方式较为简单，但存在着严重的碎片问题使得内存的利用率不高。

再者，分区式管理时，由于各作业或进程对应于不同的分区以及在分区内各作业或进程连续存放，进程的大小或内存可用空间的限制。

而且分区式管理也不利于程序段和数据段的共享。

页式管理正是为了减少碎片以及为了只在内存存放那些反复执行或即将执行的程序段与数据部分，而把那些不经常执行的程序段和数据存放于外存待执行时调入，以提高内存利用率而提出来的页式管理有动态页式管理和静态页式管理之分，动态页式管理是在静态页式管理的基础上发展起来的。

请求页式管理属于动态页式管理中的一种，它的地址变换过程与静态页式管理时的相同，也是通过页表查出相应的页面号，由页面号与页内相对地址相加而得到实际物理地址。

有关的地址变换部分是由硬件自动完成的。

当硬件变换机构发现所要求的页不在内存时，产生缺页中断信号，由中断处理程序做出相应的处理。

中断处理程序是由软件实现的。

除了在没有空闲页面时要按照置换算法选择出被淘汰页面之外，还要从外存读入所需要的虚页。

这个过程要启动相应的外存和涉及到文件系统。

因此，请求页式管理是一个十分复杂的过程，内存利用率的提高是以牺牲系统开销的代价换来的。

这里用到了置换算法。

它是在内存中没有空闲页面时被调用。

目的是选出一个被淘汰的页面。

如果内存中有足够的空闲页面存放所调入的页，则不必使用置换算法。

把内存和外存统一管理的真正目的是把那些被访问概率非常高的页存放在内存中。

因此，置换算法应该置换那些被访问概率低的页，将它们移出内存。

2.2调页策略

2.2.1何时调入页面

如果进程的许多页是存放在外存的一个连续区域中，则一次调入若干个相邻的页，会比一次调入一页的效率更高效一些。

但如果调入的一批页面中的大多数都未被访问，则又是低效的。

可采用一种以预测为基础的预调页策略，将那些预计在不久之后便会被访问的页面，预先调入内存。

如果预测较准确，那么，这种策略显然是很有吸引力的。

但目前预调页的成功率仅为50%。

且这种策略主要用于进程的首次调入时，由程序员指出应该先调入哪些页。

2.2.2请求调页策略

当进程在运行中需要访问某部分程序和数据时，若发现其所在的页面不在内存，便即提出请求，由OS将其所需页面调入内存。

由请示调页策略所确定调入的页，是一定会被访问的，再加之请求调页策略比较易于实现，故在目前的虚拟存储器中，大多采用此策略。

但这种策略每次仅调入一页，故须花费较大的系统开销，增加了磁盘I/O的启用频率。

2.2.3从何处调入页面

在请求分页系统中的外存分为两部分：

用于存放文件的文件区和用于存放对换页面的对换区。

通常，由于对换区是采用连续分配方式，而事件是采用离散分配方式，故对换区的磁盘I/O速度比文件区的高。

这样，每当发生缺页请求时，系统应从何处将缺页调入内存，可分成如下三种情况：

系统拥有足够的对换区空间，这时可以全部从对换区调入所需页面，以提高调页速度。

为此，在进程运行前，便须将与该进程有关的文件，从文件区拷贝到对换区。

系统缺少足够的对换区空间，这时凡是不会被修改的文件，都直接从文件区调入；而当换出这些页面时，由于它们未被修改而不必再将它们换出时，以后需要时，再从对换区调入。

UNIX方式。

由于与进程有关的文件都放在文件区，故凡是未运行过的页面，都应从文件区调入。

而对于曾经运行过但又被换出的页面，由于是被放在对换区，因此在下次调入时，应从对换区调入。

由于UNIX系统允许页面共享，因此，某进程所请求的页面有可能已被其它进程调入内存，此时也就无须再从对换区调入。

2.3模块设计

第三章详细设计

3.1系统设计

在进程运行过程中，若其所要访问的页面不在内存而需把它们调入内存，但内存已无空闲空间时，为了保证该进程能正常运行，系统必须从内存中调出一页程序或数据，送磁盘的对换区中。

但应将哪 个页面调出，须根据一定的算法来确定。

通常，把选择换出页面的算法称为页面置换算法（Page_Replacement Algorithms）。

 一个好的页面置换算法，应具有较低的页面更换频率。

从理论上讲，应将那些以后不再会访问的页面换出，或将那些在较长时间内不会再访问的页面调出。

3.2算法思想及流程图

3.2.1主程序流程图

如图（3—2—1）所示

主流程图（图3—2—1）

3.2.2先进先出（FIFO）页面置换算法

算法的基本思想：

这是最早出现的置换算法。

该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。

该算法实现简单只需把一个进程已调入内存的页面，按先后次序存入一个时间数组，并将其中时间值最大的页面进行淘汰，并替换入新的页面就可以实现。

算法流程图：

如图（3—2—2）所示

FIFO置换算法（图3—2—2）

3.2.3最佳页面置换置换算法（OPT）

算法的基本思想：

其所选择的被淘汰页面，将是永不使用的，或者是在最长时间内不再被访问的页面。

可保证获得最低的缺页率。

但由于人们目前还无法预知一个进程在内存的若干个页面中，哪一个页面是未来最长时间内不再被访问的，因而该算法也是无法实现的。

但是可利用该算法去评价其它算法。

算法流程图：

如图（3—2—3）所示

OPT页面置换算法（图3—2—3）

3.2.4最近最久未使用页面置换算法LRU

算法的基本思想：

当需要淘汰某一页时，选择离当前时间最近的一段时间内最久没有使用过的页先淘汰。

该算法的主要出发点是，如果某页被访问了，则它可能马上还被访问。

或者反过来说，如果某页很长时间未被访问，则它在最近一段时间不会被访问。

算法流程图：

如图（3—2—4）所示

LRU页面置换算法（图3—2—4）

第四章源程序结构分析

4.1程序结构

Input（intm,Prop[L]）//打印页面走向状态

srand（j）;//以时钟时间j为种子，初始化随机数发生器

voidprint（Pro*page1）//打印当前的页面

intSearch（inte,Pro*page1）//寻找内存块中与e相同的块号

intMax（Pro*page1）//寻找最近最长未使用的页面

intCount（Pro*page1,inti,intt,Prop[L]）//记录当前内存块中页面离下次使用间隔长度

4.2源代码分析

#include

#include

#include

#include

#defineL20//页面长度最大为20

intM;//内存块

structPro//定义一个结构体

{

intnum,time;

};

Input（intm,Prop[L]）//打印页面走向状态

{

cout<<"请输入页面长度（10～20）：

";

do

{

cin>>m;

if（m>20||m<10）

{cout<

cout<<"页面长度必须在10～20之间"<

cout<<"请重新输入L：

";

}

elsebreak;

}while

（1）;

inti,j;

j=time（NULL）;//取时钟时间

srand（j）;//以时钟时间j为种子，初始化随机数发生器

cout<

cout<<"输出随机数:

"<

cout<

for（i=0;i

{

p[i].num=rand（）%10;//产生0到9之间的随机数放到数组p中

p[i].time=0;

cout<

}

cout<

returnm;

}

voidprint（Pro*page1）//打印当前的页面

{

Pro*page=newPro[M];

page=page1;

for（inti=0;i

cout<

cout<

}

intSearch（inte,Pro*page1）//寻找内存块中与e相同的块号

{

Pro*page=newPro[M];

page=page1;

for（inti=0;i

return-1;

}

intMax（Pro*page1）//寻找最近最长未使用的页面

{

Pro*page=newPro[M];

page=page1;

inte=page[0].time,i=0;

while（i

{

if（e

i++;

}

for（i=0;i

return-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（2～6）:

";

cout<

do{

cin>>M;

if（M>6||M<2）

{cout<

cout<<"物理块m必须在2～6之间"<

cout<<"请重新输入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<

cout<<"1:

FIFO页面置换"<

cout<<"2:

LRU页面置换"<

cout<<"3:

OPT页面置换"<

cout<<"请选择页面置换算法：

"<

cin>>c;

system（"cls"）;

if（c==1）//FIFO页面置换

{

n=0;

cout<<"FIFO算法页面置换情况如下:

"<

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<

cout<<"缺页次数：

"<

"<

}

if（c==2）//LRU页面置换

{

n=0;

cout<<"LRU算法页面置换情况如下:

"<

cout<

while（i

{

inta;

t=Search（p[i].num,page）;

if（t>=0）//如果已在内存块中

{page[t].time=0;//把与它相同的内存块的时间置0

for（a=0;a

if（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;a

if（a!

=t）page[a].time++;//其它的时间加1

}

i++;

}

cout<

cout<<"缺页次数：

"<

"<

}

if（c==3）//OPT页面置换

{

n=0;

cout<<"OPT算法置换情况如下:

"<

cout<

while（i

{

if（Search（p[i].num,page）>=0）//如果已在内存块中

{

cout<

cout<<"不缺页"<

i++;

}

else//如果不在内存块中

{

inta=0;

for（t=0;t

if（page[t].num==0）a++;//记录空的内存块数

if（a!

=0）//有空内存

{

intq=M;

for（t=0;t

if（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;t

if（temp

{

temp=Count（page,i,t,p）;

s=t;}//把找到的块号赋给s

page[s].num=p[i].num;

n++;

cout<

print（page）;

i++;

}

}

}

cout<

cout<<"缺页次数：

"<

"<

}

}while（c==1||c==2||c==3）;

return0;

}

第五章调试

程序在运行的情况下，进入主界面输入菜单，如图（4—1）所示：

页面长度：

输入16，分配的物理块：

输入4，

主界面（图4—1）

选1，进入FIFO算法页面置换，如图（4—2）所示

FIFO算法置换（图4—2）

选2，进入LRU算法页面置换，如图（4—3）所示

LRU算法置换（图4—3）

选3，进入OPT算法页面置换，如图（4—4）所示

OPT算法置换（图4—4）

第六章体会与自我评价

这次操作系统课程设计，让我们对操作系统有了更深的认识，首先操作系统是一管理电脑硬件与软件资源的程序，同时也是计算机系统内核与基石。

操作系统是一个庞大的管理控制程序，大致包括5个方面的管理功能：

进程与处理机管理、作业管理、存储管理、设备管理、文件管理。

我们这次课程设计的题目是页面置换算法，是属于存储器管理。

在进程运行过程中，若其访问的页面不在内存而需把它们调入内存，但内存以无空闲空间时，为了保证该进程能正常的运行，系统必须从内存中调出一页程序或数据送磁盘的兑换区中，但应将哪个页面调出，需根据一定的算法来确定。

通常，把选择换成页面的算法称为页面置换算法。

通过本次课程设计，我们对页面置换算法的了解更加的深刻。

主要有以下置换算法：

OPT（最佳置换算法）、FIFO（先进先出置换算法）、LRU（最近最久未使用算法）。

每种算法都有各自的优缺点，OPT算法是实际中不能实现的，但是可以利用该算法去评价其它算法；FIFO算法与进程实际运行的规律不相适用，因为在进程中，有些页面经常被访问；LRU算法是根据页面调入内存后的使用情况进行决策的。

在这次课程设计中，遇到了一些困难，例如怎么实现各种算法，如何进行函数调用及对数据的限制操作等，在遇到这些困难的时候，我们会去查阅资料，仔细看书，尝试用不同的方法解决，在各种方法中选择一种最好的方法，有的时候会碰到不知道如何实现的函数，我们会查看MSDN，这次是用的Ｃ++语言做的，每一步都是自己独立完成的，这次课程设计我最大的收获是学以致用，通过这次设计我们看到了自己学习的能力，我们相信在以后的学习中，会更加的努力上进。

最后，还非常感谢辛苦的操作系统老师，首先，因为他辛苦的为我们讲解操作系统这门课，让我们对操作系统有了一定的了解，为这次课程设计奠定了良好的基础，其次，还要感谢他认真指导我们的这次课程设计，给了我们这次总体运用自己能力的机会，我们坚信：

只要功夫深，铁杵磨成针。

第七章参考文献

[1]计算机操作系统汤小丹，梁红兵，哲凤屏西安电子科技大学出版社2007.5

[2]visualC++高级编程范例谭桂华等清华大学出版社2004.5

[3]操作系统教程与实验胡明庆，高巍，钟梅清华大学出版社2007.1