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 2 3 4 5 6 7
| 类别 | 访问 | 修改 | R | M -------------------------------------- 第0类:| 没有被访问 | 没有被修改 | 0 | 0 第1类:| 没有被访问 | 已经被修改 | 0 | 1 第2类:| 已经被访问 | 没有被修改 | 1 | 0 第3类:| 已经被访问 | 已经被修改 | 1 | 1 --------------------------------------
|
现在内存中的每个页都是这0到4的其中一种。那么当发生缺页中断的时候,NRU算法就会从类别编号最小的一堆页中 随机 换出。