CPU体系结构——cache总结
CPU Cache
何为cache ：cache是内存数据的高速缓存，使用昂贵但是较快速的SRAM技术。如果cpu要访问的数据在cache中，称为“命中”，否则称为“缺失”。cache分为L1 cache、L2 cache、L3 cache，读写延迟依次增加，实现成本依次降低，这样设计是根据性能和价格的折中考虑。程序的数据和指令分别存储在两片cache中，对应数据缓存（D-cache）和指令缓存（L-cache）。
程序局部性原理 ：最近被CPU访问的数据短期内还要访问（时间局部性），被访问数据附近的数据短期内也会被CPU访问（空间局部性）。cache位于CPU和内存之间，存储内存中一小部分CPU即将访问的数据，CPU直接从cache中调用，加快读取速度。cache对CPU的性能影响取决于CPU数据交换顺序，以及CPU和cache之间的带宽。
** CPU、cache、内存和DMA（Direct Memory Access，直接存储器访问）之间的关系
多级CPU cache**：L1 cache 和 L2 cache是每个CPU core独立拥有的，L3 cache是多个cores共享的，可以认为是一个更小但是更快的内存。以下是典型的存储器层次结构，用到了三级缓存。
CPU与cache的交互过程 ：CPU收到指令后，会先去L1cache寻找相关数据，一级缓存和CPU同频运行，如果没有命中，则继续向下一级寻找，按L1、L2、L3、内存（主存）、硬盘依次寻找。程序运行过程中，可以使用perf 工具观察cache-miss的rate。
linux里用dmidecode查看cache size：
cache line ：cache的最小缓存单位。内存与cache、cache与cache之间的数据移动是以最小单位进行的（而不是单个字节），一般主流CPU的cache line大小为64Bytes。linux查看cpu cache line：
cache写机制 ：直写模式（write-through）数据更新时，同时写入cache和后端存储，操作简单但写入速度慢；回写模式（write-back）数据更新时只写缓存cache，被修改的缓存数据才写入后端存储，速度快但是掉电后数据不能恢复。、
cache一致性 ：多个处理器对内存块同时读写会引起冲突，称为一致性问题。当多个处理器核心独立执行计算机指令时，导致对于同一个内存块，多个cache有各自的备份。为了确保数据更新的正确性，采用的硬件策略协议是MESI或其变种。
M代表更改（modified），表示缓存中的数据已经更改，在未来的某个时刻将会写入内存；
E代表排除（exclusive），表示缓存的数据只被当前的核心所缓存；
S代表共享（shared），表示缓存的数据还被其他核心缓存；
I代表无效（invalid），表示缓存中的数据已经失效，即其他核心更改了数据。
cache替换策略 ：为了让cache保存最新的数据，主存向cache传送新块，如果cache可用位置被占满，需要采用一定的替换策略进行替换。常用的替换策略有：LFU、LRU、随机替换。
LFU（Least Frequently Used，最不经常使用），将访问次数最少的块替换出去，每块有个计数器，每次访问块计数器+1，替换时把计数器最小值的块换出去，同时把计数器清零。
LRU（Least Recently Used，最近最少使用），把CPU近期最少使用的块替换出去，随时记录cache各块使用情况，每块有个计数器，cache每次命中，命中块计数器清零，其他块+1，替换时把计数器最大值的块替换出去。该方法更加合理，但是系统开销大，实现复杂，保护了刚调入cache的新块，具有较高命中率。
随即替换，实现简单，速度快，但是降低了命中率和cache工作效率。
cache映射 ：直接映射、全相联映射和组相联映射三种
直接映射：将一个主存块存储到唯一的一个Cache行（多对一， 特定行 i = j mod m）。实现简单，但命中率低。
全相联映射：将一个主存块存储到任意一个Cache行。命中率高，空间利用率高，但线路复杂，成本高，速度低。
组相联映射：将一个主存块存储到唯一的一个Cache组中任意一个行。硬件较简单，速度较快，命中率较高。
cache miss ：cold misses（不可避免）、conflict misses、capacity misses（working set超过cache大小）。减少miss的次数有很多种办法（http://blog.chinaunix.net/uid-7319742-id-2059720.html），简化调用关系，减少冗余代码可以减少缺失次数。
关于cache的面试必考题
如何实现一个LRU cache？双向链表+哈希表
双向链表存储数据结点，记录数据进入cache的顺序，由于cache对插入删除的复杂度要求为O(1)，故不使用单向链表。哈希表记录元素的位置，以O(1)复杂度高效地拿到链表元素。
cache接口如下：
T Get(K key)
void Put(K key, T data)查询key是否在cache中，如果在，就返回数据，并把该数据结点移动到双向链表头部。如果不在，就用Put接口把数据插入双向链表。如果cache未满，就把新结点插入链表头部，同时用哈希表保存结点的键值和地址对；如果cache满了，就将链表最后一个结点的内容替换为新内容，然后移动到头部，更新哈希表。
// A simple LRU cache written in C++
// Hash map + doubly linked list
#include <iostream>
#include <vector>
#include <ext/hash_map>
using namespace std;
using namespace __gnu_cxx;
template <class K, class T>
struct Node{
K key;
T data;
Node *prev, *next;
};
template <class K, class T>
class LRUCache{
public:
LRUCache(size_t size){
entries_ = new Node<K,T>[size];
for(int i=0; i<size; ++i)// 存储可用结点的地址
free_entries_.push_back(entries_+i);
head_ = new Node<K,T>;
tail_ = new Node<K,T>;
head_->prev = NULL;
head_->next = tail_;
tail_->prev = head_;
tail_->next = NULL;
}
~LRUCache(){
delete head_;
delete tail_;
delete[] entries_;
}
void Put(K key, T data){
Node<K,T> *node = hashmap_[key];
if(node){ // node exists
detach(node);
node->data = data;
attach(node);
}
else{
if(free_entries_.empty()){// 可用结点为空，即cache已满
node = tail_->prev;
detach(node);
hashmap_.erase(node->key);
}
else{
node = free_entries_.back();
free_entries_.pop_back();
}
node->key = key;
node->data = data;
hashmap_[key] = node;
attach(node);
}
}
T Get(K key){
Node<K,T> *node = hashmap_[key];
if(node){
detach(node);
attach(node);
return node->data;
}
else{// 如果cache中没有，返回T的默认值。与hashmap行为一致
return T();
}
}
private:
// 分离结点
void detach(Node<K,T>* node){
node->prev->next = node->next;
node->next->prev = node->prev;
}
// 将结点插入头部
void attach(Node<K,T>* node){
node->prev = head_;
node->next = head_->next;
head_->next = node;
node->next->prev = node;
}
private:
hash_map<K, Node<K,T>* > hashmap_;
vector<Node<K,T>* > free_entries_; // 存储可用结点的地址
Node<K,T> *head_, *tail_;
Node<K,T> *entries_; // 双向链表中的结点
};
int main(){
hash_map<int, int> map;
map[9]= 999;
cout<<map[9]<<endl;
cout<<map[10]<<endl;
LRUCache<int, string> lru_cache(100);
lru_cache.Put(1, "one");
cout<<lru_cache.Get(1)<<endl;
if(lru_cache.Get(2) == "")
lru_cache.Put(2, "two");
cout<<lru_cache.Get(2);
return 0;
}首先使用链表来管理所有的已经使用或正在使用的节点（也就是物理内存页），刚开始分配了一些节点，存放在向量中，在缓冲没有使用完之前都是在向量中存放着，当向量中的缓冲使用完了，那么就必须从链表中的最后一个取出来当做新的节点来使用。在查找节点在链表中的位置时，如果每次都是从头来查找的话，效率会很低，所以使用了hash_map来管理链表中的所有节点，hash_map中都是使用过的节点，在查找时很方便。