//LRU页面置换算法的例子
#include <iostream>
using namespace std;
class MemPool
{
private:
int block_n; //内存页面数
int* indexarray;//指向一个数组,它作为当前内存中的页面队列
int append(int page_no) //在队列中加入新的一页
{
int *pt=indexarray;
int outpage=pt[0];
for(int i=0; i<block_n; ++i) //使队列前移
{
*pt=*(pt+1);
pt++;
}
pt--;
*pt=page_no;
return outpage; //返回值是被淘汰的页面号
}
int haspage(int page_no) //找到返回数组下标,否则返回-1
{
for (int b=0; b<block_n; ++b)
if (indexarray[b]==page_no)
return b;
return -1;
}
void round(int idx)//已在内存中的页面再被使用则移至队列后面,本函数实现移动
{
if (idx==block_n-1) return;
int temp=indexarray[idx], i;
for (i=idx; i<block_n-1; ++i)
indexarray[i]=indexarray[i+1];
indexarray[block_n-1]=temp;
}
public:
MemPool(int block):block_n(block)
{
indexarray=new int[block]; //pt指向一个队列,记录内存中的页面号
for (int i=0; i<block_n; ++i)
indexarray[i]=-1;
}
~MemPool(){delete []indexarray;}
int memrefresh(int newpage)//返回值是换出的页面
{
int id;
if ((id=haspage(newpage))!=-1)
{
round(id);
return -9;
}
else return append(newpage);
}
void showpool()
{
cout<< "[";
for (int i=0; i<block_n; ++i)
cout<<" "<<indexarray[i];
cout<< " ]";
}
};
int main()
{
MemPool mpages(3); //内存池
int blocks[12]={1,0,1,2,5,3,2,4,7,4,5,6}; //假设一个访问的例子
for(int i=0; i<12; ++i)
{
cout<<" 访问页面: "<<blocks[i]<<", ";
int outpg= mpages.memrefresh(blocks[i]);
if(outpg==-9)
cout<<"页面 "<<blocks[i]<<" 已经在内存中"<<endl;
else
{
cout<<"页面 "<<blocks[i]<<" 被放入内存池中, ";
cout<<"页面 "<<outpg<<" 被换出"<<endl;
}
mpages.showpool();
cout<<endl;
}
system("pause");
return 0;
}