模拟请求页式管理.doc

目 录
一、设计目的1
二、设计内容1
三、设计原理2
四、算法实现4
五、流程图5
六、源程序6
七、运行示例及结果分析14
八、心得体会16
九、参考资料16
模拟请求页式管理
一、设计目的
1。通过模拟实现请求页式存储管理的几种基本页面置换算法,了解虚拟存储技术的特点.
2。通过对页面、页表、地址转换和页面置换过程的模拟，加深对请求调页系统的原理和是实验过程的理解。
3.掌握虚拟存储请求页式存储管理中几种基本页面置换算法的基本思想和实现过程，并比较它们的效率。
二、设计内容
通过随机数产生一个指令序列，共320条指令.指令的地址按下述原则生成:
① 50% 的指令是顺序执行的;
② 25％ 的指令是均匀分布在前地址部分；
③ 25% 的指令是均匀分布在后地址部分。
具体的实施方法是：
①在 ［0，319] 的指令地址之间随机选取一起点 m；
②顺序执行一条指令；
③在前地址［0，m+1］中随机选取一条指令并执行,该指令的地址为 m′;
④顺序执行一条指令,其地址为 m′+1;
⑤在后地址 [m′+2，319］ 中随机选取一条指令并执行 ;
⑥重复上述步骤② ～ ⑤ ， 直到执行 320 次指令。
将指令序列变换成为页地址流
设:①页面大小为 1K;
②用户内存容量为 4 页到 32 页 ；
③用户虚存容量为 32K 。
在用户虚存中，按每 K 存放 10 条指令排列虚存地址，即 320 条指令在虚存中的存放方式为：
第 0 条 ~ 第 9 条指令为第 0 页 （ 对应虚存地址为 ［0,9］);
第 10 条 ～ 第 19 条指令为第 1 页 ( 对应虚存地址为 [10，19］ ) ;
┇
┇
第 310 条 ~ 第 319 条指令为第 31 页 （ 对应虚存地址为 ［310,319］） .
按以上方式，用户指令可组成 32 页.
计算并输出下述各种算法在不同内存容量下的命中率。
先进先出的算法 （FIFO);最近最久未使用算法 (LRU)；
最佳访问算法（OPT）；
三、设计原理
㈠ FIFO页面置换算法
⑴原理简述
①在分配内存页面数(AP）小于进程页面数(PP）时,当然是最先运行的AP个页面放入内存.
②这时有需要处理新的页面，则将原来内存中的AP个页面最先进入的调出（是以称为FIFO)，然后将新页面放入。
③以后如果再有新页面需要调入，则都按⑵的规则进行。
算法特点：所使用的内存页面构成一个队列。
㈡ LRU页面置换算法
⑴原理算述
①当分配内存页面数(AP）小于进程页面数(PP）时，当然是把最先执行的AP个页面放入内存。
②当需要调页面进入内存，而当前分配的内存页面全部不空闲时，选择将其中最长时间没有用到的那个页面调出，以空出内存来放置新调入的页面（称为LRU）。
算法特点：每个页面都有属性来表示有多长时间未被CPU使用的信息。
LRU算法的硬件支持
把LRU算法作为页面置换算法是比较好的，它对于各种类型的程序都能适用,但实现起来有相当大的难度,因为它要求系统具有较多的支持硬件。所要解决的问题有：
1。一个进程在内存中的各个页面各有多久时间未被进程访问；
2。如何快速地知道哪一页最近最久未使用的页面。为此，须利用以下两类支持硬件：
（1）寄存器
用于记录某进程在内存中各页的使用情况。
实页/R
R7
R6
R5
R4
R3
R2
R1
R0
1
0
1
0
1
0
0
1
0
2
1
0
1
0
1
1
0
0
3
0
0
O
0
0
1
0
0
4
0
1
1
0
1
0
1
1
5
1
1
0
1
0
1
1
0
6
0
0
1
0
1
0
1
1
7
0
0
0
0
0
1
1
1
8
0
1
1
0
1
1
0
1
（2)栈
可利用一个特殊的栈来保存当前使用的各个页面的页面号。每当进程访问某页面时，便将该页面的页面号从栈中移出，将它压入栈顶。
四、算法实现
A。命中率=1—页面失效次数/页地址流长度
B。本实验中，页地址流长度为320,页面失效次数为每次访问相应指令时，该指令所对应的页不在内存的次数.
C.关于随机数产生方法,采用TC系统提供函数RAND(）和RANDOMIZE（）来产生。
const int MaxNum=320;//指令数
const int M=5;//内存容量
int PageOrder［MaxNum]；//页面请求
int Simulate［MaxNum］［M］；//页面访问过程
int PageCount［M],LackNum；//PageCount用来记录LRU算法中最久未使用时间，LackNum记录缺页数
float PageRate;//命中率；
PageRate=1—（(float）LackNum/（float）MaxNum);//计算命中率
int n=rand（）％320；//随机数产生320次页面请求
PageOrder［k］=n/10;//根据指令产生320次页面请求
五、流程图
开 始
生成地址流
输入算法号S
1≤S≤4
形成地址页号
用户内存空间msize=2
Msize≤32
FIFO()
LRU()
OPT()
Msize加1
S=?
是否用其他算法继续
结 束
N
Y
1
2
3
Y
N
提示出错，重新输入

六、源程序
# include<iostream〉
＃ include<time。h〉
using namespace std；
const int MaxNum=320；//指令数
const int M=5;//内存容量
int PageOrder[MaxNum]；//页面请求
int Simulate[MaxNum]［M］;//页面访问过程
int PageCount［M]，LackNum；//PageCount用来记录LRU算法中最久未使用时间，LackNum记录缺页数
int PageCountOPT[M］；//PageCountOPT用来记录OPT算法中最久未使用时间
float PageRate;//命中率
int PageCount1［32]；
bool IsExit（int i）//FIFO算法中判断新的页面请求是否在内存中
{
bool f=false；
for（int j=0；j〈M；j++）
｛
if(Simulate［i-1］[j]==PageOrder［i］)//在前一次页面请求过程中寻找是否存在新的页面请求
｛
f=true;
}
｝
return f;
}
int IsExitLRU（int i）//LRU算法中判断新的页面请求是否在内存中
｛
int f=—1；
for（int j=0；j〈M；j++）
{
if（Simulate[i—1］［j］==PageOrder［i］）
{
f=j；
｝
｝
return f；
｝
int Compare(）//LRU算法找出内存中需要置换出来的页面
｛
int p，q;
p=PageCount[0］；
q=0；
for（int i=1；i<M；i++)
{
if (p〈PageCount［i]）
｛
p=PageCount［i]；
q=i;
｝
}
return q;
}
int CompareOPT（int i)//OPT算法找出内存中需要置换出来的页面
{
int temp［5]；
for（int a=0；a〈5;a++)
{
temp［a]=0；
}
for（int j=0；j〈M;j++)
{
for(int ii=i+1；ii<MaxNum；ii++)
｛
if（Simulate[i-1］［j]!=PageOrder［ii]）
{
temp［j］++；
｝
else｛
break；
｝
｝
｝
int max=temp［0]；
int maxIndex=0;
for（int i1=1；i1<M；i1++)
｛
if（max〈temp[i1]）
{
max=temp[i1］；
maxIndex=i1;
｝
}
return maxIndex;
}
void Init（）//初始化页框
｛
for（int k=0;k〈MaxNum;k++)
{
int n=rand()%320；//随机数产生320次页面请求
PageOrder［k]=n/10；//根据指令产生320次页面请求
}
for（int i=0;i<MaxNum；i++）//初始化页面访问过程
｛
for（int j=0；j〈M；j++）
｛
Simulate［i］［j]=-1；
}
}
for （int q=0;q〈M；q++）//初始化最久未使用数组
｛
PageCount［q］=0；
PageCountOPT［q］=0；
｝
｝
void AllNum（)
{
int j；
cout〈<”页面访问序列："〈〈endl；
for（j=0;j<MaxNum;j++)
{
cout〈<PageOrder［j］〈<" ”；
｝
}
void OutPut（)//输出
｛
int i,j；
cout〈<endl;
cout<〈”页面访问过程（只显示前十个）：”〈〈endl;
for（i=0；i〈10;i++）
{
for（j=0;j〈M;j++）
{
if（Simulate［i］［j］==—1)
cout<〈” ”；
else
cout<〈Simulate[i］［j］〈〈” "；
｝
cout〈<endl;
}
cout<<”缺页率= "<<LackNum<<endl；
cout<<”命中率= "<〈PageRate〈〈endl；
cout〈〈”-—-——-—-—-———-———-——-————---——-———-——-———-—-————”〈〈endl；
｝
void FIFO（）//FIFO算法
｛
int j,x=0，y=0；
LackNum=0；
Init（); //初始化
for(j=0；j<M；j++）//将前五个页面请求直接放入内存中
{
for(int k=0;k<=j;k++）
{
if（j==k）
Simulate[j］［k]=PageOrder［j］；
else
Simulate[j］［k］=Simulate[j—1］[k］；
｝
LackNum++；
｝
for（x=M;x<MaxNum;x++)
｛
for(int t=1；t<M；t++)
{
Simulate[x］［t]=Simulate[x—1］［t］；
}
if（!IsExit（x)）//根据新访问页面是否存在内存中来更新页面访问过程
｛
LackNum++；
Simulate［x］［y％M]=PageOrder[x]；
y++;
｝
}
PageRate=1-(（float）LackNum/(float)MaxNum）；//算出命中率
AllNum（）；
OutPut（）；
}
void LRU（)//LRU算法
｛
int j，x=0，y=0；
LackNum=0;
Init（）；
for（j=0;j〈M；j++)//将前五个页面请求直接放入内存中
｛
for（int k=0；k〈=j；k++）
｛
PageCount［k]++;
if（j==k）
Simulate［j］［k］=PageOrder［j]；
else
Simulate［j］[k］=Simulate［j—1］［k］；
}
LackNum++;
}
for（x=M;x<MaxNum;x++)
{
for(int t=0；t〈M；t++)//先将前一次页面访问过程赋值给新的页面访问过程
｛
Simulate［x］[t］=Simulate[x-1］［t];
｝
int p=IsExitLRU（x）;
if（p==-1）//根据返回的p值来更新页面访问过程
｛
int k;
k=Compare()；
for（int w=0；w〈M；w++)
{
if（w！=k）
PageCount［w］++；
else
PageCount［k]=1;
｝
Simulate［x］[k]=PageOrder［x］;
LackNum++；
｝
else
｛
for（int w=0；w〈M;w++）
{
if（w!=p)
PageCount[w]++；
else
PageCount［p]=1；
｝
｝
｝
PageRate=1—（(float）LackNum/(float)MaxNum）；//算出命中率
AllNum（）;
OutPut（）；
｝
void OPT（）//最佳访问算法Optimal
｛
int j，x=0，y=0;
LackNum=0；
Init(）；
for（j=0；j<M；j++）//将前五个页面请求直接放入内存中
{
for（int k=0;k<=j；k++）
{
PageCountOPT[k］++;
if（j==k）
Simulate[j］［k］=PageOrder［j];
else
Simulate［j］[k］=Simulate[j—1］［k];
}
LackNum++；
}
AllNum();
for（x=M；x<MaxNum；x++）
｛
for（int t=0;t〈M;t++）//先将前一次页面访问过程赋值给新的页面访问过程
｛
Simulate［x］［t］=Simulate[x-1］［t］;
}
int p=IsExitLRU（x)；//OPT算法中判断新的页面请求是否在内存中
if（p==-1)//根据返回的p值来更新页面访问过程
｛
int k；
k=CompareOPT(x）；//OPT算法找出内存中需要置换出来的页面
for(int w=0;w〈M;w++)
{
if（w！=k）
PageCountOPT［w］++;
else
PageCountOPT［k］=1；
}
Simulate［x］[k]=PageOrder［x］；
LackNum++；
}
else
{
for(int w=0；w<M；w++）
｛
if（w！=p）
PageCountOPT[w］++;
else
PageCountOPT[p］=1;
｝
｝
}
PageRate=1-(（float)LackNum/(float)MaxNum)；//算出命中率
OutPut（）；
}
void YourChoice（int choice)
｛
switch（choice)
｛
case 1:
cout〈〈”—-——-——-————————--—--—--——-———-——-——-——-———---——"〈〈endl；
cout<〈”FIFO算法结果如下："<〈endl;
FIFO()；
break；
case 2：
cout〈〈”—————-——-———-——-—--—--———-———--——-————--—--—-———"<〈endl;
cout〈〈”LRU算法结果如下：”〈<endl;
LRU(）;
break;
case 3：
cout<〈"————-—-————-——-—————--——-—-————-—————--————-————”〈<endl；
cout〈<”OPT算法结果如下:”〈〈endl；
OPT();
break；
case 4:
break；
default：
cout〈〈”重新选择算法:1--FIFO 2——LRU 3——OPT 4—-退出"<<endl；
cin〉〉choice;
YourChoice（choice);
｝
}
void main(）
{
int choice，i=1;
while（i）
{
cout〈<"请选择算法：1-—FIFO 2--LRU 3-—OPT 4——退出"<<endl;
cin〉〉choice；
if（choice==1｜|choice==2｜｜choice==3|｜choice==4）
｛
YourChoice（choice）;
}
}
}
七、运行示例及结果分析
八、心得体会
本次课程设计目的是通过请求页式管理中页面置换算法模拟设计，了解虚拟存储技术的特点,掌握请求页式存储管理的页面置换算法.做了这么多次课程设计了,大致的过程都熟悉了，每次的动手实践，调动了我们主动学习的积极性， 并引导我们根据实际编程要求， 训练自己实际分析问题的能力及编程能力， 并养成良好的编程习惯。通过详细的实例， 循序渐进地启发我们完成设计课程设计将要求。从拿到题目到完成整个编程，从理论到实践可以学到很多很多的东西,同时不仅可以巩固了以前所学过的知识，而且学到了很多在书本上所没有学到过的知识。通过这次课程设计使我懂得了理论与实际相结合是很重要的,只有理论知识是远远不够的，只有把所学的理论知识与实践相结合起来，从理论中得出结论,才能真正为社会服务，从而提高自己的实际动手能力和独立思考的能力.知识的获得是无止境的，只要你想学，只要你行动，就一定会有所收获的。回首这两个星期的课程设计，尽管很是头痛，很多都不会，但经过努力，我们还是学了不少知识的。这期间,老师给了我们许多帮助,非常感谢!
九、参考资料
参考文献格式例:
［1］。中国科学院南京土壤研究所西沙群岛专案组．我国西沙群岛的土壤和鸟粪矿．北京:科学出版社，1977
［2］.傅承义，陈运泰,祁贵中．地球物理学基础．北京：科学出版社，1985．477
［3］.华罗庚，王元．论一致分布与近似分析：数论方法（Ⅰ)．中国科学,1973（4）:339~357
[4］.赵均宇．略论辛亥革命前后的章太炎．光明日报,1977 03-24(4)
- 13 -