CPU中的高速缓存与置换算法
2020-05-25
加入收藏
早期计算机仅限于固定用途的程序，程序是固定在电路板上的，修改程序的话，需要重新设计电路，冯诺依曼体系确立了通用的计算机结构。
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();
}
}
