操作系统原理课程设计页面置换算法模拟程序.doc

《操作系统原理课程设计页面置换算法模拟程序.doc》由会员分享，可在线阅读，更多相关《操作系统原理课程设计页面置换算法模拟程序.doc（21页珍藏版）》请在三一办公上搜索。

1、数学与计算机学院课程设计说明书课 程 名 称: 操作系统原理-课程设计 课 程 代 码: 题 目: 页面置换算法模拟程序 年级/专业/班: 学 生 姓 名: 学 号: 开 始 时 间: 2010 年 月 日完 成 时 间: 2011 年 月 日课程设计成绩：学习态度及平时成绩（30）技术水平与实际能力（20）创新（5）说明书撰写质量（45）总 分（100）指导教师签名： 年 月 日 目 录 1 引 言11.1 问题的提出11.2国内外研究的现状11.3任务与分析22需求分析23开发平台23.1 开发工具23.1 开发语言24概要设计34.1 总体设计框图35详细设计45.1代码分析结果65.1

2、1 数据结构65.12 FIFO具体函数及设计实现65.13LRU具体函数及设计实现95.14调用关系图146测试146.1进入界面及产生页面走向146.2FIFO算法及查看结果156.3LRU算法及查看结果166.4继续进入主界面及产生页面走向166.5调度算法及结果177 总结与体会18参考文献19摘 要在地址映射过程中，若在页面中发现所要访问的页面不再内存中，则产生缺页中断。当发生缺页中断时操作系统必须在内存选择一个页面将其移出内存，以便为即将调入的页面让出空间。而用来选择淘汰哪一页的规则叫做页面置换算法。在进程运行过程中，若其所要访问的页面不在内存需把它们调入内存，但内存已无空闲空间时

3、，为了保证该进程能正常运行，系统必须从内存中调出一页程序或数据，送磁盘的对换区中。但应将哪个页面调出，所以需要根据一定的算法来确定。常用的算法有先进先出置换算法（FIFO）, 最近最久未使用置换算法（LRU）和最佳置换算法（OPT），该设计是在VC+6.0环境下分别用LRU和FIFO来实现页面置换算法的模拟程序，并测试。关键词：操作系统; 页面置换算法模拟; 进程调度; FIFO; LRU 1 引 言 1.1 问题的提出 随着硬件技术的发展，各式各样的大容量存储设备相继出现，一台计算机上可能存在多种外存储设备。不同存储设备有着不同的读写速度，同一种设备的读写速度有可能也会相差很大。因此在多种具

4、有不同读写速度的外存储设备的环境下，选择一种合适的页面淘汰算法，对整个系统的性能会有很大的提高。在进程运行过程中，若其所要访问的页面不在内存需把它们调入内存，但内存已无空闲空间时，为了保证该进程能正常运行，系统必须从内存中调出一页程序或数据，送磁盘的对换区中。但应将哪个页面调出，所以需要根据一定的算法来确定。如果能够很好的使用页面置换将大大节省内存的额外开销。1.2国内外研究的现状 1966年Belady在理论上提出最优页面置换算法（OPT）,此外还有先进先出（FIFO），最少使用置换算法（LRU）。不同存储设备有着不同的读写速度，同一种设备的读写速度有可能也会相差很大。因此在多种具有不同读写

5、速度的外存储设备的环境下，选择一种合适的页面淘汰算法，对整个系统的性能会有很大的提高。1.3任务与分析 本课题主要的目的是编制页面置换算法FIFO和LRU的模拟程序,并模拟其在内存的分配过程。同时根据页面走向，分别采用FIFO和LRU算法进行页面置换，统计缺页率；为简化操作，在淘汰一页时，只将该页在页表中抹去,而不再判断它是否被改写过，也不将它写回到辅存。2需求分析本程序实现了操作系统中页式虚拟存储管理中缺页中断理想型淘汰算法，该算法在访问串中将来再也不出现的或是在离当前最远的位置上出现的页淘汰掉。这样，淘汰掉该页将不会造成因需要访问该页又立即把它调入的现象。该程序能按要求随机确定内存大小，随

6、机产生页面数，进程数，每个进程的页数，给进程分配的页数等，然后运用理想型淘汰算法对每个进程进行计算缺页数，缺页率，被淘汰的序列等功能。3开发平台3.1 开发工具VC+6.03.1 开发语言VC+语言4概要设计4.1 总体设计框图 进入程序 输入页面数页面走向最少使用置换先进先出置换随即产生用户输入5详细设计 开始输入页面数0手动输入1随机产生(0)FIFO (1)OPT 输入数据输入个数输出FIFO结果输出OPT结果是否输入Y/y结束输出另外一种结果是否继续(N/n)图5.1详细设计框图开始初始化数据，确定页面走向判断页号是否等于页面流号算出内存中各个页号相对于当前位置，并置换了学校,也不免想

7、到自己明年将要离开的情景,心里也感觉到一种凄凉. 原来一直都想着要考研的,经过几个月的考虑,发现自己或许不适合考研吧,复习总是那么得不尽人意。离开了老师的约束和同学的相互促进，我发现自己学习总是静不下心来，效率一直不高。而且我觉得自己对本专业不是很感兴趣，害怕自己又浪费掉三年，而学不到什么东西。一直就这样犹豫着，从三月到六月，现在终于决定放弃我的考研路。考研或许真的就不适合我吧！ 决定不考研之后，我就面临着工作的问题，可是我拿什么来面对工作呢？回想起这几年，感觉自己真的学到的太少了。今天和一个老同学聊天，他也这么说，感觉自己在大学又白混了三年。暑假快要到了，我想在学校学点东西，可是具体的又不知

8、道学什么。又怕武汉的天气太热，学不了什么。不过怎么来说，我一定要为工作好好准备一下。的距离淘汰距离最大的那个页号，并进行换页距离是否相等比较出现的次数淘汰出现次数少的页号，并进行换页输出淘汰的页号模块结束否是是否图5.2为置换方法的流程图5.1代码分析结果5.11 数据结构int m, int need,int n, result1020,int state,int count1;5.12 FIFO具体函数及设计实现FIFO流程图开始页面大小m，页面走向放在head结果表result和状态表count赋值为-1Result是否为空有是否在页表内装入页表中，缺页次数count+不在替换出先进入结

9、果表中的页面在步数page+统计缺页数和缺页率输出过程及结果结束FIFO函数实现void FIFO(int m, int need,int n) /m分配物理页面大小，n需要页面数组的最大值int p=0; /当前请求的页面int del=0; /步数int count120;double count=0;/缺页数double que=0;/缺页率int result1020;/结果表for(int i =0;i=m;i+) for(int j=0;j=p) int k=needp; if(p0) for(int i=0;i=m;i+)resultip=resultip-1; int f1=0

10、; /首先看是否有空位置或者已经存在请求的页面 for(int i =0;i=m;i+) if(resultip=-1) resultip=k; f1=1; i=m+1; count1p=k; count=count+1; p=p+1; else if(resultip=k)f1=1;p=p+1;i=m+1; if(f1=1) continue; /这里发生替换 resultdelp=k;count1p=k;count=count+1; p=p+1;del=(del+1)%(m+1); cout*FIFO过程如下表*endl; for(int t3=0;t3=n;t3+)/输出原来的页面cou

11、tneedt3 ; coutendl; for(int t0 =0;t0=m;t0+)/判断页表是否填满 for(int t1=0;t1=n;t1+)if(resultt0t1!=-1)coutresultt0t1 ;else cout ;coutendl; for(int j1=0;j1=n;j1+)/对于缺页的打，否则打 if(count1j1!=-1) cout;else cout; coutendl;que=count/(n+1);/统计缺页次数和缺页率cout缺页次数为:countendl;cout缺页率count/n+1=queendl;cout*endl;5.13LRU具体函数及

12、设计实现LRU流程图开始页面大小m，页面走向放在head给表result和状态表state分配空间Result是否为空有是否在页表内装入页表中，缺页次数num+不在替换出最久没使用结果表中的页面在赋值给hsivek统计缺页数和缺页率输出过程及结果结束LRU函数实现void LRU(int m, int need,int n)m+;n+;int i, j, min, num = 1, k, flag;int state10, count20, hsive10;int result1020;memset(state, 0, sizeof(state);/初始化内存空间，给三个数组分配内存memse

13、t(count, -1, sizeof(count);memset(hsive, -1, sizeof(hsive);memset(result, -1, sizeof(result);for(i = 0; i n; i+)/将need数组值赋给resultresult0i = needi;cout*LRU过程如下表*endl;for(i = 0; i n; i+)flag = 0;/标志位，如果页面和页表内的熄灯则赋值for(j = 1; j num; j+)if(result0i = hsivej)flag = 1;statej = -1;break;if(flag = 0)/替换if(n

14、um = m)hsivenum = result0i;elsemin = -1;for(j = 1; j min)k = j;min = statej;hsivek = result0i;statek = -1;counti = 1;num+;for(j = 1; j = m; j+)resultji = hsivej;statej+;for(j = 0; j = m; j+)/输入个页面替换情况for(i = 0; i n; i+)if(resultji = -1)cout ;elsecout resultji ;cout endl;for(i = 0; i n; i+)if(counti

15、!= -1) cout;else cout;cout endl;/统计各页面缺页次数和缺页率cout 缺页次数为: num - 1 endl;cout 缺页率 num - 1 /n = double(num - 1) / n endl;cout*endl;主方法int main()cout * endl;cout * 页式存储管理 * endl;cout * endl;int m;int n=0;int choose=2;int need20;char flag;while(1)cout指定内存分配页面数:;while (flag9)cinflag;m=flag-0-1; flag= ;cou

16、t请选择页面序列产生方式:endl;cout (0)手动输入endl;cout (1)随机产生endl;while (flag1)cinflag; choose =flag-0;flag= ;if(choose=0)cout输入页面走向！以s结尾endl;while(1) while (flag9)&flag!=s) cinflag; if(flag=s) break; needn=flag-0; flag= ; n=n+1; flag= ;n=n-1;else coutn;n=n-1; for(int i=0;i=n;i+) needi=rand()%10; system(cls);cout

17、选择页面置换算法:endl;cout0-FIFO 1-LRUendl;while (flag1)cinflag; choose =flag-0; flag= ;if(choose=0)FIFO(m, need,n);else LRU(m, need,n); cout输入Y/y可以看另外一种置换算法的执行过程flag; if(flag=Y|flag=y) system(cls); if(choose=0)LRU(m, need,n);elseFIFO(m, need,n);else flag= ;cout输入N/n退出否则输入任意键继续flag;if(flag=N|flag=n) break;e

18、lse system(cls);flag= ;return 0;5.14调用关系图主方法模块 调用 调用LRU模块FIFO模块6测试6.1进入界面及产生页面走向运行结果如下图6.1 进入管理界面图6.2产生页面走向6.2FIFO算法及查看结果图6.3选择FIFO算法结果6.3LRU算法及查看结果图6.4选择LRU结果6.4继续进入主界面及产生页面走向图6.5按y继续回到主界面设置页面为46.5调度算法及结果图6.6选择LRU算法结果图6.7选择FIFO算法结果 7 总结与体会这个程序的主要思想就是要实现换页、怎么样输出淘汰的序列、计算缺页次数和缺页率。在程序中主要就是将在访问串中将来再也不出现

19、的或是在离当前最远的位置上出现的页淘汰掉。当距离相等的时候就比较使用的次数，淘汰使用次数较少的那页。该过程共有两个函数及实现FIFO的函数和实现LRU的函数，当主函数调用任意其中函数时来实现其算法。通过这次课程设计的实践，我能够熟练的掌握一些关于内存分配管理的一些算法。而在实现FIFO算法后，由于没能掌握LRU算法的过程导致实现时花了很多时间。在调试的过程中也出现的大多是关于内存分配和数组地址越界的问题，比如关于循环时各个数的递增，还有就是显示给个数组的内容等问题。就因为这些问题，多次造成了淘汰序列出错。在以后的实验中我会注意的。参考文献1 李善平等. Linux内核2.4版源代码分析大全. 北京：机械工业出版社，2002.12 陈莉君. 深入分析Linux内核源代码. 北京：人民邮电出版社，2002.83 陈向群 编著.操作系统教程.北京：北京大学出版社，2007.014 罗宇 等编著.操作系统课程设计.北京：机械工业出版社，2005.95 Gary Nutt.Linux操作系统内核实习. 北京：机械工业出版社，2002.1