院系：计算机学院
实验课程：操作系统
实验项目：模拟操作系统的页面置换
指导老师：陈红英老师
开课时间：2011 ～ 2012年度第 2学期
专业：网络工程
班级：10级
学生：yuth
学号：*
华南师范大学教务处
一、综合设计实验题目
模拟操作系统的页面置换
1、采用一种熟悉的语言，如C、PASCAL 或C++ 等，编制程序，最好关键代码采用C/C++ ，界面设计可采用其它自己喜欢的语言。
2、模拟操作系统采用OPT、FIFO 和LRU算法进行页面置换的过程。
3、设程序中地址范围为0 到32767 ，采用随机数生成256 个指令地址，满足50%的地址是顺序执行，25%向前跳，25% 向后跳。
为满足上述条件，可采取下列方法：
设d0=10000，第n个指令地址为d n，第n+1 个指令地址为d n+1，n的取值范围为0 到255。每次生成一个 1 到1024范围内的随机数a，如果a落在1 到512 范围内，则d n+1=d n+1。如果a落在513 到768范围内，则设置d n+1为1 到d n 范围内一个随机数。如果a落在769 到1024范围内，则设置d n+1为d n到32767
范围内一个随机数。
例如：srand(); 初始化一个随机函数。
a[0] ＝10*rand()/32767*255+1;
a[1]=10*rand()/32767*a[0]…语句可用来产生a[0]与a[1]中的随机数。
或采用以下方式：
（1）通过随机数产生一个指令序列，共320条指令。指令的地址按下述原则生成：
A：50%的指令是顺序执行的
B：25%的指令是均匀分布在前地址部分
C：25%的指令是均匀分布在后地址部分
具体的实施方法是：
A：在[0，319]的指令地址之间随机选取一起点m
B：顺序执行一条指令，即执行地址为m+1的指令
C：在前地址[0,m+1]中随机选取一条指令并执行，该指令的地址为m'
D：顺序执行一条指令，其地址为m'+1
E：在后地址[m'+2，3 19]中随机选取一条指令并执行
F：重复步骤A-E，直到320次指令
（2）将指令序列变换为页地址流
设：页面大小为1K；
用户内存容量4页到32页；
用户虚存容量为32K。
在用户虚存中，按每K存放10条指令排列虚存地址，即320条指令在虚存中的存放方式为：
第0 条-第9 条指令为第0页（对应虚存地址为[0，9]）
第10条-第19条指令为第1页（对应虚存地址为[10，19]）
……
第310条-第319条指令为第31页（对应虚存地址为[310，319]）
按以上方式，用户指令可组成32页。
4、页面大小的取值范围为1K，2K，4K，8K，16K 。按照页面大小将指令地址转化为页号。对于相邻相同的页号，合并为一个。
5、分配给程序的内存块数取值范围为1 块，2 块，直到程序的页面数。
6、分别采用OPT、FIFO 和LRU算法对页号序列进行调度，计算出对应的缺页中断率。
7、打印出页面大小、分配给程序的内存块数、算法名、对应的缺页中断率。
8、分析页面大小和分配给程序的内存块数对缺页中断率的影响。分析不同
的页面置换算法的调度性能。
二、中文摘要
这次实验是模拟操作系统的页面置换，分别用先进先出算FIFO、最近最久未使用算法LRU和最佳淘汰算法OPT等三种置换算法来管理管理内存块，并打印出页面大小、分配给程序的内存块数、算法名、对应的缺页中断率。最后对不同算法的调度性能。
三、关键词
页面置换 FIFO LRU OPT
四、前言
本实验的目的及要求
1、掌握操作系统的页面置换过程，加深理解页式虚拟存储器的实现原理。
2、掌握用随机数生成满足一定条件的指令地址流的方法。
3、掌握页面置换的模拟方法。
五、实验设计
（一）、需求分析
1、用一种熟悉的语言，如C、PASCAL或C++等，编制程序。
2、分别采用OPT、FIFO和LRU算法对页号序列进行调度。
（二）、设计流程
1、根据实验目标，明确实验的具体任务；
2、编写程序实现页面置换；
3、运行程序，调试；
4、记录并分析实验结果。
（二）、关键技术
根据实验要求，使得50%的指令地址是顺序执行，25%向前跳，25% 向后跳。可采取下列方法：设d0=10000，第n个指令地址为d n，第n+1 个指令地址为d n+1，n的取值范围为0 到255。每次生成一个1 到1024范围内的随机数a，如果a落在1 到512 范围内，则d n+1=d n+1。如果a落在513 到768范围内，则设置d n+1为1 到d n范围内一个随机数。如果a落在769 到1024范围内，则设置d n+1为d n到32767 范围内一个随机数。开一个数组address[]来记录指令地址，另一个数组pagenum[]记录指令地址转换后所在的页，这样就得到原始程序的页面访问序列。然后将相邻相同的页号合并。
（三）详细设计
1、设计算法流程图
2、数据结构
//程序类，指明程序地址范围和指令数
class Program
{
public:
int AddressSize; //（0~AddressSize ）
int StructureNum; //指令数
public:
Program(int m,int i)
{
AddressSize=m;
StructureNum=i;
}
};
//内存块节点类
class PhysicsPageNode
{
public:
int have; //是否有页面占领该内存块，-1代表没有，1代表有
int Page_Num; //第几页占领该内存块
int Elapsed_Time; //内存块的存在时间
PhysicsPageNode *next;
public:
PhysicsPageNode()
{
have=-1;
Elapsed_Time=0; //刚生成时内存块的存在时间为0
next = NULL;
}
};
//模拟操作系统的页面置换类
class PageReplacement
{
private:
int *address; //存储所有指令的地址
int *pagenum; //存储所有指令地址所在的页
float instr_sum; //指令数
public:
int pagesize; //页面大小(字节)
int mem_sum; //程序获得的内存块数
public:
void transform(Program p); //分析程序p，得到指令页面序列,初始化有关成员
PhysicsPageNode* getphysage(PhysicsPageNode* pp,int pn); //检查指定页是否已在内存块中
PhysicsPageNode* getfreepage(PhysicsPageNode* pp); //检查是否有空的内存块
PhysicsPageNode* getlongelapsed(PhysicsPageNode* pp); //获得最长时间没访问的内存块
void FIFO(); //先进先出算法
void LRU(); //最近最久未使用算法
void OPT(); //最佳淘汰算法
};
六、实验实现
（一）、实验主要硬件软件环境
32位PC机，VC++6.0
（二）、主要功能模块分析
1、获得页号序列模块
分析程序指令，获得页面序列。Dn为地址，D0=10000；Dn的地址获取方法：循环随机一个数a[1,1024];落在1-512，Dn=D（n-1）+1，513-768，Dn 为1~D（n-1）的随机数。如果a落在769-1024，Dn为D（n-1）~到所分析程序地址大小（32767）。然后根据页面大小，将各指令地址化为页面号。最后将相邻相同的页号合并。/*
分析程序，
功能：得到指令页面序列。
入口参数：一个程序类，指明程序地址范围和指令数。
*/
void PageReplacement::transform(Program p)
{
Sleep(10);
srand(time(0));
int a,q,r;
//初始化
instr_sum=p.StructureNum;
address = new int [instr_sum]; //存储所有指令的地址
pagenum = new int [instr_sum];
cout<<"原程序页面链:"< address[0]=10000; //指令起始地址 pagenum[0]=address[0]/pagesize; //指令地址所在的页 cout< for(int i=1;i { a = 1 + rand()%1024; if(a<=512) //顺序执行 address[i]=address[i-1]+1; else if(a<=768) //向前跳 address[i]=1 + rand()%(address[i-1]); else if(a<=1024) //向后跳 address[i] = address[i-1] + rand()%(p.AddressSize-address[i-1]); //求得指令所在的页 q=address[i]/pagesize; r=address[i]%pagesize; if(r) pagenum[i]=q; else pagenum[i]=q-1; cout< } cout< //将相邻相同的页号合并 int *newpagenum = new int [instr_sum]; newpagenum[0]=pagenum[0]; cout<<"将相邻相同的页号合并为一个后的页面链"< int j=0; for(i=1;i { if(newpagenum[j] != pagenum[i]) { j++; newpagenum[j]=pagenum[i]; } } instr_sum = j+1; //新的页面访问串的访问数(j为下标，所以加一) cout<<"新的页面访问串的访问数="< for(i=0;i { pagenum[i] = newpagenum[i]; cout< } cout< } 2、FIFO模块 先进先出算法： 设置缺页中断次数breaktimes，当中断发生时，+1. 获取可用内存块数，根据内存块数，申请对应长度的内存块链。然后进行调度。内存块内有一项Elapsed_Time作为存在时间，每调用一次，所有内存块得存在时间++。刚被调入时间为1.当要淘汰时，比较在内存块中的各存在时间，把存在时间最大的换掉。//内存页的存在时间，为存在时间。 void PageReplacement::FIFO() { float breaktimes=0; int i,pn; //生成内存页空间 PhysicsPageNode *head = new PhysicsPageNode(); PhysicsPageNode *p=head,*ppn=NULL; for(i=1;i { PhysicsPageNode *np=new PhysicsPageNode(); p->next=np; p=np; } for(i=0;i { pn=pagenum[i]; //需要载入的页号(这里还没简化) ppn=getphysage(head,pn); // 是否存在内存页 if(ppn==NULL) // 载入的页不在内存页中 { //缺页中断次数+1 breaktimes++; //获取空闲页面 ppn=getfreepage(head); if(ppn!=NULL) //获取成功 { ppn->Page_Num=pn; ppn->Elapsed_Time=1; } else //获取空闲页失败.置换存在时间最大的页面 { ppn=getlongelapsed(head); ppn->Page_Num=pn; ppn->Elapsed_Time=1; } } else //载入的页在内存页中。 { //什么也不发生 } //将在内存中的页存在时间+1 PhysicsPageNode *copp=head; while(copp!=NULL) { copp->Elapsed_Time++; } } //输出算法，页面大小，缺页中断率等。 cout<<"页面大小="<