页面置换算法

最佳置换算法和先进先出置换算法

先介绍的这两种算法都是极端的算法。最佳置换算法是一种理想条件的算法（现实生活不可能出现），主要是用作衡量其他算法的优劣。而先进先出算法是最直观的算法。

最佳置换算法

最佳置换算法的原理是：在置换点，未来最长时间不在访问的页面被置换出去。

前三个物理块被装满的时候，从第四个物理块开始就要使用置换算法了。

我们看到第三个物理块是（7，0，1），第四个需要被换入的是 2 这个页面，因为物理块中没有 2 ， 所以要判断，因为 7 是在未来时间里，最远出现的，所以被换出。

同理可以得出其他的答案。

先进先出算法

和队列的先进先出一样，先进来的先被换出去

我们看到到第三个物理块已经满了，此刻才需要执行置换算法，因为 7 是最先进来的页面，所以 7 被换出。

其他同理。

特别注意的是，这里的“先”一定是严格的出现在最前面，如上图中第五个竖框（2，3，1）中，3 将 0 替换掉了，这是因为 0 是现在框中最早出现的页面，即使我们看到上一次才刚刚访问了 0 页面。

Belady 现象：FIFO 独有的 Belady 现象是指，当分配的物理块数增多的时候，缺页率反而升高。

最近最久未使用

最近最久未使用（LRU）

和最佳置换算法不同的是，LRU 是面向过去，也就是通过过去最久没有使用的页面作为置换的页面。

还是分析第四次，当要换入 2 时，分析 7 这个页面是过去最久没有使用的页面（因为只有第一次使用），所以 7 被换出。

其他的位置可同理算出。

硬件支持

LRU 算法是需要硬件支持的，这里有两种方式

1. 寄存器
2. 栈

关于硬件支持的原理这里不展开，需要了解的同学请自行百度。

Clock 置换算法（最近未用算法）

因为 LRU 算法需要硬件支持，实际应用中更多采用近似算法。其中就有 Clock 算法

简单的 Clock 置换算法

该算法的原理是，为每一页设置访问位，将所有页通过指针链接成循环队列，就好像形成了一个圈或者环，所以叫 Clock 。

按照队列的顺序，从队头开始，那么访问位 A（请求页表中，访问位用 A 表示）为 1 ，就置 0 ，且不被换出。如果是 0 ，就换出。

（PS：A = 0 表示最近未使用，A = 1 表示最近使用）

如果一圈队列都没有找到置换页，就从头循环即可。

我们看到，指针当前指向页框 2，下一针是页框 3，两者都是 A = 1（Use = 1），所以右图均被置 0 ，而左图到页框 4（page 556）时，看到为 0，所以被换出，在右图被 page 727 替代。

改进的 Clock 算法

我们知道，一个页面如果被修改过，那么在置换时就需要被重新写入磁盘，而没有修改过，就直接放弃，这个是页面调入策略的知识，这里不展开讲。所以算法工程师就加入了修改位 M 和之前的访问位 A 结合，创造了更合理的算法。

算法的原理

首先进行 1 类扫描，如果找不到就进行 2 类扫描，（PS：还是基于 Clock 算法，只是增加了一个修改位 M 进行判断）。

如果 2 类也找不到，就重复 1 类扫描。所以实际上是在 1，2 类中扫描。

最后将找到的页面置换出来即可。