手撕操作系统中的页面置换算法

操作系统基础 内存换页算法

公平算法：

• 随机算法、先来先出（FIFO）算法、第二次机会算法、时钟算法

非公平算法：

• 最优OPT算法、NRU算法、LRU算法、工作集算法、工作集时钟算法

其中LRU算法会被面试的时候要求手撕， 因此本篇就稍微介绍一下LRU和LFU两个算法， 这两个算法除了在内存换页上会被使用到，

简单介绍一些算法：

随机更换算法

需要替换页面的时候，产生一个随机页面号，替换与该页面对应的物理页面。

先来先出（FIFO）算法

更换最早进入内存的页面。其中有Belady异常现象: 缺页率随内存块数增加而增加

最优OPT算法：

最佳置换算法是由Belady于1966年提出的一种理论上的算法。其所选择的被淘汰页面将是以后永不使用的，或许是在最长（未来）时间内不再被访问的页面。
采用最佳置换算法通常可保证获得最低的缺页率。

▲由于人们目前还无法预知，一个进程在内存的若干个页面中，哪一个页面是未来最长时间内不再被访问的，因而该算法是无法实现的。

Q： 既然无法实现， 那么他的价值是什么呢？

A： 他被作为评价一个内存换页算法效率的标榜

NRU算法

最近未使用算法（Not Recently Used，NRU），就是选择一个最近没有被访问的页面来替换，在所有的最近没有使用的页面里，按照各个页面的修改位和访问位的组合来进行划分。相比LRU需要较多硬件支持， NRU算法在页表项设置两个状态位：引用位R和修改位M

LRU

Q、什么是 LRU 算法?

A: Least Recently Used最近最久未使用算法，本质一种缓存淘汰策略。

计算机的缓存容量有限，如果缓存满了就要删除一些内容，给新内容腾位置。但问题是，删除哪些内容呢？我们肯定希望删掉哪些没什么用的缓存，而把有用的数据继续留在缓存里，方便之后继续使用。那么，什么样的数据，我们判定为「有用的」的数据呢？

LRU 缓存淘汰算法就是一种常用策略。LRU 的全称是 Least Recently Used，也就是说我们认为最近使用过的数据应该是是「有用的」，很久都没用过的数据应该是无用的，内存满了就优先删那些很久没用过的数据。

▲同时它也是一种换页算法， 在内存换页上需要较多的硬件支持（计数器or栈）

常见的缓存算法

• LRU (Least recently used) 最近最少使用，如果数据最近被访问过，那么将来被访问的几率也更高。
• LFU (Least frequently used) 最不经常使用，如果一个数据在最近一段时间内使用次数很少，那么在将来一段时间内被使用的可能性也很小。
  • LFU由于涉及频率, 因此在代码实现上有个计数器来统计出现次数T，在需要换页（缓存更新的时候）将替换掉最低T的key
• FIFO (Fist in first out) 先进先出， 如果一个数据最先进入缓存中，则应该最早淘汰掉。

LRU算法与OPT算法比较

OPT是从“向后看”的观点出发的，即它是依据以后各页的使用情况进行判断，是理想状况；而LRU算法则是“向前看”的，即根据各页以前的使用情况来判断，而页面过去和未来的走向之间虽无必然的联系，但也有一定的预测关系。
总的来说，LRU算法是一种比较好的算法。

Q: 算法要求

LRU 算法实际上是让你设计数据结构：首先要接收一个 capacity 参数作为缓存的最大容量，然后实现两个 API，一个是 put(key, val) 方法存入键值对，另一个是 get(key) 方法获取 key 对应的 val，如果 key 不存在则返回 -1。其中， get(key)的时候会把这个新查询的key放到最前端

由于性能要求，get 和 put 方法必须都是 O(1) 的时间复杂度。

• get需要O(1) --> hash or 线性表
• put需要O(1) -->链表

Coding实现

package lru;

import java.util.HashMap;
import java.util.Map;

public class LRUCache {
    class Node {
        Integer key;
        Integer val;
        // 双向列表: 前后向节点
        Node nxt, prev;

        public Node() {
        }

        Node(int k, int v) {
            this.key = k;
            this.val = v;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "key=" + key +
                    ", val=" + val +
                    '}';
        }
    }

    class DoubleList{
        private int size;
        // 头尾空指针
        private final Node head;
        private final Node tail;

        DoubleList() {
            // 初始化
            this.size = 0;
            this.head = new Node();
            this.tail = new Node();
            this.head.nxt = tail;
            this.tail.prev = head;
        }

        /**
         * 将节点到头部, head->nxt = node;
         * @param node 待插入节点
         */
        public void addFirst(Node node){
            // 4个指针关系
            node.nxt = head.nxt;
            node.prev = head;
            head.nxt.prev = node;
            head.nxt = node;
            // 记得增加当前容器Size
            this.size ++;
        }

        public void remove(Node node){
            // 略过当前节点, 调整前后指针
            node.nxt.prev = node.prev;
            node.prev.nxt = node.nxt;
            // 调整容器Size
            this.size--;
        }

        public Node removeLast(){
            // 删除尾节点, 为tail.prev
            Node node = tail.prev;
            // ▲笔误写错, 查了半小时
            node.nxt= tail;
            remove(node);
            // 删除的时候还要在mp中删除索引, 因此要返回值
            return node;
        }

        public int getSize() {
            return this.size;
        }

        @Override
        public String toString() {
            return "DoubleList{" +
                    "size=" + size +
                    '}';
        }
    }


    int capacity;
    Map<Integer, Node> mp;
    DoubleList list;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        list = new DoubleList();
        mp = new HashMap<Integer, Node>();
    }

    /**
     * 访问过的key对应的Node需要放到队首部(最近查询)
     * @param key 键
     * @return 有相应的key则返回对应Node的val, 无则返回-1
     */
    public int get(int key) {
        if ( mp.containsKey( key) ){
            int res = mp.get(key).val;
            // ★ 把当前访问的放到队首
            put(key, res);
            return res;
        }
        else return -1;
    }

    /**
     * 1. 如果已有key, 则删除容器中原有的Node, 将其放到队首
     * 2. 如果没有key,
     *      2.1 如果容器已满, 则将队尾的排出, 再将新Node加在队首
     *      2.2 如果容器未满, 则直接将新Node加在队首
     * @param key
     * @param value
     */
    public void put(int key, int value) {
        Node node = new Node(key, value);
        if (mp.containsKey(key)){
            list.remove(mp.get(key));
            list.addFirst(node);
            mp.put(key, node);
        }else{
            if ( list.getSize() == capacity ){
                Node last = list.removeLast();
                mp.remove(last.key);
            }
            list.addFirst(node);
            mp.put(key, node);
        }
    }

    @Override
    public String toString() {
        return "LRUCache{" +
                "capacity=" + capacity +
                ", mp=" + mp.toString() +
                ", list=" + list.toString() +
                '}';
    }
}

LeetCode代码检验 : 146. LRU缓存机制

算法实现参考： LRU算法：手把手带你实现一个干啥都快的快乐算法， 思路挺清晰的， 只不过只有LRUCache的代码， 需要自己实现双向链表

LFU

LFU (Least frequently used) 最不经常使用，如果一个数据在最近一段时间内使用次数很少，那么在将来一段时间内被使用的可能性也很小。

• LFU由于涉及频率, 因此在代码实现上有个计数器来统计出现次数T，在需要换页（缓存更新的时候）将替换掉最低T的ke

算法实现思路：

• O(1)查询： hash+
• O(1)修改+频率排序：set

附录

参考链接:

• 【1】简单易懂，包你学会！ | 操作系统 | 页面置换 —— 认知性了解
• 操作系统-页面置换算法（OPT、FIFO、LRU、——换页过程