早期計算機僅限于固定用途的程序，程序是固定在電路板上的，修改程序的話，需要重新設計電路，馮諾依曼體系確立了通用的計算機結構。
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();
}
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();
}
}
