一、实验目的及内容
1、实验目的：
存储管理的主要功能之一是合理分配存储空间，请求页式存储管理是常用的虚拟存储技术。本实验的目的是通过请求页式管理中页面置换算法了解虚拟存储技术的特点，掌握请求页式存储管理的页面置换算法。
2、实验内容：
共320条1通过随机数产生一个指令序列，共320条指令，指令的地址按下述原则生成：
（1） 50%的指令是顺序执行的；
（2） 25%的指令是均匀分布在前地址部分；
（3） 25%的指令是均匀分布在后地址部分
二、实验原理及基本技术路线图（方框原理图或程序流程图 ）
（见下页）
申请分配一个X大小的空间
置空闲区KX表的开始地址
表目查完？
KX[I]。STATE=空表目？
L=KX[i].addr
KX[I].SIZE>=Xi
KX[i].addr=L+X
KX[I].SIZE>=KX[I].size-Xi
被分配后的剩余空闲块
在已分配的分区FP表中找一个状态为空
表目序号F
在已分配的分区FP填入分配的信息置F的
大小=Xi F的始址=L F的状态=已分配
返回
本次无法分配
I=I+1
KX[I]。STATE=空表目？
三、所用仪器、材料（设备名称、型号、规格等或使用软件）
Microsoft Visual Studio 6.0
四、实验方法、步骤（或：程序代码或操作过程）
1、具体实施办法为：
（1） 在[0，319]之间选一个起点m；
（2） 顺序执行一条指令，即m+1条；
（3） 向前地址[0，m-1]中执行一条指令m`；
（4） 顺序执行一条指令，即m`+1条；
（5） 向后地址[m`+2，319]中执行一条指令m`
2、将指令序列变换为页地址流。
（1） 页面大小为1KB；
（2） 用户实存容量为4页到32页；
（3） 用户虚拟存储容量为32KB。
用户虚拟存储容量为32KB，每1KB中放10条指令，共320条指令（0~319）。其中0~9为0页，10~19为1页。。。。。。310~319为31页。
3、使用不同的页面调度算法处理缺页中断，并计算不同实存容量下（4K~32K）的命中率。
（1） 使用先出算法（FIFO）；
（2） 最近最少使用算法（LRU）；
（3） 最佳淘汰算法（OPT）；先淘汰最不常用的页地址；
（4） 最少访问页面地址（LFU）；
命中率算法为：
缺页中断次数
命中率=1-------------------------
页地址长度-
.
.
.4、 程序代码如下：
class freetable//空闲区说明表
{ public:
int length;//从起始地址开始的一个连续空闲区的长度
int startaddress;//空闲区的主存起始地址
int statue;}//为时是未分配状态,为0时是空表目状态
freetable t[max];
void adjust()//用冒泡法排列,并将状态为未分配的栏放在前部分
{ int i=0;
int j ;
int temp;
for(;i
{if(t[i].statue==0)
{ j=1;
for(;(j if(j==max) break;
t[i].startaddress=t[j].startaddress;
t[i].length=t[j].lenth;
t[i].statue=t[j].statue;
t[j].statue=0;
}
}
for(i=0;t[i].state==1;i++)//用冒泡法排序
i--;
for(;i>0;i--)
for(j=0;j<=i-1;j++)
{ if(t[j].startaddress>t[j+1].startaddress)
{temp=t[j+1].startaddress;
t[j+1].startaddress>t[j].startaddress;
t[j].startaddress=temp;
temp=t[j+1].lenth;
t[j+1].startaddress>t[j].lenth;
t[j].lenth=temp;
void printtable() //输出空闲表
{ int j;
for(i=0;t[i].statue==1;i++)
{cout<<"t["< cout<<"t["< cout<<"t["< }
}
int FF(int x)//最先适应算法分配主存空间
{int address;
int j=0;
for(;j {if(t[j].statue==1)//未分配状态时
{if(t[j].length==x)//刚好有与作业一样大小的空闲区
{t[j].statue==0;//把状态置为空表目
adjust();
cout<<"作业分配后的空闲区说明表:"< printtable();
ruturn(t[j].startaddress);}//返回作业在内存的首地址
if (t[j].length>x)//当空闲区的大小比作业的大
{address=t[j].startaddress;//先保存作业在内存的首地址
t[j].lenth=t[j].lenth-x;//把空闲区分为两块
t[j].startaddress=t[j].startaddress+x;
adjust();
cout<<"作业分配后的空闲区说明表:"< printtable();
return(address);}
else //当前空闲区不够大时
if(j==max) {cout<<"作业不能装入"<else if(j==max) {cout<<"作业不能装入"<void circle(int l,int s)
{int c,i;
for(c=0;(t[c].statue==1)&&(c{if((t[c-1].startaddress==s+1)&&(t[c].starataddress+t[c].length==s)&&(c+1{t[c+1].statue=0; //把下临的空闲表状态置0
t[c].length=t[c].length+t[c+1].length+1; //把上临的空闲区的长度置为3者之和
break;}
if((t[c].startaddress==s+1//下临
{ t[c].startaddress=s;
t[c].length=1-t[c].length;
break;}
if((t[c].startaddress+t[c].length==s))//上临
{t[c+1].statue=0;
t[c].length=t[c].length+1;
break;}}
if(t[c].statue==0)//上下都不临
for(i=0;i<=mac;i--) //填入空表目中
if(t[i].statue==0)
{t[j].startaddress=s;
t[j].length=1;
t[i].statue=1;
break;}
adjust();//顺序调整和紧缩空闲区表
printtable();}//最先适应算法回收
void main()
{int i;
int x;
int ad[5];
for(i=0;it[i].statue=0;
ad[0]=5;
ad[1]=26;
ad[2]=0;
t[0].startaddress=14;//初始化
t[0].length=12;
t[0].statue=1;
t[1].startaddress=32;
t[1].length=96;
t[1].statue=1;
cout<<”原始表格为”<printable();
cout<<”作业长度为”<cin>>x;
ad[3]=FF(x);//调用分配函数
cout<<”作业3的归还量:4k”<circle(4,ad[2]);//调用回收函数,回收作业3
cout<<”作业2的归还量:6k”<circle(6,ad[1]);//调用回收函数,回收作业2
五、实验过程原始记录（测试数据、图表、计算等）
.
关于随机数的产生办法.首先要初始化设置随机数,产生序列的开始点,例如:通过下列语句实现:
Srand (400)
1 计算机数,产生320条指令序列
m=160;
for(i=0;i<80;i++)
{j=j*4;
a[j]=m;
a[j+1]=m+1;
a[j+2]=a[j]*1.0*rand()\32767;
a[j+3]=a[j+2]+1;
m=a[j+3]+(319-a[j+3])*1.0*rand()\32767;
}
2 将指令序列变换成页地址流:
for(k=0;k<320;k++)
{Pt=a[k]/10;
....
}
3 计算不同算法的命中率
Rate=1-1.0 *U/320;
其中U为缺页数,320是地址流的长度.
4 输出格式
K fifo lru
4 0.23 0.25
... ... ...
32 1.0 1.0
六、实验结果、分析和结论（误差分析与数据处理、成果总结等。其中，绘制曲线图时必须用计算纸或程序运行结果、改进、收获） 通过本次上机实践，使我了解了有关于存储管理的一些知识。存储管理必须为用户分配一个物理上的主存空间，为了避免主存中的各程序相互干扰还必须实现储存保护，为了有效的利用主存空间允许多个作业共享程序和数据，各储存管理方式实现这些功能的方法是不同的，并且都要有相应的硬件作支撑。
