操作系统中的页面置换算法

1. 什么是页面置换算法

当操作系统发生缺页中断时，操作系统必须在内存中选择一个页面，将其换出内存，为即将调入的页面腾出空间。这时我们就需要一个页面置换算法。

值得注意的是，页面置换算法不仅用于内存和硬盘之间的页面置换，也用于计算机其他部分。例如 CPU 高速缓存的置换，以及应用程序应用缓存的置换，都是相通的。

2. 常用页面置换算法

2.1 最优页面置换算法 OPT

这是最好但不可能实现的算法。即在缺页中断发生时，我们把当前内存中下一次被使用时间最晚的页面置换出去。

这是不可能实现的，因为操作系统不可能知道各个页面下一次什么时候被访问。

2.2 最近未使用页面置换算法 NRU

操作系统中一般为每一个页面设置了两个状态位，当页面被读操作或写操作访问时，设置 R 位；当页面被写入时，设置 M 位。每次访问内存时就更新这些位。

当启动一个进程时，所有页面的两个状态位都被置为 0，除此之外 R 位还被定期清零，相当于标记为最近未使用页面。

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

1. 没有被访问，没有被修改。
2. 没有被访问，已被修改。
3. 已被访问，没有被修改。
4. 已被访问，已被修改。

NRU 算法随即从类编号最小的非空类中选择一个页面淘汰。原理是易于理解的。

2.3 先进先出页面置换算法 FIFO

FIFO 算法维护一个所有当前在内存中的页面的链表，最新加入的页面在表尾，最早加入的页面在表头。发生缺页中断时总是淘汰表头页面并将新调入的页面放在表尾。

FIFO 算法过于简单，没有考虑到页面访问的热点性，所以很少使用纯粹的 FIFO 算法。

2.4 第二次机会页面置换算法 SC

FIFO 算法可能会置换出经常使用的页面，为了避免这个问题，我们改进出了第二次机会算法。

当我们使用 FIFO 检查最老页面页面，即表头页面时。如果 R 位是 0，那么说明这个页面又老又不被使用，直接置换；如果 R 位置是 1，就将 R 位清零，并被页面放到链表的尾端。然后再重新从表头取页面。

2.5 时钟页面置换算法

第二次机会算法是一个比较合理的算法，为了减少它在链表中移动页面的开销，我们使用一个环形链表来进行优化。

时钟算法维护一个表针指向最老的页面，当发生缺页中断就检查这个表针所指的页面。如果 R 位是 0，就直接置换，并前移指针。如果 R 位是 1，则将 R 位清零，也前移指针。

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

LRU 是最优算法的一个很好的近似。但我们要在内存中完全实现 LRU 有很高的代价，这要求我们维护一个包含所有页面的链表。或者也可以用一个特殊的硬件来专门服务于这个需求。

NFU 算法是一种常用的软件模拟 LRU 的方式，他将每个页面和一个计数器相关联。每次时钟中断时，将每个页面的 R 位（0 或 1）累加到计数器上。这个计数器大体上跟踪了各个页面被访问的频繁程度。发生缺页中断时，就置换计数器值最小的页面。

老化算法是对 NFU 算法的进一步改良，因为 NFU 算法从不忘记任何事情，一个拥有很高计数值的页面会拥有很高的优先级。而老化算法会将每一次检查时的 R 位记录下来，并只保留有限长度，每次比较这些数字的值，并置换计数值最小的页面。

2.7 工作集页面置换算法

一个进程当前正在使用的页面的集合称为工作集。如果在进程运行过程中，工作集中的相当一部分都没有在内存中，那就会出现大量的缺页中断，极大地影响系统的性能，称这个程序发生了颠簸。

所以许多分页系统会设法跟踪进程的工作集，以确保在进程运行之前工作集就已经在内存中了，这个方法称为工作集模型。其目的在于大大减少缺页中断率，在进程运行前预先装入其工作集页面称为预先调页。

工作集页面置换算法的基本思路是找出一个不在工作集中的页面并淘汰，我们看下面的图，这是页表的一部分：

在处理每个表项时，算法会检查 R 位：

• 如果它是 1，就把当前实际时间写进页表项的上次使用时间域，以表示缺页中断发生时该页面正在被使用。既然该页面在当前时钟滴答中已经被访问过，那么显然他应该出现在工作集中，而不是被删除。并将 R 位置为 0。

• 如果它是 0，那么表示当前时间滴答中该页面还没有被访问过，则它可以被置换。为了知道它是否应该被置换，需要用当前实际运行时间减去上次使用时间，计算出生存时间，并与通常进程运行时间进行比较。

  • 如果当前生存时间更大，则该页面不在工作集中，说明可以用新页面置换它。在找到所有这样的页面后，会随机选择其中一个进行置换。
  • 如果当前生存时间更小，则页面在工作集中，那就继续检查下一个表项。

2.8 工作集时钟页面置换算法

当缺页中断发生后，需要扫描整个页表才能确定被淘汰的页面，因此基本工作集算法有很大的开销。工作集时钟算法是基于时钟算法和工作集算法的一种改进算法。

每次缺页中断时先检查指针指向的页面：

• 如果 R 位被置为 1，那么该页面在当前时间滴答中被使用过，那么把 R 位置为 0，并将指针移动到下一个页面。
• 如果 R 位被置为 0，那么要令页面生存时间和进程通常运行时间相比较。
  • 如果页面生存时间大于通常运行时间，那么不在工作集中，则置换。
  • 如果页面生村时间小于通常运行时间，那么将指针移动到下一个页面。

3. 页面置换算法小结