简述几种简单的页面置换算法
0X00 最优算法—不可能实现算法
最优算法听起来很棒，但是 实现起来是不可能的 。最优算法是：当发生缺页中断时，将最晚会用到的页换出。也就是说，有三个页，现在发生了缺页中断，第一个页在第201条指令的时候会用到，第二个页在第5001条指令的时候会用到，第三个页在第20000条指令的时候会用到，那么第三个页面就是最晚会被用到的，就将其换出。这样确实是最好的效率，但是真正实现不了的原因是：程序不可能知道自己在什么时候需要哪些内存，所以就不能找到最晚会被用到的页。因为要用未来的事情来判断所以我一般称之为未来算法。虽说实现不了，也不是说这个算法就没意义了。这个算法最大的意义就在于可以比较效率。效率越是接近最优算法的就越好，当一个算法已经能达到最优算法效率的101%时，就没必要累死累活的去优化效率了，可以去找一些别的瓶颈了。
0X01 最近未使用—NRU
如果说最优算法叫未来算法的话，那么这个最近未使用就可以叫做历史算法，这样就好理解了。当系统发生缺页中断的时候，在内存中找到最久没被用过的页，将其换出。有一种实现方法：给每一个页设置一个 R(read)位和M(modify)位 。当一个进程启动的时候将这个进程的所有页的RM位都设置为0。然后每访问一个页就将R位置为1，每修改一个页就将M置为1。系统每隔一段时间就将所有页的R置为0。那么这里就会出现四种页，其实这里只是一个表示，比如第1类。不可能出现一个没被访问就修改的页，但是第3类页经过一段时间之后将R置为0的话就是第1类了。
1 | 类别 | 访问 | 修改 | R | M |
现在内存中的每个页都是这0到4的其中一种。那么当发生缺页中断的时候，NRU算法就会从类别编号最小的一堆页中 随机 换出。
0X02 先进先出—队列置换算法 FIFO
这种算法相对容易实现，就像是数据结构中的 队列 一样。每次的新页放在队列尾部，当发生缺页中断时将队列头部的页踢掉，将新页放到队列尾部。这种算法有一个非常严重的问题就是会踢掉一些必要的页，比如操作系统核心功能。想想系统启动的时候，首先加入了10000个页以用来运行操作系统，但是发生缺页中断的时候就会将核心页换出去，然后因为核心页被换出去了就需要再换进来，有可能就造成了连续10000个页从队首换到了队尾，产生了20000个操作。
0X03 第二次机会—FIFO改进
因为FIFO会将所有队尾直接踢出去，第二次机会就是给了每个页面再一次机会。也就是说：每个页面还是有一个R位，然后有一个时间位用来记录装入时间。每当发生缺页中断的时候查看队首页的R值，如果R值为0那么就将其换出，否则就将其R值设置为0，并设置‘装入时间’（在哪个时钟的时候装入的），然后再从队首的下一个页开始判断。
0X04 时钟算法—CLOCK
因为二次机会算法还是基于单向链表的，所以会经常需要在链表中移动页面，虽然是在内存中操作但还是会浪费资源。这里就把单向链表改成了 环形链表 。当发生缺页中断的时候，检查指针指向的页面，如果页的R位是0则提出这个页面将新的页加到这个位置，并设置R位为1；否则就将当前的R位设置为0并将指针下移。所以时钟算法也可以理解成是第二次机会算法的改进版本。
图片来源：《现代操作系统》 Andrew S. Tanenbaum
0X05 最近最少使用置换算法—LRU
有这样一种情况：“在前面几条指令中频繁使用的页很可能在后面的及条指令中被使用”，所以说已经很久没有用过的页很可能在未来的一段时间内也不会被用到。所以可以在发生缺页中断的时候将最久未使用的页替换出去。为了实现LRU算法需要将所有页串成一个链表，链表的一端是最常使用的页，另一端则是最不常用的页，每次调用一个页的时候都要将整个链表更新，但移动整个链表是很慢的。
可以通过特殊硬件来实现LRU。
第一种方案：这里需要一个64位的计数器，计数器在每条指令执行完成之后自动加一，且每个页表项中需要需要足够容纳这个计数器。在每次访问内存的时候将当前计数器的值赋值给该页表项的对应区域。当发生缺页中断的时候找到每个页表项中该值最小的，这个页表项就是最近最少使用的。
需要注意的一点是： 这个计数器只有一个 而不是每个页表项一个；每个页表项里只是有一个可以容纳这个计数器的位置，也就是说要有一个64位的空间来保存数字。这里保存的数字不会随着指令的执行而自增，随着指令执行自增的就只有那个唯一的计数器。
第二种方案：假设某机器有n个页框，那么LRU硬件就是一个n * n的矩阵，初始化为零矩阵。当访问页框k时 先 将k行全部置1， 再 将k列全部置0。在任意时间二进制数值最小的行就是最近最少使用的，第二小的就是下一个最近最少使用的。
0X06 最不常用置换算法—NFU
因为LRU算法需要独立的硬件设备，然而大多数计算机并没有这种硬件，所以需要一个能用软件实现的解决方案。这种成为NFU的最不常用置换算法就是一种使用软件模拟LRU的实现。在NFU中针对每一个页设置一个计数器，每当发生缺页中断时刷新所有的页对应的计数器，先将每一个页的R值（R值用来标识该页是否用过，为0或1）加到计数器上，再将R置0。这个计数器基本可以反映某个页的使用频率。当发生缺页中断的时候就可以踢出计数器最小的页。
这个算法的一大问题就是：记忆力太强。比如说我开机的时候开机相关的页可能调用了10万次，开机之后其他的东西并没有这么高的使用率，但是因为这些页的计数器太大了，所以不会被轻易踢出去，就会导致有一批‘元老页’滞留在内存中浪费空间。
可以通过一个简单的小修改解决这个问题：首先在R值加到计数器之前先将计数器右移一位（二进制移位，最后一位抛掉），其次将R位加入到计数器的最左端，而不是最右端（简单的NFU是加入到最右端的）。经过这种修改的算法称之为 老化算法 。因为这种算法中新的操作会对计数器产生较大的影响，可以让以前的计数器迅速变老，所以称为老化算法。