1.CPU缓存架构详解
1.1 CPU高速缓存概念
在计算机的核心组件CPU中，缓存扮演着极为关键的角色，它的全称是高速缓冲存储器，是一种位于CPU和主内存之间的特殊存储器。缓存的独特之处在于，虽然它的容量相对较小，但数据读写速度却极高。
CPU高速缓存依据层级，可以细分为一级缓存、二级缓存，部分高端CPU甚至还配备了三级缓存。在这个层级体系里，每一级缓存中的全部数据，都构成了下一级缓存内容的一部分。从技术实现和成本角度来看，一级缓存的技术难度最高，制造成本也最为昂贵，随着层级的递增，二级缓存和三级缓存的技术难度和制造成本相对递减。与之相反，它们的容量呈现出相对递增的趋势，即一级缓存容量最小，二级缓存容量大于一级缓存，三级缓存容量则在三者中最大。
由于CPU的速度远高于主内存，CPU直接从内存中存取数据要等待一定时间周期，Cache中保存着CPU刚用过或循环使用的一部分数据，当CPU再次使用该部分数据时可从Cache中直接调用,减少CPU的等待时间，提高了系统的效率。
当CPU与存储设备交互时，无论是数据的读写，还是指令的存取，都倾向于集中在一个连续的区域内，这便是局部性原理。它包含两个重要方面：
- 时间局部性（Temporal Locality）：若某一信息项当前正在被访问，那么在不久的将来，它极有可能会再次被访问。常见场景如循环语句、递归函数，以及方法的频繁调用等。
- 空间局部性（Spatial Locality）：一旦某个存储位置被引用，那么在未来，其邻近位置也很可能会被访问。例如顺序执行的代码片段、连续创建的对象，以及数组元素的访问等。
1.2 CPU多核缓存架构
现代CPU为了提升执行效率，减少CPU与内存的交互，一般在CPU上集成了多级缓存架构，常见的为三级缓存结构。如下图：
CPU寄存器作为安置于CPU内部的特殊存储器，拥有超乎寻常的读写速度，相较于缓存和主存更为迅速。在数据处理过程中，CPU不会直接从主存读取数据，而是优先将常用数据存入寄存器进行处理，极大地提升了数据的访问与处理效率。然而，寄存器的容量十分有限，通常仅有几十到几百字节，这也决定了它只能存储少量的数据，在高效处理和存储规模之间形成了一种特殊的平衡。 当CPU读取一个地址中的数据时，会先在 L1 Cache 中查找。如果数据在 L1 Cache 中找到，CPU 会直接从 L1 Cache 中读取数据。如果没有找到，则会将这个请求发送给 L2 Cache，然后在 L2 Cache 中查找，如果 L2 Cache 中也没有找到，则会继续将请求发送到 L3 Cache 中。如果在 L3 Cache 中还是没有找到数据，则最后会从主内存中读取数据并将其存储到 CPU 的缓存中。
当CPU写入一个地址中的数据时，同样会先将数据写入 L1 Cache 中，然后再根据缓存一致性协议将数据写入 L2 Cache、L3 Cache 以及主内存中。具体写入过程与缓存一致性协议相关，有可能只写入 L1 Cache 中，也有可能需要将数据写入 L2 Cache、L3 Cache 以及主内存中。写入过程中也可能会使用缓存行失效、写回等技术来提高效率。
思考：这种缓存架构在多线程访问的时候存在什么问题？
CPU多核缓存架构缓存一致性问题分析
场景一
场景二
在CPU多核缓存架构里，每个处理器都配备专属的独立缓存。当涉及共享数据时，往往会存在多个副本：主内存中存有一个副本，每个请求该数据的处理器的本地缓存里也各有一个副本。关键在于，一旦某个数据副本产生变更，其他所有副本都必须同步更新，以如实反映这一变化。这就意味着，CPU多核缓存架构必须确保缓存一致性，从而保障整个系统数据的准确性与可靠性，避免因数据不一致导致的运行错误或异常情况 。
1.3 CPU缓存架构缓存一致性的解决方案
《64-ia-32-architectures-software-developer-vol-3a-part-1-manual.pdf》中有如下描述：
The 32-bit IA-32 processors support locked atomic operations on locations in system memory. These operations are typically used to manage shared data structures (such as semaphores, segment descriptors, system segments, or page tables) in which two or more processors may try simultaneously to modify the same field or flag. The processor uses three interdependent mechanisms for carrying out locked atomic operations:
• Guaranteed atomic operations
• Bus locking, using the LOCK# signal and the LOCK instruction prefix
• Cache coherency protocols that ensure that atomic operations can be carried out on cached data structures (cache lock); this mechanism is present in the Pentium 4, Intel Xeon, and P6 family processors
32位的IA-32处理器具备执行原子操作的能力，能够对系统内存中的位置进行锁定。这些原子操作在管理共享数据结构时发挥着关键作用，像信号量、段描述符、系统段或者页表这类共享数据结构，时常会面临两个或多个处理器同时尝试修改相同字段或标志的情况。
为了顺利执行锁定的原子操作，处理器运用了三种相互关联的机制：
- 确保原子操作的可靠性：处理器内置了一些特殊指令与机制，在多个处理器并发执行原子操作时，能够避免相互干扰，切实保障原子性。其实现通常依赖硬件的支持。以x86架构为例，该架构提供了诸如XADD、XCHG、CMPXCHG等一系列原子操作指令，当多个处理器同时执行这些指令时，它们之间不会产生干扰，原子性得以有效保证。
- 总线锁定机制：通过LOCK#信号和LOCK指令前缀实现，这是一种确保原子操作的有效手段，常应用于LOCK指令前缀与部分特殊指令中。当处理器执行LOCK指令前缀时，会主动拉低LOCK#信号，该信号向其他处理器传达当前总线上的数据已被锁定的信息，进而确保原子操作的顺利执行。
- 缓存一致性协议：此协议确保原子操作能够在缓存的数据结构上正常执行，也就是所谓的缓存锁定。该机制在Pentium 4、Intel Xeon以及P6系列处理器中得以应用，对于维持缓存数据的一致性、保障原子操作的正确性有着重要意义。
缓存一致性协议是一种至关重要的机制，旨在确保处理器缓存中的数据与主存中的数据时刻保持一致。在多处理器环境下，当一个处理器对某数据进行修改时，缓存一致性协议会借助处理器之间的通信，保证其他处理器缓存中的该数据能够及时更新或失效。这一过程能够有效避免数据不一致问题，确保多个处理器同时对同一数据进行操作时，它们所读取到的数据始终保持一致状态，为系统的稳定运行和数据的准确性提供了坚实保障 。
缓存锁定是基于缓存一致性协议实现原子操作的关键机制。在多处理器环境下，当多个处理器试图同时修改同一缓存行中的数据时，缓存锁定就会发挥作用。它借助缓存一致性协议，确保在任何时刻仅有一个处理器能够成功获得对该缓存行的锁定，进而保障操作的原子性，避免数据冲突和不一致问题。缓存锁定的有效运行离不开硬件的支持，不同的处理器架构，由于其设计理念、性能侧重和技术特点的差异，在缓存锁定的实现方式上也各有不同。
缓存一致性协议无法适用的特殊情形
- 数据无法缓存或跨缓存行：当需操作的数据无法被缓存至处理器内部，又或者数据跨越了多个缓存行时，处理器就会启用总线锁定。不可缓存的设备内存，例如显存、网络接口卡的缓存等，都属于无法被缓存在处理器内部的数据。这些设备内存通常不在缓存一致性协议的管控范围之内，处理器无法将它们存储到自身的缓存行中，所以在对这类数据进行操作时，只能依赖总线锁定。
- 处理器不支持缓存锁定：部分处理器不具备缓存锁定的功能。以早期的Pentium系列处理器为例，它们就没有缓存锁定机制。在这类处理器上，若要实现原子操作，唯一的选择便是使用总线锁定。不过，现代的处理器大多都支持缓存锁定，所以在实际应用中，为获取更优的性能，应优先选用缓存锁定来实现原子操作 。
1.4 缓存一致性协议实现原理
总线窥探
总线窥探（Bus snooping）是一种用于维护分布式共享内存系统中缓存一致性的方案。在该方案里，缓存中的一致性控制器（snoopy cache）会对总线事务进行监视与窥探。其中，配置了一致性控制器（snooper）的缓存被称作snoopy缓存。此方案由Ravishankar和Goodman于1983年提出，旨在解决多处理器环境下，不同处理器缓存与共享内存之间的数据一致性问题，通过对总线上数据传输和操作的监控，确保各处理器缓存中的数据与共享内存保持同步，有效避免数据不一致导致的程序运行错误 。
在计算机中，数据通过总线在处理器和内存之间传递。每次处理器和内存之间的数据传递都是通过一系列步骤来完成的，这一系列步骤称之为总线事务（Bus Transaction）
工作原理
在多处理器系统中，当特定数据被多个缓存共享时，一旦某个处理器修改了共享数据的值，这一更改就必须同步到所有持有该数据副本的其他缓存中。这种数据更改的传播过程对于维护系统的缓存一致性至关重要，能够有效防止因数据不一致导致的系统错误。
数据变更的通知机制主要通过总线窥探来实现。在这一机制下，所有的窥探者（即一致性控制器）持续监视着总线上的每一个事务。当总线上出现修改共享缓存块的事务时，各个窥探者会立即检查自身所在缓存，确认是否存有该共享块的相同副本。
一旦发现缓存中有共享块的副本，相应的窥探者就会执行特定动作，以确保缓存一致性。这些动作通常包括刷新缓存块，即更新缓存中的数据，使其与修改后的数据一致；或者使缓存块失效，让缓存不再使用旧数据，迫使下次访问时从主存或其他最新数据源获取。
此外，这些动作还会引发缓存块状态的改变，而具体的状态变化规则则取决于所采用的缓存一致性协议（cache coherence protocol）。不同的缓存一致性协议对缓存块状态的定义和转换条件有所不同，但总体目的都是为了高效、准确地维护多缓存环境下的数据一致性 。
窥探协议类型
根据管理写操作的本地副本的方式，有两种窥探协议:
写失效（Write-invalidate）
当处理器写入一个共享缓存块时，其他缓存中的所有共享副本都会通过总线窥探失效。这种方法确保处理器只能读写一个数据的一个副本。其他缓存中的所有其他副本都无效。这是最常用的窥探协议。MSI、MESI、MOSI、MOESI和MESIF协议属于该类型。
写更新（Write-update）
当处理器写入一个共享缓存块时，其他缓存的所有共享副本都会通过总线窥探更新。这个方法将写数据广播到总线上的所有缓存中。它比write-invalidate协议引起更大的总线流量。这就是为什么这种方法不常见。Dragon和firefly协议属于此类别。
缓存一致性协议
缓存一致性协议在多处理器系统中应用于高速缓存一致性。为了保持一致性，人们设计了各种模型和协议，如MSI、MESI(又名Illinois)、MOSI、MOESI、MERSI、MESIF、write-once、Synapse、Berkeley、Firefly和Dragon协议。
MESI协议
MESI协议是一种基于写失效机制的缓存一致性协议，也是在支持回写（write-back）缓存场景中应用最为广泛的协议。它还有一个别称——伊利诺伊协议（Illinois protocol），这源于它诞生于伊利诺伊大学厄巴纳 - 香槟分校。
在MESI协议下，缓存行具备四种截然不同的状态：
- 已修改（Modified，M）：处于该状态的缓存行是脏的（dirty），意味着其数据与主存中的值不一致。一旦其他CPU内核需要读取主存中对应的数据，这一缓存行必须先回写到主存，随后状态转变为共享（S）。
- 独占（Exclusive，E）：此状态表明缓存行仅存在于当前缓存中，并且数据是干净的，即与主存数据完全相同。当其他缓存尝试读取该数据时，其状态会转变为共享；而当当前缓存对数据进行写入操作时，状态则会变为已修改。
- 共享（Shared，S）：表明缓存行不仅存在于当前缓存，还存在于其他缓存中，且数据均未被修改。在这种状态下，缓存行可在任意时刻被舍弃。
- 无效（Invalid，I）：顾名思义，该状态下的缓存行已失去有效性，不能再被使用 。
MESI协议在多处理器系统中发挥着关键作用，其核心目的是保障多个处理器间共享内存数据的一致性。当某一处理器需要访问特定内存数据时，它会优先在自身缓存中进行检索，查看是否存在该数据的副本。若缓存中并无此数据副本，处理器便会发出缓存不命中（miss）请求，进而从主内存中获取该数据副本，并将其存储至自身缓存内。
在处理器发出缓存不命中请求后，如果该数据副本已存在于其他处理器或核心的缓存中（此时处于共享状态），那么这个处理器就能从其他处理器的缓存里复制该数据副本，这一过程被称作缓存到缓存复制（cache - to - cache transfer）。
缓存到缓存复制机制极大地减少了对主内存的访问频次，从而有效提升了系统性能。然而，维护数据一致性是至关重要的前提，否则极易引发数据错误或不一致的问题。所以，在执行缓存到缓存复制操作时，必须借助MESI协议中的其他状态转换规则来确保数据的一致性。举例来说，若两个缓存都处于修改状态，那么在进行缓存到缓存复制前，必须先将其中一个缓存的数据写回到主内存，以此保障数据一致性，为系统稳定运行筑牢基础 。
1.5 伪共享的问题
在多核心环境下，若不同核心上的线程分别对同一缓存行中的不同变量数据进行操作，就会频繁出现缓存失效的情况。即便从代码层面来看，这些线程所操作的数据彼此毫无关联，这种看似不合理的资源竞争现象，便是伪共享（False Sharing）。
以ArrayBlockingQueue为例，它包含三个成员变量：
- takeIndex：代表需要被取走的元素下标。
- putIndex：表示可被元素插入的位置下标。
- count：用于记录队列中元素的数量。
由于这三个变量的数据量相对较小，很容易被放置在同一个缓存行中。然而，它们在修改逻辑上相互之间并无太多关联。这就导致每当其中一个变量被修改时，之前缓存的其他变量数据都会失效，使得缓存无法充分发挥共享的效能，进而影响程序运行效率 。
如上图所示，当生产者线程put一个元素到ArrayBlockingQueue时，putIndex会修改，从而导致消费者线程的缓存中的缓存行无效，需要从主存中重新读取。
linux下查看Cache Line大小
Cache Line大小是64Byte
或者执行 cat /proc/cpuinfo 命令
避免伪共享方案
方案1：缓存行填充
class Pointer {
volatile long x; //避免伪共享： 缓存行填充
long p1, p2, p3, p4, p5, p6, p7;
volatile long y;
}
方案2：使用 @sun.misc.Contended 注解（java8）
注意需要配置jvm参数：-XX:-RestrictContended
public class FalseSharingTest {
public static void main(String[] args) throws InterruptedException {
testPointer(new Pointer());
}
private static void testPointer(Pointer pointer) throws InterruptedException {
long start = System.currentTimeMillis();
Thread t1 = new Thread(() -> {
for (int i = 0; i < 100000000; i++) {
pointer.x++;
}
});
Thread t2 = new Thread(() -> {
for (int i = 0; i < 100000000; i++) {
pointer.y++;
}
});
t1.start();
t2.start();
t1.join();
t2.join();
System.out.println(pointer.x+","+pointer.y);
System.out.println(System.currentTimeMillis() - start);
}
}
class Pointer {
// 避免伪共享： @Contended + jvm参数：-XX:-RestrictContended jdk8支持
//@Contended
volatile long x;
//避免伪共享： 缓存行填充
//long p1, p2, p3, p4, p5, p6, p7;
volatile long y;
}
方案3：使用线程的本地内存，比如ThreadLocal
ThreadLocal提供了线程局部变量，它允许每个线程都拥有自己独立的变量副本，各个线程之间的变量相互隔离，互不干扰。这样在多线程环境下，每个线程都可以安全地访问和修改自己的变量副本，而不会影响其他线程的变量值，避免了线程安全问题。
import java.util.Random;
public class ThreadLocalExample {
// 创建ThreadLocal对象，用于存储每个线程的随机数
private static final ThreadLocal<Integer> threadLocal = new ThreadLocal<>();
public static void main(String[] args) {
// 创建并启动三个线程
Thread thread1 = new Thread(() -> {
// 为线程1生成一个随机数，并存储到ThreadLocal中
int randomNumber = new Random().nextInt(100);
threadLocal.set(randomNumber);
System.out.println("Thread 1 stored value: " + randomNumber);
// 从ThreadLocal中获取值并打印
System.out.println("Thread 1 retrieved value: " + threadLocal.get());
});
Thread thread2 = new Thread(() -> {
// 为线程2生成一个随机数，并存储到ThreadLocal中
int randomNumber = new Random().nextInt(100);
threadLocal.set(randomNumber);
System.out.println("Thread 2 stored value: " + randomNumber);
// 从ThreadLocal中获取值并打印
System.out.println("Thread 2 retrieved value: " + threadLocal.get());
});
Thread thread3 = new Thread(() -> {
// 从ThreadLocal中获取值并打印，由于没有先设置值，会使用initialValue()的默认值null
System.out.println("Thread 3 retrieved value: " + threadLocal.get());
});
thread1.start();
thread2.start();
thread3.start();
}
}