实验三-存储管理.doc

实验三 存储管理（2）
1．目的和要求
存储管理的主要功能之一是合理地分配空间。请求页式管理是一种常用的虚拟存储管理技术。
本实验的目的是通过请求页式存储管理中页面置换算法模拟设计，了解虚拟存储技术的特点，掌握请求页式管理的页面置换算法。
2．实验内容
1．过随机数产生一个指令序列，共320条指令。其地址按下述原则生成：
①50%的指令是顺序执行的；
②25%的指令是均匀分布在前地址部分；
③25%的指令是均匀分布在后地址部分；
#具体的实施方法是：
A. 在[0，319]的指令地址之间随机选区一起点M;
B. 顺序执行一条指令，即执行地址为M+1的指令；
C. 在前地址[0，M+1]中随机选取一条指令并执行，该指令的地址为M’;
D. 顺序执行一条指令，其地址为M’+1；
E. 在后地址[M’+2，319]中随机选取一条指令并执行；
F. 重复A—E，直到执行320次指令。
2．指令序列变换成页地址流
设：（1）页面大小为1K；
（2） 用户内存容量为4页到32页；
（3） 用户虚存容量为32K。
在用户虚存中，按每K存放10条指令排列虚存地址，即320条指令在虚存中的存放方式为：
第0条—第9条指令为第0页（对应虚存地址为[0，9]）；
第10条—第19条指令为第1页（对应虚存地址为[10，19]）；
。。。。。。。。。。。。。。。。。。。。。
第310条—第319条指令为第31页（对应虚存地址为[310，319]）；
按以上方式，用户指令可组成32页。
3. 计算并输出下述各种算法在不同内存容量下的命中率。
A. FIFO先进先出的算法
B. LRR最近最少使用算法
C. OPT最佳淘汰算法（先淘汰最不常用的页地址）
D. LFR最少访问页面算法
E. NUR最近最不经常使用算法
3．实验提示
提示：A.命中率=1-页面失效次数/页地址流长度
B.本实验中，页地址流长度为320，页面失效次数为每次访问相应指令时，该指令所对应的页不在内存的次数。
C.关于随机数产生方法，采用TC系统提供函数RAND()和RANDOMIZE()来产生。
4．实验运行结果
试验输出如下（输出包括了用户内存从3K到32K的各种不同情况）
PAGE FIFO LRR OPT LFR NUR

试验结论
从实验数据来看，OPT算法为最好的一种算法。参考程序见下：
#include<stdio.h>
#include<iostream.h>
#include <stdlib.h>
#include<time.h>
struct aa{
int page;
int count;
aa* next;
};
void main()
{
time_t t;
srand(unsigned(time(&t)));
int i,n,j,ii,m,answer,ffalse,count,fangfa,temp1,min,nn,mm;
double sum;
aa *head,*tail,*temp,*table,*first,*ti;
/* nn=4;mm=1;
for(nn=4;nn>32;nn++)
{
for(mm=1;mm>5;mm++)
{*/
cin>>m;
//m=nn;
cout<<endl;
cout<<"fangfa: 1-FIFO;2-LRR;3-OPT;4-LFR;5-NUR"<<endl;
cout<<"Mothed:";
cin>>fangfa;
//fangfa=mm;
ffalse=0;
answer=0;
table=new(aa);
temp=table;
table->page=-1;
table->count=0;
head=table;
for(ii=2;ii<=m;ii++)
{
table=new(aa);
table->page=-1;
table->count=0;
temp->next=table;
temp=table;
if (ii==m){table->next=NULL;}
}
tail=table;
temp=head;
first=head;
count=0;
i=0;
while(i<320)
{
min=400;
if (count==0) {n=(rand()%320+1)%320; j=n/10;}
if (count==1) {n=rand()%(n+1);j=n/10;}
if(count==2) {j=((n+1)%320)/10;}
if(count==3) {j=((rand()%(320-n-2))+n+2)/10;}

table=head;
temp=head;
answer=0;
min=400;
if (fangfa==5)
{
while(table!=NULL)
{
if (table->page==j){answer=1;table->count=2;}
table=table->next;
}
if (answer!=1)
{
table=head;
while (table!=NULL)
{
if (table->count<min){temp=table;min=table->count;}
table=table->next;
}
if (temp->page!=-1) ++ffalse;
temp->page=j;
temp->count=1;
}
table=head;
if ((i%32)==0)
{
while(table!=NULL)
{
if (table->page!=-1) table->count=1;
// if (table->page==j){answer=1;++(table->count);}
table=table->next;
}
}
}
if ((fangfa==4)||(fangfa==3))
{
while(table!=NULL)
{
if (table->page==j){answer=1;++(table->count);}
table=table->next;
}
if(answer!=1)
{ table=head;
while (table!=NULL)
{
if (table->count<min){temp=table;min=table->count;}
table=table->next;
}
if (temp->page!=-1){
++ffalse;
temp->page=j;
table=head;
while(table){
table->count=1;
table=table->next;
}
}
else{
temp->page=j;
++(temp->count);
}
}
}
if (fangfa==2){
while((table!=NULL)&&(fangfa==2))
{
if (table->page==j){answer=1;temp=table;}
table=table->next;
}
if((fangfa==2)&&(answer==1))
{
//table=temp;
temp1=temp->page;
while (temp!=NULL)
{
temp->page=temp->next->page;
temp=temp->next;
}
tail->page=temp1;
}
if((answer!=1)&&(fangfa==2))
{
if (first->page!=-1)
ffalse=ffalse+1;
first->page=j;
temp=head;
while (temp!=NULL)
{
temp->page=temp->next->page;
temp=temp->next;
}
tail->page=j;
}
}
table=head;
while((table!=NULL)&&(fangfa==1))
{
if (table->page==j){answer=1;}
table=table->next;
}
if ((answer!=1)&&(fangfa==1))
{
if (first->page!=-1) ffalse=ffalse+1;
first->page=j;
if (first->next!=NULL) { first=first->next;}
else {first=head;}
}
++i;
++count;
if (count==4){count=0;}
}
sum=1.0-ffalse/320.0;
/*cout<<nn<<" ";
if (fangfa==1) cout<<"FIFO:"<<sum<<" ";
if (fangfa==2) cout<<" LRR:"<<sum<<" ";
if (fangfa==3) cout<<" OPT:"<<sum<<" ";
if (fangfa==4) cout<<" LFR:"<<sum<<" ";
if (fangfa==5) cout<<" NUR:"<<sum<<" ";
if(mm==5) cout<<endl;*/
cout<<sum<<endl;
for(ti=head;ti!=NULL;ti=ti->next)cout<<ti->page<<" ";
cout<<endl;
}