操作系统-最近最久未使用置换算法
操作系统-最近最久未使用置换算法
思想 ：赋予每个页面一个访问字段，用来记录相应页面自上次被访问以来所经历的时间t，当淘汰一个页面时，应选择所有页面中其t值最大的页面，即内存中最近一段时间内最长时间未被使用的页面予以淘汰
优点 ：由于考虑程序访问的时间局部性，一般能有较好的性能，实际应用多
缺点 ：实现需要较多的硬件支持，会增加硬件成本
LRU的硬件支持-栈 ：可利用一个特殊的栈来保存当前使用的各个页面的页面号。每当进程访问某页面时，便将该页面的页面号从栈中移出，将它再压入栈顶。即栈顶始终是最新被访问页面的编号，而栈底则是最近最久未使用页面的页面号
例子 ：
假设最小物理块数为3块。页面引用序列如下：
7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1
缺页次数：12次 缺页率：12 / 20 = 60%
解析：
（1）首先，我们先借助栈来实现各页面最近最久未使用的排序
按照页面访问顺序，页面7放入栈底，然后是页面0，再然后是页面1，栈已满
当访问页面2时，栈底的页面7出栈，页面2放在栈顶
当访问页面0时，栈中已有页面0，则重置，页面0放在栈顶
当访问页面3时，栈底的页面1出栈，页面3放在栈顶
当访问页面0时，栈中已有页面0，则重置，页面0放在栈顶
以此类推，便可得到如图栈的情况
（2）然后
进程运行时，当进程要访问7, 0, 1三个页面时都会产生缺页中断
按照页面访问顺序，当进程要访问页面2时，内存中没有页面2，产生缺页中断。内存中的三个页面7, 0, 1，页面7在内存中最近一段时间内最长时间未被使用，所以淘汰页面7，页面2装入物理块1。可以观察到在栈中对应访问页面2下，有页面2，1，0，页面7已经被淘汰了，所以让页面2代替页面7的位置
按照页面访问顺序，当进程要访问页面0时，页面0在物理块2中，不会产生缺页中断
按照页面访问顺序，当进程要访问页面3时，内存中没有页面3，产生缺页中断。此时内存中有页面2，0，1。观察对应下面栈中有页面3，0，2，所以让页面3代替页面1的位置
按照页面访问顺序，当进程要访问页面0时，页面0在物理块2中，不会产生缺页中断
按照页面访问顺序，当进程要访问页面4时，内存中没有页面4，产生缺页中断。此时内存中有页面2，0，3。观察对应下面栈中有页面4，0，3，所以让页面4代替页面2的位置
以此类推，便可得到如图情况