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

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算法，将缓存看做一个先进先出的队列，优先替换掉最先进入队列的字块示意图：3.3.2 LFU最不经常使用算法原理 LFU算法，额外记录了字块的使用频率，优先替换掉最不经常使用的字块示意图3.3.3 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();    }

实现思想：

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();    }}

实现思想：

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();    }}

实现思想：

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();    }}