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

《2022年设计一个虚拟存储区和内存工作区-编程序演示下述算法的具体实现过程-并计算访问命中率： .pdf》由会员分享，可在线阅读，更多相关《2022年设计一个虚拟存储区和内存工作区-编程序演示下述算法的具体实现过程-并计算访问命中率： .pdf（21页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、齐齐哈尔大学操作系统课程综合实践题目：主界面以灵活选择某算法班级：计本 093 姓名：赵明秋学号： 2009021114 指导教师：韩金库2008 年 12 月名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 21 页 - - - - - - - - - 主界面以灵活选择某算法实验摘要：计算机应用专业的学生全面了解和掌握系统软件, 一般软件设计方法和技术的必不可少的综合课程 , 也是了解计算机硬件和软件如何衔接的必经之路。我觉得此次实验最大的亮点以及不同于别人的地方就是将三

2、种页面置换算法按照课本上老师讲的方式直观简便的输出，在采用输出算法时，我摒弃了常人所用的一维数组输出法， 而别出心裁的采用了二维数组的输出算法，模拟了内存的物理块，清晰直观的表达了页面是如何在外存中被调入内存中的，以及各页面在调入过程中是否命中或在置换时又置换了内存中哪个页面。在软件工程的角度来看，我的系统具有高内聚低耦合的优点，即各种算法之间，并不影响彼此的函数调用，而在各算法的内部，内聚度很高。关键词 ：设计原理 , 设计方案 , 流程图 , 源代码，测试结果，结束语，参考文献课题运行环境操作系统： Windows XP 编程环境： Microsoft Visual C+6.0 1.1实验

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

4、 - - - - - 第 2 页，共 21 页 - - - - - - - - - 3、最佳置换算法（ OPT ）2.1运行环境1）操作系统： Windows XP 2）编程环境： Microsoft Visual C+6.03.1设计原理：3.1.1 先进先出算法（ FIFO）最简单的页面置换算法是先入先出（FIFO）法。这种算法的实质是，总是选择在主存中停留时间最长（即最老）的一页置换，即先进入内存的页，先退出内存。理由是：最早调入内存的页， 其不再被使用的可能性比刚调入内存的可能性大。建立一个 FIFO队列，收容所有在内存中的页。被置换页面总是在队列头上进行。当一个页面被放入内存时， 就

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

6、算法之间的主要差别是， FIFO算法利用页面进入内存后的名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 21 页 - - - - - - - - - 时间长短作为置换依据， 而 OPT算法的依据是将来使用页面的时间。如果以最近的过去作为不久将来的近似， 那么就可以把过去最长一段时间里不曾被使用的页面置换掉。 它的实质是， 当需要置换一页时， 选择在最近一段时间里最久没有使用过的页面予以置换。这种算法就称为最久未使用算法（Least Recently Used，LRU ）

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

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

9、用算法（Not Recently Used ，NUR ） 。它在存储分块表的每一表项中增加一个引用位，操作系统定期地将它们置为0。当某一页被访问时，由硬件将该位置1。过一段时间后，通过检查这些位可以确定哪些页使用过，哪些页自上次置 0后还未使用过。 就可把该位是 0的页淘汰出去， 因为在最近一段时间里它未被访问过。3.3.3最佳置换算法（ OPT ）最优置换（ Optimal Replacement）是在理论上提出的一种算法。其实质是：当调入新的一页而必须预先置换某个老页时，所选择的老页应是将来不再被使名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - -

10、 - - - - - 名师精心整理 - - - - - - - 第 4 页，共 21 页 - - - - - - - - - 用，或者是在最远的将来才被访问。采用这种页面置换算法， 保证有最少的缺页率。但是最优页面置换算法的实现是困难的，因为它需要人们预先就知道一个进程整个运行过程中页面走向的全部情况。不过，这个算法可用来衡量 （如通过模拟实验分析或理论分析）其他算法的优劣。该算法能保证有最低的缺页率， 所以称为最佳置换算法， 但是该算法紧紧是一种理想状况下的算法， 因为在进程实际运行过程中， 将来会执行到那儿页是不可预知的，所以无法选择该置换那个页出去。因此，本算法在实际中无法使用，只能作为

11、一种标准来衡量其他算法的性能4.1 设计方案1）主界面：设置页面产生算法选择界面和页面置换算法选择界面；2）子界面：页面产生算法分为两个界面，分别是随机产生算法和自己输入产生算法。页面置换算法分为三个子界面， 分别是先进先出算法界面、 最近最久未使用算法界面、最佳置换算法界面。5.1 流程图5.1.1 主流程图名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 21 页 - - - - - - - - - startt= =1switchfifo 算法 Case1Lru 算法

12、 Case2 Case3Opt 算法退出图（1）5.1.2 FIFO函数流程图：StartfindExist(i)findSpace()findReplace()退出图（2）5.1.3 LRU 函数流程图：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 21 页 - - - - - - - - - startGetmax()void InitL()endlval=0val=Equation(fold,b);Fbval.time=0;for(i=0;iBsize;i+) i

13、f (i!=val) bi.time+;T图（4）5.1.4 OPT 函数流程图：StartfindExist(i)findSpace()findReplace()退出图（5）6. 源代码名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 21 页 - - - - - - - - - 6.1 程序代码#include #include #include #define Bsize 3 #define Psize 12 #include using namespace std;

14、 int QStringPsize; 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 m

15、emory_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页面走向： ; for(i=0;iPsize;i+) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 21 页 - - - - - - - - - coutQStri

16、ngi ; 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; for(i=0;iPsize;i+) for(

17、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; 名师资料总结 - - -精品资料欢迎下载 - - -

18、- - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 21 页 - - - - - - - - - return -1; int 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)

19、 for(int b=0; bBsize; b+) memory_statebi=memory_statebi-1; s+; else space = findSpace(); if(space != -1) for(int b=0; bBsize; b+) memory_statebi=memory_statebi-1; blockspace = pagei; memory_statespacei=blockspace.content; else for(int b=0; bBsize; b+) memory_statebi=memory_statebi-1; 名师资料总结 - - -精品资

20、料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 21 页 - - - - - - - - - position = findReplace(); blockposition = pagei; memory_statepositioni=blockposition.content; for(int j=0; jBsize; j+) blockj.timer+; void YZ_replace:BlockClear() for(int i=0; iBsize; i+) blocki.content =

21、-1; blocki.timer = 0; typedef struct page int 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+) for(j=0;jPsize;j+) cij=-1; int GetMax(Page *b) 名师资料总结

22、 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 21 页 - - - - - - - - - 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+; else queue+K=fo

23、ld; val=GetMax(b); bval.num=fold; bval.time=0; for(i=0;iBsize;i+) if (i!=val) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12 页，共 21 页 - - - - - - - - - bi.time+; void YZ_replace:OPT() int exist,space,position ; for(int i=0; iPsize; i+) exist = findExist(i); if(exi

24、st != -1) for(int b=0; bBsize; b+) memory_statebi=memory_statebi-1; s+; else space = findSpace(); if(space != -1) for(int b=0; bBsize; b+) memory_statebi=memory_statebi-1; blockspace = pagei; memory_statespacei=blockspace.content; else for(int k=0; kBsize; k+) memory_stateki=memory_stateki-1; for(in

25、t j=i; jPsize; j+) if(blockk.content != pagej.content) blockk.timer = 1000; else blockk.timer = j; break; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 13 页，共 21 页 - - - - - - - - - position = findReplace(); blockposition = pagei; memory_statepositioni=blockposition

26、.content; int 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() 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - -

27、- - - 名师精心整理 - - - - - - - 第 14 页，共 21 页 - - - - - - - - - cout 请选择产生页面的方法 a: 随机产生 b: 输入产生 endl; coutF; while(F!=a&F!=b) coutF; if(F=a) P_String(QString) ; 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; w

28、hile(t) Put(); YZ_replace test1; YZ_replace test3; char select; do cout 请选择要应用的算法 :FIFO 算法 LRU 算法 OPT 算法 退出endl; int p,q; coutselect; while(select!=0&select!=1&select!=2&select!=3) cout 您的输入无效 , 请重新输入 :select; if(select=0) cout 您选择的是菜单 endl; cout完成退出 .endl; t=0; if(select=1) cout 您选择的是菜单 endl; coutF

29、IFO算法状态 :endl; test1.initia1(QString); test1.FIFO(); test1.BlockClear(); cout-endl; for(p=0;pBsize;p+) for(q=0;qPsize;q+) couttest1.memory_statepq ; coutendl; cout-endl; cout命中率 :test1.s/Psizeendl; test1.YZ_replace(); coutendl; if(select=2) int i,j; K=-1; InitL(b, c); for(i=0;iPsize;i+) Lru(QStringi

30、,b); c0i=QStringi; for(j=0;jBsize;j+) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 16 页，共 21 页 - - - - - - - - - cji=bj.num; cout 您选择的是菜单 endl; coutLRU算法状态 :endl; cout-endl; for(i=0;iBsize;i+) for(j=0;jPsize;j+) if(cij=-1) cout 0; else cout cij; cout endl; cout-end

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

32、; coutendl; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 17 页，共 21 页 - - - - - - - - - while(select=1|select=2|select=3); 7. 测试结果7.1 页面选择测试：图（7.1 ）图（7.2 ）分析：页面产生的方法有两种选择，分别是随机产生和自己输入产生，选择菜单的时候有对异常输入的处理，如果输入错误， 有错误提示， 当输入正确菜单的时候，选择 a，自动产生页面走向，如果选择b，自己可以任意输入，如果输入错误，有

33、错误提示。6.2 应用算法选择测试名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 18 页，共 21 页 - - - - - - - - - 图（7.3 ）分析：选择算法时，有异常处理，即如果输入错误，有错误提示。如果选择菜单 1，即选择了 FIFO 算法，展示此算法的置换状态并显示命中率。置换状态以二维数组的形式输出，既直观又清晰。图（7.4 ）分析：算法一进行完以后， 界面自动跳到应用算法的选择界面，即可以再次选择置换算法，选择菜单2，即选择了 LRU算法，展示此算法的置换状态并

34、显示命中率，可以和第一个算法进行对比，找出两种算法的不同。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 19 页，共 21 页 - - - - - - - - - 图（7.5 ）分析：算法二进行完以后， 界面自动跳到应用算法的选择界面，即可以再次选择置换算法，选择菜单3，即选择了 OPT算法，展示此算法的置换状态并显示命中率，可以和第二个算法进行对比，找出两种算法的不同。图（7.6 ）分析：算法二进行完以后，界面自动跳到应用算法的选择界面，即可以再次选择置换算法，选择菜单3，即选择

35、了 OPT 算法，展示此算法的置换状态并显名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 20 页，共 21 页 - - - - - - - - - 示命中率，可以和第二个算法进行对比，找出两种算法的不同。8. 结束语为期两周的操作系统课设在不断的探索、尝试、成功中结束了。现在，站在成功地峰顶， 回顾着走过的一路， 真是什么感觉都有， 枯燥、失败、劳累、迷茫、喜悦，应该说，我的设计体会相当深刻。首先，谈谈本系统的不足：我设计的页面值换算法里， 页面个数和内存个数是一个定数，在这一点上

36、没有实现与操作员的交互， 即页面数和内存个数并不能手动输入，我设计的系统在界面上并没有太大的优化，没有实现选择算法后可以重新选择页面产生的算法，重新进行页面置换的选择。 总体上来说， 这两方面是本系统可以改进的地方，虽然我的课设已经验收， 但是我在验收完成后， 继续完善了我的整个界面并改进了系统的不足之处，以达到系统的完整性，简洁性，交互性。其次，谈谈本系统特色、新的发明、创造等最后，在整体上自我评价一下我的系统：第一，在功能上，它完全实现了各种页面置换算法的模拟；第二，在界面设计上，新颖独特，独树一帜，采用了二维数组的输出方法了；第三，异常处理面面俱到，不需要担心因为输入错误而出现乱码，甚至

37、重新执行。在此课设期间我为自己总结了四句话：鄙视平庸和碌碌无为， 敢于主张自己并坚持不懈，用于忍耐寂寞、枯燥和劳累，善于探求登峰捷径且百折不挠。最最后，也是我最想说的话， 衷心地感谢李新荣老师对我的悉心指导和最大的信任。9.1 参考文献1 计算机操作系统哲凤屏汤子瀛西安电子科技大学出版社.2011 年 2 月2 C语言程序设计教程 （第三版）谭浩强张基温高级教育出版社.2008 年 4 月3 程序设计基础 （第二版）吴文虎清华大学出版社.2010 年 2 月4 C+程序设计刘娜娜北京航空大学出版社.2008 年 4 月名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 21 页，共 21 页 - - - - - - - - -