Java 内存模型

从抽象的角度来看，JMM定义了线程和主内存之间的抽象关系：

线程之间的共享变量存储在主内存（Main Memory）中
每个线程都有一个私有的本地内存（Local Memory），本地内存是JMM的一个抽象概念，并不真实存在，它涵盖了缓存、写缓冲区、寄存器以及其他的硬件和编译器优化。本地内存中存储了该线程以读/写共享变量的拷贝副本。
从更低的层次来说，主内存就是硬件的内存，而为了获取更好的运行速度，虚拟机及硬件系统可能会让工作内存优先存储于寄存器和高速缓存中。
Java内存模型中的线程的工作内存（working memory）是cpu的寄存器和高速缓存的抽象描述。而JVM的静态内存储模型（JVM内存模型）只是一种对内存的物理划分而已，它只局限在内存，而且只局限在JVM的内存。

JMM_Hardware-Memory-Architecture

硬件架构

CPU 多级缓存模型

CPU缓存(CPU Cache)的目的是为了提高访问内存(RAM)的效率。现代多核处理器，一个CPU由多个核组成，每个核又可以有多个硬件线程，比如我们说4核8线程，就是指有4个核，每个核2个线程，这在OS看来就像8个并行处理器一样。

CPU缓存有多级缓存，比如L1, L2, L3等：

• L1容量最小，速度最快，每个核都有L1缓存，L1又专门针对指令和数据分成L1d(数据缓存)，L1i(指令缓存)。
• L2容量比L1大，速度比L1慢，每个核都有L2缓存。
• L3容量最大，速度最慢，多个核共享一个L3缓存。
• L1、L2、L3的越离CPU近就越小，速度也就越快，越离CPU远，速度也越慢。

有些CPU可能还有L4缓存，比如用来在核显和CPU之间交换数据的eDRAM，不过不常见；此外还有其他类型的缓存，比如TLB(translation lookaside buffer)，用于物理地址和虚拟地址转译，这不是我们关心的缓存。

CPU-L3-Cache-Structure

它们的存取速度：

• L1的存取速度：4个CPU时钟周期
• L2的存取速度：11个CPU时钟周期
• L3的存取速度：39个CPU时钟周期
• RAM内存的存取速度：107个CPU时钟周期

为什么设计成三层？

我们的数据从内存向上，先到L3，再到L2，再到L1，最后到寄存器进行计算。那么，为什么会设计成三层？这里有以下几方面的考虑：

• 物理速度，如果要更大的容量就需要更多的晶体管，除了芯片的体积会变大，更重要的是大量的晶体管会导致速度下降，因为访问速度和要访问的晶体管所在的位置成反比。也就是当信号路径变长时，通信速度会变慢，这就是物理问题。
• 另外一个问题是，多核技术中，数据的状态需要在多个CPU进行同步。我们可以看到，cache和RAM的速度差距太大。所以，多级不同尺寸的缓存有利于提高整体的性能。这个世界永远是平衡的，一面变得有多光鲜，另一方面也会变得有多黑暗，建立多级的缓存，一定就会引入其它的问题。这里有两个比较重要的问题。
• 一个是比较简单的缓存命中率的问题
• 另一个是比较复杂的缓存更新的一致性问题

缓存分配策略和更新策略

• 当CPU从内存读数据时，如果该数据没有在缓存中(read miss)，CPU会把数据拷贝到缓存。
• 当CPU往内存写数据时，有多重写策略：
  • Write through 更新缓存的数据，同时更新内存的数据。
  • Write back 只更新缓存的数据，同时在缓存项设置一个drity标志位，内存的数据只会在某个时刻更新(比如替换cache line时)。
• 如果在写的时候数据没有在缓存中(write miss)，也有两种策略：
  • Write allocate 在写之前先把数据加载到缓存，然后再实施上面的写策略。
  • No-write allocate 不加载缓存，直接把数据写到内存。数据只有在 read miss 时才会加载到缓存。

虽然上面两组策略可以任意搭配，但通常情况下是 No-write allocate 和 Write through 一起使用，而 Write allocate 则和 Write back 一起使用，下面是 wikipedia 的两张流程图：

No-write allocate 方式的 Write through Cache：

CPU-Cache-Write-Through-Cache

Write allocate 方式的 Write back Cache：

CPU-Cache-Write-Back-Cache
当我们向一个内存写数据时，内存中的数据可能不马上被更新，这个新数据可能还在cache line呆着。因为每个核都有自己的缓存，如果CPU不做处理，可以想象一定会出问题的：比如核1改了数据，核2去读同一个数据，此时数据还在核1的缓存中，核2读到的就是老的数据。CPU为了处理多核间的缓存同步，有一套复杂的一致性协议。

缓存命中

缓存行

缓存基本上来说就是把后面的数据加载到离自己近的地方，对于 CPU 来说，它是不会一个字节一个字节的加载的，因为这非常没有效率，一般来说都是要一块一块的加载的，对于这样的一块一块的数据单位，术语叫 Cache Line。

一般来说，一个主流的 CPU 的 Cache Line 是 64 Bytes（也有的CPU用32Bytes和128Bytes），64 Bytes也就是 16 个 32 位的整型，这就是 CPU 从内存中捞数据上来的最小数据单位。

比如：Cache Line是最小单位（64Bytes），所以先把 Cache 分布多个 Cache Line，比如：L1 有 32KB，那么，32KB/64B = 512 个 Cache Line。

一方面，缓存需要把内存里的数据放到放进来，英文叫 CPU Associativity。Cache 的数据放置的策略决定了内存中的数据块会拷贝到 CPU Cache 中的哪个位置上，因为 Cache 的大小远远小于内存，所以，需要有一种地址关联的算法，能够让内存中的数据可以被映射到 Cache 中来。这个有点像内存地址从逻辑地址向物理地址映射的方法，但不完全一样。

基本上来说，我们会有如下的一些方法。

• 一种方法是，任何一个内存地址的数据可以被缓存在任何一个 Cache Line 里，这种方法是最灵活的，但是，如果我们要知道一个内存是否存在于 Cache 中，我们就需要进行 O(n) 复杂度的 Cache 遍历，这是很没有效率的。
• 另一种方法，为了降低缓存搜索算法，我们需要使用像Hash Table这样的数据结构，最简单的hash table就是做求模运算，比如：我们的 L1 Cache 有 512 个 Cache Line，那么，公式：（内存地址 mod 512）* 64 就可以直接找到所在的Cache地址的偏移了。但是，这样的方式需要我们的程序对内存地址的访问要非常地平均，不然冲突就会非常严重。这成了一种非常理想的情况了。

• 为了避免上述的两种方案的问题，于是就要容忍一定的hash冲突，也就出现了 N-Way 关联。也就是把连续的N 个 Cache Line 绑成一组，然后，先把找到相关的组，然后再在这个组内找到相关的 Cache Line。这叫 Set Associativity。如下图所示。

  
  01-technology_B-advanced_B02-CPU-Cache-Line-Set-Associativity.png

对于 N-Way 组关联，可能有点不好理解，这里个例子，并多说一些细节（不然后面的代码你会不能理解），Intel 大多数处理器的 L1 Cache 都是 32KB，8-Way 组相联，Cache Line 是 64 Bytes。这意味着，

• 32KB的可以分成，32KB / 64 = 512 条 Cache Line。
• 因为有8 Way，于是会每一Way 有 512 / 8 = 64 条 Cache Line。
• 于是每一路就有 64 x 64 = 4096 Byts 的内存。

为了方便索引内存地址，

• Tag：每条 Cache Line 前都会有一个独立分配的 24 bits来存的 tag，其就是内存地址的前24bits
• Index：内存地址后续的 6 个 bits 则是在这一 Way 的是Cache Line 索引，2^6 = 64 刚好可以索引64条Cache Line
• Offset：再往后的 6bits 用于表示在 Cache Line 里的偏移量

当拿到一个内存地址的时候，先拿出中间的 6bits 来，找到是哪组。

CPU-Cache-Pick-cache-set-by-index.png

然后，在这一个 8 组的 cache line 中，再进行 O(n) n=8 的遍历，主是要匹配前 24bits 的 tag。如果匹配中了，就算命中，如果没有匹配到，那就是 cache miss，如果是读操作，就需要进向后面的缓存进行访问了。

L2/L3 同样是这样的算法。而淘汰算法有两种，一种是随机一种是 LRU。现在一般都是以 LRU 的算法（通过增加一个访问计数器来实现）

Cache-Search-for-matching-tag-in-the-set

这也意味着：

• L1 Cache 可映射 36bits 的内存地址，一共 2^36 = 64GB 的内存
• 当 CPU 要访问一个内存的时候，通过这个内存中间的 6bits 定位是哪个 set，通过前 24bits 定位相应的Cache Line。
• 就像一个 hash Table 的数据结构一样，先是 O(1)的索引，然后进入冲突搜索。
• 因为中间的 6bits 决定了一个同一个 set，所以，对于一段连续的内存来说，每隔 4096 的内存会被放在同一个组内，导致缓存冲突。

此外，当有数据没有命中缓存的时候，CPU 就会以最小为 Cache Line 的单元向内存更新数据。当然，CPU 并不一定只是更新 64Bytes，因为访问主存实在是太慢了，所以，一般都会多更新一些。好的 CPU 会有一些预测的技术，如果找到一种 pattern 的话，就会预先加载更多的内存，包括指令也可以预加载。

这叫 Prefetching 技术 （参看，Wikipedia 的 Cache Prefetching 和 纽约州立大学的 Memory Prefetching）。比如，你在 for-loop 访问一个连续的数组，你的步长是一个固定的数，内存就可以做到 prefetching。（注：指令也是以预加载的方式执行）

缓存一致

对于主流的CPU来说，缓存的写操作基本上是两种策略：

• Write Back：写操作只在Cache上，然后再flush到内存上
• Write Through：写操作同时写到cache和内存上。

为了提高写的性能，一般来说，主流的CPU（如：Intel Core i7/i9）采用的是Write Back的策略，因为直接写内存实在是太慢了。

现在问题来了，如果有一个数据 x 在 CPU 第0核的缓存上被更新了，那么其它CPU核上对于这个数据 x 的值也要被更新，这就是缓存一致性的问题。

一般来说，在CPU硬件上，会有两种方法来解决这个问题。

1. Directory 协议。这种方法的典型实现是要设计一个集中式控制器，它是主存储器控制器的一部分。其中有一个目录存储在主存储器中，其中包含有关各种本地缓存内容的全局状态信息。当单个CPU Cache 发出读写请求时，这个集中式控制器会检查并发出必要的命令，以在主存和CPU Cache之间或在CPU Cache自身之间进行数据同步和传输。
2. Snoopy 协议。这种协议更像是一种数据通知的总线型的技术。CPU Cache通过这个协议可以识别其它Cache上的数据状态。如果有数据共享的话，可以通过广播机制将共享数据的状态通知给其它CPU Cache。这个协议要求每个CPU Cache 都可以“窥探”数据事件的通知并做出相应的反应。如下图所示，有一个Snoopy Bus的总线。
   CPU-Cache-Snoopy-Bus.png
   因为 Directory 协议是一个中心式的，会有性能瓶颈，而且会增加整体设计的复杂度。而 Snoopy 协议更像是微服务+消息通讯，所以，现在基本都是使用 Snoopy 的总线的设计。

在分布式系统中我们一般用 Paxos/Raft 这样的分布式一致性的算法，而在 CPU 的微观世界里，则不必使用这样的算法，原因是因为 CPU 的多个核的硬件不必考虑网络会断会延迟的问题。所以，CPU 的多核心缓存间的同步的核心就是要管理好数据的状态就好了。

MESI协议

缓存数据有四个状态：Modified（已修改）, Exclusive（独占的）,Shared（共享的），Invalid（无效的）。

状态流转图（太复杂！）：

CPU-Cache-MESI-Status

MESI 这种协议在数据更新后，会标记其它共享的 CPU 缓存的数据拷贝为 Invalid 状态，然后当其它 CPU 再次read 的时候，就会出现 cache miss 的问题，此时再从内存中更新数据。从内存中更新数据意味着 20 倍速度的降低。

我们能不能直接从我隔壁的 CPU 缓存中更新？是的，这就可以增加很多速度了，但是状态控制也就变麻烦了。还需要多来一个状态：Owner(宿主)，用于标记，我是更新数据的源。于是，出现了 MOESI 协议

MOESI 和 MESIF 协议

MOESI 协议允许 CPU Cache 间同步数据，于是也降低了对内存的操作，性能是非常大的提升，但是控制逻辑也非常复杂。

与 MOESI 协议类似的一个协议是 MESIF，其中的 F 是 Forward，同样是把更新过的数据转发给别的 CPU Cache 但是，MOESI 中的 Owner 状态 和MESIF 中的 Forward 状态有一个非常大的不一样—— Owner 状态下的数据是 dirty 的，还没有写回内存，Forward 状态下的数据是 clean的，可以丢弃而不用另行通知。

这里MESI协议解决了，多核之间缓存一致性问题，那单核多线程的缓存一致性怎么解决呢？

该 volatile 关键字上场了，后续文章会慢慢介绍，稍后。

参考：

1. 十分钟教你掌握CPU缓存
2. 程序优化：CPU缓存基础知识