以下为个人学习笔记和习题整理
作者地址:https://www.cnblogs.com/jokerjason/p/10711022.html

# 什么是 Cache

Cache 是用来对内存数据的缓存.
CPU 要访问的数据在 Cache 中有缓存，称为 "命中" (Hit), 反之则称为 "缺失" (Miss).
CPU 访问它的速度介于寄存器与内存之间 (数量级的差别). 实现 Cache 的花费介于寄存器与内存之间.
现在 CPU 的 Cache 又被细分了几层，常见的有 L1 Cache, L2 Cache, L3 Cache, 其读写延迟依次增加，实现的成本依次降低.
现代系统采用从 Register ―> L1 Cache ―> L2 Cache ―> L3 Cache ―> Memory ―> Mass storage 的层次结构.
下图描述的就是 CPU、Cache、内存、以及 DMA 之间的关系. 程序的指令部分和数据部分一般分别存放在两片不同的 cache 中，对应指令缓存 (I-Cache) 和数据缓存 (D-Cache).
引入 Cache 的理论基础是程序局部性原理，包括时间局部性和空间局部性。即最近被 CPU 访问的数据，短期内 CPU 还要访问 (时间); 被 CPU 访问的数据附近的数据，CPU 短期内还要访问 (空间). 因此如果将刚刚访问过的数据缓存在 Cache 中，那下次访问时，可以直接从 Cache 中取，其速度可以得到数量级的提高.
CPU 缓存 (Cache Memory) 位于 CPU 与内存之间的临时存储器，它的容量比内存小但交换速度快。在缓存中的数据是内存中的一小部分，但这一小部分是短时间内 CPU 即将访问的，当 CPU 调用大量数据时，就可避开内存直接从缓存中调用，从而加快读取速度.

下图是一个典型的存储器层次结构，我们可以看到一共使用了三级缓存

# 为什么要有多级 CPU Cache

二级缓存就是一级缓存的缓冲器：一级缓存制造成本很高因此它的容量有限，二级缓存的作用就是存储那些 CPU 处理时需要用到、一级缓存又无法存储的数据。同样道理，三级缓存和内存可以看作是二级缓存的缓冲器，它们的容量递增，但单位制造成本却递减.

另外需要注意的是 L3 Cache 和 L1,L2 Cache 有着本质的区别.L1 和 L2 Cache 都是每个 CPU core 独立拥有一个，而 L3 Cache 是几个 Cores 共享的.

# cpu 与 cache 内存交互的过程

CPU 接收到指令后，它会最先向 CPU 中的一级缓存 (L1 Cache) 去寻找相关的数据，然一级缓存是与 CPU 同频运行的，但是由于容量较小，所以不可能每次都命中。这时 CPU 会继续向下一级的二级缓存 (L2 Cache) 寻找，同样的道理，当所需要的数据在二级缓存中也没有的话，会继续转向 L3 Cache、内存 (主存) 和硬盘.

# 什么是 cache line

Cache Line 可以简单的理解为 CPU Cache 中的最小缓存单位。内存和高速缓存之间或高速缓存之间的数据移动不是以单个字节或甚至 word 完成的。相反，移动的最小数据单位称为缓存行，有时称为缓存块目前主流的 CPU Cache 的 Cache Line 大小都是 64Bytes

# cache 写机制

Cache 写机制分为 write through 和 write back 两种.

Write-through (直写模式) 在数据更新时，同时写入缓存 Cache 和后端存储。此模式的优点是操作简单；缺点是因为数据修改需要同时写入存储，数据写入速度较慢.
Write-back (回写模式) 在数据更新时只写入缓存 Cache. 只在数据被替换出缓存时，被修改的缓存数据才会被写到后端存储。此模式的优点是数据写入速度快，因为不需要写存储；缺点是一旦更新后的数据未被写入存储时出现系统掉电的情况，数据将无法找回.

# cache 一致性

多个处理器对某个内存块同时读写，会引起冲突的问题，这也被称为 Cache 一致性问题.

M 代表更改 (modified), 表示缓存中的数据已经更改，在未来的某个时刻将会写入内存；
E 代表排除 (exclusive), 表示缓存的数据只被当前的核心所缓存；
S 代表共享 (shared), 表示缓存的数据还被其他核心缓存；
I 代表无效 (invalid), 表示缓存中的数据已经失效，即其他核心更改了数据.

# cache 的局部性

程序在一段时间内访问的数据通常具有局部性。局部性分为 "时间局部性" 和 "空间局部性".

时间局部性：指当前被访问的数据随后有可能访问到
如下代码：这里的 sum 和 i 都具有时间局部性。那么它们就会被 Cache 管理，被 CPU 取值命中.

行高亮

	int Sum(int[] ay){
	int sum = 0;
	for(int i = 0; i < ay.Length; i++){
	sum += ay[i];
	}
	return sum;
	}

空间局部性：当前访问地址附近的地址可能随后被访问.
如下代码：我们知道一个二维数组在内存里的排列是按行顺序排列的，大概是这样:ay [0,0], ay [0,1], ay [0,2],ay [1,0], ay [1,1], ay [1,2]…… SumCache 的写法会完全命中 ay 在内存里的排布，而 SumMiss 的写法则会 Miss, 二者的函数执行效率差距几十倍

行高亮

	int SumCache(int[,] ay){
	int sum = 0;
	for(int i = 0; i < 10; i++){
	for(int j = 0; j < 3; j++){
	sum += ay[i,j];
	}
	}
	return sum;
	}

	int SumMiss(int[,] ay){
	int sum = 0;
	for(int j = 0; j < 3; j++){
	for(int i = 0; i < 10; i++){
	sum += ay[i,j];
	}
	}
	return sum;
	}

# cache 替换策略

Cache 工作原理要求它尽量保存最新数据，当从主存向 Cache 传送一个新块，而 Cache 中可用位置已被占满时，就会产生 Cache 替换的问题.
常用的替换算法有下面三种.

LFU
LFU (Least Frequently Used, 最不经常使用) 算法将一段时间内被访问次数最少的那个块替换出去。每块设置一个计数器，从 0 开始计数，每访问一次，被访块的计数器就增 1. 当需要替换时，将计数值最小的块换出，同时将所有块的计数器都清零.
这种算法将计数周期限定在对这些特定块两次替换之间的间隔时间内，不能严格反映近期访问情况，新调入的块很容易被替换出去.
LRU
LRU (Least Recently Used, 近期最少使用) 算法是把 CPU 近期最少使用的块替换出去。这种替换方法需要随时记录 Cache 中各块的使用情况，以便确定哪个块是近期最少使用的块。每块也设置一个计数器，Cache 每命中一次，命中块计数器清零，其他各块计数器增 1. 当需要替换时，将计数值最大的块换出.
LRU 算法相对合理，但实现起来比较复杂，系统开销较大。这种算法保护了刚调入 Cache 的新数据块，具有较高的命中率.LRU 算法不能肯定调出去的块近期不会再被使用，所以这种替换算法不能算作最合理、最优秀的算法。但是研究表明，采用这种算法可使 Cache 的命中率达到 90% 左右.
随机替换
最简单的替换算法是随机替换。随机替换算法完全不管 Cache 的情况，简单地根据一个随机数选择一块替换出去。随机替换算法在硬件上容易实现，且速度也比前两种算法快。缺点则是降低了命中率和 Cache 工作效率.

# Cache Miss

当运算器需要从存储器中提取数据时，它首先在最高级的 cache 中寻找然后在次高级的 cache 中寻找。如果在 cache 中找到，则称为命中 hit; 反之，则称为不命中 miss.
在大部分的情况下，在现代 CPU 的频率带来的运算力下，Cache Miss 比数学运算更容易成为程序的性能瓶颈，且在代码中的表现比较隐晦。这使得一味的讨论复杂度 O (n) 不再适用，因为现在效率 = 数据 + 代码，最常见的例子就是在数据量小的情况下遍历数组会比 (Hash) Map 快上很多

# 如何避免 Cache Miss

尽量使用数组，尽量分割属性 (SOA), 尽量连续的进行处理.

对于高频分配的部分，会预先分配大块内存用来管理，保证内存的连续性
在需要高性能的情形下，应该尽量避免虚函数，保证指令的连续性

计算机操作系统原理