淮海工学院计算机工程学院实验报告书评语:成绩：_________________ 指导教师：___________________________批阅时间:一、目的与要求(一)目的由于超大规模集成电器电路(VLSI)技术的发展，使存贮器的容量不断扩大，价格大幅度下降。
但从应用角度看，存贮器的容量和成本总会受到一定的限制。
所以，提高存贮器的使用效率始终是操作系统研究的重要课题之一，虚拟存贮器技术是用来扩大主存容量的一种重要的方法。
本实习要求学生独立地用高级语言编写几个常用的存贮器分配算法，并能设计一个存贮管理的模拟程序，能对各种算法进行分析比较，评测其性能优劣，从而加深对这些算法的了解。
(二)要求为了比较真实地模拟存贮器管理，可预先生成一个大致符合实际情况的指令地址流。
然后，通过模拟这样一种指令序列的执行来计算和分析比较各种算法的访问命中率。
二、示例1 •题目本示例给出采用页式分配存贮器管理方案，并通过分析、计算不同页面淘汰算法情况下的访问命中率来比较各种算法的优劣，另外也考虑改变页面尺寸大小和实际存贮器容量对计算结果的影响，从而可为选择好的算法、合适的页面尺寸和存贮器实际容量提供依据。
本程序是按下述原则生成指令序列的：(1)50%的指令是顺序执行的。
(2)25%的指令是均匀分布在前地址部分。
(3)25%的指令是均匀分布在后地址部分。
示例中选用最佳淘汰算法（OPT）和最近最少使用页面淘汰算法（LRU）计算页面命中率。
公式为：页面失败次数命中率=]_ ------------------页地址流长度假定虚拟存贮容量为3 2K，页面尺寸从1K到8K,实存容量从4页到32页。
2 .算法与框图（1）最佳淘汰算法（OPT）。
这是一种理想的算法，可用来作为衡量其他算法优劣的依据，在实际系统中是难以实现的，因为它必须先知道指令的全部地址流。
由于本示例中已生成了全部地址流，故可计算最佳命中率。
该算法的准则是淘汰已满页表中以后不再访问或是最迟访问的页。
这就要求将页表中的页逐个与后继指令访问的所有页比较，如后继指令不再访问此页，则把此页淘汰，不然得找出后继指令中最迟访问的页面予以淘汰。
可见最佳淘汰算法要化费较长的运算时间。
（2）最近最少使用页面淘汰算法（LRU）。
这是一种经常使用的方法，有各种不同的实施方案，这里是采用的是不断调整页表链的方法，即总是淘汰页表链链首的页，而把新访问的页插入链尾。
如果当前调用页已在页表内，则把它再次调整到链尾。
这样就能保证最近使用的页，总是处于靠近链尾部分，而不常使用的页就移到链首，逐个被淘汰，在页表较大时，调整页表链的代价也是不小的。
三、实验步骤与源程序#i nclude "iostream"#in elude "stdio.h"#in elude "stdlib.h"using namespace std;#define Max 30 // 某进程调入内存中的最大页面数#define Size 10 // 系统为某进程分配的最大物理块数void Init(int Block[],int m)// 初始化物理块{ int i; for(i=0;i<m;i++){Block[i]=-1;}void creat(int Page[],int n)// 输入页面串引用号{ int i; for(i=0;i<n;i++){ cin>>Page[i];}}void Init1(int Block1[],int m1){ int i; for(i=0;i<m1;i++){Block1[i]=-1;}}void creat1(int Page[],int n1){ int i;for(i=0;i<n1;i++){Page[i];}}void LRU(int Page[],int Block1[],int n1,int m1){int i,j,max_stay=0,count=0;int get=-1,flag=-1,block_num=-1;int time[Size]; for(i=0;i<m1;i++)// 初始化time[]{time[i]=0;} for(i=0;i<n1;i++){ for(j=0;j<m1;j++)// 有空闲物理块时，页面直接驻入内存空闲块{ if(Block1[j]==-1)get=j; // 物理块j 即将(/等待)驻入新页面break;}查找序号相同的页面} for(j=0;j<m1;j++) //{ if(Block1[j]==Page[i])// 物理块j 中页面与当前期望调入内存的页面相同{ time[j]=0; flag=j; break;}找到驻留内存时间最久的页面置换出} for(j=0;j<m1;j++) //if(time[j]>max_stay) max_stay=time[j];block_num=j; //block_num 标记当前序号物理块中页面驻留时间最久}if(flag==-1) // 不存在相同页面{ if(get!=-1) // 物理块即将(/ 等待)驻入新页面Block1[get]=Page[i]; // 存入页面time[get]=0; // 当前物理块重新计时for(j=0;j<=get;j++) // 已驻入页面的驻留时间加1 {time[j]++;}get=-1;else // 页面调度置换，序号block_num 的物理块是驻留时间最久的Block1[block_num]=Page[i];time[block_num]=0;for(j=0;j<Size;j++){time[j]++;}block_num=-1;max_stay=0;count++;}else // 待调入页面与序号flag 的物理块中页面相同for(j=0;j<m1;j++){time[j]++;}flag=-1;}for(j=0;j<m1;j++)// 输出物理块中的页面驻入情况{cout<<" "<<Block1[j];}cout<<endl;}if(n1>m1)count=count+m1;cout<<" 缺页中断次数为:"<<count<<endl;}void FIFO(int Page[],int Block[],int n,int m){int i,j,max_stay=0,count=0;int get=-1,flag=-1,block_num=-1;int time[Size];for(i=0;i<m;i++){ time[i]=0;}for(i=0;i<n;i++){ for(j=0;j<m;j++){ if(Block[j]==-1)get=j; break;}for(j=0;j<m;j++){ if(Block[j]==Page[i]){flag=j;break;}}for(j=0;j<m;j++){if(time[j]>max_stay){max_stay=time[j]; block_num=j;}}if(flag==-1){ if(get!=-1){Block[get]=Page[i]; time[get]=0; for(j=0;j<=get;j++) { time[j]++;}get=-1;elseBlock[block_num]=Page[i]; time[block_num]=0; for(j=0;j<Size;j++) { time[j]++;}block_num=-1;max_stay=0; count++;}elsefor(j=0;j<m;j++){time[j]++;}flag=-1;}■for(j=0;j<m;j++){cout<<" "<<Block[j];}cout<<endl;}if(n>m)count=count+m;cout<<" 缺页中断次数为:"<<count<<endl;}void menu()cout«"----- 1.LRU 页面置换算法------- "<<e ndl;coutvv" ---- 2.FIFO 页面置换算法——"<<e ndl;coutvv" ---- 3. 退出——"<<e ndl;cout«"----- 默认：-1表示物理块空闲-------- "<<endl;cout«"请选择算法"<<endl;}void main(){ int n,m,Page[Max],Block[Size],n1,m1,Block1[Size];char tcoutvve ndlvv" 请输入系统为进程分配的物理块数m<=10:";cin>>m;m1=m;In it(Block,m);In it1(Block1,m1);coutvv"请输入总页面数nv=30:";cin>>n;n1= n;cout<<"\n 请输入页面号引用串:";creat(Page ,n);creat1(Page, n1);while(1){menu();cin> >t;switch(t){case '1':LRU(Page,Block1, n1,m1);con ti nue;case 2:FIFO(Page,Block, n,m);con ti nue;case 3:exit(0);}}}四、测试数据与实验结果-' F :\Debu g\C p p Le "图1输入要分配的物理块数、页面总数、页面序列号1您.FIFO 页面 9 ■退岀——丄.駅认—表示物理块空闲- 请选择算法3 2 1缺贝中断次数为血图2 LRU 算法的实现r :■' X —①他匸 J = I请选择聲法24 -1 -14 3-14 3 54 3 54 3 52 3 S2 152 1 S2 143 143 2 43 2 1 缺页中断尿数宜学" ~~ I I图3 FIFO 算法的实现五、结果分析与实验体会页面置换算法理解比较容易，这次根据学号要求实现的是LRU 和FIFO 算法的实现。