《操作系统 - 清华大学》6 -3：局部页面置换算法：最近最久未使用算法 (LRU, Least Recently Used)

1. 最近最久未使用算法的工作原理

最近最久未使用页面置换算法，简称 LRU， 算法思路：当缺页中断产生之后，要替换哪个页？选择最久未被使用的页，要置换这个页。

最久未被使用和前面的 FIFO 算法里面最长驻留时间不是一个概念。最长驻留时间是存在时间很久，但是它可能最近被访问过，但是最久未被使用页是说它可能很长时间程序都没有读或写页的内容，这叫最久未被使用，所以它和 FIFO 算法的依据是不一样的，它的页面特征是不一样。

本质上来说它是对最优置换算法的近似

它是根据过去来推测应该把哪个页给换出去，而不是根据未来。最优置换算法替换是将来最远未被使用页，将来很久都没被使用的页面，那个页面会被淘汰出去，而这个是过去很长时间都没访问的页，这两个正好在两头。
  ~  
LRU 算法其实是根据历史来推测未来，最优置换算法是根据未来推测未来，但是在不知道未来情况下，那根据过去的访问情况来推测将来访问情况，也是一种合理的选择。
  ~  
那这个合理性是基于程序的局部性原理，程序运行过程中具有一定局部性特征，时间局部性和空间局部性，在最近一段时间之内，程序访问的代码和数据，在未来一段时间也还有很大的概率还会持续访问，还会被频繁访问，这是局部性，有了局部性之后，LRU 的依据就是合理了。
  ~  
既然有这么一个特征，那么如果说在当前这段时间之内，某些页没有被访问，那也意味着接下来一小段时间它也很可能没被访问，这是局部性原理的反推，基于这个特征，如果程序是具有局部性特征的程序，LRU算法其实会比较好地预测未来发生情况。

2. 最近最久未使用算法示例

还是刚才访问序列，如果采取 LRU 算法会产生多少次访问中断，还是同样的一幅图：

1. 前四次 1 2 3 4 访问序列是 c a d b，刚才已经说这几个页都在物理内存中，所以不会产生缺页中断
2. 第五次时，依据 LRU 算法，把最久未被使用页面给替换出去， a 页面访问时刻是2 ，b 是 4 时刻，c 是1时刻访问，d 是 3 时刻，很显然 c 是最久未被访问页，所以当第 5 个时刻访问 e 时候，需要去替换最久没有访问页是 c。
3. 访问 b， b 还在物理页中，所以不会产生中断。那么 6 7 8 这三个时刻访问页序列，由于 a 和 b 都还在物理内存中，所以不会产生中断
4. 第 9 个时刻要访问 c 了，那么应该换出哪个页？a 是在第7个时刻访问，b 是在第8个时刻访问，都是离这个 c 很近，但不代表很久，d 是在第3时刻访问，而 e 是在第5时刻访问，那么很明显在这里面就是 d 页面是最久未被访问页面，所以说会把 d 给换出去，然后把 c 换进来，产生第二次缺页中断
5. 接下要访问 d，刚把 d 换出去，这时候应该换哪页？当前最久未被访页是 e，所以说要把 e 给换出去

采取 LRU 算法之后产生了三次中断，比 FIFO 算法要少一些。

3.LRU算法实现

LRU算法找的是最久未被访问页，如果要有效实现算法，它需要记录每个页使用时间的先后顺序。主要采取某种方法记录起来，记录时间顺序的执行开销是比较大的，目前有两种可能的实现方法

3.1 LRU的页面链表实现

第一个是用链表来实现，如果说系统里面能够维护一个当前访问的页面链表，那么最近刚刚访问的页面作为首节点，放在链表的头，而最久未被使用页面放在链表的尾。

当运行程序访问内存的时候，需要看看这个内存对应的这个页是否在这个链表里面。如果在这链表里面，需要把这个页从某一位置替到链表头上，因为它当前正在被访问，代表最近访问页。如果没有的话，就把这个页插入链表中。

如果产生一次缺页中断，需要替换链表中的某一页，很明显，因为链表会把最近访问页靠近链表头，只有最久访问页放在链表尾，所以直接从链表尾把这个页给摘出来，就可以作为要替换出去的页，这是一种方法。

3.2 LRU的活动页面栈实现

第二个办法用堆栈，设置一个当前访问页的堆栈，当访问某个页时候就把这个页先压入栈顶，然后再考察栈内是否有跟这个页相同的页号，如果有，把这个页抽出来不要了，因为已经把页压到里面去了，但它需要去查找在这个栈中是否已经存在这个页号，如果存在踢出去，这个查找过程开销比较大。和刚才说的链表查找过程是一样的，都需要去查找在链表和堆栈中这个页是否存在。

如果又产生缺页中断，需要淘汰一页，那淘汰哪个？就要选择堆栈的栈底，就类似前面链表的尾部页面，因为这个页面代表它最久未被访问的页面。

刚刚那个图做例子，如果用所谓堆栈的办法来实现，就这么操作过程：

底下有 LRU 配置的 stack，就是分配一个堆栈，当每一次访页，就把这个页号压在里面去，同时还要看看这里面是否存在相同的页号，如果有把它剔出去。

1. 当走到了第 5 时刻，访问 e ，产生缺页异常，产生缺页中断之后，需要把栈的尾部给替换出去，这时候就把 e 给压栈里
2. 第 6 时刻，把 b 放栈里面去，但由于 b 已经在页帧中，会把 b 从栈中去掉，使得 b 从栈的中间位置调到栈顶。
3. 同理，第 7 时刻访问 a，会把 a 从栈的某一位置调到栈顶

这就是 LRU 算法基于栈来实现的大致处理过程。可以看到在这里面每次访问都需要去查找这个栈，那如果说这个内存中物理页帧比较多的情况，那其实查找很费时，所以整个过程实现开销是大。

3.3 链表实现 VS 堆栈实现

那这是两种实现方式，每一次内存访问某一页的时候，可能都需要去做一次查找，看这个页是否在链表中，或者说是否在堆栈中，可以做一些相关操作。那这个过程其实开销挺大。

LRU 算法表面上看起来效果不错，但是如果要把它放到操作系统里面去，需要考虑代价，它的结果虽然不错，如果代价太大，它不是一个合适的实现方法。

操作系统设计讲究的第一要高效，第二要简洁，既要达到好的效果，还要实现得快捷。如果说为了实现好效果，要花很大的代价，那整个系统性能就受到很大影响，操作系统占时间越多，也意味着留给应用程序时间越少，所以说希望操作系统用最少时间获得最佳效果，它需要一个 balance，所以 balance 情况下 LRU 算法的实现开销很大，所以它也不是一个有效的方法。