实验三模拟操作系统的页面置换.doc

院 系：计 算 机 学 院

实验课程： 操作系统
实验项目：模拟操作系统的页面置换
指导老师： 陈红英老师
开课时间：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个指令地址为dn，第 n+1 个指令地址为dn+1 ，n的取值范围为0 到255。每次生成一个 1 到1024范围内的随机数a，如果a落在1 到512 范围内，则dn+1 =dn+1。如果a落在513 到768范围内，则设置dn+1 为1 到dn范围内一个随机数。如果a落在769 到1024范围内，则设置dn+1 为dn到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个指令地址为dn，第 n+1 个指令地址为dn+1 ，n的取值范围为0 到255。每次生成一个 1 到1024范围内的随机数a，如果a落在1 到512 范围内，则dn+1 =dn+1。如果a落在513 到768范围内，则设置dn+1 为1 到dn范围内一个随机数。如果a落在769 到1024范围内，则设置dn+1 为dn到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<<"原程序页面链:"<<endl;
address[0]=10000; //指令起始地址
pagenum[0]=address[0]/pagesize; //指令地址所在的页
cout<<pagenum[0]<<ends;

for(int i=1;i<instr_sum;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<<pagenum[i]<<ends; //输出指令所在的页面
}
cout<<endl<<endl;

//将相邻相同的页号合并
int *newpagenum = new int [instr_sum];

newpagenum[0]=pagenum[0];
cout<<"将相邻相同的页号合并为一个后的页面链"<<endl;

int j=0;
for(i=1;i<instr_sum;i++)
{
if(newpagenum[j] != pagenum[i])
{
j++;
newpagenum[j]=pagenum[i];
}
}

instr_sum = j+1; //新的页面访问串的访问数(j为下标，所以加一)
cout<<"新的页面访问串的访问数="<<instr_sum<<endl;

for(i=0;i<instr_sum;i++)
{
pagenum[i] = newpagenum[i];
cout<<pagenum[i]<<ends; //输出指令所在的页面

}
cout<<endl<<endl;

}

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<mem_sum;i++) //mem_sum:程序获得的内存块数
{
PhysicsPageNode *np=new PhysicsPageNode();
p->next=np;
p=np;
}

for(i=0;i<instr_sum;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++;
copp=copp->next;
}
}

//输出算法，页面大小，缺页中断率等。
cout<<"页面大小="<<pagesize<<" 内存块数="<<mem_sum<<" FIFO 缺页中断率=";
cout.precision(2); //输出小数点后两位
cout<<breaktimes/instr_sum<<endl;
}

3、LRU模块
最近最久未使用页面置换算法（LRU）
LRU在固定时间内将各个内存页的存在时间复位，增加计数器counter，每到30将所有内存页存在时间复位。并且每使用一次内存页，将是把存在时间减3个单位，这样存在时间最大的就是最久未使用的。

void PageReplacement::LRU()
{
float breaktimes=0;
int i,pn;
//生成内存页空间
PhysicsPageNode *head=new PhysicsPageNode();
PhysicsPageNode *p=head,*ppn;
for(i=1;i<mem_sum;i++)
{
PhysicsPageNode *np=new PhysicsPageNode();
p->next=np;
p=np;
}

int counter=0; //计数器
for(i=0;i<instr_sum;i++)
{
counter++;
//增加计数器counter，每到30将所有内存页存在时间复位。
if(counter>30)
{
counter=0; //计数器归零
PhysicsPageNode *q=head;
//内存页存在时间复位
while(q!=NULL)
{
q->Elapsed_Time=1;
q=q->next;
}
}
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 //获取空闲页失败
{
//存在时间最大的为最久未使用。因为每使用一次是减3个单位的存在时间。
ppn=getlongelapsed(head);
ppn->Page_Num=pn;
ppn->Elapsed_Time=1;
}
}
else //载入的页在内存页中。
{
ppn->Elapsed_Time=ppn->Elapsed_Time-3;
}
}
//输出算法，页面大小，缺页中断率等。
cout<<"页面大小="<<pagesize<<" 内存块数="<<mem_sum<<" LRU 缺页中断率=";
cout.precision(2); //输出小数点后两位
cout<<breaktimes/instr_sum<<endl;

}

4、OPT模块
最优淘汰算法OPT
当页面存在时，存在时间参数不变化。当要淘汰一个页时，预读未来50页，并用内存页的存在时间计数。
然后淘汰存在时间最短的。计数方法，未来出现1次，将存在时间减3个单位。到时候存在时间值最大的将被淘汰。

void PageReplacement::OPT()
{
float breaktimes=0;
int i,pn;
//生成内存页空间
PhysicsPageNode *head=new PhysicsPageNode();
PhysicsPageNode *p=head,*ppn=NULL;
for(i=1;i<mem_sum;i++)
{
PhysicsPageNode *np=new PhysicsPageNode();
p->next=np;
p=np;
}

for(i=0;i<instr_sum;i++)
{
pn=pagenum[i]; //需要载入的页号
ppn=getphysage(head,pn); // 是否存在内存页
if(ppn==NULL) // 载入的页不在内存页中
{
//缺页中断次数+1
breaktimes=breaktimes+1;

//获取空闲页面
ppn=getfreepage(head);
if(ppn!=NULL) //获取成功
{
ppn->Page_Num=pn;
ppn->Elapsed_Time=1;
}
else //获取空闲页失败
{
//在这里增加预读未来50个页面计数。
int nextpage=i+1; //从下一页开始算。
int endread=i+50;
int nextpagenum;
PhysicsPageNode *temp;
temp=head;
//先复位。
while(temp!=NULL)
{
temp->Elapsed_Time=1;
temp=temp->next;
}
//下面预读未来页面并计数

for(;((nextpage<endread)&&(nextpage<=instr_sum));nextpage++)
{
nextpagenum=pagenum[nextpage];
temp=getphysage(head,nextpagenum);
if(temp!=NULL)
temp->Elapsed_Time=temp->Elapsed_Time-3;

}
ppn=getlongelapsed(head);
ppn->Page_Num=pn;
ppn->Elapsed_Time=1;

}
}
else //载入的页在内存页中。
{
// 在OPT中无需变化。
}
}
//输出算法，页面大小，缺页中断率等。
cout<<"页面大小="<<pagesize<<" 内存块数="<<mem_sum<<" OPT 缺页中断率=";
cout.precision(2); //输出小数点后两位
cout<<breaktimes/instr_sum<<endl;

}

5、辅助模块

//检查指定页是否在已内存块中
PhysicsPageNode* PageReplacement::getphysage(PhysicsPageNode* pp,int pn)
{
PhysicsPageNode *tmp=pp;

while(tmp!=NULL)
{
if(tmp->Page_Num == pn)
return tmp; //找到对应的页并返回
else
tmp=tmp->next;
}

return NULL; //没找到，返回NULL
}

//检查是否有空的内存块
PhysicsPageNode* PageReplacement::getfreepage(PhysicsPageNode* pp)
{
PhysicsPageNode *tmp=pp;

while(tmp!=NULL)
{
if(tmp->have == -1)
{
tmp->have=1;
return tmp; //找到空的内存块并返回
}
else
tmp=tmp->next;
}

return NULL; //没找到，返回NULL
}

//查找存在时间最长的内存块并返回
PhysicsPageNode* PageReplacement::getlongelapsed(PhysicsPageNode* pp)
{
PhysicsPageNode *tmp=pp,*t=pp;

while(tmp!=NULL)
{
if(tmp->Elapsed_Time > t->Elapsed_Time)
t=tmp;

tmp=tmp->next;
}

return t;
}

七、结果及结果分析
（一）测试数据
1、程序中地址范围
0 ~ 32767
2、页面大小（k）
1K，2K，4K，8K，16K
3、分配给程序的内存块数
1 块，2 块……直到程序的页面数。
4、算法
OPT、FIFO 和LRU

（二）测试结果记录

分析以上的实验结果可知：
1、一般情况下，当页面大小一定时，分配给程序的内存块数越多，缺页中断率的越小；当分配给程序的内存块数一定时，页面大小越大，缺页中断率越小。
2、当供应的内存块数达到所需最大时，缺页中断率最低。这时FIFO，LRU和OPT三种算法得到的缺页中断率一样。
3、一般情况下，OPT的性能最优，LRU缺页中断率低于FIFO。

八、实验总结
通过这次实验，我掌握了OPT、LRU和FIFO等三种算法的工作原理和进一步掌握操作系统的页面置换过程，并强化了编程解决实际问题的能力。
调试过程中发现无论哪个算法得到的缺页中断率都一样，费了一些功夫后发现原来是忘了标志已被使用的内存块，导致每次在内存块中找不到对应的页号时就会将第一个内存块的页号覆盖掉。正是因为这一小错误导致大量的时间花费在调试上。看来细节问题总是得注意的。

九、参考文献
《计算机操作系统教程》张尧学 等，清华大学出版社，2006年。
22