[操作系统] 第 6 章：页面替换算法（第 1 部分：本地化页面替换算法）
目录
- 局部页面置换算法
- 最优页面置换算法
- FIFO先进先出
- LRU最近最久未使用算法
- Clock时钟页面置换算法
- 二次机会法Enhanced Clock
- Belady现象
- FIFO/LRU/Clcok的比较
正文
局部页面置换算法
功能：当缺页中断发生，需要调入新的页但是物理内存已满，此时需要把当前一部分页换出去，空出空间。选择内存中哪一个页被替换
目标：
1.尽可能减少换入和换出的次数。具体来说，把未来不再使用或者近期不会使用/较少使用的页面换出，通常只能在局部性原理指导下依据过去的统计数据预测。
2.页面锁定。 有一些物理页是需要常驻内存的，比如OS相关的代码和数据，这些随时都有可能访问，那么这些页我们需要常驻访问。我们用页面锁定技术，把相关的页放在内存里，使得这些页不在页面置换算法的考虑范围内。
例子：
（3,0）这个序列的意思是访问了第三个页面的第0个便宜。也就说（页序号，偏移量object）。我们这里可以忽略他的偏移量，只考虑页序号。因为只有当一个页不存在的时候，才会产生缺页中断，才需要考虑页面置换。在同一个页里面有多次访问，只有第一次访问才有可能产生缺页中断，所以我们可以忽略偏移量只考虑页号。
最优页面置换算法
这个算法可以说是一个不太实际的算法，但是我们可以把它作为一个评价标准。这个算法根据未来的情况进行推算，一般来说缺页次数产生最少。一般我们用其他页面置换算法运行后的结果与最优页面置换算法比较，比较缺页次数，只要能够尽量逼近最优选法，我们就可以认为这是一种比较好的算法。
根据最优页面置换算法，由于访问之前物理内存中已经存储了abcd，所以前四次访问不会改变物理内存中的页。但是当第五次访问发生时，根据换出距离下次访问时间最长的页，得应该换出d置入e，则此时物理内存中是abce，没有d。则当下次访问d时，应该换出最长等待时间的c。第十次访问后，物理内存的页编号是abde
FIFO先进先出
链表（List），典例是程序中的Queue。
产生缺页中断次数比较多。
Belady现象：当我们给一个程序分配更多的物理页时，它的缺页次数应该减少，但是FIFO可能会导致分配的物理页越多，缺页次数增加的现象。
先入先出原则，替换list中滞留时间最久的那一个。
| 内容 | 内容 | 内容 | 内容 | 时间点 |
| a | b | c | d | 0 |
| a | b | c | d | 1 |
| a | b | c | d | 2 |
| a | b | c | d | |
| a | b | c | d | |
| e | b | c | d | |
| e | b | c | d | |
| e | a | c | d | |
| e | a | b | d | |
| e | a | b | c | |
| d | a | b | c |
LRU最近最久未使用算法
和最长滞留时间不同，最长滞留时间是在物理内存中驻留时间很久，但是他可能在近期被访问过；这个算法是换出在队列中最长时间没有被访问的页。根据程序局部性原理，在最近的一小段时间内，程序访问的代码和数据未来还有可能会继续访问，所以LRU就是合理的，因为反推局部性原理，一段时间内没用，那么接下来一段时间也可能不会用到。
缺页中断：3次
*：较久访问 标记越多，程序内优先级越高
粗体：置换/更新访问，当内存内数据被访问时，其替换优先级清零
| 访问请求 | c | a | d | b | e | b | a | b | c | d | 最终 |
| 默认a | a | a | a* | a** | a*** | a**** | a | a* | a** | a*** | a |
| 默认b | b | b | b | b | b* | b | b* | b | b* | b** | b |
| 默认c | c | c* | c** | c*** | e | e* | e** | e*** | e**** | d | d |
| 默认d | d | d | d | d* | d** | d*** | d**** | d***** | c | c | c |
LRU需要记录各个页面使用时间的先后顺序，开销比较大。目前有两种可能的实现方法。
1.使用链表[List]。每当一个页面被访问时，如果内存中有这个页，则将其放在首，最久访问自然会在不断换头的过程中排序放在尾部。没有的数据则淘汰链表尾部，然后插入首部。
例子：
| 头 | 内容 | 内容 | 尾 | 更新 |
| a | b | c | d | default |
| c | a | b | d | c |
| e | c | a | b | e |
| a | e | c | b | a |
2.使用堆栈。
页面置入栈顶后，查找是否有相同页号这个过程开销比较大。栈底一定是最久未被使用，所以需要替换时，直接替换栈底。
总结：LRU算法，结果虽然不错，但是他的开销比较大。他不是一个合适的实现方法,OS设计讲究高效且简洁，为了实现效果而花费很大代价，则得不偿失。需要一个平衡。
Clock时钟页面置换算法
LRU的近似，FIFO的改进。没有LRU的精确，但是能够近似的表明访问的先后顺序状态的算法