页面置换算法和系统颠簸分析.doc

页面置换算法与系统颠簸分析 作者：潘亮铭 汪梦泽 　摘 要： 页面置换算法是操作系统内存管理中的一个重要问题。为了研究不同页面置换算法的区别与联系以及它们对系统颠簸的影响，在此采用了将不同置换算法对比介绍的方法，阐释了几种常见的页面置换算法的原理和思想，并通过它们对系统颠簸影响的分析实验，得到了通过改进页面置换算法解决系统颠簸的三个途径。通过采用局部页面置换算法，动态调整的页面置换算法和跟踪缺页率，可以有效地实现系统颠簸的控制。 　　关键词： 页面置换算法； 系统颠簸； 缺页中断； 内存管理； 操作系统； 虚拟内存 　　中图分类号： TN964?34 文献标识码： A 文章编号： 1004?373X（2013）20?0065?06 　　0 引 言 　　在系统运行过程中，若程序所要访问的页面不在内存而需要把他们调入内存，但内存已经没有空闲空间时，为了保证该???程能正常运行，系统必须从内存中调出一页程序或数据送到磁盘的交换区中，这个过程称为页面置换。决定将哪个页面调出，需根据一定的算法来确定，通常，把选择换出页面的算法成为页面置换算法。 　　置换算法的好坏，将直接影响到系统的性能。当发生缺页中断时，虽然可以随机地选择一个页面置换，但是如果一个被频繁使用的页面被置换出内存，很可能它在很短时间内又要被调入内存，这会带来不必要的开销。 一个好的页面置换算法，应具有较低的页面更换频率。从理论上讲，应将那些以后不再会访问的页面置换出，或者把那些在较长时间内不会再访问的页面调出。这对提高系统性能极其重要。 　　1 常见的页面置换算法 　　1.1 最优页面置换算法 　　1.1.1 算法思想介绍 　　最佳页面置换算法（Optimal Page Replacement Algorithm，OPT）是一种理想情况下的页面置换算法，它在所有页面置换算法中产生的页错误率最低，但实际上该算法是不可能实现的。 　　该算法的基本思想是：发生缺页时，有些页面在内存中，其中有一页将很快被访问（也就是下一条指令要访问的那一页），而其他页面则可能要到10、100或者1 000条指令后才会被访问，每个页面都可以用在该页面首次被访问前所要执行的指令数进行标记。 　　最佳页面置换算法规定：标记最大的页应该被置换。例如，如果某页在800万条指令内不会被使用，另一页在600万条指令内不会被使用，则置换前一个页面。这个算法惟一的一个问题就是它无法实现，因为当缺页发生时，操作系统无法知道各个页面下一次是在什么时候被访问。虽然最佳页面置换算法不可能实现，但是该算法可以用于对可实现算法的性能进行衡量比较。如果一个页面置换算法不是最优的，但是它的性能与最优置换相比相差不大（如仅有2%的性能差距），那么就可以判定该算法是有实用价值的。 　　1.1.2 算法分析 　　从理论上说，当置换一个页面出内存时，被置换出的页面在将来仍然需要被访问，那个时候将发生缺页中断。既然不好的事情（缺页中断）总会发生，计算机也和人一样，希望把不愉快的事情尽可能地向后拖延。一个最好的页面置换算法应该把因为需要调入这个页面而发生的缺页中断推迟到将来，越久越好。因此选择最久之后才会被访问的页面换出内存是理论上最佳的，这也是这个算法被称为最优置换的原因。 　　1.2 先进先出页面置换算法（FIFO） 　　1.2.1 算法思想介绍 　　FIFO算法总是淘汰在内存中停留得最久的那个页面。具体实现方法是由操作系统维护一个所有当前在内存中的页面的链表，必威体育精装版进入的页面放在表尾，最久进入的页面放在表头。当发生缺页中断时，淘汰表头页面并把新调入的页面加到表尾。FIFO页面置换算法容易理解和实现，但是其性能并不总是很好。 　　1.2.2 算法分析 　　FIFO算法仅仅考虑到在内存中滞留了很久的页面的需求性可能比新进入的页面更小。就像在超级市场中，新引进的商品往往比已经库存了很久的商品更容易被购买，因此当新引进商品时，通常淘汰那个库存了最久的商品。 　　但是这种考虑显然不太准确，谁说新上架的东西一定比库存很久的东西更有用呢？考虑一个页面，它在很早的时候被调入内存，之后被频繁的引用，这个页面很容易被FIFO算法当作没用的页面从而被淘汰。因此纯粹的FIFO算法很容易淘汰重要的页面，实际很少使用。 　　1.3 第二次机会页面置换算法 　　1.3.1 算法思想介绍 　　第二次机会页面置换算法是对FIFO算法的改进。它在FIFO的基础上进行了修改，其性能较FIFO有了很大的提高，避免了把经常使用的页面置换出去。 　　和FIFO算法一样，操作系统维护一个所有当前在内存中的页面的链表，必威体育精装版进入的页面放在表尾，最久进入的页面放在表头。当需要置换页面是，检查最老页面的R位，如果它为0，表示它最近未被使用