淮海工学院计算机工程学院
实验报告书
课程名：《 操作系统原理》
题 目： 虚拟存储器 班 级： 学 号： 姓 名：
评语： 成绩： 指导教师： 批阅时间： 年 月 日 《操作系统原理 》实验报告 - 1 -
一、目的与要求 （一）目的
由于超大规模集成电器电路（ＶＬＳＩ）技术的发展，使存贮器的容量不断扩大，价格大幅度下降。但从应用角度看，存贮器的容量和成本总会受到一定的限制。所以，提高存贮器的使用效率始终是操作系统研究的重要课题之一，虚拟存贮器技术是用来扩大主存容量的一种重要的方法。
本实习要求学生独立地用高级语言编写几个常用的存贮器分配算法，并能设计一个存贮管理的模拟程序，能对各种算法进行分析比较，评测其性能优劣，从而加深对这些算法的了解。 （二）要求
为了比较真实地模拟存贮器管理，可预先生成一个大致符合实际情况的指令地址流。然后，通过模拟这样一种指令序列的执行来计算和分析比较各种算法的访问命中率。
二、示例 １．题目
本示例给出采用页式分配存贮器管理方案，并通过分析、计算不同页面淘汰算法情况下的访问命中率来比较各种算法的优劣，另外也考虑改变页面尺寸大小和实际存贮器容量对计算结果的影响，从而可为选择好的算法、合适的页面尺寸和存贮器实际容量提供依据。
本程序是按下述原则生成指令序列的： （１）５０％的指令是顺序执行的。
（２）２５％的指令是均匀分布在前地址部分。 （３）２５％的指令是均匀分布在后地址部分。
示例中选用最佳淘汰算法（OPT）和最近最少使用页面淘汰算法（ＬＲＵ）计算页面命中率。公式为：
页面失败次数 命中率＝１－ ─────── 页地址流长度
假定虚拟存贮容量为３２Ｋ，页面尺寸从１Ｋ到８Ｋ，实存容量从４页到３２页。 ２.算法与框图
（１）最佳淘汰算法（ＯＰＴ）。这是一种理想的算法，可用来作为衡量其他算法优劣的依据，在实际系统中是难以实现的，因为它必须先知道指令的全部地址流。由于本示例中已生成了全部地址流，故可计算最佳命中率。
该算法的准则是淘汰已满页表中以后不再访问或是最迟访问的页。这就要求将页表中的页逐个与后继指令访问的所有页比较，如后继指令不再访问此页，则把此页淘汰，不然得找出后继指令中最迟访问的页面予以淘汰。可见最佳淘汰算法要化费较长的运算时间。
（２）最近最少使用页面淘汰算法（ＬＲＵ）。这是一种经常使用的方法，有各种不同的实施方案，这里是采用的是不断调整页表链的方法，即总是淘汰页表链链首的页，而把新访问的页插入链尾。如果当前调用页已在页表内，则把它再次调整到链尾。这样就能保证最近使
用的页，总是处于靠近链尾部分，而不常使用的页就移到链首，逐个被淘汰，在页表较大时，调整页表链的代价也是不小的。
《操作系统原理 》实验报告 - 2 -
三、实验步骤与源程序 #include \#include \#include %using namespace std;
#define Max 30 //某进程调入内存中的最大页面数 #define Size 10 //系统为某进程分配的最大物理块数 void Init(int Block[],int m)//初始化物理块 { int i;
for(i=0;i Block[i]=-1; } } void creat(int Page[],int n)//输入页面串引用号 { int i; for(i=0;i cin>>Page[i]; } } void Init1(int Block1[],int m1) { int i; for(i=0;i Block1[i]=-1; } } void creat1(int Page[],int n1) { int i; for(i=0;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 time[i]=0; } for(i=0;i { for(j=0;j get=j; //物理块j即将(/等待)驻入新页面 break; } } for(j=0;j if(Block1[j]==Page[i])//物理块j中页面与当前期望调入内存的页面相同 { time[j]=0; flag=j; break; 《操作系统原理 》实验报告 - 3 - } } for(j=0;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 time[j]++; } block_num=-1; max_stay=0; count++; } } else //待调入页面与序号flag的物理块中页面相同 { for(j=0;j time[j]++; } flag=-1; } for(j=0;j cout<<\ } cout< if(n1>m1) count=count+m1; cout<<\缺页中断次数为:\} 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 《操作系统原理 》实验报告 - 4 - for(i=0;i get=j; break; } } for(j=0;j { if(Block[j]==Page[i]) { flag=j; break; } } for(j=0;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; } else { Block[block_num]=Page[i]; time[block_num]=0; for(j=0;j time[j]++; } block_num=-1; max_stay=0; count++; } } else { for(j=0;j time[j]++; } flag=-1; } for(j=0;j cout<<\ } cout<