操作系统中的页面置换算法很多，其中有一种性能仅次于最佳算法的算法——LRU（最近最少使用），但这一算法在操作系统层面，不好实现，因为需要记录内存块的访问情况，以便在换出页面时选择“最近最少使用”的页面换出，而记录这些信息无疑需要额外的硬件支持，物理块数多的话，需要好多的寄存器，寄存器的造价有比较贵，这些可都是白花花的银子，所以实际操作系统并不使用LRU作为置换算法。

不过在操作系统之上，随便定义个数组、哈希表就可以当作内存物理块区，所以实现起来很简单，为了方便，下面使用Java实现。

为了提高查找效率，这里选用哈希表作为内存物理块区，当然也可以使用数组、链表啥的。

思路（很简单）：

1. 维护一个最近访问链表，数据放到物理块中，同时也插入到链表中（元素越靠后表示上次访问距离现在最近）
2. 如果物理块未满，直接插入，同时也插入到链表中
3. 如果物理块满了，则替换掉链表第一个元素所在的物理块，同时也插入到链表中

以下面这个题目为例（物理块数为3，缺页12次）：

import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;

public class LRUCacheOS {
    int capacity;
    HashMap<Integer, Integer> block = null;
    List<Integer> recently = null;
    int nums = 0;

    public LRUCacheOS(int capacity) {
        this.capacity = capacity;
        this.block = new HashMap<>();
        this.recently = new LinkedList<>();
    }

    public int get(int key) {
        if (this.block.containsKey(key)) {
            recently.remove((Integer) key);
            recently.add(key);
            return this.block.get(key);
        } else {
            this.put(key, 1);
            this.nums++;
        }
        return -1;
    }

    public void put(int key, int value) {
        if (this.block.containsKey(key)) {
            this.recently.remove(key);
            this.recently.add(key);
        } else if (this.block.size() < this.capacity) {
            this.block.put(key, value);
            this.recently.add(key);
        } else {
            this.block.remove(this.recently.get(0));
            this.block.put(key, value);
            this.recently.remove(this.recently.get(0));
            this.recently.add(key);
        }
    }

    public static void main(String[] args) {
        int blocks = 3; // 物理块数量
        int[] data = {
                7, 0, 1, 2,
                0, 3, 0, 4,
                2, 3, 0, 3,
                2, 1, 2, 0,
                1, 7, 0, 1
        };

        LRUCacheOS lru = new LRUCacheOS(blocks);
        for (int i = 0; i < data.length; i++)
            lru.get(data[i]);

        System.out.println("缺页中断次数：" + lru.nums);
    }
}