一、实验目的
存储管理的主要功能之一是合理地分配空间。请求页式管理是一种常用的虚拟存储管理技术。
本实验的目的是通过请求页式管理中页面置换算法模拟设计，了解虚拟存储技术的特点，掌握请求页式存储管理的页面置换算法。
二、实验内容
（1） 通过计算不同算法的命中率比较算法的优劣。同时也考虑了用户内存
容量对命中率的影响。
页面失效次数为每次访问相应指令时，该指令所对应的页不在内存中的次数。
在本实验中，假定页面大小为 1k，用户虚存容量为 32k，用户内存容量为 4 页到 32 页。
（2） produce_addstream 通过随机数产生一个指令序列，共 320 条指令。
A、 指令的地址按下述原则生成：
1） 50%的指令是顺序执行的
2）25%的指令是均匀分布在前地址部分
3） 25%的指令是均匀分布在后地址部分 ?
B、具体的实施方法是：
1） 在[0，319]的指令地址之间随机选取一起点 m；
2） 顺序执行一条指令，即执行地址为 m+1 的指令；
3） 在前地址[0，m+1]中随机选取一条指令并执行，该指令的地 址为 m’；
4） 顺序执行一条指令，地址为 m’+1 的指令
5） 在后地址[m’+2，319]中随机选取一条指令并执行；
6） 重复上述步骤 1）~5），直到执行 320 次指令
C、将指令序列变换称为页地址流
在用户虚存中，按每 k 存放 10 条指令排列虚存地址，即 320 条指令在虚存中的存放方式为：
第 0 条~第 9 条指令为第 0 页（对应虚存地址为[0，9]）；
第 10 条~第 19 条指令为第 1 页（对应虚存地址为[10，19]）；
。。。。。。
第 310 条~第 319 条指令为第 31 页（对应虚存地址为[310，319]）；
按以上方式，用户指令可组成 32 页。
（3）计算并输出下属算法在不同内存容量下的命中率。
1）先进先出的算法（FIFO）；
2）最近最少使用算法（LRU）；
3）最佳淘汰算法（OPT）；
4）最少访问页面算法（LFR）；
其中 3）和 4）为选做内容
- 实验方案
?
?
- 实验代码
#include<iostream>
#include<ctime>
#include<cstdlib>
using namespace std;
#define dx 32 //物理块数
struct element{ //用来排序的数据结构
int data; //数据
int index; //序号
};
int cmp(const void *a,const void *b){ //升序排序
return((struct element*)a)->data - ((struct element*)b)->data;
}
void rand(int a[],int n){
int i;
struct element ele[320];
srand((int)time(0)); //初始化随机数种子
for(i=0;i<n;i++){
ele[i].data=rand(); //随机生成一个数
ele[i].index=i+1;
}
qsort(ele,n,sizeof(ele[0]),cmp); //排序
for(i=0;i<n;i++){
a[i]=ele[i].index;
}
}
class FIFO{ //FIFO类
private:
int page[dx];
int time[dx];
int zhCount; //置换次数
int qyCount; //非置换缺页次数
public:
FIFO(){ //初始化
for(int i=0;i<dx;i++)time[i]=0;
for(int i=0;i<dx;i++)page[i]=-1;
zhCount=0;qyCount=0;
}
void changePage(int m,int n){page[m]=n;time[m]=0;} //将m号物理块内容变为页n,时间归零
int returnPage(int m){return page[m];}
int returnTime(int m){return time[m];}
int zh(){return zhCount;}
int qy(){return qyCount;}
int longestTime(){ //计算时间最长的块
int max=0;
for(int i=0;i<dx;i++){
if(time[i]>time[max])max=i;
}
return max;
}
int empty(){ //判断是否有空
for(int i=0;i<dx;i++){
if(page[i]==-1)return i; //返回值非-1说明有空,空物理块位置为i
}
return -1; //返回-1说明没空
}
bool hit(int m){ //判断是否命中
for(int i=0;i<dx;i++){
if(page[i]==m)return true;
}
return false;
}
void alFIFO(int m){ //FIFO算法
if(hit(m)){
if(empty()==-1)for(int i=0;i<dx;i++)time[i]++; //命中后，所有时间均加一
else for(int i=0;i<empty();i++)time[i]++;
}
else{
if(empty()==-1){ //没空
changePage(longestTime(),m); //修改页面
for(int i=0;i<dx;i++){
time[i]++; //更换页面后,所有时间+1
}
zhCount++; //置换次数+1
}
else{ //有空
int e=empty();
for(int i=0;i<e;i++)time[i]++;
changePage(e,m); //将第一个空物理块内容变为页m
time[e]++;
qyCount++; //缺页次数+1
}
}
}
};
class LRU{ //LRU类
private:
int page[dx];
int zhCount;
int qyCount;
public:
LRU(){for(int i=0;i<dx;i++)page[i]=-1;zhCount=0;qyCount=0;} //初始化
void changePage(int m,int n){page[m]=n;} //将m号物理块内容变为页n
int returnPage(int m){return page[m];}
int zh(){return zhCount;}
int qy(){return qyCount;}
int empty(){ //判断是否有空
for(int i=0;i<dx;i++){
if(page[i]==-1)return i; //返回值非-1说明有空,空物理块位置为i
}
return -1; //返回-1说明没空
}
int hit(int m){ //判断是否命中
for(int i=0;i<dx;i++){
if(page[i]==m)return i; //命中返回物理块i
}
return -1; //未命中返回-1
}
void alLRU(int m){ //LRU算法
if(hit(m)!=-1){ //命中
int h=hit(m);
if(h>0){
for(int i=h;i>0;i--)page[i]=page[i-1]; //1到命中的物理块，全部后移一位
page[0]=m; //m页移到第一位
}
}
else{ //未命中
if(empty()==-1){ //没空
for(int i=dx-1;i>0;i--)page[i]=page[i-1];
page[0]=m;
zhCount++;
}
else{ //有空
for(int i=empty();i>0;i--)page[i]=page[i-1];
page[0]=m;
qyCount++;
}
}
}
};
int main(){
int a[320];
rand(a,320); //生成320的随机随机数列
int b[320];
for(int i=0;i<320;i++){ //生成相应页数列
b[i]=a[i]/10;
if(a[i]==320)b[i]=0;
}
int count=0;
/*cout<<"以下为指令流：\n";
for(int i=0;i<320;i++){ //输出随机数列
cout<<a[i]<<" ";
count++;
if(count%8==0)cout<<endl;
}
cout<<endl<<endl;
count=0;
cout<<"以下为页码流：\n";
for(int i=0;i<320;i++){ //输出相应页数列
cout<<b[i]<<" ";
count++;
if(count%8==0)cout<<endl;
}*/
cout<<"如需要改变物理块个数，请在代码第5行，修改dx的值（确保在1-32之间）\n";
cout<<"请选择页面置换算法（f：FIFO。l：LRU。b：比较）：\n";
char y;
cin>>y;
switch(y){
case'f':{
FIFO x;
for(int i=0;i<320;i++){
x.alFIFO(b[i]);
/*cout<<"页面 时间\n";
int count=0;
for(int j=0;j<dx;j++){
cout<<x.returnPage(j)<<" "<<x.returnTime(j)<<" ";
count++;
if(count%4==0)cout<<endl;
}*/
}
double hitRate=1.0-(double)(x.qy()+x.zh())/320;
cout<<"命中率为："<<hitRate<<endl;
break;
}
case'l':{
LRU x;
for(int i=0;i<320;i++){
x.alLRU(b[i]);
/*cout<<"页面： ";
for(int j=0;j<dx;j++)cout<<x.returnPage(j)<<" ";
cout<<endl;*/
}
double hitRate=1.0-(double)(x.qy()+x.zh())/320;
cout<<"命中率为："<<hitRate<<endl;
break;
}
case'b':{
FIFO x;
for(int i=0;i<320;i++)x.alFIFO(b[i]);
double hitRate1=1.0-(double)(x.qy()+x.zh())/320;
cout<<"FIFO命中率为："<<hitRate1<<endl;
LRU z;
for(int i=0;i<320;i++)z.alLRU(b[i]);
double hitRate2=1.0-(double)(z.qy()+z.zh())/320;
cout<<"LRU命中率为："<<hitRate2<<endl;
}
}
system("pause");
return 0;
}