MicrosoftVisualC6.0的环境下操作系统课程设计报告书

1、. . . . 目 录1 1引言引言 1 11.1 编写目的 11.2 设计容 11.3 设计原理 11.3.1 先进先出算法（FIFO）11.3.2 最优置换算法（OPT）11.3.3 最近最久未使用算法（LRU）21.4 运行环境 22 2设计方案设计方案 3 32.1 模块划分 32.3 模块调用关系图 32.4 模块流程图 32.4.1 主函数流程图 32.4.2 FIFO 函数流程图 42.4.3 LRU 函数流程图 52.4.4 OPT 函数流程图 53 3源代码源代码 6 63.1 程序代码 64 4测试结果测试结果 16164.1 页面选择测试 164.2 应用算法选择测试 1

2、65 5总结总结 18186 6程序使用说明书程序使用说明书 19197 7参考文献参考文献 1919. . . . 1 / 211 1引言引言1.11.1 编写目的编写目的在 Microsoft Visual C+6.0 的环境下用 C+语言编写程序，实现操作系统中页面在存与外存中如何置换的问题。1.21.2 设计容设计容设计一个虚拟存储区和存工作区,编程序演示下述算法的具体实现过程,并计算访问命中率。设计要求：主界面以灵活选择某算法，且以下算法都要实现1、先进先出算法（FIFO）2、最近最久未使用算法（LRU）3、最佳置换算法（OPT）1.31.3 设计原理设计原理1.3.11.3.1 先

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

4、增加了。当然，导致这种异常现象的页面走向实际上是很少见的。1.3.21.3.2 最优置换算法（最优置换算法（OPTOPT）最优置换（Optimal Replacement）是在理论上提出的一种算法。其实质是：当调入新的一页而必须预先置换某个老页时，所选择的老页应是将来不再被使用，或者是在最远的将来才被访问。采用这种页面置换算法，保证有最少的缺页率。但是最优页面置换算法的实现是困难的，因为它需要人们预先就知道一个进程整个运行过程中页面走向的全部情况。不过，这个算法可用来衡量（如通过模拟实验分析或理论分析）其他算法的优劣。. . . . 2 / 211.3.31.3.3 最近最久未使用算法（最近最

5、久未使用算法（LRULRU）FIFO 算法和 OPT 算法之间的主要差别是，FIFO 算法利用页面进入存后的时间长短作为置换依据，而 OPT 算法的依据是将来使用页面的时间。如果以最近的过去作为不久将来的近似，那么就可以把过去最长一段时间里不曾被使用的页面置换掉。它的实质是，当需要置换一页时，选择在最近一段时间里最久没有使用过的页面予以置换。这种算法就称为最久未使用算法（Least Recently Used，LRU） 。LRU 算法是与每个页面最后使用的时间有关的。当必须置换一个页面时，LRU 算法选择过去一段时间里最久未被使用的页面。LRU 算法是经常采用的页面置换算法，并被认为是相当好的

6、，但是存在如何实现它的问题。LRU 算法需要实际硬件的支持。其问题是怎么确定最后使用时间的顺序，对此有两种可行的办法：（1）计数器。最简单的情况是使每个页表项对应一个使用时间字段，并给 CPU 增加一个逻辑时钟或计数器。每次存储访问，该时钟都加1。每当访问一个页面时，时钟寄存器的容就被复制到相应页表项的使用时间字段中。这样我们就可以始终保留着每个页面最后访问的“时间” 。在置换页面时，选择该时间值最小的页面。这样做，不仅要查页表，而且当页表改变时（因 CPU 调度）要维护这个页表中的时间，还要考虑到时钟值溢出的问题。（2）栈。用一个栈保留页号。每当访问一个页面时，就把它从栈中取出放在栈顶上。这

7、样一来，栈顶总是放有目前使用最多的页，而栈底放着目前最少使用的页。由于要从栈的中间移走一项，所以要用具有头尾指针的双向链连起来。在最坏的情况下，移走一页并把它放在栈顶上需要改动6个指针。每次修改都要有开销，但需要置换哪个页面却可直接得到，用不着查找，因为尾指针指向栈底，其中有被置换页。因实现 LRU 算法必须有大量硬件支持，还需要一定的软件开销。所以实际实现的都是一种简单有效的 LRU 近似算法。一种 LRU 近似算法是最近未使用算法（Not Recently Used，NUR） 。它在存储分块表的每一表项中增加一个引用位，操作系统定期地将它们置为0。当某一页被访问时，由硬件将该位置1。过一段

8、时间后，通过检查这些位可以确定哪些页使用过，哪些页自上次置0后还未使用过。就可把该位是0的页淘汰出去，因为在最近一段时间里它未被访问过。1.41.4 运行环境运行环境操作系统：Windows XP编程环境：Microsoft Visual C+6.02 2设计方案设计方案2.12.1 模块划分模块划分主界面：. . . . 3 / 21设置页面产生算法选择界面和页面置换算法选择界面；子界面：页面产生算法分为两个界面，分别是随机产生算法和自己输入产生算法。页面置换算法分为三个子界面，分别是先进先出算法界面、最近最久未使用算法界面、最佳置换算法界面。2.32.3 模块调用关系图模块调用关系图Mai

9、n() void OPT(); void Lru(int fold,Page *b)void FIFO(); int findExist(int curpage); int findReplace()int findSpace(); int findSpace(); int findReplace(); int findExist(int curpage) int Equation(int fold,Page *b) void InitL(Page *b,int cBsizePsize) int GetMax(Page *b) 图 212.42.4 模块流程图模块流程图2.4.12.4.1 主

10、函数流程图主函数流程图. . . . 4 / 21startt= =1switchfifo算法 Case1Lru算法 Case2 Case3Opt算法退出 图 222.4.2FIFO2.4.2FIFO 函数流程图函数流程图StartfindExist(i)findSpace() findReplace()退出图 23. . . . 5 / 212.4.3LRU2.4.3LRU 函数流程图函数流程图startGetmax()void InitL()endlval=0val=Equation(fold,b);Fbval.time=0; for(i=0;iBsize;i+) if (i!=val)

11、bi.time+;T图 242.4.4OPT2.4.4OPT 函数流程图函数流程图StartfindExist(i)findSpace() findReplace()退出图 25. . . . 6 / 213 3源代码源代码3.13.1 程序代码程序代码#include #include #include#define Bsize 3#define Psize 12#includeusing namespace std;int QStringPsize;int Num=0;struct pageInfor int content;/页面号 int timer;/被访问标记 ;class YZ_

12、replacepublic: YZ_replace(); /构造函数 YZ_replace(); /析构函数 int findSpace(); /查找是否有空闲存 int findExist(int curpage); /查找存中是否有该页面 int findReplace(); /查找应予置换的页面 void FIFO(); /FIFO 算法 void OPT(); void BlockClear(); /BLOCK 恢复 void initia1(int string);/初始化 pageInfor *block; /物理块 pageInfor *page; /页面号串 int memor

13、y_stateBsizePsize; int s;private:;void P_String(int QString) /随机产生页面的各个数 int i; srand(unsigned)time(NULL); . . . . 7 / 21 for(i=0;iPsize;i+) QStringi=rand()*9/RAND_MAX+1; cout页面走向：; for(i=0;iPsize;i+)/输出各个数 coutQStringi ; coutendl;YZ_replace:YZ_replace()/构造函数初始化 Block，s=0; block = new pageInforBsize

14、; 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(j=0;jBsize;j+) memory_stateji=0;YZ_replace:YZ_replace() s=0;int Y

15、Z_replace:findSpace()/查找是否有空闲存 for(int i=0; iBsize; i+) if(blocki.content = -1) return i;/找到空闲存，. . . . 8 / 21 return -1;int YZ_replace:findExist(int curpage)/查找存中是否有该页面 for(int i=0; iBsize; i+) if(blocki.content = pagecurpage.content)/找到存中有该页面，返回 BLOCK 中位置 return i; return -1;int YZ_replace:findRep

16、lace()/查找先进先出算法中应予置换的页面 int pos = 0; for(int i=0; i= blockpos.timer) /找到应予置换页面，返回 BLOCK 中位置 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

17、+;/记录命中数的变量加 1 else space = findSpace(); if(space != -1)/存中有空闲 for(int b=0; bBsize; b+) memory_statebi=memory_statebi-1;/将第一列的数组复制到第二列 blockspace = pagei;. . . . 9 / 21 memory_statespacei=blockspace.content; else/存中没有空闲 for(int b=0; bBsize; b+) memory_statebi=memory_statebi-1; position = findReplace

18、();/找到要置换的位置 blockposition = pagei; memory_statepositioni=blockposition.content; for(int j=0; jBsize; j+) blockj.timer+;/BLOCK 中所有页面 TIMER+ void YZ_replace:BlockClear()/BLOCK 恢复 for(int i=0; iBsize; i+) blocki.content = -1; blocki.timer = 0; typedef struct page int num; /*记录页面号*/ int time; /*记录调入存时间

19、*/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+) . . . . 10 / 21 bi.num=-1; bi.time=Psize-i-1; for(i=0;iBsize;i+) for(j=0;jPsi

20、ze;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+; . . . . 11 / 21 else queue+K=fold;/*记录调入页面

21、*/ val=GetMax(b); bval.num=fold; bval.time=0; for(i=0;iBsize;i+) if (i!=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+;/命中次数加 1else/存中不存在该

22、页面 space = findSpace();/查找是否有空闲存if(space != -1)/有空闲存for(int b=0; bBsize; b+)memory_statebi=memory_statebi-1;blockspace = pagei;/页面调入存memory_statespacei=blockspace.content;elsefor(int k=0; kBsize; k+)memory_stateki=memory_stateki-1; for(int j=i; jPsize; j+). . . . 12 / 21 if(blockk.content != pagej.c

23、ontent) blockk.timer = 1000; /将来不会用，设置 TIMER 为一个很大数 else blockk.timer = j; break; position = findReplace(); blockposition = pagei; memory_statepositioni=blockposition.content;int decide(string str) /判断输入数据是否为整型for(int i=0;istr.size();i+) if(stri9)return 0;break;return i;int trans(string str) /将字符串转换

24、成数字int sum=0;for(int i=0;istr;a=decide(str);while(a=0). . . . 13 / 21cout输入错误,请重新输入！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(QString) ; if(F=b) cout请输入各页面号:endl;for(int i=0;iPsize;i+)QStringi=put(

25、); coutendl; cout|-|endl;void main() cout|-页 面 置 换 算 法-|endl; cout|-|endl; int t=1; while(t) Put(); YZ_replace test1; YZ_replace test3;. . . . 14 / 21 char select; do cout请选择要应用的算法:FIFO 算法 LRU 算法 OPT 算法 退出endl; int p,q; coutselect; while(select!=0&select!=1&select!=2&select!=3) cout您的输入无

26、效,请重新输入:select; if(select=0) cout您选择的是菜单endl; cout完成退出.endl; t=0; if(select=1) cout您选择的是菜单endl; coutFIFO 算法状态: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; te

27、st1.YZ_replace(); coutendl; if(select=2) int i,j; K=-1; InitL(b, c); for(i=0;iPsize;i+). . . . 15 / 21 Lru(QStringi,b); c0i=QStringi;/*记录当前的存单元中的页面*/ for(j=0;jBsize;j+) 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 co

28、ut cij; cout endl; cout-endl; 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/Psizee

29、ndl; test3.YZ_replace(); coutendl;. . . . 16 / 21 while(select=1|select=2|select=3); 4 4测试结果测试结果4.14.1 页面选择测试页面选择测试图 41图 42分析：页面产生的方法有两种选择，分别是随机产生和自己输入产生，选择菜单的时候有对异常输入的处理，如果输入错误，有错误提示，当输入正确菜单的时候，选择 a，自动产生页面走向，如果选择 b，自己可以任意输入，如果输入错误，有错误提示。4.24.2 应用算法选择测试应用算法选择测试图 43分析：选择算法时，有异常处理，即如果输入错误，有错误提示。如果选择菜单

30、 1，即选择了 FIFO 算法，展示此算法的置换状态并显示命中率。置换状态以二维数组的形式输出，既直观又清晰。. . . . 17 / 21图 44分析：算法一进行完以后，界面自动跳到应用算法的选择界面，即可以再次选择置换算法，选择菜单 2，即选择了 LRU 算法，展示此算法的置换状态并显示命中率，可以和第一个算法进行对比，找出两种算法的不同。图 45分析：算法二进行完以后，界面自动跳到应用算法的选择界面，即可以再次选择置换算法，选择菜单 3，即选择了 OPT 算法，展示此算法的置换状态并显示命中率，可以和第二个算法进行对比，找出两种算法的不同。. . . . 18 / 21图 46分析：算法三进行完以后，界面自动跳到应用算法的选择界面，选择 0，可以退出此系统，显示完成退出。5 5总结总结为期两周的操作系统课设在不断的探索、尝试、成功中结束了。现在，站在成功地峰顶，回顾着走过的一路，真是什么感觉都有，枯燥、失败、劳累、迷茫、喜悦，应该说，我的设计体会相当深刻。首先，谈谈本系统的不足：第一，我设计的页面值换算法里，页面个数