CPU 缓存基础知识

并发编程首先需要简单了解下现代CPU相关知识。通过一些简单的图，简单的代码，来认识CPU以及一些常见的问题。

CPU存储与缓存的引入

下图描述了存储器金字塔层次结构

正因为CPU的计算速度与内存速度的严重不匹配，所以加上了多级缓存，让CPU能执行更多的指令

常见的三级缓存结构

如下图，描述一个有2个CPU且多核心的

• L1高速缓存：也叫一级缓存。一般内置在内核旁边，是与CPU结合最为紧密的CPU缓存。一次访问只需要2~4个时钟周期
• L2高速缓存：也叫二级缓存。空间比L1缓存大，速度比L1缓存略慢。一次访问约需要10多个时钟周期
• L3高速缓存：也叫三级缓存。部分单CPU多核心的才会有的缓存，介于多核和内存之间。存储空间已达Mb级别，一次访问约需要数十个时钟周期。

当CPU要读取一个数据时，首先从L1缓存查找，命中则返回；若未命中，再从L2缓存中查找，如果还没有则从L3缓存查找（如果有L3缓存的话）。如果还是没有，则从内存中查找，并将读取到的数据逐级放入缓存。如下图所示

缓存一致性协议

因为现代CPU的架构，所以必然会遇到多个处理器都涉及同一块主内存区域的更改时，这就将导致各自的缓存数据不一致；所以需要采取一定的规范来解决这个问题。如下图所示：

• 总线锁是把CPU和内存的通信给锁住了；使得在锁定期间，其它处理器不能操作内存的其它数据，这样开销较大

• 缓存锁不需锁定总线，只需要"锁定"被缓存的共享对象（实际为：缓存行）即可；接受到lock指令，通过缓存一致性协议，维护本处理器内部缓存和其它处理器缓存的一致性。相比总线锁，会提高CPU利用率。

MESI协议

MESI协议是基于Invalidate的高速缓存一致性协议，并且是支持回写高速缓存的最常用协议之一。

MESI 是指4种状态的首字母。每个缓存行(Cache Line)有4个状态，可用2个bit表示，它们分别是：

状态	描述	监听任务
M 修改 (Modified)	该Cache line有效，数据被修改了，和内存中的数据不一致，数据只存在于本Cache中。	缓存行必须时刻监听所有试图读该缓存行相对就主存的操作，这种操作必须在缓存将该缓存行写回主存并将状态变成S（共享）状态之前被延迟执行。
E 独享、互斥 (Exclusive)	该Cache line有效，数据和内存中的数据一致，数据只存在于本Cache中。	缓存行也必须监听其它缓存读主存中该缓存行的操作，一旦有这种操作，该缓存行需要变成S（共享）状态。
S 共享 (Shared)	该Cache line有效，数据和内存中的数据一致，数据存在于很多Cache中。	缓存行也必须监听其它缓存使该缓存行无效或者独享该缓存行的请求，并将该缓存行变成无效（Invalid）。
I 无效 (Invalid)	该Cache line无效。	无

当某个cpu修改缓存行数据时，其它的cpu通过监听机制获悉共享缓存行的数据被修改，会使其共享缓存行失效。本cpu会将修改后的缓存行写回到主内存中。此时其它的cpu如果需要此缓存行共享数据，则从主内存中重新加载，并放入缓存，以此完成了缓存一致性。

缓存行 cache line

• 程序局部性原理（这里解释为：访问内存或缓存的某个位置，顺带的把紧邻的位置一起读取出来）

  1. 缓存行越大，局部性空间效率越高，但读取时间慢
  2. 缓存行越小，局部性空间效率越低，但读取时间快

常见的缓存行一般64字节

通过代码实例认识缓存行的重要性

import java.util.concurrent.CountDownLatch;public class Main {private static class T {public volatile long x;}public static T[] arr = new T[2];static {arr[0] = new T();arr[1] = new T();}// 一亿次static int FOR_COUNT = 100_000_000;public static void main(String[] args) throws Exception{CountDownLatch latch = new CountDownLatch(2);Thread t1 = new Thread(()->{for (int i = 0; i < FOR_COUNT; i ++){arr[0].x ++;}latch.countDown();});Thread t2 = new Thread(()->{for (int i = 0; i < FOR_COUNT; i ++){arr[1].x ++;}latch.countDown();});final long start = System.nanoTime();t1.start();t2.start();latch.await();System.out.println((System.nanoTime() - start) /1_000_000 + " ms");}
}

在自己电脑上(2.3 GHz 双核Intel Core i5)跑如上代码要接近3000豪秒了

如上程序是：两个线程分别处理一个对象数组的不同变量，而这个变量是个volatile long x; ，因为数组的2个变量是在同一个缓存行中的，每次修改都修改了同一个缓存行，要有缓存同步操作，所以比较慢。

再看如下程序，只需修改T的定义

private static class T {public volatile long p1, p2, p3, p4, p5, p6, p7;public volatile long x;public volatile long p8, p9, p10, p11, p12, p13, p14;
}

可以降低到1000毫秒左右，因为数组的两个元素：arr[0].x 与 arr[1].x 不会在一个缓存行中；这样修改用的各自的缓存行，互不影响：

56字节
x(8字节)
56字节
56字节
x(8字节)
56字节

当然使用@Contended（运行加上`-XX:-RestrictContended）是最方便的

CPU指令的乱序执行

cpu中为了能够让指令的执行尽可能地并行起来，从而发明了流水线技术。但是如果两条指令的前后存在依赖关系，比如数据依赖，控制依赖等，此时后一条语句就必需等到前一条指令完成后，才能开始。cpu为了提高流水线的运行效率，会做出比如：

1. 对无依赖的前后指令做适当的乱序和调度；
2. 对控制依赖的指令做分支预测；
3. 对读取内存等的耗时操作，做提前预读；
4. …

这些都可能会导致指令乱序

---

附: 指令流水线是为提高处理器执行指令的效率，把一条指令的操作分成多个细小的步骤（取指、译码、执行、访问主存、写回），每个步骤由专门的电路完成的方式。举个例子：例如一条指令要执行要经过3个阶段：取指令、译码、执行，每个阶段都要花费一个机器周期，如果没有采用流水线技术，那么这条指令执行需要3个机器周期；如果采用了指令流水线技术，那么当这条指令完成取指后进入译码的同时，下一条指令就可以进行取指了，这样就提高了指令的执行效率。

通过代码实例认识到CPU指令乱序执行

google blog: Memory Reordering Caught in the Act

代码如下：

public class Main {static int x, y, a, b;public static void main(String[] args) throws Exception{int i = 0;while (true) {x = 0;y = 0;b = 0;a = 0;Thread A = new Thread(new Runnable() {@Overridepublic void run() {a = 1;x = b;}});Thread B = new Thread(new Runnable() {@Overridepublic void run() {b = 1;y = a;}});A.start();B.start();A.join();B.join();i++;if(x == 0 && y == 0){System.err.println(i + " " + x + " " + y);break;}}System.out.println("main end");}
}

指令有序的话，理论上不会出现x，y都等于0的情况；如果出现，则可以说明指令乱序

如上程序运行一段时间后（需要耐心等待一下），退出输出如下：

后续在认识线程安全（可见性，原子性，顺序性）的时候还将复习到此知识。