请求页式管理中的页面置换算法性能分析.doc

请求页式管理中的页面置换算法性能分析

指导老师： 余 宏 生
组 员：邓祥镭201041210123
殷 嵘201041210124
柯希杰201041210125
石贤主201041210126
尚晨曦201041210141

请求页式管理中的页面置换算法性能分析
（湖北理工学院，黄石 435000）
摘要：随着虚拟存储技术在操作系统中的应用，大大提高了操作系统的性能，其中页面置换算法是虚拟存储管理的重要组成部分，页面置换算法的优劣将直接影响系统的整体性能。随着大量有着不同读写速度的外存设备共存于系统中，单一置换算法同样影响着系统的整体性能。
关键词：操作系统；虚拟存储；页面置换；算法
The request paging page replacement algorithm performance analysis
Abstract：With virtual storage technology in the application of the operating system, greatly improve the performance of the operating system, including page replacement algorithm is an important part of virtual storage management page replacement algorithm quality will directly affect the overall performance of the system. As the speed of read and write a lot of different peripheral storage devices coexist in the system, a single replacement algorithm also affects the overall performance of the system.
Keyword：Operating stystem；Virtual storage；Page replacement；Algorithm

5

1、引言
虚拟存储器的实现是建立在离散分配存储管理方式的基础上的，一般采用分页请求系统或分段请求系统来实现。分页（段）请求系统是在分页（段）系统的基础上，增加了请求调页（段）功能、页面（分段）置换功能所形成的页（段）式虚拟存储器系统。它允许只装入若干页面（分段）的用户程序和数据（而非全部程序和数据），便可以启动运行。以后，再通过调页（段）功能及页面（分段）置换功能，把所需要的页面（分段）调入内存，同时把暂时不运行的页面（分段）换出到外存上，置换时以页面（分段）为单位。
在请求分页式系统中，每当所要访问的页面不在内存时，便要产生一缺页中断，请求操作系统将所缺之页面调入内存。若内存已无空间时，为了保证该进程能正常运行，系统必须从内存中调出一个页面，但应该将哪个页面调出，则必须根据一定的算法来确定。通常，把选择换出页面的算法称为页面置换算法(Page_Replacement Algorithms)。
一个好的页面置换算法，应具有较低的页面更换频率。从理论上讲，应将那些以后不再会访问的页面换出，或将那些在较长时间内不会再访问的页面调出。
2、 传统的页面置换算法
传统的页面置换算法主要有FIFO（First In First Out，先进先出）、最佳置换算法（Optimal）、LRU（Least Recently Used，最近最久未使用）和LFU（Least Frequently Used，最近最少使用）等算法。
2.1、先进先出(FIFO)页面置换算法
这是最早出现的置换算法。该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。该算法实现简单只需把一个进程已调入内存的页面，按先后次序链接成一个队列，并设置一个指针，称为替换指针，使它总是指向最老的页面。但它所依据的条件是各个页面调入内存的时间，而页面调入的先后并不能反映页面的使用情况，故此算法性能一般较差。
2.2、最佳置换算法OPT(Optimal)
它是由Belady于1966年提出的一种理论上的算法。其所选择的被淘汰页面，将是以后永不使用的或者是在最长(未来)时间内不再被访问的页面。采用最佳置换算法，通常可保证获得最低的缺页率。但由于人目前还无法预知一个进程在内存的若干个页面中，哪一个页面是未来最长时间内不再被访问的，因而该算法是无法实现的，便可以利用此算法来评价其它算法。
2.3、最近最久未使用（LRU）置换算法
最近最久未使用（LRU）置换算法，是根据页面调入内存后的使用情况进行决策的。由于无法预测各页面将来的使用情况，只能利用“最近的过去”作为“最近的将来”的近似，因此，LRU置换算法是选择最近最久未使用的页面予以淘汰。但是页面的过去和未来的走向之间并无必然的联系。
2.4、最近最少使用（LFU）置换算法
LFU页面置换算法假定在一段时间内访问频率较高的页面与那些访问频率较低的页面相比，更有可能在不远的将来被访问，因而选择在一段时间内访问频率较低的页面予以淘汰，即将最近时期使用最少的页面作为淘汰页。
3、 程序清单
参考实验步骤如下：
#include "stdio.h"
char find(int j);
int findo(int j);
int l(int j);
int queye;
double queyelu;
char z='%';

char a[4][20]={'7','0','1','2','0','3','0','4','2','3','0','3','2','1','2','0','1','7','0','1'};
//char a[][];

void fifo() //先进先出算法
{ int i=2,m,j;
queye=1;
a[1][0]=a[0][0];
for(j=1;j<20;j++)
{
if (i>3)i=1;
if (find(j)=='F') //调用查找函数
{
a[i][j]=a[0][j];
for(m=1;m<4;m++)
{if(m!=i)a[m][j]=a[m][j-1]; }
queye=queye+1;
i=i+1;
}
else
{
a[1][j]=a[1][j-1];
a[2][j]=a[2][j-1];
a[3][j]=a[3][j-1];
}

}
for(i=0;i<4;i++) //输出序列
{
for(j=0;j<20;j++)
{
printf("%c ",a[i][j]);
}
printf("\n");
}
//printf("%d\n",queye);
queyelu=queye*100/20;
printf("缺页率：%4.1f%c\n",queyelu,z);
//printf("\%\n");
}
char find(int j) //查找FIFO函数
{
//int j;
if (j>=3 && (a[0][j]==a[1][j-1] || a[0][j]==a[2][j-1] || a[0][j]==a[3][j-1]))
return ('T');
else
return('F');
}

void opt() //OPT置换算法
{
int i,j,m,t;
a[1][0]=a[0][0];
//a[1][1]=a[0][0];

for(j=1;j<3;j++)
{
for(i=1;i<j+2;i++)
{ if((i-j)==1)
a[i][j]=a[0][j];
else
a[i][j]=a[i][j-1];
}
}
queye=3;
for(j=3;j<20;j++)
{
if(find(j)=='F')
{
t=findo(j);
// printf("\n%d\n",t);
for(m=1;m<4;m++)
{if(m!=t)a[m][j]=a[m][j-1]; }
// a[i][j]=a[i-1][j];
a[t][j]=a[0][j];
queye=queye+1;

}
else
{
a[1][j]=a[1][j-1];
a[2][j]=a[2][j-1];
a[3][j]=a[3][j-1];
}
}
for(i=0;i<4;i++) //输出序列
{
for(j=0;j<20;j++)
{
printf("%c ",a[i][j]);
}
printf("\n");
}

queyelu=queye*100/20;
printf("缺页率：%4.1f%c\n",queyelu,z);

}
int findo(int j) //查找OPT的函数
{
int x=21,y=21,z=21,m,t;

for (m=19;m>j;m--)
{
if (a[1][j-1]==a[0][m])x=m;
if (a[2][j-1]==a[0][m])y=m;
if (a[3][j-1]==a[0][m])z=m;
}
//max=x;
t=1;

if (y>x && y>z)t=2;
if(z>x && z>y)t=3;

return (t);
}

void lru() //LRU置换算法
{

int u,j,i;
int k;

a[1][0]=a[0][0];
//a[1][1]=a[0][0];

for(j=1;j<3;j++)
{
for(i=1;i<j+2;i++)
{ if((i-j)==1)
a[i][j]=a[0][j];
else
a[i][j]=a[i][j-1];
}
}
queye=3;
for (j=3;j<20;j++)
{
if (find(j)=='T') //调用查找函数
{
u=l(j);

// k=a[u][j];
k=2;
for(i=3;i>0;i--)
{
if(i!=u)
{ a[k][j]=a[i][j-1];
k=k-1;
}

}
a[3][j]=a[0][j];
}
else
{
for(i=1;i<3;i++)
{
a[i][j]=a[i+1][j-1];
}
a[3][j]=a[0][j];

queye=queye+1;
}
}
for(i=0;i<4;i++) //输出序列
{
for(j=0;j<20;j++)
{
printf("%c ",a[i][j]);
}
printf("\n");
}
queyelu=queye*100/20;
printf("缺页率：%4.1f%c\n",queyelu,z);

}

int l(int j) //查找要替换的位置
{
if (a[0][j]==a[1][j-1])return(1);
if (a[0][j]==a[2][j-1])return(2);
if (a[0][j]==a[3][j-1])return(3);
}

void main()
{
printf("先进先出算法:\n");
fifo();
printf("最佳置换OPT算法:\n");
opt();
printf("LRU算法:\n");
lru();
}

4．对不同算法的性能进行评价。
FIFO算法较易实现，对具有线性顺序特征的程序比较适用，而对具有其他特征的程序则效率不高，此算法还可能出现抖动现象（Belady）异常。LRU算法基于程序的局部性原理，所以适用用大多数程序，此算实现必须维护一个特殊的队列——页面淘汰队列。OPT算法虽然产生的缺页数最少，然而，却需要预测程序的页面引用串，这是无法预知的，不可能对程序的运行过程做出精确的断言，不过此理论算法可用做衡量各种具体算法的标准。
5、 结论
本文首先对虚拟存储器存在的基本原理进行了分析，知道分页系统存在的可能性。然后对传统的几种页面置换算法进行了介绍，利用编写的程序分析各自的性能，比较得出了每种算法的优点和缺点。
参考文献：
【1】《操作系统》 清华大学出版社
6、附录（程序运行结果）