算法连载（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;
  }
  
 }

}

本文地址：http://com.8s8s.com/it/it22393.htm