操作系统原理课件作者周苏教学课件第7章节存储管理.ppt

7.4.3 先进先出（FIFO）页面置换算法 另一种开销较小的页面置换算法是先进先出（FIFO，First-In First-Out）算法。考虑由操作系统维护一个所有当前在内存中的页面的链表，必威体育精装版进入的页面放在表尾，最久进入的页面移到表头。当发生缺页中断时，淘汰表头的页面并把新调入的页面加到表尾。但FIFO算法可能会淘汰那些常用的页面，由于这一原因，很少使用纯粹的FIFO算法。 7.4.4 第二次机会页面置换算法 FIFO算法可能会把经常使用的页面置换出去，为了避免这一问题，对该算法做一个简单的修改：检查最老页面的R位。如果R位是0，那么这个页面既老又没有被使用，可以立刻置换掉；如果是1，就将R位清0，并把该页面放到链表的尾端，修改它的装入时间使它就像刚装入的一样，然后继续有哪些信誉好的足球投注网站。这一算法称为第二次机会（second chance）算法。 第二次机会算法就是寻找一个最近的时钟间隔以来没有被访问过的页面。如果所有的页面都被访问过了，该算法就简化为纯粹的FIFO算法。 7.4.5 时钟页面置换算法 尽管第二次机会算法是一个比较合理的算法，但它经常要在链表中移动页面，既降低效率又不是很有必要。一个更好的办法是把所有的页面都保存在一个类似钟面的环形链表中，一个表针指向最老的页面，如图7-12所示。 图7-12 时钟页面置换算法 7.4.5 时钟页面置换算法 当发生缺页中断时，算法首先检查表针指向的页面，如果它的R位是0就淘汰该页面，并把新的页面插入到这个位置，然后把表针前移一个位置；如果R位是1就清除R位并把表针前移一个位置，重复这个过程直到找到了一个R位为0的页面为止。 7.4.6 最近最少使用（LRU）页面置换算法 基于这样的观察：在前面几条指令中频繁使用的页面很可能在后面的几条指令中被使用。反过来说，已经很久没有使用的页面很有可能在未来较长的一段时间内仍然不会被使用。这个思想提示了一个可实现的算法：在缺页中断发生时，置换未使用时间最长的页面。这个策略称为最近最少使用（LRU，Least Recently Used）页面置换算法。 7.4.6 最近最少使用（LRU）页面置换算法 虽然LRU在理论上是可以实现的，但代价很高。为了完全实现LRU，需要在内存中维护一个所有页面的链表，最近最多使用的页面在表头，最近最少使用的页面在表尾。困难的是，在每次访问内存时都必须要更新整个链表。在链表中找到一个页面，删除它，然后把它移动到表头是一个非常费时的操作，即使使用硬件实现也一样费时（假设有这样的硬件）。 7.4.6 最近最少使用（LRU）页面置换算法 还是有一些使用特殊硬件实现LRU的方法。例如，要求硬件有个64位计数器C，它在每条指令执行完后自动加1，每个页表项必须有一个足够容纳这个计数器值的域。在每次访问内存后，将当前的C值保存到被访问页面的页表项中。一旦发生缺页中断，操作系统就检查所有页表项中计数器的值，找到值最小的一个页面，这个页面就是最近最少使用的页面。 7.4.6 最近最少使用（LRU）页面置换算法 再看看第二个硬件实现的LRU算法。在一个有n个页框的机器中，LRU硬件可以维持一个初值为0的n×n位的矩阵。当访问到页框k时，硬件首先把k行的位都设置成1，再把k列的位都设置成0。在任何时刻，二进制数值最小的行就是最近最少使用的，第二小的行是下一个最近最少使用的，以此类推。 7.4.7 最不常用页面置换算法 前面两种LRU算法虽然在理论上都是可以实现的，但只有非常少的计算机拥有这种硬件。这里考虑一个能用软件实现的解决方案，称为最不常用（NFU，Not Frequently Used）算法。该算法将每个页面与一个软件计数器相关联，计数器的初值为0。每次时钟中断时，由操作系统扫描内存中所有的页面，将每个页面的R位（它的值是0或1）加到它的计数器上。这个计数器大体上跟踪了各个页面被访问的频繁程度。发生缺页中断时，则置换计数器值最小的页面。 7.4.7 最不常用页面置换算法 NFU的主要问题是它从来不忘记任何事情。比如，在一个多次（扫描）编译器中，在第一次扫描中被频繁使用的页面，当程序进入第二次扫描时，其计数器的值可能仍然很高。实际上，如果第一次扫描的执行时间恰好是各次扫描中最长的，含有以后各次扫描代码的页面的计数器可能总是比含有第一次扫描尺码的页面小，结果是操作系统将置换有用的页面而不是不再使用的页面。 7.4.7 最不常用页面置换算法 对NFU做一个小小的修改，以使它能很好地模拟LRU。修改分为两部分：首先，在R位被加进之前先将计数器右移一位，其次，将R位加到计数器最左端的位而不是最右端的位。修改以后的算法称为老化（aging）算法，图7-13解释了它是如何工作的。 7.4.7 最不常用页面置换算法 假设在第一个时