模拟请求页式管理.docx

一、设计目的1
二、设计容1
三、设计原理3
四、算法实现4
五、流程图5
六、源程序5
七、运行例如及结果分析20
八、心得体会20
九、参考资料20
模拟请求页式管理
一、设计目的
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］;）

I

I
第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]页面访问过程
intPageCount[M],LackNum;//PageCoun用来记录LRU算法中最久未使用时间，
LackNum记录缺页数
float PageRate命/中率；
PageRate=1-((float)LackNum/(float)MaxNum计十算命中率
int n=rand()%320; //机数产生320次页面请求
PageOrder[k]=n/10;根据指令产生320次页面请求
五、流程图

Y

int Simulate[MaxNum][M];页面访问过程intPageCount[M],LackNum;//PageCoun用来记录LRU算法中最久未使用时间，
LackNum记录缺页数
int PageCountOPT[M];//PageCountOP用来记录OPT算法中最久未使用时间
float PageRate^/中率
int PageCount1[32];
bool IsExit(int i)//算法O中判断新的页面请否在存中
{
bool f=false;
for(int j=0;j<M;j++)
{
if(Simulate[i-1][j]==PageOrd在前一-次页面请求过程中寻找是否存在
新的页面请求
{
f=true;
}
}
return f;
}
int IsExitLRU(int i)//算法中判断新的页面请否在存中
{
int f=-1;
for(int j=0;j<M;j++)
{
if(Simulate[i-1][j]==PageOrder[i])
{
f=j;
}
}
return f;
}
int pare()//L算法找出存中需要置换出来的页面
{
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 pareOPT(int i)//算法找出存中需要置换出来的页面{
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++)
}
}
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()//FIFC算法
{
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)MaxNu算;出命中率
AllNum();
OutPut();
}
void LRU()//LR。算法
{
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=0;t<M;t++)/先将前一次页面访问过程赋值给新的页面访问过
程
{
Simulate[x][t]=Simulate[x-1][t];
}
int p=IsExitLRU(x);
if(p==-1) /根据返回的p值来更新页面访问过程
{
int k;
k=pare();
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)MaxNu算;出命中率
AllNum();
OutPut();
}
void OPT()/最正确访问算法。ptimal
{
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=0;t<M;t++)/先将前一次页面访问过程赋值给新的页面访问过
程
{
Simulate[x][t]=Simulate[x-1][t];
}
int p=IsExitLRU(x);//OP算法中判断新的页面请否在存中
if(p==-1)/根据返回的p值来更新页面访问过程
{
int k;
k=pareOPT(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)MaxNu算;出命中率
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] 华罗庚，元.论一致分布与近似分析：数论法〔1〕.中国科学，1973 (4) 339〜357
[4] 均宇.略论辛亥革命前后的章太炎.光明日报，1977 03-24 (4)