页面替换

南通大学

计算机科学与技术学院

操

作

系

统

实

验

报

告

班级：计 091

姓名：马 瑞 凯

学号：0913022022

实验名称 页面替换算法

一、实验目的

1、进一步理解页面算法的相关内容。

2、明白页面替换的主要任务。

3、通过编程掌握页面替换的主要算法。

二、实验内容

常见的置换算法有：

1) 最佳页面替换算法OPT ：

调入一页而必须淘汰一个旧页时，所淘汰的页应该是以后不再访问的页或距现在最长时间后再访问的页。

2) 先进先出页面替换算法FIFO

算法总是淘汰最先调入主存的那一页，或者说在主存中驻留时间最长的那一页（常驻的除外)。

3) 最近最少用页面替换算法LRU

算法淘汰的页面是在最近一段时间里较久未被访问的那页。

根据程序局部性原理，那些刚被使用过的页面，可能马上还要被使用，而在较长时间里未被使用的页面，可能不会马上使用到。

4) 第二次机会页面替换算法SCR

改进FIFO算法,把FIFO与页表中的“引用位”结合起来使用：

检查FIFO中的队首页面(最早进入主存的页面),如果它的“引用位”是0,这个页面既老又没有用，选择该页面淘汰;

如果“引用位”是1,说明它进入主存较早，但最近仍在使用。把它的“引用位”清0,并把这个页面移到队尾，把它看作是一个新调入的页。

算法含义：最先进入主存的页面，如果最近还在被使用的话,仍然有机会作为像一个新调入页面一样留在主存中。

5) 时钟页面替换算法Clock FIFO算法

把SCR算法中的FIFO队列改为循环页面队列， 减少入队出队操作。

一个页面首次装入主存，其“引用位”置0 。

主存中的任何页面被访问时, “引用位”置1。

淘汰页面时,从指针当前指向的页面开始扫描循环队列，把遇到的“引用位”是1的页面的“引用位”清0,跳过这个页面; 把所遇到的“引用位”是0的页面淘汰掉,指针推进一步。

三、算法实现部分代码

1.FIFO页面置换：

if(c==1)

{

n=0;

cout<<" ******************************************

"<

cout<

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<<"缺页次数："<

}

2. LRU页面置换算法：

if(c==2)

{

n=0;

cout<<" ******************************************

"<

cout<

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

"<

cout<

cout<<" ******************************************

"<

while(i

{

int a;

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<<"缺页次数："<

}

3. OPT页面置换算法：

if(c==3)

{

n=0;

cout<<" ******************************************

"<

cout<

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

cout<

cout<<" ******************************************

"<

while(i

{

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

{

cout<

cout<<"不缺页"<

i++;

}

else //如果不在内存块中

{

int a=0;

for(t=0;t

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

if(a!=0) //有空内存块

{

int q=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

{

int temp=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<<"缺页次数："<

}

四、实验结果