页面置换算法概念
- 功能
- 当出现缺页异常时 需调入新页面且内存已满 置换算法选择被置换的物理页面
- 设计目标
- 尽可能地减少页面调入调出次数
- 把未来不再访问 或 短期内不访问的页面调出
- 页面锁定 (Frame locking)
- 描述必须常驻内存的逻辑页面
- 操作系统的关键代码
- 要求响应速度的代码和数据
- 页表中的锁定标志位 (Lock bit)
页面置换算法评价方法
- 记录进程访问内存的页面轨迹
1
2
3
4
5虚拟地址访问用(页号, 位移)表示
(3,0), (1,9), (4,1), (2,1), (5,3), (2,0), (1,9), (2,4), (3,1), (4,8)
对应的页面轨迹
3, 1, 4, 2, 5, 2, 1, 2, 3, 4
替换如 c, a, d, b, e, b, a, b, c, d - 评价标准
- 模拟页面置换算法的行为 记录各个置换算法产生缺页的次数 越少越好
局部页面置换算法
置换页面的选择范围仅限于当前进程占用的物理页面内 (在当前进程中的物理页面来决定换哪个页)
- 最优算法 (预测未来来决定 太理想)
- 先进先出算法 (先进先出并不一定反映了实际的访问特征 性能较差)
- 最近最久未使用算法 (统计过去 假设过去的特征是对未来的预测)
- 时钟算法
- 最不常用算法
最优页面置换算法 (OPT optional)
置换在未来最长时间不访问页面
最优页面置换算法实现
- 缺页时 计算内存中的每个逻辑页面的下一次访问时间
- 选择 未来最长时间 不访问 的页面
最优页面置换算法特征
- 缺页次数最少
- 实际系统中无法实现
- 无法预知每个页面在下次访问前的等待时间
- 但是能作为置换算法性能评测依据
最优页面置换算法示例
1 | 第一次 第二次 第三次 第四次都是正常访问的 |
先进先出置换算法 (FIFO First-In First-Out)
选择在内存中驻留时间 最长的 页面进行置换
先进先出置换算法实现
- 维护一个记录所有位于内存中的逻辑页面的链表
- 链表元素按照驻留时间排序 链首最长 链尾最短
- 出现缺页时 选择链首页面进行置换 新页面加到链尾
先进先出置换算法特征
- 实现简单
- 性能较差 调出的页面很可能是经常访问的
- 进程分配物理页面数增加时 缺页不一定减少(Belady 现象)
- 有缺陷 不单独使用 揉到其它算法里一起使用
先进先出置换算法示例
1 | 第一次 第二次 第三次 第四次 都是正常访问 |
最近最久未使用页面置换算法 (LRU Least Recently Used)
属于 最优置换算法 和 先进先出置换算法 的折中
- 选择最长时间没有被引用的页面进行置换
- 某些页面长时间未被访问 则它们在将来还可能会长时间不会访问
最近最久未使用算法实现
- 缺页时 计算内存中每个逻辑页面的上一次访问时间
- 选择上一次使用到当前时间 最长的 页面置换出去
最近最久未使用算法特征
最优置换算法的一种近似
最近最久未使用算法示例
1 | 第一次 第二次 第三次 第四次 都不产生缺页异常 |
最近最久未使用算法可能实现
每次访问开销都很大
- 页面链表
- 系统维护一个按最近一次访问时间排序的链表
- 链表首节点是最近刚刚访问过的页面
- 链表尾节点是最久未使用的页面
- 访问内存时 找到相应页面 并将其移到链首
- 缺页时 置换链表尾节点的页面
- 系统维护一个按最近一次访问时间排序的链表
- 活动页面栈
- 访问时 将页号压入栈顶 并将栈内相同的页号删去
- 缺页时 置换栈底页面
最近最久未使用算法栈实现
1 | 第一 ~ 第四次 相安无事 但要将依次访问过的页 压入栈顶 |
时钟页面置换算法 (Clock)
仅对页面的访问情况进行大致统计 (统计过去一段时间 这个页面是否被访问过 若访问过则留下 没访问过则按照现有顺序做置换)
- 数据结构
- 在页表项加入 访问位 Access 位 描述页面在过去一段时间内访问情况
- 各页面组织成环形链表
- 指针指向最先调入的页面 后绕着环形链表走 看起来很像 时钟
- 算法
- 访问页面时 在页表项 记录页面访问情况
- 缺页时 从指针处开始顺序查找未被访问过的页表进行置换
时钟置换算法特征
时钟算法是 LRU(最久未使用算法) 和 FIFO(先进先出算法) 做折中
因为它既不像 LRU 考虑的那么详细 又不像 FIFO 只在意一段时间内若不访问 就做置换 考虑的那么粗
时钟置换算法实现
- 页面装入内存时 访问位 置 0
- 访问页面 (读/写) 时 访问位 置 1
- 缺页时 从指针当前位置顺序检查环形链表
- 访问位为 0 则置换此页
- 访问位为 1 则访问位置 0 指针继续移动到下一个页面 直到找到可置换页面
时钟置换算法示例
1 | 第一 ~ 第四次访问 的页面都已在环形链表中 故而 只将访问位 置 1 |
改进时钟置换算法
- 时钟置换算法缺点
之前的时钟置换算法如果要置换的页是被修改过的 那么就会先要将修改过的页 写到外存 然后
才将要换入的页读入内存 消耗时间过长
- 改进
减少修改页的缺页处理开销 (如果要置换的页被修改了 则不置换此页 同时操作系统定期将修改过的页写到外存)
- 算法
- 在页面中加入修改位 并在访问时 进行相应修改
- 缺页时 修改页面标志位 以跳过有修改的页面
改进时钟置换算法实例
1 | 第一次 只访问 c 访问位 置 1 |
最不常用算法 (LFU Least Frequently Used)
缺页时 置换访问次数最少的页
最不常用算法实现
- 每个页面设置一个访问计数
- 访问页数 访问计数 + 1
- 缺页时 置换 计数最小的页面
最不常用算法特征
- 算法开销大
- 开始时频繁使用 以后不使用的页面难换出 (因为页面在里面待的越久 访问计数越大)
- 解决方法 较大的计数定期右移
LRU 和 LFU 的区别
- LRU 关注多久未使用 时间越短越好 (维护栈)
- LFU 关注次数 待的越久越好 (稍微简单些)
最不常用算法示例
1 | 每次访问 修改 页面的计数 前 四次访问 都只是 累加 |
LFU 不能够比较快的访问 但是 它可以用在 读取硬盘这种存储访问 时间长一些也没关系
Belady 现象
采用 FIFO 等算法时 可能出现分配的物理页面数增加 缺页次数反而升高的异常现象
产生 Belady 现象的原因
- FIFO 算法的置换特征 与 进程访问内存的动态特征矛盾
- 被它置换出去的页面 并不一定是 进程 近期不会访问的页面
总而言之就是预测(近期不访问的页面)不合理
FIFO 的 Belady 现象
1 | 当物理页面数 为 3 时 使用 FIFO 页面置换算法 共产生 9 次 缺页次数 |
LRU 没有 Belady 现象
LRU FIFO 和 Clock 比较
- LRU 和 FIFO 本质都是 先进先出算法
- LRU 根据页面最近访问时间排序
- LRU 需要动态地调整顺序 (算法性能好 系统开销大)
- FIFO 根据页面进入内存的实际排序
- FIFO 的页面进入时间是固定不变的 (系统开销较小 但会发生 Belady 现象)
当页面进入内存后 没有被访问了 最近访问时间和进入内存的时间相同时 LRU 可退化成 FIFO
- Clock 算法是 它们的折中
- 页面访问时 不动态调整页面在链表中的顺序 只是做一个标记
- 缺页时 再将它移动到链表末尾 (跳过访问位 为 1 的页面)
对于未被访问的页面 LRU FIFO Clock 性能一样 因为都退化到 FIFO 了
对于被访问过的页面 Clock 算法 不能记录准确的访问时间 而 LRU 可以
全局页面置换算法
置换页面的选择范围是所有(所有进程)可换出的物理页面 (考虑的角度是从各个进程所需的内存不同)
- 工作集算法
- 缺页率算法
给进程分配可变数目的物理页面
局部页面置换算法的不足
局部页面置换算法没有考虑进程访存的差异 (进程在不同阶段内存需求是不同的)
(使用局部页面置换算法 无论怎么置换 物理页面始终是那么多 缺页次数不能减少 如果给它加一些物理页面 性能会提高很多)
全局页面置换算法需要解决的问题
- 进程在不同阶段的内存需求是变化的
- 分配给进程的内存也需要在不同阶段有所变化
- 全局置换算法需要确定分配给进程的物理页面数
CPU利用率和并发进程数的关系
- CPU利用率 与 并发进程数存在相互促进和制约的关系
- 进程数少时 提高并发进程数 可提高 CPU利用率
- 并发进程导致内存访问增加
- 并发进程的内存访问会降低访存局部性特征 (两个进程所做的事情不相干 局部性原理不适用)
- 局部性特征下降 缺页率上升和 CPU利用率下降
工作集
一个进程当前正在使用的逻辑页面的集合 可表示为二元函数 W(t, Δ)
- t 是当前的执行时刻
- Δ 为工作集窗口(Working-set window) 一个定长的页面访问时间窗口
- W(t, Δ) 为在当前时刻t前的 Δ 时间窗口中所有访问页面所组成的集合
- | W(t, Δ) | 为工作集大小 页面数量
工作集的变化
- 进程开始执行后 随着访问新页面逐步建立较稳定的工作集
- 当内存访问的局部性区域的位置大致稳定时(只访问那几个页面 没有大的改变时) 工作集大小也大致稳定
- 局部性区域的位置改变时(进程前一项事情做完 去做下一项事情时) 工作集快速扩张和快速收缩过渡到下一个稳定值
常驻集
在当前时刻 进程实际驻留在内存当中的页面集合
- 工作集和常驻集的关系
- 工作集是进程运行过程中固有的性质 (进程在一段时间访问的页面集合)
- 常驻集 取决于 系统分配给进程的物理页面数 和 页面置换算法 (实际在内存中的页)
- 缺页率和常驻集的关系
- 常驻集 包含 工作集时 缺页较少 (进程访问的页都在内存里)
- 工作集发送剧烈过渡时 缺页较多
- 进程常驻集大小达到一定数目后 缺页率不会明显下降 (内存够进程功能使用了 再去加内存 反而效率下降)
工作集置换算法
换出不在工作集中的页面 (并不一定是在缺页时才做 因此开销大)
工作集置换算法实现
窗口大小 τ 当前时刻前τ个内存访问的页引用是工作集
- 访存链表 维护窗口内的访存页面链表
- 访存时 换出不在工作集的页面 (开销大)
- 缺页时 换入页面
工作集置换算法示例
1 | 第一次访问 缺页 装入 c 此时 窗口大小 τ 为 4 不需要换出页 |
缺页率算法 (PFF Page Fault Frequency)
缺页率 (Page fault rate) = 缺页次数 / 内存访问次数(不好用) 更多时候使用 缺页平均时间间隔的倒数
- 影响缺页率因素
- 页面置换算法 (只有这个能自己控制)
- 分配给进程的物理页面数
- 页面大小
- 程序的编写方法 (局部性特征)
缺页率算法实现
通过调节常驻集的大小 使每个进程的缺页率保持在一个合理的范围
- 若进程缺页率过高 则增加常驻集以分配更多物理页面数
- 若进程缺页率过低 减少常驻集 将一些页面置换到外存
- 访存时 设置引用位标记
- 缺页时 计算从上次缺页时间 t_last 到现在 t_current 的时间间隔
- 如果 t_current - t_last > T 缺页率低 则置换 所有在[t_last, t_current]中没有被引用的页 使其用在更有意义的地方(CPU并发率提高)
- 如果 t_current - t_last <= T 缺页率高 则增加缺失页到常驻集中
缺页率算法示例
1 | 第一次访问 出现缺页 直接加(因为没有之前状态可供参考) 第二次 第三次 不缺页 |
跟 工作集算法对比 工作集算法每一次访问都在考虑置换哪一个页面到外存 缺页率算法只有在时间间隔够大的时候 才置换到外存 将置换这一过程放到了 缺页中断来完成
和 局部置换算法一样 开销降低
抖动和负载控制
抖动产生是因为 随着驻留内存的进程数目增加 分配给每个进程的物理页面数不断减小 缺页率不断上升
因此操作系统需在 并发水平 和 缺页率之间达到一个平衡 需要选择一个适当的进程数目 和 进程所需要的物理页面数
- 抖动问题(Thrashing)
- 进程物理页面太少 不能包含工作集
- 造成大量缺页 频繁置换
- 进程运行速度变慢
负载控制
通过调节并发进程数 (MPL Multiprogramming level) 来进行系统负载控制
- 找到 平均缺页间隔时间 (MTBF Mean time between page faults) = 缺页异常处理时间 (PFST Page fault service time) 的范围
