页面置换算法

页面置换算法

当 CPU 访问的页面不在物理内存时，便会产生一个缺页中断，请求操作系统将所缺页调入到物理内存。如果此时在物理内存中找不到空闲页，操作系统必须在内存中选择一个页面将其换出内存，以便为即将调入的页面腾出空间。如果要换出的内存已经被修改过，就必须把它写回磁盘以更新该页面在磁盘上的副本；如果该页面没有被修改过，那么不需要写回。直接用调入的页面覆盖被淘汰的页面就可以了。

因此，页面置换算法的目标是，尽可能的减少页面换入换出的次数，下面将介绍几个重要的算法。

最优页面置换算法

该算法是这样工作的：在缺页中断发生时，有些页面在内存中，其中有一个页面将很快被访问，其他页面则可能要 100、1000 条指令后才会被访问，每个页面都用该页面下一次被访问前所要执行的指令数作标记。

最优页面置换算法规定应该置换标记数最大的页面。这个算法的唯一缺点就是它无法实现，因为当缺页中断发生时，操作系统也无法知道各个页面下一次在什么时候被访问。

最近未使用页面置换算法

为了使操作系统能够收集有用的统计信息，在大部分具有虚拟内存的计算机中，系统为每一页设置了两个状态位。当页面被访问（读或写）时设置 R 位；当页面被写入（即修改）时设置 M 位。每次访问内存时更新这些值，一旦设置某位为 1，它就一直保持 1 直到操作系统将它复位。

可以用 R 位和 M 位来构造一个简单的页面置换算法：当启动一个进程时，它的所有页面的两个位都由操作系统设置成 0，R 位被定期地（比如在每次时钟中断时）清零，以区别最近没有被访问的页面和被访问的页面。

当发生缺页中断时，操作系统检查所有的页面并根据它们当前的 R 位和 M 位的值，把它们分为 4 类：

• 第 0 类：没有被访问，没有被修改
• 第 1 类：没有被访问，已被修改
• 第 2 类：已被访问，没有被修改
• 第 3 类：已被访问，已被修改

尽管第 1 类看起来有点匪夷所思，但是一个第 3 类的页面在它的 R 位被时钟中断清零后就成了第 1 类。时钟中断不清除 M 位是因为在决定一个页面是否需要写回到磁盘时将用到该信息。

NRU（Not Recently Used，最近未使用）算法随机地从编号最小的非空类中挑选一个页面淘汰。这个算法的隐含的意思是，在最近一个时钟周期中淘汰一个没有被访问的已修改页面要比淘汰一个被频繁使用的干净页面好。

先进先出页面置换算法

FIFO（First-In First-Out，先进先出）算法思想非常简单，就是最先被放入内存的页面最早被换出。

实现方式也比较简单，可以由操作系统维护一个有长度限制的内存页链表，每次添加时从尾部插入，当超过长度限制时，就将链表头部的内存页置换掉。

下图仅是先进先出演示：

第二次机会页面置换算法

FIFO 算法可能会把经常使用的页面置换出去，为了避免这一问题，对该算法做一个简单的修改：检查最老页面的 R 位。如果 R 位是 0，那么这个页面既老又没有被使用，可以立刻置换掉；如果是 1，就将 R 位清零，并把该页面放到链表的尾端，使它就像刚装入一样，然后继续搜索。这一算法称为第二次机会（second chance）算法。

第二次机会算法就是寻找一个在最近的时钟间隔内没有被访问过的页面。如果所有的页面都被访问过，该算法就简化为纯粹的 FIFO 算法。

时钟页面置换算法

尽管第二次机会是一个比较合理的算法，但它经常在链表中移动页面，既降低了效率也不是很有必要。一个更好的方法是把所有的页面都保存在一个环形链表中，一个指针指向最老的页面。

当发生缺页中断时，算法首先检查表指针指向的页面：

• R 位为 0 就淘汰该页面，并把新的页面插入这个位置，然后把表指针向前移动一个位置
• R 位为 1 就清除 R 位并把表指针向前去移动一个位置，重复这个过程直到找到一个 R 位为 0 的页面为止

最近最少使用页面置换算法

LRU（Least Recently Used）算法的思想是：在缺页中断发生时，置换未使用时间最长的页面。

该思想依据程序的局部性原理：在前面几条指令中频繁使用的页面很可能在后面的几条指令中被使用。换句话说，已经很久没有使用的页面很有可能在未来较长一段时间内仍然不会被使用。

虽然 LRU 理论上是可行的，但代价很高。为了实现 LRU，需要在内存中维护一个所有页面的链表，最近使用做多的页面在表头，最近使用最少的在表尾。困难的是在每次访问内存时都必须更新整个链表。

最不常用页面置换算法

最不常用（LFU）算法，它的意思是当发生缺页中断时，选择「访问次数」最少的那个页面，并将其淘汰。

有一些使用特殊硬件实现 LFU 的方法。它的实现方式是，对每个页面设置一个计数器，每当一个页面被访问时，该页面的访问计数器就累加 1。在发生缺页中断时，淘汰计数器值最小的那个页面。

有个严重的问题，LFU 算法只考虑了频率问题，没考虑时间的问题，比如有些页面在过去时间里访问的频率很高，但是现在已经没有访问了，而当前频繁访问的页面由于没有这些页面访问的次数高，在发生缺页中断时，就会可能会误伤当前刚开始频繁访问，但访问次数还不高的页面。

这个问题的解决的办法还是有的，可以定期减少访问的次数，比如当发生时间中断时，把过去时间访问的页面的访问次数除以 2，也就说，随着时间的流失，以前的高访问次数的页面会慢慢减少，相当于加大了被置换的概率。