操作系统论文

目录TOC\o"1-5"\h\z\o"CurrentDocument"摘要21、关于页面置换算法的一些基本概念及思想2\o"CurrentDocument"2、页面置换算法的介绍32.1先进先出页面置换(FIFO)算法32.2最近最少使用页面置换(LRU)算法4\o"CurrentDocument"2.3最佳(Optimal)置换算法5\o"CurrentDocument"3、问题及总结6\o"CurrentDocument"参考文献7摘要随着计算机的普及，人们生活得到极大改善，人们在精神方面也同样需要提高，所以越来越多的人进行着各种各样的学习。操作系统是计算机中最重要的环节之一，也是计算机专业学生的一门重要的专业课程。操作系统的好坏，直接影响整个计算机系统的性能和用户对计算机的使用。一个精心设计的操作系统能极大的扩展计算机的功能，充分发挥系统中的各种设备的使用效率，提高系统的可靠性。由于操作系统中各种软硬件资源的管理，内容比较繁琐，具有很强的实践性，要学好这门课程，必须把理论和实践紧密结合，才能取得较好的学习效果。通过实验操作，让我更好地掌握了操作系统的原理以及实现方法，加深对操作系统基础理论和重要算法的理解。页面置换算法，是操作系统中对于页式存储管理中的一种软件虚拟存储管理方式实现的一种具体的算法操作，页面置换算法的优劣将会影响虚拟存储系统的性能，进而影响整个系统的性能。操作系统的调度算法选择将受到很多因素的影响，评价调度算法的优劣和性能也是十分复杂的事情，不同类型操作系统的调度算法往往不一样，由于应用程序的特性、对影响时间和系统资源要求不尽相同，使得调度算法的设计比较复杂。选择调度算法的基本原则是计算机系统的性能的要求。1、关于页面置换算法的一些基本概念及思想页面置换算法主要是记录内存的忙闲状态。为进程分配和释放内存。当主存的空间太小而无法装入所有的进程时.就需要在内存和硬盘之间进行调度操作。多数操作系统只采用某种特定的页面置换算法进行置换.无法预先探测当前运行进程的页面访问模式。因此不能根据不同的页面访问模式，选用不同的

页面置换算法。当然，如果能对不同的访问模式选取相应的页面置换算法。将提高操作系统的调度能力。进而提高整个系统的性能。页面置换算法主要是记录内存的忙闲状态。为进程分配和释放内存。当主存的空间太小而无法装入所有的进程时.就需要在内存和硬盘之间进行调度操作。多数操作系统只采用某种特定的页面置换算法进行置换.无法预先探测当前运行进程的页面访问模式。因此不能根据不同的页面访问模式，选用不同的页面置换算法。当然，如果能对不同的访问模式选取相应的页面置换算法。将提高操作系统的调度能力。进而提高整个系统的性能。在进程中运行过程中，若所要访问的页面不在内存中，需要调入页面时，选择内存中的那个物理页面将其调出。通常只能再局部性原理指导下，把未来不再使用的页面调出。如何选择调度策略即页面置换算法至关重要，置换算法的好坏，直接影响着系统的性能，因此有必要将常见的FIFO、LRU、OPT三种算法进行比较，分析性能。因此我们需要选择一种好的算法来对内存虚拟扩充的一种有效方法，提高内存利用2、页面置换算法的介绍2、页面置换算法的介绍r=在操作系统的运行过程中，若发现内存已无空闲的空间。为了确保系统中的进程能正常运行，就涉及到内存和磁盘的程序或数据交换。然而将哪些页面调入和调出，就需要根据算法来确定。这些算法被称为页面置换算法(pagereplacementalgorithms)。2.1先进先出页面置换(FIFO)算法先进先出(firstinfirstout，FIFO)算法是最早出现的置换算法，它的基本思想是：每次置换最先调入内存的页面。即将内存中等待时间最长的页面进行置换。此算法的适用范围是顺序结构程序。因为在这种程序中。最先进入内存的页面不再被访问的可能性最大。但在实际应用中。由于程序的局部性原理，经常会出现程序的某段或者数据的某个区域，在进程生命周期期间频繁地被调用。此种情况下，假如采用FIFO算法，这些页面就会被反复调入调出。极大地影响了系统的性能。该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。该算法实现简单，只需把一个进程已调入内存的页面，按照先后次序链接成一个队列，并设置一个指针，称为替换指针，使它总指向最老的页面。但该算法与进程实际运行的规律不相适应，因为在进程中，有些页面经常被访问，比如，含有全局变量、常用函数、例程等的页面，FIFO算法并不能保证这些页面不被淘汰。以下为采用FIFO算法进行页面置换的例子(图1)。当进程第一次访问页面2时，将把第7页置换出，因为它是最先被调入内存的；在第一次访问页面3时，又将把页0置换出，因为它在现有的2，0，1三个页面中是最老的页。由图1可以看出，利用FIFO算法时进行了12次页面置换。引用率70120304230321201701777222444000777000333222111001110003332221图1利用FIFO置换算法时的置换图2.2最近最少使用页面置换(LRU)算法最近最少使用(1eastrecentlyused，LRU)算法的基本思想是：依据物理块中最近使用页面情况预测未来使用情况。FIFO置换算法性能之所以较差，是因为它所依据的条件是各个页面调入内存的时间，而页面调入的先后并不能反映页面的使用情况。最近最久未使用（LRU）的页面置换算法，是根据页面调入内存后的使用情况进行决策的。由于无法预测各页将来的使用情况，只能利用“最近的过去”作为“最近的将来”的近似，因此，LRU置换算法是选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间t，当须淘汰一个页面时，选择现有页面中其t值最大的，即最近最久未使用的页面予以淘汰。利用LRU算法对上例进行页面置换算法的结果如图2所示。当进程第一次对页面2进行访问时，由于页面7是最近最久未访问的，故将它置换出去。当进程第一次对页面3进行访问时，第1页成为最近最久未使用的页，将它换出。根据各页以前的使用情况来判断，页面过去和未来的走向之间并无必然的关系。引用率70120304230321201701777224440111000000333001133222227页框图2利用LRU置换算法时的置换图选择最近最少使用的页面进行置换。即置换最长时间未被使用的页面。根据程序的局部性原理.在过去一段时间里不经常被访问的页面，在将来被访问的可能性会很通过仿真实验结果以及对更多的数据进行测试的结果分析和比较，得出如下结论：2.3最佳（Optimal）置换算法最佳置换算法是由Belady于1966年提出的一种理论上的算法。其所选择的被淘汰的页面，将是以后永不使用的，或是在最长（未来）时间内不再被访问的页面。采用最佳置换算法，通常可保证获得最低的缺页率。但由于人们目前还无法预知一个进程在内存的若干个页面中，哪一个页面是将来最长时间内不再访问的，因而该算法时无法实现的，但可以利用该算法评价其他算法。现举例说明如下(图3)。进程运行时，先将前三个页面装入内存。以后，当进程要访问页面2时，将会产生缺页中断。此时OS根据最佳置换算法，将选择页面7予以淘汰。这是因为页面0将作为第5个被访问的页面，页面1是第14个被访问的页面，而页面7则要在第18次页面访问时才需要调入。下次访问页面0时，因它已在内存而不必产生缺页中断。当进程第一次访问页面3时，又将引起页面1被淘汰，因为，它在现有的1，2，0三个页面中，将是以后最晚才被访问的。由图可以看出，采用最佳置换算法发生了6次页面置换。引用率70120304230321201701777234017000033211122200页框图3利用optimal置换算法时的置换图3、问题及总结操作系统的页面调度算法还有很多种，每种算法的效率在不同的作业进程中都可能不同，这些算法的实现各不相同，算法的复杂度也不一样，但并不是算法越复杂它的效果最好。FIFO是最简单的一种算法，但有些时候它的效率也有可能是最好的。所以，判断一个算法的好坏还有从实际情况出发，不能轻易下结论。FIFO算法可能发生Belady异常现象。虽然大量的数据对LRU算法进行验证没有出现Belady异常现象。但是并不能说明其不可能产生Belady异常现象。实际上大量的研究表明LRU算法不会出现Belady异常现象。影响缺页率的因素有分配给进程的物理块面置换算法的基本思想。在WindowsXP中，用数、页面置换算法和进程对页面的访问序列。虽然VisualC++实现这两种页面置换算法，并用数据对由数据分析得出了几种影响缺页率的因素.但是实际上影响缺页率的因素还有页面大小、快表的设置等。通常情况，虽然有时HFO算法的缺页率比LRU算法的缺页率低.但是在大多情况下，LRU算法的缺页率都比FIF0算法的缺页率低。LRU算法的优点是其最接近最优的页面置换算法，即它缺页率是比较低的，缺点是实现LRU算法需要硬件的支持，增加了系统的成本。FIFO算法的优点是其