算法连载（7）--操作系统之3种页面置换算法
1.问题描述及设计思想：在进程运行过程中，若其所要访问的页面不在内存需把它们调入内存，但内存已无空闲空间时，为了保证该进程能正常运行，系统必须从内存中调出一页程序或数据，送磁盘的对换区中。但应将哪个页面调出，所以需要根据一定的算法来确定。以下分别是三个算法的设计思想。
OPTIMAL：最佳置换算法。其所选择的被淘汰页面，将是以后永不使用的，或是在最长（未来）时间内不再被访问的页面。
FIFO：先进先出置换算法。该算法总是淘汰最先进入内存的页面，既选择在内存中驻留时间最久的页面予以淘汰。
LRU：最近最久未使用置换算法。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间T，当须淘汰一个页面时，选择现有页面中其T值最大的给予淘汰。
#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 zhanjiantao(028054115)---|"<<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;
}
}
}