亚洲视频二区_亚洲欧洲日本天天堂在线观看_日韩一区二区在线观看_中文字幕不卡一区

早期計(jì)算機(jī)僅限于固定用途的程序，程序是固定在電路板上的，修改程序的話，需要重新設(shè)計(jì)電路，馮諾依曼體系確立了通用的計(jì)算機(jī)結(jié)構(gòu)。

1.2 馮諾依曼體系概述

• 輸入設(shè)備：用于完成數(shù)據(jù)的接收，將數(shù)據(jù)送入到運(yùn)算器中
• 控制器：控制器是整個(gè)計(jì)算機(jī)的指揮控制中心，通過(guò)向其他設(shè)備發(fā)出控制信號(hào)來(lái)控制、控制計(jì)算機(jī)，使其能自動(dòng)、協(xié)調(diào)地工作。
• 運(yùn)算器：在控制器的統(tǒng)一控制下，負(fù)責(zé)對(duì)數(shù)據(jù)進(jìn)行加工、完成各種運(yùn)算，如算術(shù)運(yùn)算、邏輯運(yùn)算、位移、比較等。其數(shù)據(jù)取自存儲(chǔ)器，運(yùn)算結(jié)果又內(nèi)送往存儲(chǔ)器。
• 存儲(chǔ)器：計(jì)算機(jī)系統(tǒng)中用于保存信息的記憶設(shè)備，存放計(jì)容算機(jī)中所有數(shù)據(jù)的場(chǎng)所
• 輸出設(shè)備：將運(yùn)算結(jié)果輸出、展示給用戶
• 控制器和運(yùn)算器共同構(gòu)成了中央處理器（cpu）

根據(jù)馮諾依曼體系構(gòu)成的計(jì)算機(jī)，必須具有如下功能：

• 能夠把需要的程序和數(shù)據(jù)送至計(jì)算機(jī)中
• 能夠長(zhǎng)期記憶程序、數(shù)據(jù)、中間結(jié)果及最終運(yùn)算結(jié)果的能力
• 能夠具備算術(shù)、邏輯運(yùn)算和數(shù)據(jù)傳送等數(shù)據(jù)加工處理的能力
• 能夠按照要求將處理結(jié)果輸出給用戶

2. 現(xiàn)代計(jì)算機(jī)體系

由于cpu的運(yùn)算速率遠(yuǎn)遠(yuǎn)高于存儲(chǔ)器，因此cpu經(jīng)?？辙D(zhuǎn)等待數(shù)據(jù)的傳輸，造成資源的浪費(fèi)，這種現(xiàn)象被叫做馮諾依曼瓶頸。

現(xiàn)代計(jì)算機(jī)在馮諾依曼體系結(jié)構(gòu)的基礎(chǔ)上進(jìn)行了修改，主要是為了解決cpu與存儲(chǔ)設(shè)備之間的性能差異問(wèn)題。

現(xiàn)代計(jì)算機(jī)體系中的cpu由 高速存儲(chǔ)器 + 運(yùn)算器 + 控制器構(gòu)成。

存儲(chǔ)器被拆分成兩部分：高速存儲(chǔ)器和低速存儲(chǔ)器。高速存儲(chǔ)器包括內(nèi)存、寄存器等，用于處理運(yùn)算過(guò)程中的數(shù)據(jù)存儲(chǔ)。低速存儲(chǔ)器包括磁盤、磁帶等，用于存儲(chǔ)需要長(zhǎng)期保存的設(shè)備，現(xiàn)代計(jì)算機(jī)結(jié)構(gòu)可以理解為以存儲(chǔ)器為核心的結(jié)構(gòu)。

3. 計(jì)算機(jī)存儲(chǔ)器

3.1 存儲(chǔ)器的分類

按照存儲(chǔ)介質(zhì)來(lái)劃分，存儲(chǔ)器可分為：

• 半導(dǎo)體存儲(chǔ)器 (半導(dǎo)體元器件組成的存儲(chǔ)設(shè)備)
• 磁存儲(chǔ)器（磁性材料構(gòu)成的存儲(chǔ)設(shè)備）

按照存取方式來(lái)劃分，存儲(chǔ)器可分為：

• 隨機(jī)存儲(chǔ)器（隨機(jī)讀取、與位置無(wú)關(guān)）
• 串行存儲(chǔ)器（與位置有關(guān)，按順序查找）
• 只讀存儲(chǔ)器（只讀不寫）

3.2 存儲(chǔ)器的層次結(jié)構(gòu)

選擇存儲(chǔ)器時(shí)，一般從讀寫速度、存儲(chǔ)容量、價(jià)格三個(gè)維度來(lái)考量。相同的價(jià)格下，讀寫速度越快越好，存儲(chǔ)容量越大越好。

計(jì)算機(jī)中的存儲(chǔ)設(shè)備根據(jù)成本考慮劃分為三個(gè)層次：

1 緩存

cpu中的寄存器以及高速的緩存，速度最快，成本最高。

2.主存

計(jì)算機(jī)中的內(nèi)存條，速度適中，成本適中。

3.輔存

U盤、硬盤等設(shè)備，速度最慢，成本最低。

存儲(chǔ)器的層次結(jié)構(gòu)如下圖所示：

cpu可以直接往高速緩存、主存中讀寫信息，高速緩存和主存之間可以相互讀寫信息（緩存信息的置換），主存可以往輔存讀寫信息。

3.3 高速緩存的置換算法

為了解決主存速度不足的問(wèn)題，在cpu和主存之間增加了一層速度快、容量小的緩存。程序經(jīng)常訪問(wèn)的內(nèi)存，一般存在于一個(gè)較小的連續(xù)區(qū)域中，因此只需要把這段內(nèi)存中的數(shù)據(jù)放置到高速緩存中，即可大大提升cpu運(yùn)轉(zhuǎn)效率。

衡量高速緩存效率的常用指標(biāo)有緩存命中率和訪問(wèn)效率。

緩存命中率，側(cè)重于訪問(wèn)緩存次數(shù)與總訪問(wèn)次數(shù)的比例，計(jì)算公式如下：

緩存命中率 = 緩存取數(shù)據(jù)次數(shù) / (緩存取數(shù)據(jù)次數(shù) + 內(nèi)存取數(shù)據(jù)次數(shù))

訪問(wèn)效率，側(cè)重于訪問(wèn)緩存耗時(shí)與平均訪問(wèn)時(shí)間的比例，計(jì)算公式如下：

平均訪問(wèn)時(shí)間 = 緩存命中率 × 訪問(wèn)緩存耗時(shí) + (1 - 緩存命中率) × 訪問(wèn)內(nèi)存耗時(shí) 訪問(wèn)效率 = 訪問(wèn)緩存耗時(shí) / 平均訪問(wèn)時(shí)間

良好的緩存置換算法能夠大大提升緩存的訪問(wèn)效率，常用的緩存置換算法有：

• 先進(jìn)先出算法（FIFO）
• 最不經(jīng)常使用算法（LFU）
• 最近最少使用算法（LRU）

3.3.1 FIFO 先進(jìn)先出算法

• 原理： FIFO算法，將緩存看做一個(gè)先進(jìn)先出的隊(duì)列，優(yōu)先替換掉最先進(jìn)入隊(duì)列的字塊
• 示意圖：

3.3.2 LFU最不經(jīng)常使用算法

• 原理 LFU算法，額外記錄了字塊的使用頻率，優(yōu)先替換掉最不經(jīng)常使用的字塊
• 示意圖

3.3.3 LRU 最近最少使用算法

• 原理 優(yōu)先替換最長(zhǎng)時(shí)間未被使用的字塊，有多種實(shí)現(xiàn)方法，一般使用雙向鏈表，把當(dāng)前訪問(wèn)節(jié)點(diǎn)放到鏈表頭部，當(dāng)鏈表空間滿了之后，最先刪除鏈表尾部的元素。
• 示意圖

3.3.4 緩存算法的通用性

以上算法不僅適用于cpu高速緩存的實(shí)現(xiàn)，當(dāng)我們存在高速設(shè)備與低速設(shè)備需要進(jìn)行數(shù)據(jù)交互的時(shí)候，也可以借鑒這部分的實(shí)現(xiàn)，比較常用的一種場(chǎng)景是，程序讀取硬盤中的數(shù)據(jù)，例如數(shù)據(jù)庫(kù)、文件等，可以將部分?jǐn)?shù)據(jù)，緩存到內(nèi)存中，提升訪問(wèn)效率。

4. 置換算法JAVA模擬實(shí)現(xiàn)

4.1 通用代碼

定義通用緩存接口，具有存值、取值兩個(gè)功能

public interface Cache<E> {
    /**
     * 從緩存中獲取元素
     * @param key 緩存鍵
     * @return 緩存數(shù)據(jù)
     */
    E get(String key);

    /**
     * 往緩存中插入數(shù)據(jù)
     * @param key 緩存鍵
     * @param value 緩存值
     */
    void put(String key,E value);
}

置換算法底層依靠雙向鏈表來(lái)實(shí)現(xiàn)，采用雙向鏈表的原因是，雙向鏈表能夠很簡(jiǎn)單的實(shí)現(xiàn)：獲取頭部節(jié)點(diǎn)、獲取尾部節(jié)點(diǎn)、增刪頭部節(jié)點(diǎn)、增刪尾部節(jié)點(diǎn)、中間插入節(jié)點(diǎn)、中間刪除節(jié)點(diǎn)等功能。

依托于雙向鏈表，能夠很方便的實(shí)現(xiàn)隊(duì)列、棧等線形數(shù)據(jù)結(jié)構(gòu)。

關(guān)于鏈表的基礎(chǔ)知識(shí)，可以查看另一篇文章： 數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)-鏈表（java實(shí)現(xiàn)）

雙向鏈表代碼實(shí)現(xiàn)如下：

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

        /**
         * 指向前一個(gè)節(jié)點(diǎn)
         */
        private Node<E> prev;
        /**
         * 指向后一個(gè)節(jié)點(diǎn)
         */
        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;
    /**
     * 當(dāng)前元素個(gè)數(shù)
     */
    private int size;

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

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

    /**
     * 添加頭部節(jié)點(diǎn)
     *
     * @return 添加后的節(jié)點(diǎn)信息
     */
    public Node<E> addHead(Node<E> node) {
        if (size == capacity) {
            throw new IllegalArgumentException("鏈表空間已滿");
        }
        if (head == null) {
            // 處理當(dāng)前不存在節(jié)點(diǎn)的情況，將當(dāng)前節(jié)點(diǎn)設(shè)置為頭節(jié)點(diǎn)、尾節(jié)點(diǎn)
            head = node;
            tail = node;
        } else {
            head.prev = node;
            node.next = head;
            head = node;
        }
        size++;
        return node;
    }

    /**
     * 添加尾部節(jié)點(diǎn)
     *
     * @return 添加后的節(jié)點(diǎn)信息
     */
    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;
    }

    /**
     * 刪除頭部節(jié)點(diǎn)
     *
     * @return 被刪除的頭部節(jié)點(diǎn)數(shù)據(jù)
     */
    public Node<E> delHead() {
        if (size == 0) {
            throw new IllegalArgumentException("當(dāng)前鏈表為空");
        }
        Node<E> resultNode = head;
        if (head.next == null) {
            tail = null;
            head = null;
        } else {
            head.next.prev = null;
            head = head.next;
        }
        size--;
        return resultNode;
    }

    /**
     * 刪除尾部節(jié)點(diǎn)
     *
     * @return 被刪除的尾部節(jié)點(diǎn)數(shù)據(jù)
     */
    public Node<E> delTail() {
        if (size == 0) {
            throw new IllegalArgumentException("當(dāng)前鏈表為空");
        }
        Node<E> resultNode = tail;
        if (tail.prev == null) {
            tail = null;
            head = null;
        } else {
            tail.prev.next = null;
            tail = tail.prev;
        }
        size--;
        return resultNode;
    }

    /**
     * 刪除任意節(jié)點(diǎn)
     *
     * @return 刪除的節(jié)點(diǎn)數(shù)據(jù)
     */
    public Node<E> delNode(Node<E> node) {
        if (size == 0) {
            throw new IllegalArgumentException("當(dāng)前鏈表為空");
        }
        if (node == null) {
            // 默認(rèn)刪除尾部節(jié)點(diǎn)
            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 先進(jìn)先出算法實(shí)現(xiàn)

實(shí)現(xiàn)思想：

• hashMap維護(hù)鍵、緩存節(jié)點(diǎn)之間的關(guān)系
• 雙向鏈表維護(hù)緩存隊(duì)列，當(dāng)容量耗盡時(shí)，優(yōu)先從隊(duì)列頭部刪除元素

public class FIFOCache<E> implements Cache<E> {
    /**
     * 存放緩存結(jié)果
     */
    public Map<String, DoubleLinkedList.Node<E>> map;
    /**
     * 緩存隊(duì)列，用于置換
     */
    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)) {
            // 已經(jīng)存在數(shù)據(jù)，先移除掉隊(duì)列中數(shù)據(jù)，然后再將數(shù)據(jù)添加到隊(duì)尾
            list.delNode(map.get(key));
            map.put(key, node);
            list.addTail(node);
        } else {
            if (list.getSize() >= list.getCapacity()) {
                // 如果隊(duì)列已滿，刪除隊(duì)首元素
                DoubleLinkedList.Node<E> delNode = list.delHead();
                map.remove(delNode.getKey());
            }
            // 隊(duì)列尾部添加元素
            list.addTail(node);
            map.put(key, node);
        }
    }

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

4.3 LRU 最近最少使用算法實(shí)現(xiàn)

實(shí)現(xiàn)思想：

• hashMap維護(hù)鍵、緩存節(jié)點(diǎn)之間的關(guān)系
• 雙向鏈表維護(hù)緩存隊(duì)列
• 當(dāng)使用鍵命中緩存時(shí)，將隊(duì)列中的節(jié)點(diǎn)移除掉，往隊(duì)列頭部重新添加節(jié)點(diǎn)
• 當(dāng)容量耗盡時(shí)，優(yōu)先從隊(duì)尾刪除元素

public class LRUCache<E> implements Cache<E> {
    /**
     * 存放緩存結(jié)果
     */
    public Map<String, DoubleLinkedList.Node<E>> map;
    /**
     * 緩存隊(duì)列，用于置換
     */
    private final DoubleLinkedList<E> list;

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

    /**
     * 訪問(wèn)緩存
     */
    @Override
    public E get(String key) {
        if (map.get(key) == null) {
            return null;
        }
        // 被訪問(wèn)后，放到鏈表頭
        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)) {
            // 如果緩存中已經(jīng)存在，刪除原來(lái)的值
            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 最近最少使用算法實(shí)現(xiàn)

實(shí)現(xiàn)思想：

• hashMap維護(hù)鍵、緩存節(jié)點(diǎn)之間的關(guān)系
• hashMap維護(hù)訪問(wèn)頻率、該頻率對(duì)應(yīng)的節(jié)點(diǎn)隊(duì)列之間的關(guān)系
• 當(dāng)使用鍵命中緩存時(shí)，將緩存訪問(wèn)頻率加1，從之前的節(jié)點(diǎn)隊(duì)列中移除，再新的訪問(wèn)頻率對(duì)應(yīng)的隊(duì)列中尾部插入新節(jié)點(diǎn)。
• 當(dāng)容量耗盡時(shí)，優(yōu)先從最低訪問(wèn)頻率的隊(duì)首刪除元素

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)) {
            // 修改節(jié)點(diǎn)，更新值，并更新命中頻率
            LFUNode<E> node = (LFUNode<E>) map.get(key);
            node.setValue(value);
            updateFreq(node);
        } else {
            // 新增節(jié)點(diǎn)
            if (size >= capacity) {
                // 節(jié)點(diǎn)滿了，從最小頻率隊(duì)列里移除頭節(jié)點(diǎn)
                DoubleLinkedList<E> minFreqDoubleLinkedList = freqMap.get(getMinFreq());
                DoubleLinkedList.Node<E> delNode = minFreqDoubleLinkedList.delHead();
                if(minFreqDoubleLinkedList.getSize() == 0){
                    freqMap.remove(getMinFreq());
                }
                map.remove(delNode.getKey());
                size--;
            }
            // 添加節(jié)點(diǎn)
            LFUNode<E> newNode = new LFUNode<>(key,value);
            newNode.freq = 1;
            map.put(key,newNode);
            // 將節(jié)點(diǎn)添加到訪問(wèn)頻率為1的隊(duì)列中
            if(!freqMap.containsKey(1)){
                freqMap.put(1,new DoubleLinkedList<>());
            }
            size++;
            freqMap.get(1).addTail(newNode);
        }
    }

    /**
     * 獲取最小訪問(wèn)頻率
     */
    private Integer getMinFreq(){
        int min = Integer.MAX_VALUE;
        for (Integer freq : freqMap.keySet()) {
            min = Math.min(freq,min);
        }
        return min;
    }

    /**
     * 更新節(jié)點(diǎn)頻率、頻率散列表
     *
     * @param node 節(jié)點(diǎn)
     */
    private void updateFreq(LFUNode<E> node) {
        // 從當(dāng)前頻率鏈表中刪除節(jié)點(diǎn)
        int freq = node.freq;
        DoubleLinkedList<E> freqDoubleLinkedList = freqMap.get(freq);
        freqDoubleLinkedList.delNode(node);
        if(freqDoubleLinkedList.getSize() == 0){
            // 如果頻率對(duì)隊(duì)列為空，移除頻率
            freqMap.remove(freq);
        }

        // 更新節(jié)點(diǎn)訪問(wèn)頻率，并添加到頻率對(duì)應(yīng)的鏈表中
        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);
    }

    /**
     * 帶使用頻率的節(jié)點(diǎn)信息
     *
     * @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();
    }
}