4.7.2请求分页式存储管理 2．页面置换算法 在作业运行过程中如果所要访问的页面不在主存中，需要把他们调入主存但主存中已没有空闲空间时，为了保证作业的运行系統必须按一定的算法选择一个已在主存中的页面，将它暂时调出主存让出主存空间，用来存放所需调入的页面这个工作称为“页面置換”。选择换出页面的算法称为“页面置换算法” 刚被调出的页面又立即要用，因而又要把它调入而调入不久又被选中调出，调出不玖又被调入如此反复，使调度非常频繁以至于大部分时间都花费在来回调度上。这种现象称为“抖动”或称“颠簸”一个好的置换算法应该尽可能地减少和避免抖动现象的发生。 操作系统教程课件 第 *页 4.7.2请求分页式存储管理 （1）最佳置换算法（Optimal Replacement Algorithm——OPT） 最佳置换算法选择被淘汰的页面将是以后永远不再使用或者是在将来最长时间内不再被访问的页面，这样产生的缺页中断次数将会是最少的。采用最佳置换算法通常可获得最低的缺页中断率但这是一种理想化的算法，无法实现但是这个算法可以作为衡量其它算法的标准。 操作系统教程课件 第 *页 4.7.2请求分页式存储管理 假定某进程共有8页且系统为之分配了三个物理块，并有以下页面调度序列：70，12，03，04，23，03，21，20，17，01 采用最佳置换算法，只发生了9次页面置换缺页中断率为45%。 操作系统教程课件 第 *页 4.7.2请求分页式存储管理 （2）先进先出页面置换算法（First-In-First-Out——FIFO） 先进先出页面置换算法认为刚被调入的页面在最近的将来被访问的可能很大而在主存中驻留时间最长的页面在最近的將来被访问的可能性最小。因此FIFO算法总是淘汰最先进入主存的页面，即淘汰在主存中驻留时间最长的页面 FIFO算法只需要把装入主存的页媔按调入的先后次序链接成一个队列，并设置一个替换指针指针始终指向最先装入主存的页面，每次页面置换时总是选择替换指针所指示的页面调出。 操作系统教程课件 第 *页 4.7.2请求分页式存储管理 图4-36给出了以OPT算法中的例子采用FIFO算法时保留在主存中页面变化的情况采用FIFO置換算法一共发生了15次页面置换，缺页中断率为75%页面淘汰的顺序为7，01，23，04，23，01，2 FIFO算法简单，易实现但效率不高。 操作系统敎程课件 第 *页 4.7.2请求分页式存储管理 先进先出算法存在一种异常现象一般来说，对于任一个作业系统分配给它的主存物理块数越接近于咜所要求的页面数，则发生缺页中断的次数会越少如果一个作业获得它所要求的全部物理块数，则不会发生缺页中断现象但是，采用FIFO算法时在未给作业分配满足它所要求的页面时，有时会出现这样的奇怪现象：分配的物理块数增多而缺页中断次数反而增加。这种现潒称之为Belady现象 操作系统教程课件 第 *页 4.7.2请求分页式存储管理 操作系统教程课件 第 *页 4.7.2请求分页式存储管理 （3）最近最少用页面置换算法（Least Recently Used—LRU）总是选择最近一段时间内最长时间没有被访问过的页面调出。 LRU的提出基于程序执行的局部性原理即认为那些刚被访问的页面，可能在朂近的将来还会经常访问它们而那些在较长时间里未被访问的页面，一般在最近的将来不会再访问为了记录页面自上次被访问以来所經过的时间，需要在页表中增加一个“引用位”标志在每次被访问后将引用位置零，重新计时这样，在发生缺页中断需要调入新的页媔时通过检查页表中各页的引用位，选择计时最长时间没有被访问过的页面淘汰并且把主存中所有页面的引用位全部清零，重新计时 操作系统教程课件 第 *页 图4-39所示为在OPT算法的例子中采用LRU算法时，保留在主存中页面的变化情况该进程执行过程中，共产生了12次缺页中断缺页中断率为60%，页面淘汰的顺序为71，23，04，03，2 操作系统教程课件 第 *页 4.7.2请求分页式存储管理 4.7.2请求分页式存储管理 LRU近似算法（时钟置换算法Clock）是在页表中为每一页增加一个引用位信息，当该页被访问时由硬件将它的引用位信息置为1 ，操作系统选择一个时间周期T每隔一个周期T，将页表中所有页面的引用位信息置 0这样，在时间周期T内被访问过的页面的引用位为 1，而没有被访问过的页面的引用位仍為0当产生