cpu中的高速缓存与置换算法

1. 冯诺依曼体系

1.1 诞生背景

早期计算机仅限于固定用途的程序，程序是固定在电路板上的，修改程序的话，需要重新设计电路，冯诺依曼体系确立了通用的计算机结构。

1.2 冯诺依曼体系概述

冯诺依曼体系
  • 输入设备：用于完成数据的接收，将数据送入到运算器中
  • 控制器：控制器是整个计算机的指挥控制中心，通过向其他设备发出控制信号来控制、控制计算机，使其能自动、协调地工作。
  • 运算器：在控制器的统一控制下，负责对数据进行加工、完成各种运算，如算术运算、逻辑运算、位移、比较等。其数据取自存储器，运算结果又内送往存储器。
  • 存储器：计算机系统中用于保存信息的记忆设备，存放计容算机中所有数据的场所
  • 输出设备：将运算结果输出、展示给用户
  • 控制器和运算器共同构成了中央处理器（cpu）

根据冯诺依曼体系构成的计算机，必须具有如下功能：

  • 能够把需要的程序和数据送至计算机中
  • 能够长期记忆程序、数据、中间结果及最终运算结果的能力
  • 能够具备算术、逻辑运算和数据传送等数据加工处理的能力
  • 能够按照要求将处理结果输出给用户

2. 现代计算机体系

由于cpu的运算速率远远高于存储器，因此cpu经常空转等待数据的传输，造成资源的浪费，这种现象被叫做冯诺依曼瓶颈。
现代计算机在冯诺依曼体系结构的基础上进行了修改，主要是为了解决cpu与存储设备之间的性能差异问题。

现代计算机体系

现代计算机体系中的cpu由 高速存储器 + 运算器 + 控制器构成。
存储器被拆分成两部分：高速存储器和低速存储器。高速存储器包括内存、寄存器等，用于处理运算过程中的数据存储。低速存储器包括磁盘、磁带等，用于存储需要长期保存的设备，现代计算机结构可以理解为以存储器为核心的结构。

3. 计算机存储器

3.1 存储器的分类

按照存储介质来划分，存储器可分为：

  • 半导体存储器 (半导体元器件组成的存储设备)
  • 磁存储器（磁性材料构成的存储设备）

按照存取方式来划分，存储器可分为：

  • 随机存储器（随机读取、与位置无关）
  • 串行存储器（与位置有关，按顺序查找）
  • 只读存储器（只读不写）

3.2 存储器的层次结构

选择存储器时，一般从读写速度、存储容量、价格三个维度来考量。相同的价格下，读写速度越快越好，存储容量越大越好。
计算机中的存储设备根据成本考虑划分为三个层次：
1 缓存
cpu中的寄存器以及高速的缓存，速度最快，成本最高。
2.主存
计算机中的内存条，速度适中，成本适中。
3.辅存
U盘、硬盘等设备，速度最慢，成本最低。

存储器的层次结构如下图所示：


存储器的层次结构

cpu可以直接往高速缓存、主存中读写信息，高速缓存和主存之间可以相互读写信息（缓存信息的置换），主存可以往辅存读写信息。

3.3 高速缓存的置换算法

为了解决主存速度不足的问题，在cpu和主存之间增加了一层速度快、容量小的缓存。程序经常访问的内存，一般存在于一个较小的连续区域中，因此只需要把这段内存中的数据放置到高速缓存中，即可大大提升cpu运转效率。

衡量高速缓存效率的常用指标有缓存命中率和访问效率。

缓存命中率，侧重于访问缓存次数与总访问次数的比例，计算公式如下：

缓存命中率 = 缓存取数据次数 / (缓存取数据次数 + 内存取数据次数)

访问效率，侧重于访问缓存耗时与平均访问时间的比例，计算公式如下：

平均访问时间 = 缓存命中率 × 访问缓存耗时 + (1 - 缓存命中率) × 访问内存耗时
访问效率 = 访问缓存耗时 / 平均访问时间

良好的缓存置换算法能够大大提升缓存的访问效率，常用的缓存置换算法有：

  • 先进先出算法（FIFO）
  • 最不经常使用算法（LFU）
  • 最近最少使用算法（LRU）

3.3.1 FIFO 先进先出算法

  • 原理：
    FIFO算法，将缓存看做一个先进先出的队列，优先替换掉最先进入队列的字块

  • 示意图：


    FIFO算法

3.3.2 LFU最不经常使用算法

  • 原理
    LFU算法，额外记录了字块的使用频率，优先替换掉最不经常使用的字块

  • 示意图


    LFU算法

3.3.3 LRU 最近最少使用算法

  • 原理
    优先替换最长时间未被使用的字块，有多种实现方法，一般使用双向链表，把当前访问节点放到链表头部，当链表空间满了之后，最先删除链表尾部的元素。

  • 示意图


    LRU算法

3.3.4 缓存算法的普适性

以上算法不仅适用于cpu高速缓存的实现，当我们存在高速设备与低速设备需要进行数据交互的时候，也可以借鉴这部分的实现。
比较常用的一种场景是，程序读取硬盘中的数据，例如数据库、文件等，可以将部分数据，缓存到内存中，提升访问效率。

4. 置换算法java模拟实现

4.1 通用代码

定义通用缓存接口，具有存值、取值两个功能

public interface Cache<E> {
    /**
     * 从缓存中获取元素
     * @param key 缓存键
     * @return 缓存数据
     */
    E get(String key);

    /**
     * 往缓存中插入数据
     * @param key 缓存键
     * @param value 缓存值
     */
    void put(String key,E value);
}

置换算法底层依靠双向链表来实现，采用双向链表的原因是，双向链表能够很简单的实现：获取头部节点、获取尾部节点、增删头部节点、增删尾部节点、中间插入节点、中间删除节点等功能。
依托于双向链表，能够很方便的实现队列、栈等线形数据结构。
关于链表的基础知识，可以查看另一篇文章：数据结构基础-链表（java实现）
双向链表代码实现如下：

public class DoubleLinkedList<E> {
    static class Node<E> {
        /**
         * 键
         */
        private String key;
        /**
         * 值
         */
        private E value;

        public Node(String key, E value) {
            this.key = key;
            this.value = value;
        }

        /**
         * 指向前一个节点
         */
        private Node<E> prev;
        /**
         * 指向后一个节点
         */
        private Node<E> next;

        public String getKey() {
            return key;
        }

        public E getValue() {
            return value;
        }

        public void setValue(E value) {
            this.value = value;
        }

        @Override
        public String toString() {
            return String.format("{%s:%s}", key, value.toString());
        }
    }

    /**
     * 链表容量
     */
    private final int capacity;
    /**
     * 链表头部
     */
    private Node<E> head;
    /**
     * 链表尾部
     */
    private Node<E> tail;
    /**
     * 当前元素个数
     */
    private int size;

    public DoubleLinkedList() {
        this(Integer.MAX_VALUE);
    }

    public DoubleLinkedList(int capacity) {
        this.capacity = capacity;
    }

    /**
     * 添加头部节点
     *
     * @return 添加后的节点信息
     */
    public Node<E> addHead(Node<E> node) {
        if (size == capacity) {
            throw new IllegalArgumentException("链表空间已满");
        }
        if (head == null) {
            // 处理当前不存在节点的情况，将当前节点设置为头节点、尾节点
            head = node;
            tail = node;
        } else {
            head.prev = node;
            node.next = head;
            head = node;
        }
        size++;
        return node;
    }

    /**
     * 添加尾部节点
     *
     * @return 添加后的节点信息
     */
    public Node<E> addTail(Node<E> node) {
        if (size == capacity) {
            throw new IllegalArgumentException("链表空间已满");
        }
        if (tail == null) {
            tail = node;
            head = node;
        } else {
            tail.next = node;
            node.prev = tail;
            tail = node;
        }
        size++;
        return node;
    }

    /**
     * 删除头部节点
     *
     * @return 被删除的头部节点数据
     */
    public Node<E> delHead() {
        if (size == 0) {
            throw new IllegalArgumentException("当前链表为空");
        }
        Node<E> resultNode = head;
        if (head.next == null) {
            tail = null;
            head = null;
        } else {
            head.next.prev = null;
            head = head.next;
        }
        size--;
        return resultNode;
    }

    /**
     * 删除尾部节点
     *
     * @return 被删除的尾部节点数据
     */
    public Node<E> delTail() {
        if (size == 0) {
            throw new IllegalArgumentException("当前链表为空");
        }
        Node<E> resultNode = tail;
        if (tail.prev == null) {
            tail = null;
            head = null;
        } else {
            tail.prev.next = null;
            tail = tail.prev;
        }
        size--;
        return resultNode;
    }

    /**
     * 删除任意节点
     *
     * @return 删除的节点数据
     */
    public Node<E> delNode(Node<E> node) {
        if (size == 0) {
            throw new IllegalArgumentException("当前链表为空");
        }
        if (node == null) {
            // 默认删除尾部节点
            node = tail;
        }
        if (node.equals(tail)) {
            return delTail();
        } else if (node.equals(head)) {
            return delHead();
        } else {
            node.prev.next = node.next;
            node.next.prev = node.prev;
            size--;
            return node;
        }
    }

    public int getCapacity() {
        return capacity;
    }

    public int getSize() {
        return size;
    }

    @Override
    public String toString() {
        StringBuilder stringBuilder = new StringBuilder("DoubleLinkedList: ");
        Node<E> node = head;
        while (node != null) {
            stringBuilder.append(node.toString());
            if (node != tail) {
                stringBuilder.append("-->");
            }
            node = node.next;
        }
        return stringBuilder.toString();
    }

4.2 FIFO 先进先出算法实现

实现思想：

  • hashMap维护键、缓存节点之间的关系
  • 双向链表维护缓存队列，当容量耗尽时，优先从队列头部删除元素
public class FIFOCache<E> implements Cache<E> {
    /**
     * 存放缓存结果
     */
    public Map<String, DoubleLinkedList.Node<E>> map;
    /**
     * 缓存队列，用于置换
     */
    private final DoubleLinkedList<E> list;

    public FIFOCache(int capacity) {
        this.map = new HashMap<>();
        this.list = new DoubleLinkedList<>(capacity);
    }

    @Override
    public E get(String key) {
        if (map.get(key) == null) {
            return null;
        }
        return map.get(key).getValue();
    }

    @Override
    public void put(String key, E value) {
        if (list.getCapacity() == 0) {
            throw new IllegalArgumentException("缓存容量为空");
        }
        DoubleLinkedList.Node<E> node = new DoubleLinkedList.Node<>(key, value);
        if (map.containsKey(key)) {
            // 已经存在数据，先移除掉队列中数据，然后再将数据添加到队尾
            list.delNode(map.get(key));
            map.put(key, node);
            list.addTail(node);
        } else {
            if (list.getSize() >= list.getCapacity()) {
                // 如果队列已满，删除队首元素
                DoubleLinkedList.Node<E> delNode = list.delHead();
                map.remove(delNode.getKey());
            }
            // 队列尾部添加元素
            list.addTail(node);
            map.put(key, node);
        }
    }

    @Override
    public String toString() {
        return list.toString();
    }
}

4.3 LRU 最近最少使用算法实现

实现思想：

  • hashMap维护键、缓存节点之间的关系
  • 双向链表维护缓存队列
  • 当使用键命中缓存时，将队列中的节点移除掉，往队列头部重新添加节点
  • 当容量耗尽时，优先从队尾删除元素
public class LRUCache<E> implements Cache<E> {
    /**
     * 存放缓存结果
     */
    public Map<String, DoubleLinkedList.Node<E>> map;
    /**
     * 缓存队列，用于置换
     */
    private final DoubleLinkedList<E> list;

    public LRUCache(int capacity) {
        this.map = new HashMap<>();
        this.list = new DoubleLinkedList<>(capacity);
    }

    /**
     * 访问缓存
     */
    @Override
    public E get(String key) {
        if (map.get(key) == null) {
            return null;
        }
        // 被访问后，放到链表头
        DoubleLinkedList.Node<E> node = map.get(key);
        list.delNode(node);
        list.addHead(node);
        return node.getValue();
    }

    @Override
    public void put(String key, E value) {
        if (list.getCapacity() == 0) {
            throw new IllegalArgumentException("缓存容量为0");
        }
        DoubleLinkedList.Node<E> newNode = new DoubleLinkedList.Node<>(key, value);
        if (map.containsKey(key)) {
            // 如果缓存中已经存在，删除原来的值
            DoubleLinkedList.Node<E> eNode = map.get(key);
            list.delNode(eNode);
        } else {
            if (list.getSize() >= list.getCapacity()) {
                // 缓存已满,清空链表尾部元素
                DoubleLinkedList.Node<E> eNode = list.delTail();
                map.remove(eNode.getKey());
            }
        }
        list.addHead(newNode);
        map.put(key, newNode);
    }

    @Override
    public String toString() {
        return list.toString();
    }
}

4.4 LFU 最近最少使用算法实现

实现思想：

  • hashMap维护键、缓存节点之间的关系
  • hashMap维护访问频率、该频率对应的节点队列之间的关系
  • 当使用键命中缓存时，将缓存访问频率加1，从之前的节点队列中移除，再新的访问频率对应的队列中尾部插入新节点。
  • 当容量耗尽时，优先从最低访问频率的队首删除元素
public class LFUCache<E> implements Cache<E> {
    private final int capacity;
    private int size;
    private Map<String, DoubleLinkedList.Node<E>> map;
    private Map<Integer, DoubleLinkedList<E>> freqMap;

    public LFUCache(int capacity) {
        this.capacity = capacity;
        map = new HashMap<>();
        freqMap = new HashMap<>();
    }


    @Override
    public E get(String key) {
        if (map.get(key) == null) {
            return null;
        }
        LFUNode<E> node = (LFUNode<E>) map.get(key);
        updateFreq(node);
        return node.getValue();
    }

    @Override
    public void put(String key, E value) {
        if (capacity == 0) {
            throw new IllegalArgumentException("缓存容量为0");
        }

        if (map.containsKey(key)) {
            // 修改节点，更新值，并更新命中频率
            LFUNode<E> node = (LFUNode<E>) map.get(key);
            node.setValue(value);
            updateFreq(node);
        } else {
            // 新增节点
            if (size >= capacity) {
                // 节点满了，从最小频率队列里移除头节点
                DoubleLinkedList<E> minFreqDoubleLinkedList = freqMap.get(getMinFreq());
                DoubleLinkedList.Node<E> delNode = minFreqDoubleLinkedList.delHead();
                if(minFreqDoubleLinkedList.getSize() == 0){
                    freqMap.remove(getMinFreq());
                }
                map.remove(delNode.getKey());
                size--;
            }
            // 添加节点
            LFUNode<E> newNode = new LFUNode<>(key,value);
            newNode.freq = 1;
            map.put(key,newNode);
            // 将节点添加到访问频率为1的队列中
            if(!freqMap.containsKey(1)){
                freqMap.put(1,new DoubleLinkedList<>());
            }
            size++;
            freqMap.get(1).addTail(newNode);
        }
    }

    /**
     * 获取最小访问频率
     */
    private Integer getMinFreq(){
        int min = Integer.MAX_VALUE;
        for (Integer freq : freqMap.keySet()) {
            min = Math.min(freq,min);
        }
        return min;
    }

    /**
     * 更新节点频率、频率散列表
     *
     * @param node 节点
     */
    private void updateFreq(LFUNode<E> node) {
        // 从当前频率链表中删除节点
        int freq = node.freq;
        DoubleLinkedList<E> freqDoubleLinkedList = freqMap.get(freq);
        freqDoubleLinkedList.delNode(node);
        if(freqDoubleLinkedList.getSize() == 0){
            // 如果频率对队列为空，移除频率
            freqMap.remove(freq);
        }

        // 更新节点访问频率，并添加到频率对应的链表中
        freq++;
        LFUNode<E> newNode = new LFUNode<>(node.getKey(),node.getValue());
        newNode.freq = freq;
        if (!freqMap.containsKey(freq)) {
            freqMap.put(freq, new DoubleLinkedList<>());
        }
        DoubleLinkedList.Node<E> addNode = freqMap.get(freq).addTail(newNode);
        map.put(addNode.getKey(),newNode);
    }

    /**
     * 带使用频率的节点信息
     *
     * @param <E>
     */
    private static class LFUNode<E> extends DoubleLinkedList.Node<E> {
        /**
         * 使用频率
         */
        private int freq;

        public LFUNode(String key, E value) {
            super(key, value);
        }
    }

    @Override
    public String toString() {
        StringBuilder str = new StringBuilder();
        str.append("\nprintStart---------------------------------------------\n");
        for (Integer freqKey : freqMap.keySet()) {
            str.append("freq[").append(freqKey).append("] ---> ");
            DoubleLinkedList<E> freqList = freqMap.get(freqKey);
            str.append(freqList.toString());
            str.append("\n");
        }
        str.append("printEnd------------------------------------------------\n");
        return str.toString();
    }
}
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 206,013评论 6赞 481
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 88,205评论 2赞 382
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 152,370评论 0赞 342
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 55,168评论 1赞 278
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 64,153评论 5赞 371
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 48,954评论 1赞 283
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 38,271评论 3赞 399
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 36,916评论 0赞 259
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 43,382评论 1赞 300
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,877评论 2赞 323
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,989评论 1赞 333
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 33,624评论 4赞 322
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 39,209评论 3赞 307
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,199评论 0赞 19
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,418评论 1赞 260
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 45,401评论 2赞 352
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 42,700评论 2赞 345