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

1、齐齐哈尔大学操 作系统课程综合实践题目：主界面以灵活选择某算法 班级：计本093姓名：赵明秋学号：2009021114指导教师：韩金库2008年 12月2、最近最久未使用算法（LRU）主界面以灵活 选择某算法实 验摘要：计算机应用专业的学 生全面了解和掌握系统软件, 一般软件设计方法和技术的必不可少的综合课程, 也是了解计算机硬件和软件如何衔接的必经之路。我觉得此次实验最大 的亮点以及不同于别人的地方就是将三种 页面置换算法按照课本上老师讲的方式直观简便的输出 ，在采用输出算法时 ，我摒弃了常人所用的 一维数组输出法，而别出心裁的采用了二维数组的输出算法，模拟了内存了页面是如何在外存 置换了内

2、存中哪个页 各种算法之间，并不中被调入内存中的，以及各页面在调入过面。在软件工程的角度来看，我的系统具影响彼此的函数调用，而在各算法的内部的物理块，清晰直观的表达程中是否命中或在置换时又有高内聚低耦合的优点，即,内聚度很高。关键词 ：设计原理, 设计方案 , 流程图 , 源代码，测试结果，结束语，参考文献课题 运 行环 境操作系统：Windows XP编程环境：Microsoft Visual C+6.0实 验内容 ：通过模拟实现请求页式存储管理的几种基本页面置换算法，了解虚拟存储 TOC o 1-5 h z 技术的特点，掌握虚拟存储请求页式存储管理中几种基本页面置换算法的基本思想和实现过程，

3、并比较它们的效率。熟悉虚拟存储管理的各种液面置换算法 ，并辨析恶魔你程序实现请求页式存储管理的页面置换算法。设计一个虚拟存储区和内存工作区 , 编 程序演示下述算法的具体实现过程,并计算访问命中率。设计要求：主界面以灵活选择某算法，且以下算法都要实现1、先进先出算法（FIFO）3、最佳置换算法（OPT）2.1 运 行环境1）操作系统：Windows XP2）编程环境：Microsoft Visual C+6.03.1 设 计原理 ：3.1.1 先进先出算法（FIFO）最简单的页面置换算法是先入先出（ FIFO） 法。 这种算法的实质是，总是 TOC o 1-5 h z 选择在主存中停留时间最长

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

5、中的队首唤出，队首指针后移一位即可，算法容易实现牡丹石最先进入内存的野末必将来就不用再到，甚至可能很快就会用到，所以不能保证有效的缺页率，算法性能较差。3.2.2 最近最久未使用算法（LRU）FIFO算法和OPT法之间的主要差别是，FIFO算法利用页面进入内存后的 时间长短作为置换依据，而 OPTT法的依据是将来使用页面的时间。如果以 最近的过去作为不久将来的近似，那么就可以把过去最长一段时间里不曾被使用的页面置换掉。它的实质是，当需要置换一页时，选择在最近一段时间里最久没有使用过的页面予以置换。这种算法就称为最久未使用算法（ Least Recently Used ， LRU）。lruB法是

6、与每个页面最后使用的时间有关的。当必须置换一个页面时，LRU算法选择过去一段时间里最久未被使用的页面。LRU算法是经常采用的页面置换算法，并被认为是相当好的，但是存在如何实现它的问题。LRU算法需要实际硬件的支持。其问题是怎 么确定最后使用时间 的顺序，对此有两种可行的办法：1）计数器。最简单的情况是使每个页表项对应一个使用时间字段，并给CPU曾加一个逻辑时钟或计数器。每次存储访问，该时钟都加1。每当访问一个页面时，时钟寄存器的内容就被复制到相应页表项的使用时间字段中。这样我们就可以始终保留着每个页面最后访问的“时间 ”。在 置换页面时，选择该时间值最小的页面。这样做，不仅要查页表，而且当页表

7、改变时（因 CPUS度）要 维护这个页表中的时间，还要考虑到时钟值溢出的问题。2）栈。用一个栈保留页号。每当访问一个页面时，就把它从栈中取出放 TOC o 1-5 h z 在栈顶上。这样一来，栈顶总是放有目前使用最多的页，而栈底放着目前最少使用的页。由于要从栈的中间移走一项，所以要用具有头尾指针的双向链连起来。在最坏的情况下，移走一页并把它放在栈顶上需要改动6个指针。每次修改都要有开销，但需要置换哪个页面却可直接得到，用不着查找，因为尾指针指向栈底，其中有被置换页。 因实现LRUB法必须有大量硬件支持，还需要一定的软件开销。所以实际实 现 的都是一种简单有效的LRU近似算法。一种LRU近似算法

8、是最近未使用算法（Not Recently Used , NUR。佗在存储分块表的每一表项中增加一个引用位，操作系统定期地将它们置为0。当某一页被访问时，由硬件将该位置1 。过一段时间 后，通过检查这些位可以确定哪些页使用过，哪些页自上次置0后还未使用过。 就可把该位是0 的页淘汰出去，因为在最近一段时间里它未被访问过。3.3.3 最佳置换算法（OPT）最优置换（ Optimal Replacement ）是 在理论上提出的一种算法。其实质是：使 TOC o 1-5 h z 用，或者是在最远的将来才被访问。采用这种页面置换算法，保证有最少的缺页率。但是最优页面置换算法的实现是困难的，因为它需要

9、人们预先就知道一个进程整个运行过程中页面走向的全部情况。不过，这个算法可用来衡量（如通过模拟实验分析或理论分析）其他算法的优劣。该算法能保证有最低的缺页率，所以称为最佳置换算法，但是该算法紧紧是一种理想状况下的算法，因为在进程实际运行过程中，将来会执行到那儿页是不可预知的，所以无法选择该置换那个页出去。因此，本算法在实际中无法使用，只能作为一种标准来衡量其他算法的性能4.1 设计方案1）主界面：设置页面产生算法选择界面和页面置换算法选择界面；2）子界面：页面产生算法分为两个界面，分别是随机产生算法和自己输入产生算法。页面置换算法分为三个子界面，分别是先进先出算法界面、最近最久未使用算法界面、最

10、佳置换算法界面。流程图主流程图图（1）5.1.2 FIFO函数流程图:图（2）Start5.1.3 LRU函数流程图:5.1.4 OPT8数流程图:图（5）6.源代码6.1 程序代码#include #include #include#define Bsize3#define Psize12#includeusing namespace std;int QStringPsize;int Num=0;struct pageInforint content;int timer;class YZ_replacepublic:YZ_replace();YZ_replace();int findSpac

11、e();int findExist(int curpage);int findReplace();void FIFO();void OPT();void BlockClear();void initia1(int string);pageInfor *block;pageInfor *page;int memory_stateBsizePsize;int s;private:;void P_String(int QString)int i;srand(unsigned)time(NULL);for(i=0;iPsize;i+)QStringi=rand()*9/RAND_MAX+1;cout

12、页面走向： ;for(i=0;iPsize;i+)coutQStringiII.coutendl;YZ_replace:YZ_replace()s=0;block = new pageInforBsize; for(int i=0; iBsize; i+) blocki.content = -1;blocki.timer = 0;void YZ_replace:initia1(int QString )int j;page = new pageInforPsize;for(int i=0; iPsize; i+)pagei.content = QStringi;pagei.timer = 0;

13、for(i=0;iPsize;i+)for(j=0;jBsize;j+)memory_stateji=0;YZ_replace:YZ_replace()s=0;int YZ_replace:findSpace()for(int i=0; iBsize; i+) if(blocki.content = -1) return i;return -1;int YZ_replace:findExist(int curpage)for(int i=0; iBsize; i+) if(blocki.content = pagecurpage.content) return i;return -1;int

14、YZ_replace:findReplace()int pos =0;for(int i=0; i= blockpos.timer)pos = i;return pos;void YZ_replace:FIFO()int exist,space,position ;for(int i=0; iPsize; i+) exist = findExist(i);if(exist !=-1)for(int b=0; bBsize; b+)memory_statebi=memory_statebi-1; s+; elsespace = findSpace();if(space !=-1)for(int

15、b=0; bBsize; b+)memory_statebi=memory_statebi-1;blockspace = pagei;memory_statespacei=blockspace.content; elsefor(int b=0; bBsize; b+)memory_statebi=memory_statebi-1;position = findReplace(); blockposition = pagei;memory_statepositioni=blockposition.content;for(int j=0; jBsize; j+) blockj.timer+;voi

16、d YZ_replace:BlockClear() for(int i=0; iBsize; i+) blocki.content = -1; blocki.timer = 0;typedef struct pageint num;int time;Page;Page bBsize;Page callBsize;int cBsizePsize;int queue100;int K;void InitL(Page *b,int cBsizePsize)int i,j;for(i=0;iBsize;i+)bi.num=-1;bi.time=Psize-i-1;for(i=0;iBsize;i+)f

17、or(j=0;jPsize;j+) cij=-1;int GetMax(Page *b)int i;int max=-1;int tag=0;for(i=0;imax) max=bi.time;tag=i;return tag;int Equation(int fold,Page *b) int i;for(i=0;i=0)bval.time=0;for(i=0;iBsize;i+)if (i!=val) bi.time+;elsequeue+K=fold; val=GetMax(b); bval.num=fold; bval.time=0;for(i=0;iBsize;i+) if (i!=

18、val)bi.time+; void YZ_replace:OPT()int exist,space,position ;for(int i=0; iPsize; i+) exist = findExist(i);if(exist !=-1)for(int b=0; bBsize; b+) memory_statebi=memory_statebi-1; s+; elsespace = findSpace();if(space !=-1)for(int b=0; bBsize; b+)memory_statebi=memory_statebi-1; blockspace = pagei;mem

19、ory_statespacei=blockspace.content; elsefor(int k=0; kBsize; k+) memory_stateki=memory_stateki-1;for(int j=i; jPsize; j+)!=if(blockk.content pagej.content) blockk.timer = 1000; else blockk.timer = j; break;position = findReplace();blockposition = pagei;memory_statepositioni=blockposition.content;int

20、 decide(string str)for(int i=0;istr.size();i+)if(stri9)return 0;break;return i;int trans(string str)int sum=0;for(int i=0;istr;a=decide(str);while(a=0)cout 输入错误 , 请重新输入！ str;a=decide(str);d=trans(str);return d;void Put()cout 请选择产生页面的方法a: 随机产生b: 输入产生 endl;coutF;while(F!=a&F!=b)coutF;if(F=a)P_String(Q

21、String) ;if(F=b)cout 请输入各页面号:endl;for(int i=0;iPsize;i+)QStringi=put();coutendl;cout|endl;void main()cout| 页 面 置 换 算 法|endl;cout|endl;int t=1;while(t) Put();YZ_replace test1;YZ_replace test3;char select;OPTJdocout请选择要应用的算法：FIFO算法LRUM法法 退出 endl;int p,q;coutselect;while(select!=0&select!=1&select!=2&s

22、elect!=3)(cout您的输入无效,请重新输入：select;) if(select=0) (cout您选择的是菜单endl; cout完成退出.endl;t=0;)if(select=1) (cout”您选择的是菜单endl; coutFIFO 算法状态:endl;test1.initia1(QString);test1.FIFO();test1.BlockClear(); coutendl;for(p=0;pBsize;p+) (for(q=0;qPsize;q+) couttest1.memory_statepq ; coutendl; ) coutendl; cout命中率:te

23、st1.s/Psizeendl; test1.YZ_replace(); coutendl; ) if(select=2) ( int i,j; K=-1; InitL(b, c);for(i=0;iPsize;i+) (Lru(QStringi,b); c0i=QStringi; for(j=0;jBsize;j+) cji=bj.num;cout您选择的是菜单endl; coutLRU 算法状态：endl;coutendl;for(i=0;iBsize;i+) (for(j=0;jPsize;j+) ( if(cij=-1) cout 0; else cout cij; cout endl

24、; coutendl;cout命中率：(Psize-(K+1)/Psize; coutt;coutendl; if(select=3) (cout您选择的是菜单endl; coutOPT算法状态:endl;test3.initia1(QString);test3.OPT();test3.BlockClear(); coutendl;for(p=0;pBsize;p+) ( for(q=0;qPsize;q+) couttest3.memory_statepq ; coutendl; coutendl;cout命中率:test3.s/Psizeendl;test3.YZ_replace(); c

25、outendl;while(select=1|select=2|select=3); 7.测试结果7.1页面选择测试:C sDocment3= and SOPH 算,上 R Hj送R产三五间式万T - = PETH1匕节；=上 生遗中的素甲星工面在间e 367Z75732 I 3一贝莺置换算法“应菜是忧 费的法图（7.2）分析：页面产生的方法有两种选择，分别是随机产生和自己输入产生，选择菜单的时候有对异常输入的处理，如果输入错误，有错误提示，当输入正确菜单的时候，选择a,自动产生页面走向，如果选择 b,自己可以任意输入，如 果输入错误，有错误提示。6.2应用算法选择测试c * C: Docme

26、 nt s and Set t mMMAdiinrL3上工七 ni: 泉画、寿 明敝.q01 OzbnjgM.ql91 . exe-图（7.3）分析：选择算法时，有异常处理，即如果输入错误，有错误提示。如果选 择菜单1,即选择了 FIFO算法，展示此算法的置换状态并显示命中率。置换状 态以二维数组的形式输出，既直观又清晰。4八L小耳至宣法 出且在 仃MJPI罩法 6A艮山请跖施九餐单目：2 您造的是菜单O 而堂法状号C : fiE3cuaent s and Setii iirtgXAdMxnL s t bt a r超明轼Ax,qu一 3u.UJI ) 算ilt 的号单,一 鬻定 应菜是世 要人

27、的法 军地胃图(7.4)分析：算法一进行完以后，界面自动跳到应用算法的选择界面，即可以再 次选择置换算法，选择菜单 2,即选择了 LRU算法，展示此算法的置换状态并 显示命中率，可以和第一个算法进行对比，找出两种算法的不同。愉中率：I；!艇瘁聚应用的算击 8FIP0算法1WWJ 脑管指五菜基号:一J33Z2Z?f?222077777777 1 1-P +gE+oril：./5.ori .注zJR青鼠A在11-话哂草：4 电单 八应林重於 ; 1口的匕TLRUt图(7.5)分析：算法二进行完以后，界面自动跳到应用算法的选择界面，即可以再次选择置换算法，选择菜单3,即选择了 OPTT法，展示此算法的置换状态并显示命中率，可以和第二个算法进行对比，找出两种算法的不同flfi7?777777| 1，中率hZt?愁择要应用的算法EL *1阳式往 OLRU算/ CMJFI葬柱 屈出ST加7遑空5 32.昭阵，申率b12选淬要应用的算往XCF1F0目.注G?L用I甲去