《页面置换算法c,,实现实验报告》由会员分享，可在线阅读，更多相关《页面置换算法c,,实现实验报告（16页珍藏版）》请在金锄头文库上搜索。
1、为了适应公司新战略的发展，保障停车场安保新项目的正常、顺利开展，特制定安保从业人员的业务技能及个人素质的培训计划页面置换算法c,实现实验报告计算机操作系统实验报告实验题目：页面置换算法班级：信息管理与信息系统一班姓名：周晨妍学号：XX指导老师：匡林爱日期：一题目要求：设计一个虚拟存储区和内存工作区，编程序演示下述算法的具体实现过程，并计算访问命中率：要求设计主界面以灵活选择某算法，且以下算法都要实现1)最佳置换算法(OPT)：将以后永不使用的或许是在最长(未来)时间内不再被访问的页面换出。2)先进先出算法(FIFO)：淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。3)最近最
2、久未使用算法(LRU)：淘汰最近最久未被使用的页面。4)时钟页面置换算法(Clock)二实验目的：1、用C语言编写OPT、FIFO、LRU，Clock四种置换算法。2、熟悉内存分页管理策略。3、了解页面置换的算法。4、掌握一般常用的调度算法。5、根据方案使算法得以模拟实现。6、锻炼知识的运用能力和实践能力。三相关知识：1虚拟存储器的引入：局部性原理：程序在执行时在一较短时间内仅限于某个部分；相应的，它所访问的存储空间也局限于某个区域，它主要表现在以下两个方面：时间局限性和空间局限性。2虚拟存储器的定义：虚拟存储器是只具有请求调入功能和置换功能，能从逻辑上对内存容量进行扩充的一种存储器系统。3虚
3、拟存储器的实现方式：分页请求系统，它是在分页系统的基础上，增加了请求调页功能、页面置换功能所形成的页面形式虚拟存储系统。请求分段系统，它是在分段系统的基础上，增加了请求调段及分段置换功能后，所形成的段式虚拟存储系统。4页面分配：平均分配算法，是将系统中所有可供分配的物理块，平均分配给各个进程。按比例分配算法，根据进程的大小按比例分配物理块。考虑优先的分配算法，把内存中可供分配的所有物理块分成两部分：一部分按比例地分配给各进程；另一部分则根据个进程的优先权，适当的增加其相应份额后，分配给各进程。5页面置换算法：常用的页面置换算法有OPT、FIFO、LRU、Clock、LFU、PBA等。四设计思想
4、：选择置换算法，先输入所有页面号，为系统分配物理块，依次进行置换：OPT基本思想：是用一维数组pagepSIZE存储页面号序列，memerymSIZE是存储装入物理块中的页面。数组nextmSIZE记录物理块中对应页面的最后访问时间。每当发生缺页时，就从物理块中找出最后访问时间最大的页面，调出该页，换入所缺的页面。【特别声明】若物理块中的页面都不再使用，则每次都置换物理块中第一个位置的页面。FIFO基本思想：是用队列存储内存中的页面，队列的特点是先进先出，与该算法是一致的，所以每当发生缺页时，就从队头删除一页，而从队尾加入缺页。或者借助辅助数组timemSIZE记录物理块中对应页面的进入时间，
5、每次需要置换时换出进入时间最小的页面。LRU基本思想：是用一维数组pagepSIZE存储页面号序列，memerymSIZE是存储装入物理块中的页面。数组flag10标记页面的访问时间。每当使用页面时，刷新访问时间。发生缺页时，就从物理块中页面标记最小的一页，调出该页，换入所缺的页面。五流程图：如下页所示六、作业表表1、最佳置换算法表2、先进先出置换算法表3、最近最久未使用算法表4、时钟页面置换算法操作系统课程设计报告院：计算机工程学院专业：计算机科学与技术专业学生姓名:*班级：*学号:*题目：页面置换算法起迄日期:*设计地点:*指导教师:*一、课程设计目的操作系统是计算机教学中最重要的环节之一
6、，也是计算机专业学生的一门重要的专业课程。操作系统质量的好坏，直接影响整个计算机系统的性能和用户对计算机的使用。一个精心设计的操作系统能极大地扩充计算机系统的功能，充分发挥系统中各种设备的使用效率，提高系统工作的可靠性。由于操作系统涉及计算机系统中各种软硬件资源的管理，内容比较繁琐，具有很强的实践性。要学好这门课程，必须把理论与实践紧密结合，才能取得较好的学习效果。课程设计是学生学习完计算机操作系统课程后，进行的一次全面的综合训练，通过课程设计，让学生更好地掌握操作系统的原理及实现方法,加深对操作系统基础理论和重要算法的理解，加强学生的动手能力。二、课程设计内容模拟仿真请求分页调度算法OPT、
7、FIFO、LRU、LFU、CLOCK等模拟页面调度算法，并提供性能比较分析功能。三、系统分析与设计1、系统分析由于分区式管理尽管实现方式较为简单，但存在着严重的碎片问题使得内存的利用率不高。再者，分区式管理时，由于各作业或进程对应于不同的分区以及在分区内各作业或进程连续存放，进程的大小或内存可用空间的限制。而且分区式管理也不利于程序段和数据段的共享。页式管理正是为了减少碎片以及为了只在内存存放那些反复执行或即将执行的程序段与数据部分，而把那些不经常执行的程序段和数据存放于外存待执行时调入，以提高内存利用率而提出来的页式管理有动态页式管理和静态页式管理之分，动态页式管理是在静态页式管理的基础上发
8、展起来的。请求页式管理属于动态页式管理中的一种，它的地址变换过程与静态页式管理时的相同，也是通过页表查出相应的页面号，由页面号与页内相对地址相加而得到实际物理地址。有关的地址变换部分是由硬件自动完成的。当硬件变换机构发现所要求的页不在内存时，产生缺页中断信号，由中断处理程序做出相应的处理。中断处理程序是由软件实现的。除了在没有空闲页面时要按照置换算法选择出被淘汰页面之外，还要从外存读入所需要的虚页。这个过程要启动相应的外存和涉及到文件系统。因此，请求页式管理是一个十分复杂的过程，内存利用率的提高是以牺牲系统开销的代价换来的。这里用到了置换算法。它是在内存中没有空闲页面时被调用。目的是选出一个被
9、淘汰的页面。如果内存中有足够的空闲页面存放所调入的页，则不必使用置换算法。把内存和外存统一管理的真正目的是把那些被访问概率非常高的页存放在内存中。因此，置换算法应该置换那些被访问概率低的页，将它们移出内存。调页策略1)何时调入页面如果进程的许多页是存放在外存的一个连续区域中，则一次调入若干个相邻的页，会比一次调入一页的效率更高效一些。但如果调入的一批页面中的大多数都未被访问，则又是低效的。可采用一种以预测为基础的预调页策略，将那些预计在不久之后便会被访问的页面，预先调入内存。如果预测较准确，那么，这种策略显然是很有吸引力的。但目前预调页的成功率仅为50%。且这种策略主要用于进程的首次调入时，由
10、程序员指出应该先调入哪些页。2)请求调页策略当进程在运行中需要访问某部分程序和数据时，若发现其所在的页面不在内存，便即提出请求，由OS将其所需页面调入内存。由请示调页策略所确定调入的页，是一定会被访问的，再加之请求调页策略比较易于实现，故在目前的虚拟存储器中，大多采用此策略。但这种策略每次仅调入一页，故须花费较大的系统开销，增加了磁盘I/O的启用频率。从何处调入页面在请求分页系统中的外存分为两部分：用于存放文件的文件区和用于存放对换页面的对换区。通常，由于对换区是采用连续分配方式，而事件是采用离散分配方式，故对换区的磁盘I/O速度比文件区的高。这样，每当发生缺页请求时，系统应从何处将缺页调入内
11、存，可分成如下三种情况：(1)系统拥有足够的对换区空间，这时可以全部从对换区调入所需页面，以提高调页速度。为此，在进程运行前，便须将与该进程有关的文件，从文件区拷贝到对换区。(2)系统缺少足够的对换区空间，这时凡是不会被修改的文件，都直接从文件区调入；而当换出这些页面时，由于它们未被修改而不必再将它们换出时，以后需要时，再从对换区调入。(3)UNIX方式。2、系统设计：在进程运行过程中，若其所要访问的页面不在内存而需把它们调入内存，但内存已无空闲空间时，为了保证该进程能正常运行，系统必须从内存中调出一页程序或数据，送磁盘的对换区中。但应将哪个页面调出，须根据一定的算法来确定。通常，把选择换出页
12、面的算法称为页面置换算法(Page_ReplacementAlgorithms)。一个好的页面置换算法，应具有较低的页面更换频率。从理论上讲，应将那些以后不再会访问的页面换出，或将那些在较长时间内不会再访问的页面调出。则有以下页面置换方法：1）、先进先出(FIFO)页面置换算法：这是最早出现的置换算法。该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。该算法实现简单只需把一个进程已调入内存的页面，按先后次序存入一个时间数组，并将其中时间值最大的页面进行淘汰，并替换入新的页面就可以实现。2）、最近最久未使用页面置换算法LRU：算法的基本思想：当需要淘汰某一页时，选择离当
13、前时间最近的一段时间内最久没有使用过的页先淘汰。该算法的主要出发点是，如果某页被访问了，则它可能马上还被访问。或者反过来说，如果某页很长时间未被访问，则它在最近一段时间不会被访问。3）、最佳页面置换置换算法其所选择的被淘汰页面，将是永不使用的，或者是在最长时间内不再被访问的页面。可保证获得最低的缺页率。但由于人们目前还无法预知一个进程在内存的若干个页面中，哪一个页面是未来最长时间内不再被访问的，因而该算法也是无法实现的。但是可利用该算法去评价其它算法。4）、简单Clock置换算法该算法是当某页被访问时，其访问位被设置为1，置换算法选择某一页淘汰时，只需检查页的访问位，如果是0，则将该页换出，如
14、果为1，则重新将它置0，暂不换出，而给该页第二次驻留内存的机会，再按照FIFO算法检查下一个页面。当检查到队列的最后一个页面时，若其访问位仍为1，则再返回到队首的第一个页面。5）最少使用置换算法该置换算法选择在最近一段时间内使用最少的页面作为淘汰页。LFU算法并不能真正的反映出页面的使用情况。3、模块设计：系统功能结构图4、数据结构说明：程序中用到了structstructPagetime/字段privateintnum;/页面的序号privateinttimer;/不同的算法有不同的含义privateintcount;/页面访问次数/属性publicintNumgetreturnnum;setnum=value;publicintTimergetreturntimer;settimer=value;publicintCountgetreturncount;setcount=value;程序中用到了字符串和数组publicstringpage;/用于接收页面序列publicstringstrsize;/用于接收物理块数page=page_;strsize=size_;/声明struct数组，用于存储内存中页面的信息PagetimeX=newPaget
