页面置换算法演示教辅工具

毕业设计（论文）题目页面置换算法演示教辅系统学院软件学院专业名称软件工程班级学号11205128学生姓名指导教师二O一五年六月摘要操作系统是计算机里面重要的系统软件之一，而页面置换算法是操作系统里面一个比较重要的知识点，所以学好这一章的内容必然重要，由于无法实际的将内容展示出来，导致学习者在学习方面存在着一定的困难，基于目前没有针对于页面置换算法的完善的演示工具，故将此次的毕业设计内容着眼于该演示工具的开发。本文主要描述页面置换算法教辅演示系统，首先介绍了系统的设计目标，开发环境，实施方案和关键技术。其次介绍了系统的详细设计过程页面置换算法的算法设计，各算法模块的设计，界面设计。最后对系统的优缺点，以及自己的期望做了一个简单的总结。本系统是使用了强大的SKIN控件美化皮肤，使用MFC搭建界面，算法使用C编写，具有设计灵活，操作简单，运行效率高等特点。关键词MFC操作系统ABSTRACTOPERATINGSYSTEMISONEOFTHEIMPORTANTSYSTEMSOFTWARESINTHECOMPUTER,ANDPAGEREPLACEMENTALGORITHMISQUITEANSIGNIFICANTPOINTINOPERATINGSYSTEMTHEREFORE,ITSVERYIMPORTANTTOLEARNTHISCHAPTERWELLFORTHEREASONTHATTHECONTENTSCANNOTBESHOWEDUPINDETAIL,LEARNERSMAYHAVESOMETROUBLESINLEARNINGFORLACKINGPERFECTPRESENTATIONTOOLSINPAGEREPLACEMENTALGORITHMATPRESENT,THEGRADUATIONDESIGNTHISTIMEWILLFOCUSONTHEDEVELOPMENTOFTHEPRESENTATIONTOOLSTHEARTICLECONCENTRATESONPAGEREPLACEMENTALGORITHMTEACHINGPRESENTATIONSYSTEMFIRSTLY,ITINTRODUCESTHESYSTEMDESIGNGOALS,DEVELOPMENTENVIRONMENT,IMPLEMENTATIONPLANSANDKEYTECHNIQUESINTHESYSTEMSECONDLY,ITGIVESUSADETAILDESIGNPROCESSOFTHESYSTEMINCLUDINGTHEALGORITHMDESIGNOFPAGEREPLACEMENTALGORITHM,EACHDESIGNOFALGORITHMMODULESANDINTERFACEDESIGNFINALLY,WEMADEASUMMARYONTHEBENEFITS,DRAWBACKSOFTHESYSTEMANDOUREXPECTATIONSTHESYSTEMISPOWERFULINSKINBEAUTIFICATION,ITSINTERFACEISSETUPBYMFCANDITSALGORITHMISWRITTENBYCTHESYSTEMHASTHEFEATURESOFFLEXIBLEDESIGN,EASYOPERATIONANDHIGHEFFICIENCYKEYWORDSMFCOPERATINGSYSTEM目录1引言111国内外研究概况及发展趋势112课题意义113课题目标214设计内容与设计结果2141设计内容21411LFU模块21412FIFO模块21413OPT模块31414NRU模块3142设计结果32总体设计与实施方案421总体设计4211系统需求分析5212系统实现的目标522实施方案5221设计环境需求与关键技术5222方案实施步骤63系统设计与实现731系统业务流程732系统结构设计7321程序结构7322数据结构7323程序流程图733系统具体设计和实现11331FIFO算法实现模块11332OPT算法模块13333LRU法模块15334CLOCK算法模块16335错误信息提示模块18336主界面模块20337特色功能模块204程序的调试及故障分析245计评价和改进要求及目标2551设计评价2552改进的要求及目标266总结27参考文献28致谢291引言11国内外研究概况及发展趋势当前计算机的硬件技术发展迅速，但是内存的成本却随之迅速下降，容量也随之增大，尽管如此但是还是不能够根本的来满足软件对内存日益增长的需求，所以对存储空间进行充分的利用是现在操作系统的当务之急。1961年英国曼彻斯特大学推出了“虚拟内存”的概念，并且实现了这一技术，目前大多数计算机都采用此技术，比如IBM370系列。正是由于这种成熟的技术，所以推动了计算机的发展，同时在一些微型计算机的存储管理技术上也使用这种技术。正是由于这种特性，所以使得计算机操作系统显得尤为的重要。基于一个这样的情况页面置换算法演示的这个系统有着很大的推动力以及它自己的优势，相信在未来的市场厂有着不可估量的潜力。12课题意义现在是21世纪，计算机发展特别迅速，由此改变了人们的生活方式，在精神方面人们也受着它们的影响，很多人也因此进行各种的学习来满足自己精神方面的追求。操作系统是计算里面一个特别重要的一章，也是软件专业学生里面必须学习的一个十分重要的课程。操作系统的好坏决定着计算机的性能以及用户对其体验的好坏，我们可以通过提高各种设备资源的和设备的使用效率来提高系统的可利用性。操作系统十分的复杂以及繁琐，所以如果要很好的掌握这门学科，就得将实践与理论相结合，这样才能达到事半功倍的效果。而且为了使同学更好的理解操作系统中页面置换算算法的原理，知道它是怎么实现，有必要开发一个页面置换算法演示教辅系统，帮助老师教学，帮助学生理解。13课题目标页面置换算法演示教辅系统要达到以下的目标1、可以选择需要演示的页面置换算法。2、可以进行自动演示。3、可以进行手动演示。4、操作人员可以自动输入想要演示的页面号。5、系统软件可以随机产生演示所需的页面号。6、操作人员输入错误数据或者非法字符，系统软件会给出提醒。7、演示完成后，系统软件自动的会算出缺页次数，缺页率，置换次数，置换率。14设计内容与设计结果141设计内容页面置换算法演示教辅系统主要有LFU,FIFO,OPT,NRU四大算法演示功能模块。1411LFU模块LFU模块主要分为分步演示，直接演示，自动输入页面号，手动输入页面号，演示提示功能。直接演示点击这个功能，操作可以看到演示完成后的一个结果。分步演示点击这个功能，演示人员可以分步进行操作，能够清楚看到页面置换的每一个步骤，方便讲解。自动输入页面号系统软件自动生成演示的页面号。手动输入页面号演示人员可以输入自己想要演示的页面号。演示提示当用户输入错误数据时，系统软件会给予错误提示。1412FIFO模块FIFO模块主要分为直接演示，分步演示，自动输入页面号，手动输入页面号，演示提示功能。直接演示点击这个功能，操作可以看到演示完成后的一个结果。分步演示点击这个功能，演示人员可以分步进行操作，能够清楚看到页面置换的每一个步骤，方便讲解。自动输入页面号系统软件自动生成演示的页面号。手动输入页面号演示人员可以输入自己想要演示的页面号。演示提示当用户输入错误数据时，系统软件会给予错误提示。1413OPT模块OPT模块主要分为直接演示，分步演示，自动输入页面号，手动输入页面号，演示提示功能。直接演示点击这个功能，操作可以看到演示完成后的一个结果。分步演示点击这个功能，演示人员可以分步进行操作，能够清楚看到页面置换的每一个步骤，方便讲解。自动输入页面号系统软件自动生成演示的页面号。手动输入页面号演示人员可以输入自己想要演示的页面号。演示提示当用户输入错误数据时，系统软件会给予错误提示。1414NRU模块NRU模块主要分为直接演示，分步演示，自动输入页面号，手动输入页面号，演示提示功能。直接演示点击这个功能，操作可以看到演示完成后的一个结果。分步演示点击这个功能，演示人员可以分步进行操作，能够清楚看到页面置换的每一个步骤，方便讲解。自动输入页面号系统软件自动生成演示的页面号。手动输入页面号演示人员可以输入自己想要演示的页面号。演示提示当用户输入错误数据时，系统软件会给予错误提示。142设计结果操作人员可以直接操作此款软件进行一个辅助性的教学演示。1、进入系统菜单主界面后，需要自己确定页面总数和物理快数。2、确定是手动输入所需演示的页面号还是让系统软件自动生成页面号。3、选择演示功能类型，可以选择分步演示，也可以选择直接演示。4、确定演示的算法。5、演示完成后可以看到置换次数，置换率，缺页次数，缺页率等数据。2总体设计与实施方案21总体设计211系统需求分析随着现在计算机的飞速发展，人们对计算机的了解也越来越多。而操作系统是计算机里面一个非常重要的学科，页面置换算法是里面一个很重要的知识点。书面文字的讲解过于书面化，学生理解起来会非常的困难，而且会比较的枯燥。基于这样一个问题，本课题拟于开发适合教师教学，能够帮助学生更好的学习计算机操作系统里面的页面置换算法这一章的内容。功能需求首先有四个算法的演示的选择，每个算法必须有分步演示和直接演示两种。分步演示是一步一步的进行页面的置换，直接演示是置换之后的所有结果。然后要有手动输入页面号和系统自动产生页面号，这样可以避免系统产生的随机性。最后算法演示完成后，系统软件会计算出缺页率，缺页次数，置换率，置换次数。性能需求点击功能系统软件会迅速的做出反应，系统具有提示性的信息。可以给演示人员提供一些帮助性的建议。运行要求有提示框对每一步的步骤进行提示。用户界面有菜单栏，软件名称。其他要求界面比较简洁大方，界面比较统一，操作比较简单，可维护性比较好，系统比较安全。212系统实现的目标页面置换算法演示教辅系统具有四个模块包括FIFO模块，OPT模块，NRU模块，LFU模块。系统结构图如图21所示。页面置换演示教辅系统FIFO算法OPT算法LFU算法NRU算法分步演示直接演示分步演示直接演示分步演示直接演示分步演示直接演示22实施方案221设计环境需求与关键技术想要开发一个好的系统软件就得需要一个好的开发环境和平台，所以我们选择了VS2005作为编译环境。硬件环境酷睿I3/2G操作系统WIN7软件编译环境VISUALSTUDIO2005VISUALSTUDIO微软推出的比较完善的开发工具，能给多种开发语言生成开发环境，如VISUALBASIC,VISUALC,VISUALC,VISUALF。使用VISUALSTUDIO可以利用它里面的类库，比如搭界面的MFC，可以直接拖入控件搭建自己想要的界面，无需用代码生成，简单而且高效，省去了程序员的许多麻烦，节省下来的时间可以用来完善系统的功能和提高系统的运行效率，大大提高了软件的质量。MFC介绍，是微软提供的库类库,形式的C类封装了WINDOWSAPI,并包含一个应用程序框架,为了减少工作负载应用程序开发人员。句柄类包含大量的WINDOWS包含包装类和许多内置控件和组件包装类。MFC将核心代码封装好了，你只需调用将就可以了，你只需考虑自己的逻辑，无需考虑一些每次编程需要用的重复的作用。SKIN介绍，系统软件开发，是一种非常特别的软件界面开发技术。使得原本复杂的界面编程变得非常的容易，随着换肤的技术不断的发展，SKIN不仅是一种换肤控件，而且是功能比较强大的换肤插件。你只需在你的程序中添加几句简单的代码就可以让你的界面变得漂亮，而且SKIN库提供各种不同风格的主题，供你选择。SKIN实现原理它属于第二代的外挂式的界面库，主要采用了HOOK与子类化技术来实现应用程序的自动更换皮肤。222方案实施步骤页面置换算法演示教辅系统的开发经过调研、需求分析、系统设计、编码实现、系统调试等阶段。1、调研，主要是了解市场上对页面置换算法的需求。2、需求分析，确定系统的业务逻辑，分析软件的所需功能。3、系统设计，具体的设计系统功能，设计页面完成整体设计。4、编码实现，编写代码实现设计功能。5、系统调试，调试代码查看是否BUG的地方，使功能更加完美。3系统设计与实现31系统业务流程系统操作流程如下1、进入系统，开始选择所需演示的物理块和页面总数。2、选择1完成后，选择需要执行的方式，是分步演示还是直接演示，两种演示结果不一样，一个是显现每一步的步骤，一个是直接出结果。3、提示帮助，如果演示人员输入错误的数据，系统软件会自己报错，提示操作人员发生错误。32系统结构设计321程序结构当进程要访问某个页面时，首先判断页面是否已经满了，如果没满页面进入直接加入物理块中，如果满了则进行相应的算法进行置换。322数据结构_MEMORY物理快_TOTAL页面数MYT总页面序列MYM物理块号MYB各个物理块对应的时间权或距离权323程序流程图1、FIFO先进先出算法这是最早出现的置换算法。该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。该算法实现简单只需把一个进程已调入内存的页面，按先后次序链接成一个队列，并设置一个指针，称为替换指针，使它总是指向最老的页面。FIFO算法流程图如图31所示。算法开始检查MYTGETATI的内容是否已存于MYM中求出最先调入内存的页面AIMM_MEMORY将其替换MYMSETATA,MYTGETATI否AS输出数组MYM输出缺页次数和置换次数计算缺页率和置换率并输出算法结束是图31FIFO算法流程图2、LFU最近最久未使用算法是根据页面调入内存后的使用情况进行决策的。由于无法预测各页面将来的使用情况，只能利用“最近的过去”作为“最近的将来”的近似，因此，LRU置换算法是选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间T，当须淘汰一个页面时，选择现有页面中其T值最大的，即最近最久未使用的页面予以淘汰。LFU算法流程图如图32所示。算法开始检查MYTGETATI的内容是否已存于M中找出MYB值最大的序号，存入J否MYMGETATIAASMYBSETATJ0除J号外的MYB1输出数组M输出缺页次数计算缺页率并输出算法结束记录A在内存中的位置JMYBSETATJ0图32LFU算法流程图3、OPT最佳置换算法其所选择的被淘汰页面，将是以后永不使用的或许是在最长未来时间内不再被访问的页面。采用最佳置换算法，通常可保证获得最低的缺页率。但由于人目前还无法预知一个进程在内存的若干个页面中，哪一个页面是未来最长时间内不再被访问的，因而该算法是无法实现的，便可以利用此算法来评价其它算法。OPT算法流程图如图33所示。是算法开始检查MYTGETATI的内容是否已存于M中物理页没填满直接填入即AIM否向后对比，存储当前页面与往后页面之间的距离MYMSETATK,H重新设置物理页面的距离权MYBSETATK,9999输出数据计算缺页率并输出算法结束记录页面不需要置换XFALSE，同时M找到距离权最大的页面将其替换掉DMYBGETATH图33OPT算法流程图4、CLOCK时钟算法又名NRU算法。简单的CLOCK算法，只需为每页设置一位访问位，再将内存中的所有页面都通过链接指针链接成一个循环队列。当某页被访问时，其访问位置1，否则置为0，当要进行页面置换的时候，只需判断访问位是否为0，是的话将页面置换出来，不是的话重新将其置为0，然后继续访问。CLOCK算法流程图如图34所示。是算法开始检查MYTGETATI的内容是否已存于M中物理页没填满直接填入即AIM否MYMGETATIAASMYBSETATJ0除J号外的MYB1输出数组M输出缺页次数计算缺页率并输出算法结束记录A在内存中的位置JMYBSETATJ0图34CLOCK算法流程图33系统具体设计和实现331FIFO模块手动输入或者自动生成序列，算法运行后的结果如图35所示。演示人员可以自己选择物理块，页面总数。是图35FIFO算法主要实现代码FORINTK0K0YIFMYMGETATJMYTGETATYQ/MYBSETATJ,QIFAQAQASMYMSETATA,MYTGETATI335错误信息提示模块当操作人员输入错误的数据时，系统软件会弹出对话框给予提示，警告信息数据错误。1、当用户输入小数以及负数时，系统软件会提醒用户输入整数。如图39所示。图39错误12、当页面总数或者页面号为0时，软件会给出提示，页面不能小于物理块。如图310所示。图310错误23、当操作人员输入的数据为符号之类的非法数字时，软件会弹出对话框给出警告，输入序列有非法字符。如图311所示。图311错误3336主界面模块主界面包括四个算法选择供演示人员选择，演示人员可以选择直接演示也可以选择分步演示，此外系统还提供分步文字提示功能，能够用文字提示你进行到哪一步，哪一个页面需要替换。如图312所示。图312主界面337特色功能模块页面置换算法教辅系统特色功能模块当进程读取到页面号是会有颜色标记页面号，提示操作人员当前页面号正在读取。还有提示框会提示页面号的置换情况以及置换结束后出现的置换率，置换次数，缺页率，缺页次数。1、执行分步演示功能，软件会用颜色标记的方法提示操作人员此时读取到的页面号。如图313所示。图3132、在算法演示的过程中，软件会提示操作人员此时页面是否命中，是否加入页面。如图314所示。图3143、在算法演示完成之后，软件会自动算出页面置换算法的置换次数，置换率，缺页率，缺页次数等数据。如图315所示。图315主要实现代码CHARFORMATCFZEROMEMORYCFCBSIZESIZEOFCHARFORMATCFDWMASKCFM_BOLD|CFM_COLOR|CFM_FACE|CFM_ITALIC|CFM_SIZE|CFM_UNDERLINECFBCHARSETANSI_CHARSETCFDWEFFECTS0CFYHEIGHT2020/文字高度STRCPYCFSZFACENAME,“宋体“/设置字体CFCRTEXTCOLORRGB200,100,255/文字颜色IFMYTEXT“IFMYTGETATI10M_RICHEDIT2SETSELX,Y1M_RICHEDIT2SETSELECTIONCHARFORMATCFXX3YY3ELSEM_RICHEDIT2SETSELX,YM_RICHEDIT2SETSELECTIONCHARFORMATCFXX2YY2ELSEIFMYTGETATI10M_RICHEDITSETSELX,Y1M_RICHEDITSETSELECTIONCHARFORMATCFXX3YY3ELSEM_RICHEDITSETSELX,YM_RICHEDITSETSELECTIONCHARFORMATCFXX2YY24程序的调试及故障分析程序的调试与测试是开发周期不可或缺的一个环节。软件开发不可能取得一次性成功的，必须经历开发测试完善在测试这些阶段。可以用一个文本来记录你测试的结果，再根据你的测试结果来对软件进行修改。本系统经过测试遇到如下几个问题1、当点击分步演示时，只能执行这个功能，无法触发其他功能。因为使用了模态对话框来达到分步演示的效果，所以目前无法解决这个问题。2、物理块数目为0时，程序崩溃。解决办法设置提示信息，当物理块数目为0时，进行错误提示，这样操作人员就知道数据具有错误信息，程序不会发生崩溃。5计评价和改进要求及目标51设计评价本系统达到刚开始最初的设计初衷1、简单的界面，使用方便。2、能够帮助老师进行教学演示，方便学生理解，提高教学质量。3、安装起来方便，对硬件环境要求比较低。4、运行效率高，简单易懂。5、具有各种信息提示，便于演示人员理解操作。6、具有特色功能，可以吸引学习人员。52改进的要求及目标虽然基本功能达到了但是这个系统还是有很多欠缺的地方，比如可以做一个教学性的反馈模型，软件可以自动演示。当缺页率，置换率不在一个正常的范围值内时，软件自动减少物理块数，从而使它达到一个标准值，这样可以给演示人员示范一个比较好的范围。在提示页面动态这块，本软件采用的是让字体标记颜色并且增大它的大小，通过这样提示演示人员目前页面的状态，这个完全可以进一步的优化，可以使数字进行闪动，这样达到的效果更加直观。由于技术问题，自己还无法实现，希望有关公司或者人士能够解决一问题。界面方面自己使用的是SKIN皮肤库，做的比较简单，还需要做进一步的改进。演示算法的物理块数有限制，由于界面排版的问题，目前只能演示20个物理块，而且在最大化，最小化这块也有问题，这个自己没有处理好，得花时间去将它改进好，否则无法成为一个好的算法演示系统。自己的目标是希望能够开发出一个真正可以帮助老师的算法演示系统，能够演示所有页面置换算法，在此基础上能够有一个标准的反馈模型，可以给老师做一个简单的示范，不过由于时间和技术上的问题自己没能做的更加的全面，不过以后有时间的话，自己还是希望能够完成这个系统的开发，将这个系统做的完美，能够真正意义上在各大高校推广起来使用。经历了此次开发自己也是确切的感受到文件系统对一个操作系统的重要性，其作用领域几乎涵盖了操作系统的所有文件，所有属性等，对各种文件操作都是基于文件系统来完成的。由此可见文件系统在目前任何操作系统上的