设计一个虚拟存储区和内存工作区编程序演示下述算法的具体实现过程并计算访问命中率剖析.doc

齐齐哈尔大学
操作系统课程综合实践

题目：　主界面以灵活选择某算法

班级：　 　 计本093　　 　 　

姓名：　　 赵明秋 　　　　　

学号：　 2009021114　 　　　

指导教师： 韩金库　　 　

2008年 12 月
主界面以灵活选择某算法实验

摘要：
计算机应用专业的学生全面了解和掌握系统软件,一般软件设计方法和技术的必不可少的综合课程,也是了解计算机硬件和软件如何衔接的必经之路。
我觉得此次实验最大的亮点以及不同于别人的地方就是将三种页面置换算法按照课本上老师讲的方式直观简便的输出 ，在采用输出算法时，我摒弃了常人所用的一维数组输出法，而别出心裁的采用了二维数组的输出算法，模拟了内存的物理块，清晰直观的表达了页面是如何在外存中被调入内存中的，以及各页面在调入过程中是否命中或在置换时又置换了内存中哪个页面。在软件工程的角度来看，我的系统具有高内聚低耦合的优点，即各种算法之间，并不影响彼此的函数调用，而在各算法的内部，内聚度很高。

关键词：设计原理, 设计方案, 流程图,源代码，测试结果，结束语，参考文献

课题运行环境

操作系统：Windows XP
编程环境：Microsoft Visual C++6.0

1.1 实验内容：

通过模拟实现请求页式存储管理的几种基本页面置换算法，了解虚拟存储技术的特点，掌握虚拟存储请求页式存储管理中几种基本页面置换算法的基本思想和实现过程，并比较它们的效率。熟悉虚拟存储管理的各种液面置换算法，并辨析恶魔你程序实现请求页式存储管理的页面置换算法。
设计一个虚拟存储区和内存工作区,编程序演示下述算法的具体实现过程,并计算访问命中率。
设计要求：
主界面以灵活选择某算法，且以下算法都要实现
1、先进先出算法（FIFO）
2、最近最久未使用算法（LRU）
3、最佳置换算法（OPT）

2.1 运行环境

1）操作系统：Windows XP
2）编程环境：Microsoft Visual C++6.0
3.1 设计原理：

3.1.1 先进先出算法（FIFO）
最简单的页面置换算法是先入先出（FIFO）法。这种算法的实质是，总是选择在主存中停留时间最长（即最老）的一页置换，即先进入内存的页，先退出内存。理由是：最早调入内存的页，其不再被使用的可能性比刚调入内存的可能性大。建立一个FIFO队列，收容所有在内存中的页。被置换页面总是在队列头上进行。当一个页面被放入内存时，就把它插在队尾上。这种算法只是在按线性顺序访问地址空间时才是理想的，否则效率不高。因为那些常被访问的页，往往在主存中也停留得最久，结果它们因变“老”而不得不被置换出去。
FIFO的另一个缺点是，它有一种异常现象，即在增加存储块的情况下，反而使缺页中断率增加了。当然，导致这种异常现象的页面走向实际上是很少见的。
该算法将所有使用的内存页面构成一个循环列队，每次置换时将队列中的队首唤出，队首指针后移一位即可，算法容易实现牡丹石最先进入内存的野末必将来就不用再到，甚至可能很快就会用到，所以不能保证有效的缺页率，算法性能较差。

3.2.2 最近最久未使用算法（LRU）
FIFO算法和OPT算法之间的主要差别是，FIFO算法利用页面进入内存后的时间长短作为置换依据，而OPT算法的依据是将来使用页面的时间。如果以最近的过去作为不久将来的近似，那么就可以把过去最长一段时间里不曾被使用的页面置换掉。它的实质是，当需要置换一页时，选择在最近一段时间里最久没有使用过的页面予以置换。这种算法就称为最久未使用算法（Least Recently Used，LRU）。
LRU算法是与每个页面最后使用的时间有关的。当必须置换一个页面时，LRU算法选择过去一段时间里最久未被使用的页面。
LRU算法是经常采用的页面置换算法，并被认为是相当好的，但是存在如何实现它的问题。LRU算法需要实际硬件的支持。其问题是怎么确定最后使用时间的顺序，对此有两种可行的办法：
（1）计数器。最简单的情况是使每个页表项对应一个使用时间字段，并给CPU增加一个逻辑时钟或计数器。每次存储访问，该时钟都加1。每当访问一个页面时，时钟寄存器的内容就被复制到相应页表项的使用时间字段中。这样我们就可以始终保留着每个页面最后访问的“时间”。在置换页面时，选择该时间值最小的页面。这样做，不仅要查页表，而且当页表改变时（因CPU调度）要维护这个页表中的时间，还要考虑到时钟值溢出的问题。
（2）栈。用一个栈保留页号。每当访问一个页面时，就把它从栈中取出放在栈顶上。这样一来，栈顶总是放有目前使用最多的页，而栈底放着目前最少使用的页。由于要从栈的中间移走一项，所以要用具有头尾指针的双向链连起来。在最坏的情况下，移走一页并把它放在栈顶上需要改动6个指针。每次修改都要有开销，但需要置换哪个页面却可直接得到，用不着查找，因为尾指针指向栈底，其中有被置换页。
因实现LRU算法必须有大量硬件支持，还需要一定的软件开销。所以实际实现的都是一种简单有效的LRU近似算法。
一种LRU近似算法是最近未使用算法（Not Recently Used，NUR）。它在存储分块表的每一表项中增加一个引用位，操作系统定期地将它们置为0。当某一页被访问时，由硬件将该位置1。过一段时间后，通过检查这些位可以确定哪些页使用过，哪些页自上次置0后还未使用过。就可把该位是0的页淘汰出去，因为在最近一段时间里它未被访问过。

3.3.3 最佳置换算法（OPT）
最优置换（Optimal Replacement）是在理论上提出的一种算法。其实质是：当调入新的一页而必须预先置换某个老页时，所选择的老页应是将来不再被使用，或者是在最远的将来才被访问。采用这种页面置换算法，保证有最少的缺页率。但是最优页面置换算法的实现是困难的，因为它需要人们预先就知道一个进程整个运行过程中页面走向的全部情况。不过，这个算法可用来衡量（如通过模拟实验分析或理论分析）其他算法的优劣。
该算法能保证有最低的缺页率，所以称为最佳置换算法，但是该算法紧紧是一种理想状况下的算法，因为在进程实际运行过程中，将来会执行到那儿页是不可预知的，所以无法选择该置换那个页出去。因此，本算法在实际中无法使用，只能作为一种标准来衡量其他算法的性能

4.1 设计方案
1）主界面：
设置页面产生算法选择界面和页面置换算法选择界面；
2）子界面：
页面产生算法分为两个界面，分别是随机产生算法和自己输入产生算法。
页面置换算法分为三个子界面，分别是先进先出算法界面、最近最久未使用算法界面、最佳置换算法界面。
5.1 流程图
5.1.1主流程图

图（1）

5.1.2 FIFO函数流程图：

图（2）
5.1.3 LRU函数流程图：

图（4）
5.1.4 OPT函数流程图：

图（5）

6.源代码
6.1 程序代码
#include <iostream>
#include <time.h>
#include<math.h>
#define Bsize 3
#define Psize 12
#include<string>
using namespace std;
int QString[Psize];
int Num=0;
struct pageInfor
{
int content;
int timer;
};
class YZ_replace
{
public:
YZ_replace();
~YZ_replace();
int findSpace();
int findExist(int curpage);
int findReplace();
void FIFO();
void OPT();
void BlockClear();
void initia1(int string[]);
pageInfor *block;
pageInfor *page;
int memory_state[Bsize][Psize];
int s;
private:
};
void P_String(int QString[])
{
int i;
srand((unsigned)time(NULL));
for(i=0;i<Psize;i++)
{
QString[i]=rand()*9/RAND_MAX+1;
}
cout<<"页面走向：";
for(i=0;i<Psize;i++)
{
cout<<QString[i]<<" ";
}
cout<<endl;
}
YZ_replace::YZ_replace()
{
s=0;
block = new pageInfor[Bsize];
for(int i=0; i<Bsize; i++)
{
block[i].content = -1;
block[i].timer = 0;
}
}
void YZ_replace::initia1(int QString[] )
{
int j;
page = new pageInfor[Psize];
for(int i=0; i<Psize; i++)
{
page[i].content = QString[i];
page[i].timer = 0;
}
for(i=0;i<Psize;i++)
for(j=0;j<Bsize;j++)
memory_state[j][i]=0;
}
YZ_replace::~YZ_replace()
{
s=0;
}

int YZ_replace::findSpace()
{
for(int i=0; i<Bsize; i++)
if(block[i].content == -1)
return i;
return -1;
}
int YZ_replace::findExist(int curpage)
{
for(int i=0; i<Bsize; i++)
if(block[i].content == page[curpage].content)
return i;
return -1;
}

int YZ_replace::findReplace()
{
int pos = 0;
for(int i=0; i<Bsize; i++)
if(block[i].timer >= block[pos].timer)
pos = i;
return pos;
}

void YZ_replace::FIFO()
{
int exist,space,position ;
for(int i=0; i<Psize; i++)
{
exist = findExist(i);
if(exist != -1)
{
for(int b=0; b<Bsize; b++)
{
memory_state[b][i]=memory_state[b][i-1];
}
s++;
}
else
{
space = findSpace();
if(space != -1)
{
for(int b=0; b<Bsize; b++)
{
memory_state[b][i]=memory_state[b][i-1];
}
block[space] = page[i];
memory_state[space][i]=block[space].content;
}
else
{
for(int b=0; b<Bsize; b++)
{
memory_state[b][i]=memory_state[b][i-1];
}
position = findReplace();
block[position] = page[i];
memory_state[position][i]=block[position].content;
}
}
for(int j=0; j<Bsize; j++)
block[j].timer++;
}
}

void YZ_replace::BlockClear()
{
for(int i=0; i<Bsize; i++)
{
block[i].content = -1;
block[i].timer = 0;
}
}

typedef struct page
{
int num;
int time;
}Page;

Page b[Bsize];
Page call[Bsize];
int c[Bsize][Psize];
int queue[100];
int K;

void InitL(Page *b,int c[Bsize][Psize])
{
int i,j;
for(i=0;i<Bsize;i++)
{
b[i].num=-1;
b[i].time=Psize-i-1;
}
for(i=0;i<Bsize;i++)
for(j=0;j<Psize;j++)
c[i][j]=-1;
}
int GetMax(Page *b)
{
int i;
int max=-1;
int tag=0;
for(i=0;i<Bsize;i++)
{
if(b[i].time>max)
{
max=b[i].time;
tag=i;
}
}
return tag;
}
int Equation(int fold,Page *b)
{
int i;
for(i=0;i<Bsize;i++)
{
if (fold==b[i].num)
return i;
}
return -1;
}
void Lru(int fold,Page *b)
{
int i;
int val;
val=Equation(fold,b);
if (val>=0)
{
b[val].time=0;
for(i=0;i<Bsize;i++)
if (i!=val)
b[i].time++;
}
else
{
queue[++K]=fold;
val=GetMax(b);
b[val].num=fold;
b[val].time=0;
for(i=0;i<Bsize;i++)
if (i!=val)
b[i].time++;
}
}

void YZ_replace::OPT()
{
int exist,space,position ;
for(int i=0; i<Psize; i++)
{
exist = findExist(i);
if(exist != -1)
{
for(int b=0; b<Bsize; b++)
{
memory_state[b][i]=memory_state[b][i-1];
}
s++;
}
else
{
space = findSpace();
if(space != -1)
{
for(int b=0; b<Bsize; b++)
{
memory_state[b][i]=memory_state[b][i-1];
}
block[space] = page[i];
memory_state[space][i]=block[space].content;
}
else
{
for(int k=0; k<Bsize; k++)
{
memory_state[k][i]=memory_state[k][i-1];
for(int j=i; j<Psize; j++)
{
if(block[k].content != page[j].content)
{ block[k].timer = 1000; }
else
{ block[k].timer = j; break;}
}
}
position = findReplace();
block[position] = page[i];
memory_state[position][i]=block[position].content;
}
}
}
}

int decide(string str)
{
for(int i=0;i<str.size();i++)
{
if(str[i]<'0'||str[i]>'9')
{
return 0;
break;
}
}
return i;
}
int trans(string str)
{
int sum=0;
for(int i=0;i<str.size();i++)
sum=sum+(str[i]-'0')*pow(10,str.size()-i-1);
return sum;
}

int put()
{
int a,d;
string str;
cin>>str;
a=decide(str);
while(a==0)
{
cout<<"输入错误,请重新输入！"<<endl;
cin>>str;
a=decide(str);
}
d=trans(str);
return d;
}
void Put()
{
cout<<"请选择产生页面的方法 a:随机产生 b:输入产生"<<endl;
cout<<"您选择的菜单是:";
char F;
cin>>F;
while(F!='a'&&F!='b')
{
cout<<"输入错误，请重新输入:";
cin>>F;
}
if(F=='a')
P_String(QString) ;
if(F=='b')
{
cout<<"请输入各页面号:"<<endl;
for(int i=0;i<Psize;i++)
{
QString[i]=put();
}
}
cout<<endl;
cout<<"|---------------------------------------------------------------|"<<endl;
}
void main()
{
cout<<"|-----------------------页 面 置 换 算 法-----------------------|"<<endl;
cout<<"|---------------------------------------------------------------|"<<endl;
int t=1;
while(t)
{
Put();
YZ_replace test1;
YZ_replace test3;
char select;
do{
cout<<"请选择要应用的算法:<1>FIFO算法 <2>LRU算法 <3>OPT算法 <0>退出"<<endl;
int p,q;
cout<<"请您输入菜单号:";
cin>>select;
while(select!='0'&&select!='1'&&select!='2'&&select!='3')
{
cout<<"您的输入无效,请重新输入:"<<endl;
cin>>select;
}
if(select=='0')
{
cout<<"您选择的是菜单<0>"<<endl;
cout<<"完成退出."<<endl;
t=0;
}

if(select=='1')
{
cout<<"您选择的是菜单<1>"<<endl;
cout<<"FIFO算法状态:"<<endl;
test1.initia1(QString);
test1.FIFO();
test1.BlockClear();
cout<<"-------------------------------------------"<<endl;
for(p=0;p<Bsize;p++)
{
for(q=0;q<Psize;q++)
cout<<test1.memory_state[p][q]<<" ";
cout<<endl;
}
cout<<"-------------------------------------------"<<endl;
cout<<"命中率:"<<test1.s<<"/"<<Psize<<endl;
test1.~YZ_replace();
cout<<endl;
}
if(select=='2')
{
int i,j;
K=-1;
InitL(b, c);
for(i=0;i<Psize;i++)
{
Lru(QString[i],b);
c[0][i]=QString[i];
for(j=0;j<Bsize;j++)
c[j][i]=b[j].num;
}
cout<<"您选择的是菜单<2>"<<endl;
cout<<"LRU算法状态:"<<endl;
cout<<"------------------------------------------"<<endl;
for(i=0;i<Bsize;i++)
{
for(j=0;j<Psize;j++)
{
if(c[i][j]==-1)
cout<<" 0";
else
cout<<" "<<c[i][j];
}
cout<<" "<<endl;
}
cout<<"------------------------------------------"<<endl;
cout<<"命中率:"<<(Psize-(K+1))<<"/"<<Psize;
cout<<'\t';
cout<<endl;
}
if(select=='3')
{
cout<<"您选择的是菜单<3>"<<endl;
cout<<"OPT算法状态:"<<endl;
test3.initia1(QString);
test3.OPT();
test3.BlockClear();
cout<<"------------------------------------------"<<endl;
for(p=0;p<Bsize;p++)
{
for(q=0;q<Psize;q++)
cout<<test3.memory_state[p][q]<<" ";
cout<<endl;
}
cout<<"------------------------------------------"<<endl;
cout<<"命中率:"<<test3.s<<"/"<<Psize<<endl;
test3.~YZ_replace();
cout<<endl;
}
}while(select=='1'||select=='2'||select=='3');
}
}

7.测试结果
7.1 页面选择测试：

图（7.1）

图（7.2）
分析：页面产生的方法有两种选择，分别是随机产生和自己输入产生，选择菜单的时候有对异常输入的处理，如果输入错误，有错误提示，当输入正确菜单的时候，选择a，自动产生页面走向，如果选择b，自己可以任意输入，如果输入错误，有错误提示。
6.2 应用算法选择测试

图（7.3）
分析：选择算法时，有异常处理，即如果输入错误，有错误提示。如果选择菜单1，即选择了FIFO算法，展示此算法的置换状态并显示命中率。置换状态以二维数组的形式输出，既直观又清晰。

图（7.4）
分析：算法一进行完以后，界面自动跳到应用算法的选择界面，即可以再次选择置换算法，选择菜单2，即选择了LRU算法，展示此算法的置换状态并显示命中率，可以和第一个算法进行对比，找出两种算法的不同。

图（7.5）
分析：算法二进行完以后，界面自动跳到应用算法的选择界面，即可以再次选择置换算法，选择菜单3，即选择了OPT算法，展示此算法的置换状态并显示命中率，可以和第二个算法进行对比，找出两种算法的不同。

图（7.6）
分析：算法二进行完以后，界面自动跳到应用算法的选择界面，即可以再次选择置换算法，选择菜单3，即选择了OPT算法，展示此算法的置换状态并显示命中率，可以和第二个算法进行对比，找出两种算法的不同。

8.结束语
为期两周的操作系统课设在不断的探索、尝试、成功中结束了。现在，站在成功地峰顶，回顾着走过的一路，真是什么感觉都有，枯燥、失败、劳累、迷茫、喜悦，应该说，我的设计体会相当深刻。
首先，谈谈本系统的不足：
我设计的页面值换算法里，页面个数和内存个数是一个定数，在这一点上没有实现与操作员的交互，即页面数和内存个数并不能手动输入，我设计的系统在界面上并没有太大的优化，没有实现选择算法后可以重新选择页面产生的算法，重新进行页面置换的选择。总体上来说，这两方面是本系统可以改进的地方，虽然我的课设已经验收，但是我在验收完成后，继续完善了我的整个界面并改进了系统的不足之处，以达到系统的完整性，简洁性，交互性。
其次，谈谈本系统特色、新的发明、创造等
最后，在整体上自我评价一下我的系统：
第一，在功能上，它完全实现了各种页面置换算法的模拟；第二，在界面设计上，新颖独特，独树一帜，采用了二维数组的输出方法了；第三，异常处理面面俱到，不需要担心因为输入错误而出现乱码，甚至重新执行。
在此课设期间我为自己总结了四句话：鄙视平庸和碌碌无为，敢于主张自己并坚持不懈，用于忍耐寂寞、枯燥和劳累，善于探求登峰捷径且百折不挠。
最最后，也是我最想说的话，衷心地感谢李新荣老师对我的悉心指导和最大的信任。

9.1 参考文献
[1] 《计算机操作系统》 哲凤屏 汤子瀛 西安电子科技大学出版社.2011年2月
[2]《C语言程序设计教程》（第三版）谭浩强 张基温 高级教育出版社.2008年4月
[3]《程序设计基础》（第二版）吴文虎 清华大学出版社.2010年2月
[4]《C++程序设计》 刘娜娜 北京航空大学出版社.2008年4月