在此展示3种算法：FIFO、OPT、LRU 算法。(点击进入百度百科介绍)
1、任意给出一组页面访问顺序（如页面走向是1、2、5、7、5、7、1、4、3、5、6、4、3、2、1、5、2）。
2、分配给该作业一定的物理块（如3块、4块等）。
3、利用OPT,FIFO,LRU页面置换算法模拟页面置换过程并计算其缺页率。
4、每访问一个页面均需给出内存中的内容（内存中的页面号），若有淘汰还需给出淘汰的页面号。
算法大致流程：
实验代码:
#include <string>
#define maxPage 100
using namespace std;
int phyBlockNum;
int show(int * block,int ispageL) {
string str[2]= {" 否"," 是"};
for(int i=0; i<phyBlockNum; i++) {
if(block[i]==-1) cout<<" \t";
else cout<<block[i]<<"\t";
}
cout<<str[ispageL]<<endl;
}
bool inblock(int *block,int page) {
for(int i=0; i<phyBlockNum; i++) {
if(page==block[i]) return 1;
}
return 0;
}
void FIFO(int* block,int* page) {
for(int i=0; i<phyBlockNum; i++) block[i]=-1;
int i,j=0,temp;
cout<<"页号\t";
cout<<"是否缺页\n";
for(i=0; page[i]!=-1; i++) {
temp=page[i];
cout<<temp<<"\t";
if(!inblock(block,temp)) {
block[(j++)% phyBlockNum]=temp;
temp=1;
} else temp=0;
show(block,temp);
}
cout<<"FIFO算法的缺页率为"<<(double)j/(double)i<<endl;
}
void OPT(int* block,int* page) {
for(int i=0; i<phyBlockNum; i++) block[i]=-1;
int i,pageL=0,temp,max,* ntime;
ntime=new int(phyBlockNum);
for(i=0; i<phyBlockNum; i++) ntime[i]=-1;
cout<<"页号\t";
for(i=0; i<phyBlockNum; i++) cout<<"页块"<<i<<"\t";
cout<<"是否缺页\n";
for(i=0; block[phyBlockNum-1]==-1; i++) {
temp=page[i];
cout<<temp<<"\t";
if(!inblock(block,temp)) {
block[pageL++]=temp;
temp=1;
} else temp=0;
show(block,temp);
}
for(; page[i]!=-1; i++) {
temp=page[i];
cout<<temp<<"\t";
max=0;
for(int k=0; k<phyBlockNum; k++) {
for(int m=i; page[m]!=-1; m++) {
if(page[m]==block[k]) {
ntime[k]=m;
break;
} else if(page[m+1]==-1) ntime[k]=m+1;
}
}
for(int j=1; j<phyBlockNum; j++) max=ntime[max]<ntime[j]?j:max;
if(!inblock(block,temp)) {
block[max]=temp;
pageL++;
temp=1;
} else temp=0;
show(block,temp);
}
cout<<"OPT算法的缺页率为"<<(double)pageL/(double)i<<endl;
}
void LRU(int* block,int* page) {
for(int i=0; i<phyBlockNum; i++) block[i]=-1;
int i,pageL=0,temp,min,* ntime;
ntime=new int(phyBlockNum);
for(i=0; i<phyBlockNum; i++) ntime[i]=-1;
cout<<"页号\t";
for(i=0; i<phyBlockNum; i++) cout<<"页块"<<i<<"\t";
cout<<"是否缺页\n";
for(i=0; block[phyBlockNum-1]==-1; i++) {
temp=page[i];
cout<<temp<<"\t";
if(!inblock(block,temp)) {
block[pageL++]=temp;
temp=1;
} else temp=0;
show(block,temp);
}
for(; page[i]!=-1; i++) {
temp=page[i];
min=0;
for(int k=0; k<phyBlockNum; k++) {
for(int m=i; m>=0; m--) {
if(page[m]==block[k]) {
ntime[k]=m;
break;
} else if(m==0) ntime[k]=-1;
}
}
for(int j=1; j<phyBlockNum; j++) min=ntime[min]>ntime[j]?j:min;
cout<<temp<<"\t";
if(!inblock(block,temp)) {
block[min]=temp;
pageL++;
temp=1;
} else temp=0;
show(block,temp);
}
cout<<"LRU算法的缺页率为"<<(double)pageL/(double)i<<endl;
}
int main() {
int * Block;
int pageQue[maxPage];
cout<<"输入分配给改作业的物理块数:";
cin>>phyBlockNum;
Block=new int(phyBlockNum);
cout<<"输入一组页面访问顺序,输入-1结束:";
for(int i=0; i<maxPage; i++) {
cin>>pageQue[i];
if(pageQue[i]==-1) break;
}
cout<<"\n-----------------OPT算法-----------------\n";
OPT(Block,pageQue);
cout<<"\n-----------------FIFO算法----------------\n";
FIFO(Block,pageQue);
cout<<"\n-----------------LRU算法-----------------\n";
LRU(Block,pageQue);
return 0;
}
运行结果:
输入分配给改作业的物理块数:4
输入一组页面访问顺序,输入-1结束:1 2 5 7 5 7 1 4 3 5 6 4 3 2 1 5 2 -1
-----------------OPT算法-----------------
页号 页块0 页块1 页块2 页块3 是否缺页
1 1 是
2 1 2 是
5 1 2 5 是
7 1 2 5 7 是
5 1 2 5 7 否
7 1 2 5 7 否
1 1 2 5 7 否
4 1 2 5 4 是
3 3 2 5 4 是
5 3 2 5 4 否
6 3 2 6 4 是
4 3 2 6 4 否
3 3 2 6 4 否
2 3 2 6 4 否
1 1 2 6 4 是
5 5 2 6 4 是
2 5 2 6 4 否
OPT算法的缺页率为0.529412
-----------------FIFO算法----------------
页号 页块0 页块1 页块2 页块3 是否缺页
1 1 是
2 1 2 是
5 1 2 5 是
7 1 2 5 7 是
5 1 2 5 7 否
7 1 2 5 7 否
1 1 2 5 7 否
4 4 2 5 7 是
3 4 3 5 7 是
5 4 3 5 7 否
6 4 3 6 7 是
4 4 3 6 7 否
3 4 3 6 7 否
2 4 3 6 2 是
1 1 3 6 2 是
5 1 5 6 2 是
2 1 5 6 2 否
FIFO算法的缺页率为0.588235
-----------------LRU算法-----------------
页号 页块0 页块1 页块2 页块3 是否缺页
1 1 是
2 1 2 是
5 1 2 5 是
7 1 2 5 7 是
5 1 2 5 7 否
7 1 2 5 7 否
1 1 2 5 7 否
4 1 4 5 7 是
3 1 4 3 7 是
5 1 4 3 5 是
6 6 4 3 5 是
4 6 4 3 5 否
3 6 4 3 5 否
2 6 4 3 2 是
1 1 4 3 2 是
5 1 5 3 2 是
2 1 5 3 2 否
LRU算法的缺页率为0.647059
