页面置换-操作系统实验报告.doc

实验二 页面置换算法实现
一、实验目的
（1）了解内存分页管理策略
（2）掌握调页策略
（3）掌握一般常用的调度算法
（4）学会各种存储分配算法的实现方法。
（5）了解页面大小和内存实际容量对命中率的影响。
二、实验内容
采用页式分配存储方案，通过分别计算不同算法的命中率来比较算法的优劣，
同时也考虑页面大小及内存实际容量对命中率的影响，设计一个虚拟存储区和内
存工作区，并使用下述算法来模拟实现页面的置换：
1. 先进先出的算法（FIFO）
2. 最近最久未使用算法（LRU）
3. 最佳置换算法（OPT）
实验分析
在进程运行过程中，若其所访问的页面不存在内存而需要把它们调入内存，
但内存已无空闲时，为了保证该进程能够正常运行，系统必须从内存中调出一页
程序或数据送磁盘的对换区中。但应调出哪个页面，需根据一定的算法来确定，
算法的好坏，直接影响到系统的性能。一个好的页面置换算法，应该有较低的页面更换频率。
2.1 先进先出（FIFO ）页面置换算法
当需要访问一个新的页面时，首先查看物理块中是否就有这个页面，若要查

看的页面物理块中就有，则直接显示，不需要替换页面；如果要查看的页面物理
块中没有，就需要寻找空闲物理块放入，若存在有空闲物理块，则将页面放入；
若没有空闲物理块，则替换页面。并将物理块中所有页面 timer++
2.2 最近久未使用 (LRU) 置换算法的思路
最近久未使用置换算法的替换规则，是根据页面调入内存后的使用情况来进
行决策的。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问
以来所经历的时间，当需淘汰一个页面的时候选择现有页面中其时间值最大的进
行淘汰。
2.3 最佳（OPT）置换算法的思路
其所选择的被淘汰的页面，是以后不使用的，或者是在未来时间内不再被访
问的页面，采用最佳算法，通常可保证获得最低的缺页率。
三、 实验流程
3.1 系统功能图

图3-1 系统功能图

3.2 算法流程图

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

图3-2 先进先出页面置换算法流程图
2） 最近久未使用 (LRU) 置换算法

图3-3 最近久未使用置换算法流程图
3） 最佳（ OPT ）置换算法

图3-4 最佳置换算法流程图

四、 源程序
#include
#include
#include
#include
#define L 20 //页面长度最大为20
int M; //内存块
struct Pro//定义一个结构体
{
int num,time;
}

Input(int m,Pro p[L])//打印页面走向状态
{
cout<<"请输入页面长度(10～20)：";
do
{
cin>>m;
if(m>20||m<10)
{ cout<t<i++)
cout<t e=page[0].time,i=0;
while(ige=page1;
int count=0;
for(int j=i;j
cout<>M;
if(M>6||M<2)

{ cout<
cout<>c;
if(c==1)//FIFO页面置换
{
n=0;
cout<<" FIFO算法页面置换情况如下: "<=0) //当前页面在内存中
{

cout<面
t++; //下一个内存块
i++; //指向下一个页面
}
}
}
cout<age);
if(t>=0)//如果已在内存块中
{ page[t].time=0;//把与它相同的内存块的时间置0
for(a=0;age[t].num=p[i].num; //进行替换
page[t].time=0; //替换后时间置为0
cout< {
n=0;
cout<<" OPT算法置换情况如下:"<=0)//如果已在内存块中
{
cout<].num==0)a++;//记录空的内存块数
if(a!=0) //有空内存
{
int q=M;
for(t=0;tt)q=t;//把空内存块中块号最小的找出来
page[q].num=p[i].num;
n++;
cout< int temp=0,s;
for(t=0;t
}
}
cout<先出(FIFO) 页面置换算法运行结果
选择算法1之后，进入算法1 的操作。系统会显示算法的页面置换情况。先来先服务算法的运行图如图5-2所示。

图5-2 先进先出页面置换算法运行结果图
5.3 最近久未使用 (LRU) 置换算法运行结果
选择算法2之后，进入算法2 的操作。系统会显示算法的页面置换情况。最近久未使用的运行图如图5-3所示。

图5-3 最近久未使用置换算法运行结果图
4） 最佳（ OPT ）置换算法运行结果
选择算法3之后，进入算法3 的操作。系统会显示算法的页面置换情况。最近久未使用的运行图如图5-4所示。

图5-4 最佳置换算法运行结果图
四、 总结

通过本次实验，我对页面置换算法的了解更加的深刻。页面置换算法主要有以下置换算法：OPT（最佳置换算法）、FIFO（先进先出置换算法）、LRU（最近最久未使用算法）。在进程运行过程中，若其访问的页面不在内存而需把它们调入内存，但内存以无空闲空间时，为了保证该进程能正常的运行，系统必须从内存中调出一页程序或数据送磁盘的兑换区中，但应将哪个页面调出，需根据一定的算法来确定。

（注：专业文档是经验性极强的领域，无法思考和涵盖全面，素材和资料部分来自网络，供参考。可复制、编制，期待你的好评与关注）