计算机操作系统原理与核心设计-第7章.pptVIP

* * * * * * * * * * * * * * * * * * * * * * * * * * * */19 7.7 页面置换算法 当需要的页不在内存时，操作系统必须从内存中选择一页并将其移到外存，然后把需要的页调入内存。在每次缺页时，不同的选择会使系统的效率有很大不同。对页面置换算法的研究已经非常深入，下面介绍几个重要的算法。这几个算法都是采用固定分配局部置换的内存分配策略。 */19 7.7.1最优页面置换算法 当发生缺页时，当前内存中的这几页中，有的页可能以后再也不用了，那么把这个页置换出去是最好的，如果当前内存中的几页都要使用，那么就选择一个最后用到的页并把它置换出去。（向后看） */19 7.7.1最优页面置换算法 假定系统为某进程分配了三个物理块，进程的页面走向如下： 7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1 现在分配给该作业的三个物理块为空 ，采用OPT算法，置换过程如何呢？ */19 7.7.1最优页面置换算法 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 1 7 0 1 2 7 0 3 7 X X X 最佳页面算法（OPT） */19 7.7.2 先进先出置换算法 置换最先进入内存的页 先进先出算法（FIFO） 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 1 7 0 1 2 7 0 3 7 X X X */19 7.7.2 先进先出置换算法 页面走向 物理块 0 1 2 3 0 1 4 0 1 2 3 4 0 0 0 0 1 2 3 0 0 0 1 4 4 1 1 1 2 3 0 1 1 1 4 2 2 2 2 3 0 1 4 4 4 2 3 3 缺页 Y Y Y Y Y Y Y Y Y 页面走向 物理块 0 1 2 3 0 1 4 0 1 2 3 4 0 0 0 0 0 0 0 1 2 3 4 0 1 1 1 1 1 1 1 2 3 4 0 1 2 2 2 2 2 2 3 4 0 1 2 3 3 3 3 3 4 0 1 2 3 4 缺页 Y Y Y Y Y Y Y Y Y Y */19 7.7.3最近最少使用置换算法 最近最少使用（LRU）置换算法的思想是当发生缺页时，系统会选择当前内存页面中没有被使用时间最久的那一页，即最少使用的那一页，并将它置换出去。 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 1 7 0 1 2 7 0 3 7 X X X */19 7.7.3最近最少使用置换算法 最近最久未用算法（LRU）硬件支持 R 实页 R7 R6 R5 R4 R3 R2 R1 R0 1 0 1 0 1 0 0 1 0 2 1 0 1 0 1 1 0 0 3 0 0 0 0 0 1 0 0 4 0 1 1 0 1 0 1 1 5 1 1 0 1 0 1 1 0 6 0 0 1 0 1 0 1 1 7 0 0 0 0 0 1 1 1 8 0 1 1 0 1 1 0 1 移位寄存器 R = Rn-1Rn-2Rn-3…R2R1R0 */19 7.7.4 用软件模拟LRU算法 最不常用（NFU）算法：该算法将每个页面与一个软件记数器相联，记数器的初值为0。每次时钟中断时，由操作系统扫描内存中的所有的页面，将每个页面的R位（它的值是0或1）加到它的记数器上。实际上这个记数器是试图跟踪各个页面的访问频繁程度。发生页面失效时，计数器最小的页面被淘汰。这样做有没有问题呢？ 对NFU进行一个简单的修改来模拟LRU。首先，在R位被加进来之前先将记数器右移一位；然后将R位加到记数器的最左端的位。 */19 7.7.4 用软件模拟LRU算法 (a) 1 0 1 0 1 1 1 1 0 0 1 0 1 1 0 1 0 1 1 0 0 0 1 0 0 1 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 1 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 1 0 1 0 0 0 0 0 1 1 1 1 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0