页面置换算法
1. 页面置换的概念
功能：选择被置换的物理页面
设计目标：
- 减少页面的调入调出的次数
- 将未来或短期内不访问的页面调出
页面锁定：不可以置换的页面
即页表项中的标志锁定位置1的页面（通常是操作系统页面，需要高读写的页面等）
1.1 局部置换
选择范围：当前进程占用的物理页面
分为：
- 最优算法
- 先进先出算法
- 最近最久未使用算法
1.2 全局置换
选择范围：所有可换出的物理页面
分为：
- 工作集算法
- 置换率算法
2. 三大局部置换解决算法
2.1 最优页面置换算法 optimal
思路： 未来时间不会访问的页面
实现：
- 缺页时，计算每个页面下一次访问的时间
- 选择未来最长时间访问的页面
特征：
- 缺页最少
- 实际上无法实现
- 因为无法预知
- 可以作为其他置换算法的性能评价依据
2.2 先进先出算法 FIFO
思路：在内存驻留时间最长的页面进行置换
实现：
- 维护一个记录所有位于内存中的逻辑页面链表
- 按驻留内存的时间排序，链首最长，链尾最短
- 缺页时，选择链首页面进行置换，新页面添加到链尾
特征：
- 实现简单
- 性能较差，调出的页面可能经常访问
- 进程分配物理页面数增加时，缺页不一定减少（Belady现象）
- 很少单独使用
2.3 最近最久未使用算法 LRU （Least Recently Used）
思路：选择最长时间没有被引用的页面进行置换
（如某些页面长时间未被访问，在未来可能会长时间不会访问）
实现：
- 缺页时，计算每个页面上一次访问的时间
- 选择上一次使用到当前时间最长的页面
特征：
- 最优置换算法的一种近似
2.4 LRU算法的可能实现办法
- 页面链表
- 按最近一次访问的时间排序的页面链表
- 链表首节点是最近访问的页面
- 尾节点是最久未使用的页面
- 活动页面栈
- 访问页面时，将此页号压入栈顶，并在栈内相同的页号抽出
- 缺页时，置换栈底的页面
特征：
开销大
用栈实现LRU算法
3. 时钟置换算法和最不常用算法
3.1 时钟置换算法 clock （FIFO和LRU的折中版）
思路：仅对页面的访问情况进行大致统计
数据结构：
- 在页表项中增加访问位，描述页面在过去一段时间呃访问情况
- 各页面组织成环形链表
- 指针指向最先调入的页面
算法：
- 访问页面时，在页表项记录页面的访问情况（访问位置1）
- 缺页时，从指针处开始顺序查找未被访问的页面进行置换
特征：
LRU和FIFO的折中
替换前：
替换后：
示例：
改进的clock算法
思路：
减少了修改页的缺页处理开销
算法：
页表项增加修改位
缺页时，修改页面标志位，跳过修改的页面
读 ——> 10
写 ——> 11
找置换时：
11 ——> 01
10/01 ——> 00
00 ——> 置换 （然后该页面为10）
3.2 最不常用算法 LFU （Least Frequently Used）
思路：
缺页时，置换访问次数最少的页面
实现：
- 每个页面设置一个访问计数
- 访问每个页面时，访问次数+1
- 缺页时，置换计数最小的页面
特征：
- 开销大
- 解决办法：衰减右移
LRU 和 LFU 的区别
- LRU 关注多久未访问，时间越短越好
- LFU 关注访问次数，次数越多越好
4. Belady现象 和 局部置换算法的比较
4.1 Belady现象
现象：
采用FIFO等算法时，可能出现分配的物理页面数增加，缺页次数反而升高的异常现象
原因：
1. FIFO算法的置换特征与进程访问内存的动态特征矛盾
2. 被它置换出去的页面并不一定是进程近期不会访问的
物理页数为 3
+1后，物理页数为 4
证明：存在 belady现象
LRU算法没有Belady现象！
4.2 LRU，FIFO和clock算法的比较
LRU 和 FIFO 本质上都是先进先出的思路
- LRU依据页面的最近访问时间排序
- LRU需要动态调整顺序（维护一个栈…）
- FIFO依据页面进入内存的时间排序
- FIFO的页面进来后是固定不变的
LRU 可以退化成FIFO
如：1，2，3，4，5，6，1，2，3
比较
- LRU 性能好，开销大
- FIFO 性能差，但会发生Belady现象
- clock 是他们的折中
- 页面访问时，不动态调整页面在链表中的顺序，仅作标记
- 缺页时，再把它移动到链表末尾
5. 全局页面置换算法
局部置换算法没有考虑进程访问的差异
思路：全局置换算法为进程分配可变数目的物理页面
问题？
- 进程再不同阶段的内存需求是变化的
- 分配给进程的内存在需要不同阶段有所变化
- 全局置换算法需要确定分配给进程的物理页面数
5.1 工作集置换算法
工作集：一个进程当前正在使用的逻辑页面集合，可表示为二元函数W(t, delta)
示例：
工作集的变化：
工作集置换算法
思路：换出不在工作集的页面
窗口大小 t ：
当前时刻前t个内存访问的页引用是工作集，t被称为窗口大小
实现方法：
- 访存链表：维护窗口内的访存页面链表
- 访存时，换出不在工作集的页面，更新访存链表 （复杂的地方）
- 缺页时，换入页面，更新访存链表
缺点：
开销大
5.2 缺页率算法
缺页次数 / 内存访问次数 or 缺页平均时间间隔的倒数的平均值
影响的因素：
- 页面置换算法 （可控制的）
- 分配给进程的物理页面数目
- 页面大小
- 程序的编写方法
缺页率置换算法 图示：
实现：
- 访存时，设置引用标志
- 缺页时，计算从上次缺页时间T_last到现在T_current的时间间隔
- T_current - T_last > T 置换所有在[T_last, T_current]的页面
- T_current - T_last < T 增加缺失页放入常驻集中
6. 抖动和负载控制
6.1 抖动问题
抖动：
- 进程中物理页面太少，不能包含工作集
- 造成大量缺页，频繁置换
- 进程运行速度变慢
产生抖动的原因：
- 驻留在内存的进程数目增加，分配给每个进程的物理页面减少，缺页率上升
需要在并发和缺页率之间达到一个平衡
6.2 负载控制
调节并发进程数 MPL 来进行系统负载控制
