深入理解 操作系统 LRU算法（以洛谷P1540题为例）

LRU算法

L e a s t R e c e n t l y U s e d Least Recently Used LeastRecentlyUsed 算法，意为“最近最少使用”，这是操作系统内存管理部分重要的一个页置换算法。

解释：LRU chooses that page that has not been used for the longest period of time.

追溯Operating System

Operating System 中特别重要的三个页置换算法：

• First-In-First-Out (FIFO) Algorithm
• Optimal Algorithm
• Least Recently Used (LRU) Algorithm

当然还有很多其他算法，比如LRU Approximation Algorithms，不提……

Optimal Algorithm 与 LRU Algorithm

Optimal Algorithm 为什么是“最优”呢？因为它着眼未来，但实际上，“未来并不可以准确预测”，所以不能在计算机上真正实现，但LRU是可以的。

LRU的思想，恰如其名，着眼于过去，它根据过去的使用做出判断。

简而言之，就是“谁最近没被用过，就把谁换出去”，栈和队列这样的数据结构就可以帮助我们实现这一点。 当然，也可以对页面的引用时间进行计时，通过计时进行页置换。

LRU算法实例

给出一个 reference string ：“7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1”，置换顺序如下：（注意下图前三次也是换进去的呀，每个页都是经历Demand Paging才得以从外存换入内存的）

栈实现的解读

比如下图，在 a → b 的时候，相当于把7号页从栈中抽出来放到栈底（注意栈底在顶部），从栈顶换出页，新换入的页插入栈底。（实际上就相当于队列结构啦）

洛谷P1540题 题目要求

P1540题目链接

分析

在有经验的人看来，确实，普通的模拟+使用队列作为辅助数据结构，一个小题。

问题是，你还想到了什么？ 没错——LRU算法！

其实这题的背景本身就是OS的虚拟内存页置换算法啊！

AC代码（Java语言描述）

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Queue queue = new LinkedList();
        Scanner scanner = new Scanner(System.in);
        int limit = scanner.nextInt(), num = scanner.nextInt(), counter = 0, result = 0;
        while (queue.size()