页面置换算法_最近未用置换算法nru

最优算法：

理论最优，不可实现。

为每个在物理内存有副本的虚拟内存分页增加“距离下次调用还需要经过多少指令数”，将指令最大的虚拟内存分页从对应的物理内存中淘汰。

NRU（Not Recently Used，最近未使用算法）：

为每个虚拟页面维护两个字段：访问字段R和修改字段M

R=0，未访问；R=1，已被访问；（R位被定期清零。）

M=0，未修改；M=1，已修改。

根据R与M的值，将虚拟分页分为以下四类：

第0类：R=0，M=0；

第1类：R=0,M=1;（第3类在R位定期清零后得到第1类）

第2类：R=1,M=0;

第3类：R=1,M=1；

当发生缺页中断且物理内存满了，会从最小的非空类中随机选取一个页面淘汰，如果该页面是脏的，需要回写到磁盘。

先进先出算法（FIFO，First In，First Out）

维护一个链表，当发生缺页中断且物理内存满了，删除链表头部元素，并在链表尾部加入新的虚拟分页。

第二次机会算法

针对FIFO算法的改进，如果表头页面R=0，直接淘汰(或者回写到磁盘)，否则将表头页面的R置为0，加入表尾，继续检查新的表头。

时钟算法

针对第二次机会算法的改进，因为第二次机会算法需要在表头与表尾之间移动元素，所以时钟算法构建的是环形链表。

最近最少使用算法（LRU）

记录每个虚拟分页的访问次数，当发生缺页中断且物理内存满了，将访问次数最少的虚拟页面对应的物理内存中的分页进行淘汰。

缺点：因为需要维护链表，比较耗时。

NFU（Not Frequently Used,最不常用算法）

每次时钟中断时，操作系统扫描每个页面的R位，并将R位的值加到计数器中。

缺点：不会遗忘。

老化算法

之前时钟周期内的访问次数会随着时间的推移而被降低权重。

更新计数器的方法：

将计数器的值无符号右移1位，将当前时钟周期内的R值加入到最高位上。

工作集算法

记录程序过去k次访问的页面或者过去时间内访问的页面作为工作集。

以“过去时间内访问的页面作为工作集”为例：

当发生缺页中断且物理内存满了，首先扫描页框元素，如果R=1，则更新当前页面的“上次使用时间”为当前时间，并将R置为0（不确定，后续查证）；如果R=0，计算“上次使用时间”与当前时间之差，如果大于，则替换，否则扫描下一个元素。

如果扫描结束后没有淘汰元素，说明当前的页框元素都在工作集中，因此就需要去淘汰R=0中生存时间最长的页面。

工作集时钟算法

工作集算法与时钟算法的结合。