页面替换算法实验报告_页面置换算法实验报告
页面替换算法实验报告由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“页面置换算法实验报告”。
操作系统页面替换算法实验报告
姓名： 沈慧 班级： 计091 学号： 0913022006
页面替换算法
一．目的和要求
（一）目的存储管理的主要功能之一是合理地分配空间。请求页式管理是一种常用的虚拟存储管理技术。
本实验的目的是通过请求页式管理中页面置换算法的模拟设计，来了解虚拟存储技术的特点，掌握请求页式管理的页面置换算法。
（二）要求
模拟页式虚拟存储管理中硬件的地址转换和缺页中断，并用最佳页面替换算法（OPT）、最近最少使用页面替换算法（LRU）、先进先出调度算法（FIFO）处理缺页中断。
二、算法描述
1．先进先出(FIFO)置换算法的思路
该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。该算法实现简单，只需把一个进程已调入内存的页面，按照先后次序连接成一个队列，并设置一个替换指针，使它总指向最老的页面。
2．最近久未使用(LRU)置换算法的思路
最近久未使用置换算法的替换规则，是根据页面调入内存后的使用情况来进行决策的。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间，当需淘汰一个页面的时候选择现有页面中其时间值最大的进 行淘汰。
3.最佳（OPT）置换算法的思路
其所选择的被淘汰的页面，奖是以后不使用的，或者是在未来时间内不再被访问的页面，采用最佳算法，通常可保证获得最低的缺页率。
三、方案设计
1、数据结构 cla RAMPAGE { protected: int *RAM;//内存各块，存放各页
int ramcount;//内存块数
int *PAGE;//接收用户要访问的各页
int pagecount;//页数
int *CHANGEPAGE;//存放淘汰的各页 int maxpage;//页的最大页号
int shortage;//缺页的数量 public: RAMPAGE();//初始化
void input();//用户输入
void FIFO();//FIFO算法 void LRU();//LRU算法 void OPT();//OPT算法
~RAMPAGE();//释放空间
};
三、测试与运行
1、输入要测试的数据
2、采用FIFO方法进行页面置换
3、采用LRU算法进行页面置换
4、采用OPT算法进行页面置换
源程序代码：
#include #include #include using namespace std;cla RAMPAGE { protected: int *RAM;//内存各块，存放各页 int ramcount;//内存块数
int *PAGE;//接收用户要访问的各页
int pagecount;//页数
int *CHANGEPAGE;//存放淘汰的各页 int maxpage;//页的最大页号
int shortage;//缺页的数量 public: RAMPAGE();//初始化
void input();//用户输入
void FIFO();//FIFO算法 void LRU();//LRU算法 void OPT();//OPT算法
~RAMPAGE();//释放空间 };RAMPAGE::RAMPAGE(){ ramcount=0;//内存块数
pagecount=0;//页数
maxpage=0;//页的最大页号 } void RAMPAGE::input()//用户输入 { cout>ramcount;//用户输入块数
RAM=new int [ramcount];//内存各块，存放各页 cout>page;//用户输入页号
PAGE2[i]=page;//该页进入预分配空间
if(page>maxpage)maxpage=page;//找出最大页 i++;} pagecount=i;//记录用户输入的页数 CHANGEPAGE=new int[pagecount];PAGE=new int[pagecount];//接收用户要访问的各页
for(i=0;i
} delete [] PAGE2;//释放预申请空间 }
void RAMPAGE::FIFO(){ cout=maxpage||ramcount>=pagecount){ cout
int j=0,k=0,l=0;//j记录内存序号，k记录淘汰页空间序号，l记录未被写入的内存块号
cout
in=0;for(j=0;j
}
if(in==0)//页不在内存块
{
shortage++;
if(RAM[ramcount-1]!=-1)//最后一个内存块标记为-1，表示它未被写入过页号
{
CHANGEPAGE[k]=RAM[l];//!-1,则要进行淘汰，记录要被淘汰的页号
k++;
}
RAM[l]=PAGE[i];//新页写入块，将该块初次写入
l++;
if(l==ramcount)l=0;}
}
for(j=0;j
{cout
cout
cout
}
void RAMPAGE::LRU(){ cout=maxpage||ramcount>=pagecount){ cout
int i=0;for(i=0;i
cout
for(j=0;j
if(PAGE[i]==RAM[j])
{
in=1;
break;
}
}
if(in==0&&RAM[ramcount-1]!=-1){
shortage++;
for(j=0;j
RAM2[j]=0;
for(j=0;j
{
for(p=i-1;p>=0;p--)
{ RAM2[j]++;//RAM2[]存储当前内存中各页的权值（距该页上次被访问待了多长时间）
if(RAM[j]==PAGE[p])break;
}
}
int max=0;for(j=0;j
{
if(RAM2[j]>max)
max=RAM2[j];//max标记最大的权值
}
for(j=0;j
{
if(max==RAM2[j])break;//定位max对应的最大权值页号的存储块号
}
CHANGEPAGE[k]=RAM[j];//将该块中的页号放入淘汰序列
RAM[j]=PAGE[i];//要访问的页写入内存块好
k++;// 淘汰数加1
}
if(in==0&&RAM[ramcount-1]==-1){
shortage++;
RAM[l]=PAGE[i];
l++;} }
for(j=0;j
cout
for(int m=0;m
void RAMPAGE::OPT(){ cout=maxpage||ramcount>=pagecount){ cout
int i=0;for(i=0;i
cout
for(j=0;j
in=0;for(j=0;j
if(PAGE[i]==RAM[j])
{
in=1;
break;
}
}
if(in==0&&RAM[ramcount-1]!=-1){
shortage++;
for(j=0;j
RAM2[j]=0;
for(j=0;j
{
for(p=i+1;p
{ RAM2[j]++;//RAM2[]存储当前内存中各页的权值（距该页下次被访问要待多长时间）
if(RAM[j]==PAGE[p])break;
}
}
int max=0;for(j=0;j
{
if(RAM2[j]>max)
max=RAM2[j];
}
for(j=0;j
{
if(max==RAM2[j])break;
}
CHANGEPAGE[k]=RAM[j];
RAM[j]=PAGE[i];
k++;
}
if(in==0&&RAM[ramcount-1]==-1){
shortage++;
RAM[l]=PAGE[i];
l++;} }
for(j=0;j
cout
for(int m=0;m
delete []PAGE;//释放访问各页空间
delete []CHANGEPAGE;//释放淘汰页空间 }
int main(){
率： RAMPAGE *task;
again: coutinput();cout
cout>number;switch(number){ case 1: task->FIFO();break;case 2: task->LRU();break;case 3: task->OPT();break;default : cout
cout>number;switch(number){ case 1: task->FIFO();break;case 2: task->LRU();break;case 3: task->OPT();break;default : cout
cout
cout>number;switch(number){ case 1: task->FIFO();break;case 2: task->LRU();break;case 3: task->OPT();break;
default : cout
cout
delete task;cout>goon;if(goon=='y'){ system(“CLS”);
goto again;} return 0;}
