zhuanlan.zhihu.com/p/391327282
页面置换算法
当需要调入新页面，但内存已满时，页面置换算法 选择一个被换出的页面，再将新页面载入
先进先出算法
OPT页面置换算法
最佳算法（OPTimal）：选择未来最久不被访问的
不可能实现！（预测未来最热卖的商品）
意义：给出理论上的最好结果，以供比较
最近最久未使用（Least Recently Used）LRU
选择自上次被访问以来经历时间最久的
硬件开销太大，难以实现
实际OS中，采用近似LRU的方法
Clock算法
循环队列，依次检查。若A（访问位）=0，换出；若A=1，置A=0，检查下一个。
改进后
不仅利用访问位A，还利用修改位D
- A=0，D=0，最近未访问，也未被修改；
- A=0，D=1，最近未访问，但被修改；
- A=1，D=0，最近被访问，但未被修改；
- A=1，D=1，最近被访问，且被修改。
AD=00最应该被替换，AD=11最不应替换
页面分配策略
给每个进程分配至少多少个物理块
固定分配和可变分配
给每个进程分配多少个物理块？
固定
- 平均分配算法
- 比例分配算法
- 优先级分配算法
可变
允许分配给进程的物理块数随时间变化
全局&局部置换
可变分配在置换时，换出属于谁的页面？
若每个进程已经固定分配物理页面数量，则不可能去抢夺其它进程的页面，因而也就不可能全局置换。
全局置换（Global Replacement）
- 可以置换所有进程的页面
局部置换（Local Replacement）
- 仅置换进程自己的页面
页面缓冲算法
页缓冲算法（PBA，Page Buffering Algorithm）
- 空闲页面池，统一管理空闲的物理页面
- 修改页面池，将D=1的页面暂存
好处：防止将被换出的页面马上又要使用的情况（house keeping）
实用策略-工作集
- 进程开始执行后，随着访问新页面逐步建立较稳定的工作集
- 当内存访问的局部性区域的位置大致稳定时，工作集大小也大致稳定
- 局部性区域的位置改变时，工作集快速扩张和收缩过渡到下一个稳定值
抖动
- CPU利用率与并发进程数存在相互促进和制约的关系
- 进程数少时，提高并发进程数，可提高CPU利用率
- 并发进程进一步增加，导致内存访问增加
- 分配给每个进程的物理块太少，导致缺页率上升和CPU利用下降
- 抖动：每个进程频繁的缺页，换进/换出
- 抖动
- 进程物理页面太少，不能包含工作集
- 造成大量缺页，频繁置换
- 进程运行速度变慢
- 产生抖动的原因
- 随着驻留内存的进程数目增加，分配给每个进程的物理页面数
- 不断减小，缺页率不断上升
- 抖动的预防方法
- 采用局部置换策略
- 把工作集算法融入处理机调度
- “L=S”准则
- 选择暂停的进
