页面置换算法概念：
1、功能：
当出现缺页异常时，需调入新页面，而内存已满时，置换算法选择被置换的物理页面
2、设计目标：
尽可能减少页面的调入调出次数
把未来不再访问或短期不再访问的页面调出
3、页面锁定：
描述必须常驻内存的l逻辑页面
操作系统的关键部分
要求响应速度的代码和数据
页表中的锁定标志位
4 、置换算法的评价方法：
记录进程访问内存的页面轨迹
模拟页面置换行为，记录产生缺页的次数
更少的缺页，更好的性能
5、分类：
局部页面置换算法：置换页面的选择范围j仅限于当前进程占用的物理页面
- 最优算法，先进先出算法，最近最久未使用算法
- 时钟算法，最不常用算法
全局页面置换算法：置换页面的选择范围是所有可换出的物理页面 - 工作集算法，缺页率算法
最优算法，先进先出算法，最近最久未使用算法
- 最优算法：
基本思路：置换在未来最长时间不访问的页面
算法实现：
缺页时，计算内存中每个逻辑页面d的下一次访问时间，选择未来最长时间内不访问的页面
算法特征：
缺页最少，是理想情况
s实际系统中无法实现
无法预知每个页面下次访问q前的等待时间 - 先进先出算法
思路：选择在内存驻留时间最长的页面进行置换
实现：
维护一个记录所有位于内存中的逻辑页面链表
链表元素按照z驻留内存的时间排序， - 最近最久未使用算法：
思路：选择最长时间没有被y引用的页面进行置换
如果某些页面长时间未被访问，z则他们在将来还可能会长时间不被访问
时钟置换算法和最不常用置换算法
- 时钟置换算法：
思路：对页面访问情况进行大致统计
数据结构：
在页表项中增加f访问位，描述页面在过去一段时间内的访问情况
各页面组织成h环形链表
指针指向最先调入的页面
算法：
访问页面时，z在页表项记录页面访问情况
缺页时，c从指针处开始顺序查找未被访问的页面进行置换 - 最不常用算法：
思路：
缺页时，置换访问次数最少的页面
实现：
每个页面设置一个访问计数
f访问页面时，访问计数+1
缺页时，置换计数最小的页面
Belady现象和局部置换算法
- Belady现象
现象：
采用FIFO等算法时，可能会出现分配的物理页面数增加，缺页次数反而s升高的异常现象
原因：
FIFO算法的置换特征与进程访问内存的动态特征矛盾
被它置换出去的页面并不一定是进程近期不会访问的
全局置换算法：
- 工作集置换算法
思路：给进程分配可变数目的物理页面
要解决的问题：
进程在不同阶段的内存需求是不断变化的
分配给进程的内存也需要在不同阶段进行变化
全局置换算法需要确定分配给进程的物理页面数
思路：
换出不在工作集中的页面
窗口大小t
当前时刻前t个内存访问的页引用是工作集，成为时间窗口大小
实现方法：
访存链表
