操作系统L10

Page Replacement Algorithms 页面置换算法

页面错误（page fault）强制选择
- 哪一页必须被移除 remove
- 为到来的页制造空间 make room
- 即在内存中选择一个页面将其换出内存，以便为即将调入的页面腾出空间
换出的页面
- 如果被修改过，必须将其写回磁盘以更新该页面在磁盘上的副本 saved
- 如果没有被修改过，直接覆盖即可 overwritten
最好不要选择经常使用的页面
- 很可能在很短时间内又被调入内存中
总览

Optimal Page Replacement Algorithm 最优页面置换算法

替换将在最远点引用的页面
最优但是不可能实现

Not Recently Used Page Replacement Algorithm 最近未使用页面置换算法

简称NRU
系统为每一页面设置了两个状态位
- 当页面被访问(读或写)时设置R位
- 当页面被写入(即修改)时设置M位
这些位包含早每个页表项中
当一个进程启动时，所有页面的R和M都设置为0
- 周期性的，R位会清零
页面被分为4类

NRU算法随机地从类编号最小地非空类中挑选一个页面淘汰

FIFO Page Replacement Algorithm 先进先出页面置换算法

开销较小
由操作系统维护一个所有当前在内存中地页面的链表，最新进入的页面放在表尾，最早进入的页面放在表头
发生缺页中断时，淘汰表头的页面并把新调入的页面加到表尾
优点：易于实现
缺点：经常使用的页面可能会被清除

Second Chance Page Replacement Algorithm 第二次机会页面置换算法

在FIFO基础进行修改，检查最老页面的R位
- R位是０，页面既老又没有被实现，可以立刻置换掉
- R位是1，就将R位清０，并把该页面放到链表的尾端，修改它的装入时间使它像刚装入的一样

本质上是在寻找一个在最近的时钟间隔内没有被访问过的页面

The Clock Page Replacement Algorithm　时钟页面置换算法

把所有的页面都保存在一个类似钟面的环形链表中，一个表针指向最老的页面

Least Recently Used (LRU)　最近最少使用页面置换算法

假设最近使用过的页面很快就会再次使用
- 丢弃最长时间未使用的页面
软件解决方案
- 必须保持一个页面的链表：最近使用在前面，在后面最少；每次内存引用更新这个列表
- 太贵了

可以使用硬件解决方案 - 为硬件配备 64 位计数器 - 在每条指令执行完后自动加１ - 计数器值存储在刚刚引用的页的页表条目中 - 每个页表项必须有一个足够容纳这个计数器值的域 - 发生缺页中断后，选择计数器值最低的页面 - 选择计数器值最低的页面 - 问题：页表非常大，变得更大 - 为具有n 个页框的机器维护一个n x n 位的矩阵 - 引用页框 K 时： - (i) 将第 K 行设置为全 1。 - (ii) 将 K 列设置为全 0。 - 实质上就是在被引用时， - 将自己那一行变为1，让自己变大 - 让自己所在所有行即对应的列置为０，让其他变小 - 二进制值最小的行是 LRU 页

用软件模拟LRU

只有非常少的计算机拥有这种硬件，需要一种能用软件实现的解决方案
一种可能的方案称为NFU(Not Frequently Used, 最不常用)算法

NFU

该算法将每个页面与一个软件计数器相关联，计数器的初值为0
- 每次时钟中断时，扫描所有页面时，将每个页面的R位(0/1)加到它的计数器上
- 计数器大体跟踪各个页面被访问的频繁程度
- 发生缺页中断时，则置换计数器值最小的页面
问题：从不忘记任何事情，所以很久以前的页面引用频率可能有最高的计数器
解决：修改为NFU with Aging