《操作系统--页面置换算法》
实验报告
学 号：****
班 级：电科10-1班
专 业：电子信息科学与技术
一、实验目的
1．通过模拟实现几种基本页面置换的算法，了解虚拟存储技术的特点。
2．掌握虚拟存储请求页式存储管理中几种基本页面置换算法的基本思想，并至少用三种算法来模拟实现。
3．通过对几种置换算法页面的比较，来对比他们的优缺点，并通过比较更换频率来对比它们的效率。
二、实验内容：
设计一个虚拟存储区和内存工作区，并使用下述算法来模拟实现页面的置换：
1. 先进先出的算法（FIFO）
2. 最近最久未使用算法（LRU）
3. 最佳置换算法（OPT）
三、实验分析
在进程运行过程中，若其所访问的页面不存在内存而需要把它们调入内存，但内存已无空闲时，为了保证该进程能够正常运行，系统必须从内存中调出一页程序或数据送磁盘的对换区中。但应调出哪个页面，需根据一定的算法来确定，算法的好坏，直接影响到系统的性能。
一个好的页面置换算法，应该有较低的页面更换频率。
假设分给一作业的物理块数为3 ，页面数为20个。
页面号为(20个)：
7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1
1．先进先出(FIFO)置换算法的思路
该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。该算法实现简单，只需把一个进程已调入内存的页面，按照先后次序连接成一个队列，并设置一个替换指针，使它总指向最老的页面。
2．最近久未使用(LRU)置换算法的思路
最近久未使用置换算法的替换规则，是根据页面调入内存后的使用情况来进行决策的。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间，当需淘汰一个页面的时候选择现有页面中其时间值最大的进
行淘汰。
3.最佳（OPT）置换算法的思路
其所选择的被淘汰的页面，奖是以后不使用的，或者是在未来时间内不再被访问的页面，采用最佳算法，通常可保证获得最低的缺页率。
4．数据结构
struct pageInfor
{
int content;//页面号
int timer;//被访问标记
};
class PRA
{
public:
PRA(void);
int findSpace(void); //查找是否有空闲内存
int findExist(int curpage); //查找内存中是否有该页面
int findReplace(void); //查找应予置换的页面
void display(void); //显示
void FIFO(void); //FIFO算法
void LRU(void); //LRU算法
void BlockClear(void);//BLOCK清空，以便用另一种方法重新演示
pageInfor * block; //物理块
pageInfor * page; //页面号串
private:
};
5．FIFO页面置换算法
当需要访问一个新的页面时，首先调用findExist(i)函数来查看物理块中是否就有这个页面，若要查看的页面物理块中就有，则调用display函数直接显示，不需要替换页面；如果要查看的页面物理块中没有，就需要寻找空闲物理块放入，若存在有空闲物理块，则将页面放入；若没有空闲物理块，则调用findReplace函数替换页面。并将物理块中所有页面timer++。
6．LRU页面置换算法
当需要访问一个新的页面，首先调用findExist(i)函数查看物理块中是否就有这个页面。
7. OPT页面置换算法
当需要访问一个新的页面，首先调用findExist(i)函数来查看物理块中是否有这个页面。
8．寻找置换页面函数findReplace比较三个物理块中的时间标记timer，找到时间最久的。
四、源程序结构分析
1．程序结构
程序共有以下九个部分：
int findSpace(void);//查找是否有空闲内存
int findExist(int curpage);//查找内存中是否有该页面
int findReplace(void);//查找应予置换的页面
void display(void);//显示
void FIFO(void);//FIFO算法
void LRU(void);//LRU算法
void OPT(void);//OPT算法；
void BlockClear(void);//BLOCK清空，以便用另一种方法重新演示
int main() //主程序
2．源程序代码
#include ＜iostream.h＞
#define Bsize 3
#define Psize 20
struct pageInfor
{
int content;//页面号
int timer;//被访问标记
};
class PRA
{
public:
PRA(void);
int findSpace(void);//查找是否有空闲内存
int findExist(int curpage);//查找内存中是否有该页面
int findReplace(void);//查找应予置换的页面
void display(void);//显示
void FIFO(void);//FIFO算法
void LRU(void);//LRU算法
void Optimal(void);//OPTIMAL算法
void BlockClear(void);//BLOCK恢复
pageInfor * block;//物理块
pageInfor * page;//页面号串
private:
};
PRA::PRA(void)
{
int QString[20]={7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1};
block = new pageInfor[Bsize];
for(int i=0; i＜Bsize; i++)
{
block[i].content = -1;
block[i].timer = 0;
}
page = new pageInfor[Psize];
for(i=0; i＜Psize; i++)
{
page[i].content = QString[i];
page[i].timer = 0;
}
}
int PRA::findSpace(void)
{
for(int i=0; i＜Bsize; i++)
if(block[i].content == -1)
return i;//找到空闲内存，返回BLOCK中位置
return -1;
}
int PRA::findExist(int curpage)
{
for(int i=0; i＜Bsize; i++)
if(block[i].content == page[curpage].content)
return i;//找到内存中有该页面，返回BLOCK中位置
return -1;
}
int PRA::findReplace(void)
{
int pos = 0;
for(int i=0; i＜Bsize; i++)
if(block[i].timer ＞= block[pos].timer)
pos = i;//找到应予置换页面，返回BLOCK中位置
return pos;
}
void PRA::display(void)
{
for(int i=0; i＜Bsize; i++)
if(block[i].content != -1)
cout＜＜block[i].content＜＜" ";
cout＜＜endl;
}
void PRA::Optimal(void)
{
int exist,space,position ;
for(int i=0; i＜Psize; i++)
{
exist = findExist(i);
if(exist != -1)
{ cout＜＜"不缺页"＜＜endl; }
else
{
space = findSpace();
if(space != -1)
{
block[space] = page[i];
display();
}
else
{
for(int k=0; k＜Bsize; k++)
for(int j=i; j＜Psize; j++)
{
if(block[k].content != page[j].content)
{ block[k].timer = 1000; }//将来不会用，设置TIMER为一个很大数
else
{
block[k].timer = j;
break;
}
}
position = findReplace();
block[position] = page[i];
display();
}
}
}
}
void PRA::LRU(void)
{
int exist,space,position ;
for(int i=0; i＜Psize; i++)
{
exist = findExist(i);
if(exist != -1)
{
cout＜＜"不缺页"＜＜endl;
block[exist].timer = -1;//恢复存在的并刚访问过的BLOCK中页面TIMER为-1
}
else
{
space = findSpace();
if(space != -1)
{
block[space] = page[i];
display();
}
else
{
position = findReplace();
block[position] = page[i];
display();
}
}
for(int j=0; j＜Bsize; j++)
block[j].timer++;
}
}
void PRA::FIFO(void)
{
int exist,space,position ;
for(int i=0; i＜Psize; i++)
{
exist = findExist(i);
if(exist != -1)
{cout＜＜"不缺页"＜＜endl;}
else
{
space = findSpace();
if(space != -1)
{
block[space] = page[i];
display();
}
else
{
position = findReplace();
block[position] = page[i];
display();
}
}
for(int j=0; j＜Bsize; j++)
block[j].timer++;//BLOCK中所有页面TIMER++
}
}
void PRA::BlockClear(void)
{
for(int i=0; i＜Bsize; i++)
{
block[i].content = -1;
block[i].timer = 0;
}
}
void main(void)
{
cout＜＜"|----------页 面 置 换 算 法----------|"＜＜endl;
cout＜＜"|---power by wangxinchuang(080501228)---|"＜＜endl;
cout＜＜"|-------------------------------------|"＜＜endl;
cout＜＜"页面号引用串:7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1"＜＜endl;
cout＜＜"----------------------------------------------------"＜＜endl;
cout＜＜"选择＜1＞应用Optimal算法"＜＜endl;
cout＜＜"选择＜2＞应用FIFO算法"＜＜endl;
cout＜＜"选择＜3＞应用LRU算法"＜＜endl;
cout＜＜"选择＜0＞退出"＜＜endl;
int select;
PRA test;
while(select)
{
cin＞＞select;
switch(select)
{
case 0:
break;
case 1:
cout＜＜"Optimal算法结果如下:"＜＜endl;
test.Optimal();
test.BlockClear();
cout＜＜"----------------------"＜＜endl;
break;
case 2:
cout＜＜"FIFO算法结果如下:"＜＜endl;
test.FIFO();
test.BlockClear();
cout＜＜"----------------------"＜＜endl;
break;
case 3:
cout＜＜"LRU算法结果如下:"＜＜endl;
test.LRU();
test.BlockClear();
cout＜＜"----------------------"＜＜endl;
break;
default:
cout＜＜"请输入正确功能号"＜＜endl;
break;
}
}
}
五 、实验结果
1运行后的初始界面
2 opt算法 3.FIFO算法 4LRU算法
第二篇：实验报告三 内存页面置换算法的设计
实验报告三
——内存页面置换算法的设计
姓名：** 学号：*** 班级：信息安全二班
一、实习内容
• 实现最近最久未使用（LRU）置换算法
二、实习目的
• LINUX中，为了提高内存利用率，提供了内外存进程对换机制，内存空间的分配和回收均以页为单位进行，一个进程只需将其一部分调入内存便可运行，还支持请求调页的存储管理方式。
• 本实习要求学生通过请求页式存储管理中页面置换算法模拟设计，了解虚拟存储技术的特点，掌握请求页式存储管理的页面置换算法。
三、实习题目
1. 最近最久未使用（LRU）置换算法原理就是：当需要淘汰某页面时，选择当前一段时间内最久未使用过的页先淘汰，即淘汰距当前最远的上次使用的页。
• 例如: 分配给该进程的页块数为3，一个20位长的页面访问序列为:12560,36536,56042,70435，
则缺页次数和缺页率按下图给出:
2. 假定分配给该进程的页块数为3，页面访问序列长度为20。本实验可以采用数组结构实现，首先随机产生页面序列，当发生请求调页时，若内存已满，则需要利用LRU算法，将当前一段时间内最久未使用过的页替换出去。
• 模拟程序的算法如下图：
四、实现代码为：
#include＜stdio.h＞
#define M 3
#define N 20
#define Myprintf printf("|---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---|\n") /*表格控制*/
typedef struct page
{
int num; /*记录页面号*/
int time; /*记录调入内存时间*/
}Page; /* 页面逻辑结构，结构为方便算法实现设计*/
Page b[M]; /*内存单元数*/
int c[M][N]; /*暂保存内存当前的状态：缓冲区*/
int queue[100]; /*记录调入队列*/
int K; /*调入队列计数变量*/
/*初始化内存单元、缓冲区*/
void Init(Page *b,int c[M][N])
{
int i,j;
for(i=0;i＜N;i++)
{
b[i].num=-1;
b[i].time=N-i-1;
}
for(i=0;i＜M;i++)
for(j=0;j＜N;j++)
c[i][j]=-1;
}
/*取得在内存中停留最久的页面,默认状态下为最早调入的页面*/
int GetMax(Page *b)
{
int i;
int max=-1;
int tag=0;
for(i=0;i＜M;i++)
{
if(b[i].time＞max)
{
max=b[i].time;
tag=i;
}
}
return tag;
}
/*判断页面是否已在内存中*/
int Equation(int fold,Page *b)
{
int i;
for(i=0;i＜M;i++)
{
if (fold==b[i].num)
return i;
}
return -1;
}
void Lru(int fold,Page *b) /*LRU核心部分*/
{
int i;
int val;
val=Equation(fold,b);
if (val＞=0)
{
b[val].time=0;
for(i=0;i＜M;i++)
if (i!=val)
b[i].time++;
}
else//页面不存在
{
queue[++K]=fold;/*记录调入页面*/
val=GetMax(b);
b[val].num=fold;
b[val].time=0;
for(i=0;i＜M;i++)
if (i!=val)
b[i].time++;
}
}
main()/*主程序*/
{
int a[N]={1,0,5,1,7,1,0,2,4,1,0,0,8,7,5,4,3,2,3,4};
int i,j;
start:
K=-1;
Init(b, c);
for(i=0;i＜N;i++)
{
Lru(a[i],b);
c[0][i]=a[i];
/*记录当前的内存单元中的页面*/
for(j=0;j＜M;j++)
c[j][i]=b[j].num;
}
/*结果输出*/
printf("nei cun zhuang tai ：\n");
Myprintf;
for(j=0;j＜N;j++)
printf("|%2d ",a[j]);
printf("|\n");
Myprintf;
for(i=0;i＜M;i++)
{
for(j=0;j＜N;j++)
{
if(c[i][j]==-1)
printf("|%2c ",32);
else
printf("|%2d ",c[i][j]);
}
printf("|\n");
}
Myprintf;
printf("\ndiao ru dui lie :");
for(i=0;i＜K+1;i++)
printf("%3d",queue[i]);
printf("\nque ye ci shu ：%6d\nque ye lv：%16.2f%%\n",K+1,(float)(K+1)/N*100);
}
五、在虚拟机上的具体操作及结果
六、思考题
• 比较LRU和其他置换算法各自的优缺点，能够实现其他置换算法模拟设计，分析内存页面数的变化对各种置换算法命中率的影响。
答: 内存页面数越多哦,命中率越高.
LRU算法可以减少页错误率,较易理解.
最优算法页错误最低,且没有Belady异常,但是较难实现
FIFO算法容易理解和实现,但是页错误率较高
七、实验总结
明白LRU算法的原理,当内存页面中不存在当前页面时,且没有空闲页面,将替换近期最少使用的页面,这种算法可以有效减少替换掉常用页面的次数,从而减少页错误率.