算法--操作系统--3种页面置换算法

算法连载（7）--操作系统之3种页面置换算法
作者： 来自： 阅读次数： 58033 [大 中 小]


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


#include

#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 {
block.cOntent= -1;
block.timer = 0;
}

page = new pageInfor[Psize];
for(i=0; i {
page.cOntent= QString;
page.timer = 0;
}
}

int PRA::findSpace(void)
{
for(int i=0; i if(block.cOntent== -1)
return i;//找到空闲内存，返回BLOCK中位置
return -1;
}

int PRA::findExist(int curpage)
{

for(int i=0; i if(block.cOntent== page[curpage].content)
return i;//找到内存中有该页面，返回BLOCK中位置

return -1;
}

int PRA::findReplace(void)
{
int pos = 0;

for(int i=0; i if(block.timer >= block[pos].timer)
pos = i;//找到应予置换页面，返回BLOCK中位置
return pos;
}

void PRA::display(void)
{


for(int i=0; i if(block.content != -1)
cout<.content<<" ";
cout< }


void PRA::Optimal(void)
{
int exist,space,position ;

for(int i=0; i {
exist = findExist(i);
if(exist != -1)
{ cout<<"不缺页"< else
{
space = findSpace();
if(space != -1)
{
block[space] = page;
display();
}
else
{
for(int k=0; k for(int j=i; j {
if(block[k].content != page[j].content)
{ block[k].timer = 1000; }//将来不会用，设置TIMER为一个很大数
else
{
block[k].timer = j;
break;
}
}
position = findReplace();
block[position] = page;
display();
}
}
}
}

void PRA::LRU(void)
{
int exist,space,position ;

for(int i=0; i {
exist = findExist(i);
if(exist != -1)
{
cout<<"不缺页"< block[exist].timer = -1;//恢复存在的并刚访问过的BLOCK中页面TIMER为-1
}
else
{
space = findSpace();
if(space != -1)
{
block[space] = page;
display();
}
else
{
position = findReplace();
block[position] = page;
display();
}
}
for(int j=0; j block[j].timer++;
}
}

void PRA::FIFO(void)
{

int exist,space,position ;

for(int i=0; i {
exist = findExist(i);
if(exist != -1)
{cout<<"不缺页"<
else
{
space = findSpace();
if(space != -1)
{
block[space] = page;
display();
}
else
{
position = findReplace();
block[position] = page;
display();
}
}
for(int j=0; j block[j].timer++;//BLOCK中所有页面TIMER++
}
}

void PRA::BlockClear(void)
{
for(int i=0; i {
block.cOntent= -1;
block.timer = 0;
}
}


void main(void)
{
cout<<"|----------页 面 置 换 算 法----------|"< cout<<"|---power by zhanjiantao(028054115)---|"< cout<<"|-------------------------------------|"< cout<<"页面号引用串:7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1"< cout<<"----------------------------------------------------"< cout<<"选择<1>应用Optimal算法"< cout<<"选择<2>应用FIFO算法"< cout<<"选择<3>应用LRU算法"< cout<<"选择<0>退出"< int select;
PRA test;


while(select)
{
cin>>select;
switch(select)
{
case 0:
break;
case 1:
cout<<"Optimal算法结果如下:"< test.Optimal();
test.BlockClear();
cout<<"----------------------"< break;
case 2:
cout<<"FIFO算法结果如下:"< test.FIFO();
test.BlockClear();
cout<<"----------------------"< break;
case 3:
cout<<"LRU算法结果如下:"< test.LRU();
test.BlockClear();
cout<<"----------------------"< break;
default:
cout<<"请输入正确功能号"< break;
}

}

}
发布时间：2005-4-15

[ Last edited by frog on 2005-10-23 at 16:17 ]