操作系统内存最全解析！！！(12) _操作系统

尽管看起来好像无法实现第一类页面，但是当第三类页面的 R 位被时钟中断清除时，它们就会发生。时钟中断不会清除 M 位，因为需要这个信息才能知道是否写回磁盘中。清除 R 但不清除 M 会导致出现一类页面。
NRU(Not Recently Used) 算法从编号最小的非空类中随机删除一个页面。此算法隐含的思想是，在一个时钟内（约 20 ms）淘汰一个已修改但是没有被访问的页面要比一个大量引用的未修改页面好，NRU 的主要优点是易于理解并且能够有效的实现。
先进先出页面置换算法另一种开销较小的方式是使用 FIFO(First-In,First-Out) 算法，这种类型的数据结构也适用在页面置换算法中。由操作系统维护一个所有在当前内存中的页面的链表，最早进入的放在表头，最新进入的页面放在表尾。在发生缺页异常时，会把头部的页移除并且把新的页添加到表尾。

还记得缺页异常什么时候发生吗？我们知道应用程序访问内存会进行虚拟地址到物理地址的映射，缺页异常就发生在虚拟地址无法映射到物理地址的时候。因为实际的物理地址要比虚拟地址小很多（参考上面的虚拟地址和物理地址映射图），所以缺页经常会发生。

先进先出页面可能是最简单的页面替换算法了。在这种算法中，操作系统会跟踪链表中内存中的所有页。下面我们举个例子看一下（这个算法我刚开始看的时候有点懵逼，后来才看懂，我还是很菜）

文章插图

初始化的时候，没有任何页面，所以第一次的时候会检查页面 1 是否位于链表中，没有在链表中，那么就是 MISS，页面1 进入链表，链表的先进先出的方向如图所示。
类似的，第二次会先检查页面 2 是否位于链表中，没有在链表中，那么页面 2 进入链表，状态为 MISS，依次类推。
我们来看第四次，此时的链表为 1 2 3，第四次会检查页面 2 是否位于链表中，经过检索后，发现 2 在链表中，那么状态就是 HIT，并不会再进行入队和出队操作，第五次也是一样的。
下面来看第六次，此时的链表还是 1 2 3，因为之前没有执行进入链表操作，页面 5 会首先进行检查，发现链表中没有页面 5 ，则执行页面 5 的进入链表操作，页面 2 执行出链表的操作，执行完成后的链表顺序为 2 3 5 。

第二次机会页面置换算法我们上面学到的 FIFO 链表页面有个缺陷，那就是出链和入链并不会进行 check 检查，这样就会容易把经常使用的页面置换出去，为了避免这一问题，我们对该算法做一个简单的修改：我们检查最老页面的 R 位，如果是 0 ，那么这个页面就是最老的而且没有被使用，那么这个页面就会被立刻换出。如果 R 位是 1，那么就清除此位，此页面会被放在链表的尾部，修改它的装入时间就像刚放进来的一样。然后继续搜索。
这种算法叫做第二次机会(second chance)算法，就像下面这样，我们看到页面 A 到 H 保留在链表中，并按到达内存的时间排序。

文章插图

a）按照先进先出的方法排列的页面；b）在时刻 20 处发生缺页异常中断并且 A 的 R 位已经设置时的页面链表。
假设缺页异常发生在时刻 20 处，这时最老的页面是 A ，它是在 0 时刻到达的。如果 A 的 R 位是 0，那么它将被淘汰出内存，或者把它写回磁盘（如果它已经被修改过），或者只是简单的放弃（如果它是未被修改过）。另一方面，如果它的 R 位已经设置了，则将 A 放到链表的尾部并且重新设置装入时间为当前时刻（20 处），然后清除 R 位。然后从 B 页面开始继续搜索合适的页面。
寻找第二次机会的是在最近的时钟间隔中未被访问过的页面。如果所有的页面都被访问过，该算法就会被简化为单纯的 FIFO 算法。具体来说，假设图 a 中所有页面都设置了 R 位。操作系统将页面依次移到链表末尾，每次都在添加到末尾时清除 R 位。最后，算法又会回到页面 A，此时的 R 位已经被清除，那么页面 A 就会被执行出链处理，因此算法能够正常结束。
时钟页面置换算法即使上面提到的第二次页面置换算法也是一种比较合理的算法，但它经常要在链表中移动页面，既降低了效率，而且这种算法也不是必须的。一种比较好的方式是把所有的页面都保存在一个类似钟面的环形链表中，一个表针指向最老的页面。如下图所示