【操作系统】第六章：页面置换算法
功能目标
功能：当缺页中断发生，需要调入新的页面而内存已满时，选择当中哪个物理页面被置换。
目标：尽可能减少页面的换进换出次数。
页面锁定：将相关的页（必须常驻操作系统的关键部分）放在内存里面，确保操作系统随时能够正常工作
6.1 最优页面置换算法
基本思路
（如果能预知将来）根据将来什么时候访问，将距离再次使用间隔时间最长的页作为被置换的页面（不太实际，无法预知未来）
可用作其他算法的性能评价依据。
实例
6.2 先进先出算法（FIFO）
基本思路
选择在内存中驻留时间最长的页面并淘汰之。
系统维护着一个链表，记录了所有位于内存中的逻辑页面，链表首页驻留时间最长，尾部最短，发生缺页中断时，链表首页先淘汰，在链表尾部加入新的页面。
特点
性能较差，调出的页面有可能是经常要访问的页面，并且有可能出现 Belady现象（后面讲），很少单独使用。
实例
6.3 最近最久未使用（LRU）
基本思路
当一个缺页中断发生时，选择最久未使用的那个页面并淘汰之。
根据过去推测将来。（过去使用的较少，推测将来使用的也会很少）
特点：
LRU算法需要记录各个页面使用的先后顺序，开销比较大
两种可能的实现方式：
链表
系统维护一个页面链表，最近刚刚使用的页面作为首节点，最久未使用的页面作为尾节点
堆栈
设置一个活动页面栈，当访问某页时，将此页号压入栈顶，然后考察站内是否有与此页面相同的页号，有则抽出。需要淘汰一个页面时，总是选择栈底的页面。
实例
6.4 时钟页面置换算法
Clock 页面置换算法，LRU 近似，对 FIFO 的一种改进
基本思路
需用用到页表中的访问位，页面被装入内存时，访问位初始化为0，页面被读写，访问位被置为1
将页面制成环形链表，指针指向最先进来的页
发生缺页中断时，指针开始移动
若所指页面访问位为0，立即被淘汰
若所指页面访问位为1，把该位置为0，指针继续移动
特点
访问位只占一个字节，只有两种可能，结果不是很准确！
准确率跟 LRU 差不多
实例
6.5 二次机会法
基本思想
同时使用 脏位（dirty bit）和访问位（used bit） 来指导位置交换。
脏位：用来标识是否进行过写操作
如果执行过写操作，则脏位置为1，淘汰该页时需要将其写入物理硬盘以更新信息
如果没有执行过写操作，则脏位置为0，淘汰该页时直接将其释放即可，不需要再写入硬盘
特点
实例
6.6 最不常用法
基本思路
当一个缺页中断发生时，选择访问次数最少的那个页面，淘汰之
实现方法
对每个页面设置一个计数器，页面被访问时计数器加一。发生缺页中断时，选择计数器最小的淘汰。
特点
引入计数器占用物理内存，开销较大。
检索计数器觉得淘汰谁时同样存在开销。
6.7 Belady现象、LRU、FIFO、Clock
Belady现象：在采用FIFO算法时，有时候会出现分配的物理页面数增加，缺页率反而提高的异常现象
产生原因：FIFO算法的置换特征与进程访问内存的动态特征是矛盾的，与置换算法的目标是不一致的，因此，被它置换出去的页面并不一定是进程不会访问的。
FIFO算法
- 三个物理页帧：
-
- 四个物理页帧：
LRU算法
6.8 局部页面替换算法的问题、工作集模型
工作集模型
6.9 两个全局置换算法
工作集页置换算法
基本思想：
需要替换页面时，替换那些不在工作集窗口内的页
工作集会随程序执行挪动，如果某个页不在工作集窗口之内，它会被丢掉
- 在整个系统层面，会确保整个系统的缺页次数较低
缺页率页面置换算法
缺页率：
缺页次数 / 内存访问次数
- 影响因素：
- 页面置换算法
- 分配给进程的物理页大小
- 页面本身大小
- 程序的编写
- 方法：
- 缺页率高——–增加工作集
- 缺页率低——–减少工作集
- 影响因素：
总结：对操作系统而言，如果要应对多个正在运行的程序，采取全局页替换算法效果要好于局部页替换算法
6.10 抖动问题
