相关算法

1. 最优页面置换算法（不可能实现）
在缺页中断发生时，有些页面在内存中，其中有一个页面将很快被访问，其他页面可能要10、1000……条指令才会被访问，每个页面都可以用在该页面首次被访问前所要执行的指令数作为标记。
虽然它无法被实现，但可用作一个性能参考。如某个算法比他只差1%，则说明该再花费精力去提升该算法是不划算的。

2. 最近未使用页面置换算法（NRU，Not Recently Used）
在大部分具有虚拟内存的计算机中，系统为每一页面设置了两个状态栏。当页面被访问时设置R位；当页面（即修改页面）被写入时设置M位。每次访问内存时更新这些位，因此由硬件来设置它们是必要的。
可以用R和M位来构建一个页面置换算法：
当启动一个进程时，它的所有页面的两个位都由操作系统设置成0，R位被定期地（比如在每次时钟中断时）清零，以区别最近没有被访问的页面和被访问的页面
当发生缺页中断时，操作系统检查所有的页面并根据它们当前的R位和M位的值，把它们分为4类：
0类：没有被访问，没有修改
1类：没有访问，已修改
2类：访问，未修改
3类：访问，已修改
NRU（Not Recently Used，最近未使用）算法随机地从类编号最小的非空类中挑选一个页面淘汰；即在最近的一个时钟滴答声中，淘汰一个没有被访问的已修改页面要比淘汰一个被频繁使用的“干净”页面要号。
NRU主要优点是易于理解和能够有效地被实现，虽然它的性能不是最好的，但是已经够用了。

3. 先进先出页面置换算法（FIFO，First-In First-Out）
该算法开销较小，由系统维护一个当前在内存中的页面的链表，最新进入的页面放在表尾，最久进入的页面放在表头。当发生缺页中断时，淘汰表头的页面并把新调入的页面加到表尾。

4. 第二次机会页面置换算法（second chance）
在FIFO基础上，检查最老页面R位。如果R位是0，那么这个页面即老又没被使用，可以被立即置换掉；如果是1，就将R位清0，并把页面放到链表的尾端，修改它的装入时间使他像刚装入一样，然后继续搜索。



在上图中，假设在时间20发生了一次缺页中断，这时最老的页面是A，它是在时刻0到达的。如果A的R位是0，则将它淘汰出内存，如果其R位已经设置了，则将A放到链表的尾部并且重新设置“装入时间”为当前时刻（20），然后清除R位。然后从B页面开始继续搜索合适的页面。
💡
第二次机会算法寻找一个最近的时钟间隔以来没有访问过的页面。如果所有页面都被访问了，该算法就简化为纯粹的FIFO算法。
它需要经常在链表中移动页面，降低了效率且不是必要的。

5. 时钟页面置换算法
在第二机会算法的链表基础上，把所有的页面都保存在一个环形链表中，一个指针指向最老的页面。



当发生缺页中断时，算法首先检查表指向的页面，如果它的R位是0就淘汰该页面，并把新的页面插入这个位置。然后把表针前移一位；如果R位是1就清楚R位并把表针前移一位。重复该步骤直到找到了一个R位为0的页面为止。

6. 最近最少使用页面置换算法（LRU，Least Recently Used）
可知，已经很久没有使用的页面可能在未来很长一段时间内仍然不会被使用。即在缺页中断发生时，置换未使用时间最长的页面。这个策略就称为LRU。
它在理论上可以实现，但是代价很高。需要在内存中维护一个所有页面的链表，最近最多使用的页面在表头，最近最少使用的页面在表尾。但是很难在每次访问内存时都必须更新整个链表。
• 使用特殊硬件实现LRU
1. 一个64位计数器C，它在每条指令执行完后自动加1，每个页表项必须有一个足够容纳这个计数器值的域。在每次访问内存后，将当前的C值保存到被访问页面的页表项中。一旦发生缺页中断，操作系统就检查所有页表项中计数器的值，找到值最小的一个页面，这个页面就是最近最少使用的页面。
2. 在一个有n个页框的机器中，LRU硬件可以维持一个初值为0的n×n位的矩阵。当访问到页框k时，硬件先把k行的位都设置成1，再把k列的位都设置成0。在任何时刻，二进制数值最小的行就是最近最少使用的

7. 工作集页面置换算法

请求调页 页面正在需要时才被调入，而不是预先装入的。

一个进程当前正在使用的页面的集合称为它的工作集（working set），如果整个工作集都被装入到了内存中，那么进程在运行到下一运行阶段（例如，编译器的下一遍扫描）之前，不会产生很 多缺页中断。若内存太小而无法容纳下整个工作集，那么进程的运行过程中会产生大量的缺页中断。
工作集模型（working set model）：分页系统设法跟踪进程的工作集，确保在让进程运行前，它的工作集就已经在内存中了，其目的在于大大减少缺页中断率。
💡
工作集是随着时间变化的。
为了实现工作集模型，操作系统必须跟踪哪些页面在工作集中。通过这些信息可以推导出一个合理的页面置换算法：当发生缺页中断时，淘汰一个不在工作集中的页面。
为了实现该算法，就需要一种精确的方法来确定哪些页面在工作集中。根据定义，工作集就是最近k次内存访问所使用过的页面的集合（有些设计者使用最近k次页面访问，但是选择是任意的）。为了实现工作集算法，必须预先选定k的值。一旦选定某个值，每次内存访问之后，最近k次内存访问所使用过的页面的集合就是惟一确定的了。
基于工作集的页面置换算法：
基本思路就是找出一个不在工作集中的页面并淘汰它。

假定使用硬件来置R位和M位。同样，假定在每个时钟滴答中，有一个定期的时钟中断会用软件方法来清除R位。每当缺页中断发生时，扫描页表以找出一个合适的页面淘汰之。
 

8. 老化算法（aging）
NFU（Not Frequently Used，最不常用）算法:该算法将每个页面与一个软件计数器相关联，计数器的初值为0。每次时钟中断时，由操作系统扫描内存中所有的页面，将每个页面的R位（它的值是0或1）加到它的计数器上。这个计数器大体上跟踪了各个页面被访问的频繁程度。发生缺页中断时，则置换计数器值最小的页面。
对NFU进行修改得到老化算法：首先，在R位被加进之前先将计数器右移一位；其次，将R位加到计数器最左端的位而不是最右端的位。



该算法与LRU区别：
• 老化算法的计数器只有有限位数，就限制了其对以往页面的记录。

9. 工作集时钟页面置换算法
基于工作集算法基础上，基于时钟算法并且使用了工作集信息，称为WSClock（工作集时钟）算法。它实现简单，性能较好，所以在实际工作中得到了广泛应用。
与时钟算法一样，所需的数据结构是一个以页框为元素的循环表，最初，该表是空的。当装入第一个页面后，把它加到该表中。随着更多的页面的加入，它们形成一个环。每个表项包含来自基本工作集算法的上次使用时间，以及R位（已标明）和M位（未标明）。



每次缺页中断时，首先检查指针指向的页面。如果R位被置为1，该页面在当前时钟滴答中就被使用过，那么该页面就不适合被淘汰。然后把该页面的R位置为0，指针指向下一个页面，并重复该算法。
原则上，所有的页面都有可能因为磁盘I/O在某个时钟周期被调度。为了降低磁盘阻塞，需要设置一个限制，即最大只允许写回n个页面。一旦达到该限制，就不允许调度新的写操作。
如果指针经过一圈返回它的起始点会发生：
• 至少调度了一次写操作
• 没有调度过写操作
 

页面置换算法总结：

• 最优算法在当前页面中置换要访问刀的页面。但是没有方法来判断哪个页面是最后一个要访问的。因此该算法不能使用。

• NRU算法根据R位和M位的状态把页面分为四类。从编号最小的类中随机选择一个页面置换。该算法易于实现，但是性能不是很好，还存在更好的算法。

• FIFO算法通过维护一个页面的链表来记录它们装入内存的顺序。淘汰的是最老的页面，但是该页面可能仍在使用，因此FIFO算法不是一个好的选择。

• 第二次机会算法是对FIFO算法的改进，它在移出页面前先检查该页面是否正在被使用。如果该页面正在被使用，就保留该页面。这个改进大大提高了性能。时钟算法是第二次机会算法的另一种实现。它具有相同的性能特征，而且只需要更少的执行时间。

• LRU算法是一种非常优秀的算法，但是只能通过特定的硬件来实现。如果机 器中没有该硬件，那么也无法使用该算法。NFU是一种近似于LRU的算法，它的 性能不是非常好，然而，老化算法更近似于LRU并且可以更有效地实现，是一个 很好的选择。

• 最后两种算法都使用了工作集。工作集算法有合理的性能，但它的实现开销 较大。工作集时钟算法是它的一种变体，不仅具有良好的性能，并且还能高效地 实现。