请求页式管理缺页中断模拟设计FIFO,OPT

1、学 号： 0121110340232课 程 设 计题 目系统软件开发实训A学 院计算机科学与技术学院专 业计算机科学与技术专业班 级计算机1102班姓 名田蓝指导教师 李玉强2014年1月13日课程设计任务书学生姓名： 田蓝 专业班级： 计算机1102班 指导教师： 李玉强 工作单位： 计算机科学与技术学院 题 目: 请求页式管理缺页中断模拟设计-FIFO、OPT初始条件：1预备内容：阅读操作系统的内存管理章节内容，了解有关虚拟存储器、页式存储管理等概念，并体会和了解缺页和页面置换的具体实施方法。2实践准备：掌握一种计算机高级语言的使用。要求完成的主要任务: （包括课程设计工作量及其技术要求，

2、以及说明书撰写等具体要求）1实现指定淘汰算法。能够处理以下的情形： 能够输入给作业分配的内存块数； 能够输入给定的页面，并计算发生缺页的次数以及缺页率； 缺页时，如果发生页面置换，输出淘汰的页号。2设计报告内容应说明： 课程设计目的与功能； 需求分析，数据结构或模块说明(功能与框图)； 源程序的主要部分； 测试用例，运行结果与运行情况分析； 自我评价与总结。时间安排：设计安排3周：查阅、分析资料 1天系统软件的分析与建模 4天系统软件的设计 5天系统软件的实现 3天撰写文档 1天课程设计验收答辩 1天设计验收安排：设计周的第三周的指定时间到实验室进行上机验收。设计报告书收取时间：课程设计验收答

3、辩完结时。（注意事项：严禁抄袭，一旦发现，抄与被抄的一律按0分记）指导教师签名： 2013 年 12 月 10日系主任（或责任教师）签名： 2013 年 12 月 10日请求页式管理缺页中断模拟设计FIFO、OPT1课程设计目的与功能 1.1设计目的 结合操作系统所学内存页式管理章节，掌握虚拟内存设计的重要性，熟悉和掌握请求分页式存储管理的实现原理，通过分析、设计和实现页式虚拟存储管理缺页中断的模拟系统，重点掌握当请求页面不在内存而内存块已经全部被占用时的替换算法（主要通过FIFO和OPT实现），并考察替换算法的评价指标缺页次数和缺页率，得到每次淘汰的页面。高级语言设计并实现出的结果程序要能够

4、很好地显示页面调入和替换详细信息,能够输入要访问的页面的顺序，及能够输入给作业分配的内存块数。1.2初始条件及可发环境 1.2.1初始条件 1预备内容：阅读操作系统的内存管理章节内容，了解有关虚拟存储器、页式存储管理等概念，并体会和了解缺页和页面置换的具体实施方法。2实践准备：掌握一种计算机高级语言的使用。 1.2.2开发环境 （1）使用系统：Windows 7（2）使用语言：java（3）开发工具：eclipse1.3功能实现 设计的结果程序能实现FIFO、OPT算法模拟页式存储管理缺页中断，主要能够处理以下的情形：(1) 用户能够输入给定分配的内存块数；(2) 用户输入给定的页面，并计算发

5、生缺页的次数、缺页率及淘汰页面次序；（3） 缺页时，如果发生页面置换，输出淘汰的页号；(4) 程序可随机生成页面序列，或用户输入；（5）能够显示分配的内存块数的存储情况2需求分析及设计说明 2.1需求分析 由于纯页式存储管理提高了内存的利用效率，但并不为用户提供虚存，并且会产生磁盘碎片问题。用户程序将受到物理内存大小的限制。而虚存的存储管理技术请求分页存储管理技术和请求分段技术，则很好的解决了这个问题。该设计虚拟实现请求分页管理（只实现FIFO和OPT）。请求分页系统是在分页系统的基础上，增加了请求调页功能和页面置换功能所形成的页式虚拟存储系统。它允许只装入部分页面的程序和数据，便启动运行。以

6、后，再通过调页功能和页面置换功能，陆续把即将要运行的页面调入内存，同时把暂时不运行的页面换出到外存上，置换时以页面为单位。实现将程序正在运行时所需的但尚未在内存的页面调入内存，再将内存中暂时不用的页面从内存置换到外存磁盘上。而我选择的是FIFO,OPT调度算法。主要考虑三种情况：1.不缺页，此时我不需要从外存中调入新的页面进入内存；2.缺页，但是内存空间块数没有满，不需要淘汰内存中的页面，把缺页的页面直接调入内存中；3.缺页，但是内存空间已经满了，访问页面时需要淘汰旧的的页面，从外存中调入新的页面进入内存中。请求分页的具体实现过程如图1图1请求分页流程图 2.2设计说明 2.2.1算法分析在进

7、程运行过程中，若其所要访问的页面不在内存，需要把它们调入内存，但已无空闲已空闲空间时，为了保证该进程能正常运行，系统必须从内存中调出一页程序或数据，送磁盘的对换区。但应将哪个页面调出，必须根据替换算法来确定。该设计采用的是常见置换算法中的先进先出(FIFO)、理想型淘汰算法OPT(Optimal Replacement Algorithm）。详细算法原理如下：FIFO(先进先出算法)基本思想：总是选择在内存驻留时间最长的一页将其淘汰，因为最早调入内存的页，不再被使用的可能性比近期调入内存的大。该算法实现简单，只需要把一个进程调入内存的页面，按先后次序连结成一个队列，并设置一个指针，称为替换指针

8、，使它总是指向最老的页面。但是该算法与进程实际运行的规律不相适应，因为在进程中，有些页面经常被访问，比如有全局变量、常用函数，例程等的页面，FIFO算法并不能保证这些页面不被淘汰。使用FIFO替换算法效率比较低，可能会比理想型算法要多出一倍。低的原因是：基于处理器按线性顺序访问地址空间这一假设。事实上，许多时候，处理器不是按线性顺序访问地址空间的。例如，执行循环结构的程序段。使用FIFO算法时，在未给进程或作业分配足够它所需要的页面数时，有时会出现分配的页面数增，缺页次数反而增加的现象（Belady现象）。 例如针对请求序列：1 2 3 4 1 2 5 1 2 3 4 5，若分配3个可用内存块

9、，使用FIFO算法，一共会缺页9次，缺页率：75%；而如果分配4个可用内存块，则一共会缺页10次，缺页率：83.3%。OPT(理想型淘汰算法)基本思想：当要调入一新页而必须淘汰一旧页时，所淘汰的页是以后不再使用的，或者是以后相当长的时间内不会使用的。采用理想型替换算法，通常可保证获得最低的缺页率。但是由于人们目前无法预知一个进程在内存的若干个页面中，哪个页面是未来最长时间内不再被访问的，因而该算法是无法实现的，但是在模拟设计中，由于是事先给定一个页面序列，即知道各个时刻以前和以后的页面出现情况，所以可实现该算法。在实际系统中，虽无法实现理想型淘汰算法，但是可用它来评价其他替换算法。2.2.2数

10、据结构 主函数运用两个数组a、b,数组a用于存放输入的待处理页面号，b数组用于记录内存中页面的置换情况。 FIFO（先来先出算法）：将每次进入的页面往数组b的最后添加，当缺页发生时，则淘汰b0即可。定义两个变量：是否缺页的变量f：f=0时：表示不缺页，不需要淘汰页面；f=1时，表示缺页。而缺页时又需要分两种情况，这时定义另一个变量v，来表示缺页时，内存是否有空余：v=1时：表示发生缺页，但是内存空间有空余，不需要淘汰页面，直接把缺页的页面号调入内存中；v=0时：表示发生缺页，但是内存空间已经满了，需要淘汰页面，再把缺页的页面号调入内存中。 OPT（理想型淘汰算法）：也是运用两个跟FIFO算法中

11、一样含义的数组a,b.不缺页的情况和缺页，但是内存空间有空余的情况的实现跟FIFO一样的，但是主要的区别是缺页但是空间已满，需要淘汰页面的情况，OPT中淘汰页面的算法比FIFO中较复杂。运用了HashMap，通过来记录内存空间数组b中的每一个元素在a中即将访问的页面号中对应的最远的位置，以便来确定a中在内存空间的但未被访问的页面的最远的页面号的距离。也通过一个返回类型为HashMap的函数：compare（a，b，i）来实现求得对应的最远距离的元素，从何确定应该淘汰内存中的哪一个页面。在OPT中也定义两个变量：是否缺页的变量f：f=0时：表示不缺页，不需要淘汰页面；f=1时，表示缺页。而缺页时

12、又需要分两种情况，这时定义另一个变量v，来表示缺页时，内存是否有空余：v=1时：表示发生缺页，但是内存空间有空余，不需要淘汰页面，直接把缺页的页面号调入内存中；v=0时：表示发生缺页，但是内存空间已经满了，需要淘汰页面，再把缺页的页面号调入内存中。3源程序的主要部分3.1主函数输入输出部分：public static void main(String arge) throws IOExceptionSystem.out.print(请输入页面使用列表,以空格分开:); Scanner sc = new Scanner(System.in); String input = sc.nextLine

13、(); String aList = input.split(s); int aFIFO = new intaList.length; int aOPT = new intaList.length; try for( int strIndex = 0; strIndex aList.length; strIndex+ ) aFIFOstrIndex = Integer.valueOf( aListstrIndex); aOPTstrIndex = Integer.valueOf( aListstrIndex); catch(Exception e) System.out.println(输入的

14、必须是数字,请重新开始！); System.exit(0); System.out.print( 请输入内存空间大小: ); Scanner bsc = new Scanner(System.in); int bLength = bsc.nextInt(); System.out.println( bLength );if( bLength = 0 )System.out.println( 内存空间输入错误，当前输入为0 ); System.exit(0); int bFIFO = new intbLength;int bOPT = new intbLength;for( int bIndex

15、 = 0; bIndex bLength; bIndex+ )bFIFObIndex = -2;bOPTbIndex = -2;Person person = new Person();System.out.println( FIFO );person.fifo(aFIFO, bFIFO); System.out.println(nOPT);person.opt(aFIFO, bOPT);3.2 FIFO主要代码：public void fifo( int a, int b ) int count = 0; /用来记录缺页的次数int n = a.length;int m = b.length

16、;int i,j,f,v;for( i = 0; i n; i+ )f = 1; /f=1：表示缺页，需要淘汰页面；f=0：表示不缺页v = 0; /v=1：表示发生缺页！内存有空余，可直接调入内存；v=0；发生缺页，内存空间已满，需要淘汰页面for( j = 0; j m; j+ )if( bj = ai ) /表示不缺页f = 0;if( bj = -2) /b【j】的初始值为-2，表示发生缺页，但内存有空余 v = 1;break;if( f = 0 )System.out.println( 不缺页 ); else if( v = 1 ) System.out.print(ai + );

17、System.out.println(发生缺页！内存有空余，可直接调入内存);bj =a i;count+; else System.out.print(ai);System.out.print(发生缺页! 淘汰页面为： + b0); /每次发生缺页时都淘汰b0/*淘汰页面的过程，因为缺页时都淘汰b0，故淘汰页面时将b1m-1向前移动，即bj=bj+1 * 而把新调入内存的页面号加入到数组的最后一个元素b【m-1中*/System.out.println();for(j=0;jm-1;j+)bj=bj+1; bm-1=ai;count+;System.out.print(内存空间的存储情况为：

18、 );for( int t = 0; t b.length; t+ )System.out.print(bt + );System.out.println( );double rate = (double)count/n;System.out.println(发生缺页的次数: + count);System.out.println(缺页率为： + rate);3.3 OPT主要代码：public void opt(int a,int b)int count = 0; /用来记录缺页的次数int n = a.length;int m = b.length;int i,j,f,v; for( i

19、= 0; i n; i+ )f = 1;v = 0;for( j = 0; j m; j+ ) if( bj = ai) f = 0;if( bj = -2 ) v = 1;break;if( f = 0 ) System.out.println(不缺页);else if( v = 1 ) System.out.print( ai + );System.out.println( 发生缺页！内存有空余，可直接调入内存 );bj = ai;count+;elseint distance = 0; /表示b中的所有元素中在a中最远的的下标int bFarEstIndex = 0; /表示要淘汰的页面

20、在b中的下标HashMap targetMap = compare( b, a, i );for( int bIndex = 0; bIndex b.length; bIndex+ )if( targetMap.get( bbIndex ) = 0 ) /表示bbIndex在a未被访问的页面号中再也不会出现，直接淘汰，跳出循环System.out.print( ai );System.out.println( 发生缺页! 淘汰页面为： + bbIndex );bbIndex = a i;count+;break; else if( distance targetMap.get( bbIndex

21、 ) )bFarEstIndex = bIndex;distance = targetMap.get( bbIndex );if( distance != 0 )System.out.print( ai );System.out.println( 发生缺页! 淘汰页面为： + bbFarEstIndex);count+;bbFarEstIndex = ai;System.out.print( 内存空间的存储情况为： );for( int t = 0; t b.length; t+ )System.out.print(bt + );System.out.println( );double rat

22、e = (double)count/n;System.out.println(发生缺页的次数: + count);System.out.println(缺页率为： + rate);/*aIndex是指a中即将要访问的的页面号的下标， * compare()函数运用HashMap，通过它的key，value值来求内存空间数组b中的每一个元素在a中即将被访问的页面号中的各自最远的的位置， * key对应着bNum，而value值对应着最远距离。即bNum中记录着b中每个元素在a中的最远距离*/public HashMap compare( int b, int a ,int aIndex )Has

23、hMap targetMap = new HashMap();for( int bNum : b ) targetMap.put( bNum , 0 ); /for( int index = aIndex+1 ; index a.length; index+ )int aTemp = aindex; /依次把a中即将要访问的的页面号后面未被访问的页面号赋给aTempfor( int bNum : b ) /遍历数组b，把b每个元素的再即将访问的a中的最远距离放入其元素bNum中if( bNum = aTemp )targetMap.put( bNum , index );/把对应的最远下标放入

24、bNum中return targetMap;4 测试用例，运行结果与运行情况分析1. 输入的页面号为：1 2 3 4 1 2 5 1 2 3 4 5内存空间块数：4输出结果为：2.输入的页面号为：1 2 3 4 1 2 5 1 2 3 4 5内存空间块数：4输出结果为：2. 输入的页面号为：2 3 4 5 1 2 3 4 1 5内存空间块数：3输出结果为：5 自我评价与总结 本周我们进行了系统软件开发实训的课程设计，在拿到题目以后便着手准备，通过查阅课本和相关的资料，对本次课程设计要实现的功能有了深刻的了解，在此基础上写起实验代码变得心应手。现将本次课程设计总结如下：本次课程设计顺利的实现了对

25、页面置换算法FIFO和OPT的模拟演示。通过本次课程设计,加深了对操作系统的认识,了解了操作系统中各种资源分配算法的实现,特别是对虚拟存储,页面置换有了深入的了解,并且用java来实现了该实验，提高了自己的编程能力，同时也使自己对java的熟悉能力提高了很多。页面置换算法FIFO和 OPT理解起来相当容易，但在实际编程实现的时候需要注意各种细节，需要耐心细致，实际编程中遇到一些细节上的小问题确实需要仔细考虑才行。从实验结果分析可知，OPT置换算法的效率要高于FIFO置换算法，这也符合理论分析。遗憾的是，OPT算法无法在操作系统中实现，因为它要求必须预先知道每一个进程的访问串。本次课程设计中的不

26、足之处在于所采用的数据结构不够合理，输入的页面序列是保存在一个数组中，有最大长度的限制，应该采用像动态链表等数据结构，减少静态方法的限制。通过这次课程设计，进一步的加深了对课本上知识的理解和掌握，更深的体会到了操作系统的构造性能在计算机系统中的重要性，更深贴的体会到了实践的重要性，只有将在课堂上学到的知识融入于实践中，才能锻炼我们的思维能力、培养我们学以致用灵感，在以后的学习中，在学好理论知识的同时，我会更加重视每一次实验，使自己能更好的将知识用于实践中。最后，感谢在课程设计过程中给予我帮助的同学和在检查验收过程中提出本次课程设计中不足之处的老师，是你们的帮助和指正让我明白的自己的不足，谢谢你

27、们!本科生课程设计成绩评定表班级：计算机1102班姓名：田蓝学号：0121110340232序号评分项目满分实得分1学习态度认真、遵守纪律102设计分析合理性103设计方案正确性、可行性、创造性204设计结果正确性405设计报告的规范性106设计验收10总得分/等级评语：注：最终成绩以五级分制记。优（90-100分）、良（80-89分）、中（70-79分）、及格（60-69分）、60分以下为不及格指导教师签名：2014 年月日附件：源代码：import java.io.*;import java.util.HashMap;import java.util.Scanner;public clas

28、s Person /先入先出的调度算法过程public void fifo( int a, int b ) int count = 0; /用来记录缺页的次数int n = a.length;int m = b.length;int i,j,f,v;for( i = 0; i n; i+ )f = 1; /f=1：表示缺页，需要淘汰页面；f=0：表示不缺页v = 0; /v=1：表示发生缺页！内存有空余，可直接调入内存；v=0；发生缺页，内存空间已满，需要淘汰页面for( j = 0; j m; j+ )if( bj = ai ) /表示不缺页f = 0;if( bj = -2) /b【j】的

29、初始值为-2，表示发生缺页，但内存有空余 v = 1;break;if( f = 0 )System.out.println( 不缺页 ); else if( v = 1 ) System.out.print(ai + );System.out.println(发生缺页！内存有空余，可直接调入内存);bj =a i;count+; else System.out.print(ai);System.out.print(发生缺页! 淘汰页面为： + b0); /每次发生缺页时都淘汰b0/*淘汰页面的过程，因为缺页时都淘汰b0，故淘汰页面时将b1m-1向前移动，即bj=bj+1 * 而把新调入内存的

30、页面号加入到数组的最后一个元素b【m-1中*/System.out.println();for(j=0;jm-1;j+)bj=bj+1; bm-1=ai;count+;System.out.print(内存空间的存储情况为： );for( int t = 0; t b.length; t+ )System.out.print(bt + );System.out.println( );double rate = (double)count/n;System.out.println(发生缺页的次数: + count);System.out.println(缺页率为： + rate);/最佳调度算法

31、public void opt(int a,int b)int count = 0; /用来记录缺页的次数int n = a.length;int m = b.length;int i,j,f,v; for( i = 0; i n; i+ )f = 1;v = 0;for( j = 0; j m; j+ ) if( bj = ai) f = 0;if( bj = -2 ) v = 1;break;if( f = 0 ) System.out.println(不缺页);else if( v = 1 ) System.out.print( ai + );System.out.println( 发生

32、缺页！内存有空余，可直接调入内存 );bj = ai;count+;elseint distance = 0; /表示b中的所有元素中在a中最远的的下标int bFarEstIndex = 0; /表示要淘汰的页面在b中的下标HashMap targetMap = compare( b, a, i );for( int bIndex = 0; bIndex b.length; bIndex+ )if( targetMap.get( bbIndex ) = 0 ) /表示bbIndex在a未被访问的页面号中再也不会出现，直接淘汰，跳出循环System.out.print( ai );System

33、.out.println( 发生缺页! 淘汰页面为： + bbIndex );bbIndex = a i;count+;break; else if( distance targetMap.get( bbIndex ) )bFarEstIndex = bIndex;distance = targetMap.get( bbIndex );if( distance != 0 )System.out.print( ai );System.out.println( 发生缺页! 淘汰页面为： + bbFarEstIndex);count+;bbFarEstIndex = ai;System.out.pr

34、int( 内存空间的存储情况为： );for( int t = 0; t b.length; t+ )System.out.print(bt + );System.out.println( );double rate = (double)count/n;System.out.println(发生缺页的次数: + count);System.out.println(缺页率为： + rate);/*aIndex是指a中即将要访问的的页面号的下标， * compare()函数运用HashMap，通过它的key，value值来求内存空间数组b中的每一个元素在a中即将被访问的页面号中的各自最远的的位置， * key对应着bNum，而value值对应着最远距离。即bNum中记录着b中每个元素在a中的最远距离*/public HashMap compare( int b, int a ,int aIndex )HashMap targetMap = new HashMap();for( int bNum : b ) targetMap.put( bNum , 0 ); /for( int index = aIndex+1 ; index a.