操作系统11-页面置换算法_第二次机会算法 scr算法程序

11 页面置换算法

11.1 最优页面置换算法(optimal) (OPT)

算法思路：每个页面用在该页面将来首次被访问前所要执行的指令数进行标记,标记最大的页面应该被淘汰

这个页面置换算法无法实现,当发生页面失效时，操作系统是不知道内存中的每个页面将来会在什么时候被访问的

可以用于对比其他可实现算法的性能

11.2 最近未使用页面置换算法(not recently used) (NRU)

为了收集页面被使用的统计信息，大多数支持虚拟存储的计算机都给每页设置了两个状态位

• R: 每当页面被访问则置R位
• M:每当页面被写则置M位
• 当一进程开始执行，所有页面的R、M位被OS置0
• 周期性的(比如每个时钟中断)将R位清0，以区别这个页面是否最近被访问
• 时钟中断不能清M位，因为该信息对是否回存磁盘有用

页面失效时，OS检测所有页面，根据R和M将其分成四类,NRU算法总是淘汰编号等级最低的任一页面

• Class 0: (R=0, M=0)
• Class 1: (R=0, M=1)
• Class 2: (R=1, M=0)
• Class 3: (R=1, M=1)

11.3 先进先出页面置换算法 (First-in First-out ) (FIFO)

OS维护一个所有当前内存的页面的链表，最老的页面在表头，最新的在表尾,页面失效时,淘汰表头的页面，新调入页面放表尾.

Belady异常:只有FIFO会发生，当内存为其增加块后，缺页率反而提高。

11.3第二次机会页面置换算法（second chance ）（SC）

算法思路：页面失效发生时，检查最老页面的R位 ,如R为0，则该页面为最老且未被访问页面，立即置换,如R为1，清除该位，页面放在链表尾部，重新搜索

寻找上一个时钟间隔以来没有被访问的最老页面,如果所有的页面都被访问过，算法退化成FIFO。

算法改进：时钟页面置换算法（clock）

保存所有内存页面在一个类似钟面的环形链表,一个指针指向最老页面

11.4 最近最久未用页面置换算法(least recently used) (LRU)

算法思路：前面执行的几条指令所频繁使用的页面可能在后面的几条指令中还会用到,当页面失效时淘汰最长时间未使用的页面

特点：

• 最优页面置换算法的很好的近似

• 使用页面的链表管理方式实现代价较高

LRU计数器：

• 系统装备一64位计数器C, 能每执行一条指令自动加1
• 每个页表项有一个足够容纳计数器值的域
• 每次内存访问后,存放当前C值到刚访问的页面的页表项
• 当页面失效发生时,OS检查页表中所有表项的计数器值找出最小的一个进行淘汰