一、基本概念

并发与并行

并行(parallel)：指在同一时刻，有多条指令在多个处理器上同时执行。所以无论从微观还是从宏观来看，二者都是一起执行的。
并发(concurrency)：指在同一时刻只能有一条指令执行，但多个进程指令被快速的轮换执行，使得在宏观上具有多个进程同时执行的效果，但在微观上并不是同时执行的，只是把时间分成若干段，使多个进程快速交替的执行。
并发是并行的假象，目标都是最大化CPU的使用率

一、什么是JMM模型

Java内存模型（java memory model）是一种抽象概念，并不真实存在。
JMM描述了一组规则或者规范，通过此类规范定义了程序中各个变量的在共享数据区和私有数据区域的访问方式。

工作内存

JVM运行程序实体是线程，每个线程创建时，JVM为其创建一个工作内存（栈空间），用于存储线程私有数据。
线程对变量的操作，必须在工作内存中进行。工作内存中存储主内存中的变量副本。

主内存

所有变量都存储在主内存，是共享的内存区域，所有线程都可以访问。
多个线程对同一变量访问可能发生线程安全问题。

变量操作

1.将变量从主内存拷贝到自己的工作内存
2.对变量进行操作，操作完成后，将变量写回主内存，不能在主内存中操作变量。

内存交互操作

一个变量如何从主内存拷贝到工作内存、如何从工作内存同步到主内存之间的实现细节，Java内存模型定义了以下八种操作来完成：

  1.   - lock（锁定）：作用于主内存的变量，把一个变量标识为一条线程**独占状态**。
  2.   - unlock（解锁）：作用于主内存变量，把一个处于锁定状态的变量释放出来，释放后的变量才可以被其他线程锁定。
  3.   - read（读取）：作用于主内存变量，把一个变量值从**主内存传输**到线程的**工作内存**中，以便随后的load动作使用
  4.   - load（载入）：作用于工作内存的变量，它把read操作从主内存中得到的变量值放入工作内存的变量副本中。
  5.   - use（使用）：作用于工作内存的变量，把工作内存中的一个变量值**传递给执行引擎**，每当虚拟机遇到一个需要使用变量的值的字节码指令时将会执行这个操作。
  6.   - assign（赋值）：作用于工作内存的变量，它把一个从**执行引擎**接收到的值**赋值**给**工作内存**的变量，每当虚拟机遇到一个给变量赋值的字节码指令时执行这个操作。
  7.   - store（存储）：作用于工作内存的变量，把**工作内存**中的一个变量的值**传送到主内存**中，以便随后的write的操作。
  8.   - write（写入）：作用于主内存的变量，它把store操作从工作内存中一个变量的值传送到主内存的变量中。

image.png
Java内存模型还规定了在执行上述八种基本操作时，必须满足如下规则：

  1.   - 要把一个变量从主内存中复制到工作内存，就需要按顺寻地执行read和load操作， 如果把变量从工作内存中同步回主内存中，就要按顺序地执行store和write操作。但**Java内存模型**只**要求**上述操作必须按顺序执行，而**没有保证必须是连续执行**。
  2.   - 不允许read和load、store和write操作之一单独出现
  3.   - 不允许一个线程丢弃它的最近assign的操作，即变量在工作内存中改变了之后必须同步到主内存中。
  4.   - 不允许一个线程无原因地（没有发生过任何assign操作）把数据从工作内存同步回主内存中。
  5.   - 一个新的变量只能在主内存中诞生，不允许在工作内存中直接使用一个未被初始化（load或assign）的变量。即就是对一个变量实施use和store操作之前，必须先执行过了assign和load操作。
  6.   - 一个变量在同一时刻只允许一条线程对其进行lock操作，但lock操作可以被同一条线程重复执行多次，多次执行lock后，只有执行相同次数的unlock操作，变量才会被解锁。lock和unlock必须成对出现
  7.   - 如果对一个变量执行lock操作，将会清空工作内存中此变量的值，在执行引擎使用这个变量前需要重新执行load或assign操作初始化变量的值
  8.   - 如果一个变量事先没有被lock操作锁定，则不允许对它执行unlock操作；也不允许去unlock一个被其他线程锁定的变量。
  9.   - 对一个变量执行unlock操作之前，必须先把此变量同步到主内存中（执行store和write操作）。

Java内存模型与硬件内存架构的关系

Java内存模型与硬件内存架构之间存在差异
硬件内存架构：寄存器、缓存内存、主内存。（硬件设备，没有工作内存、主内存概念。对于硬件，所有的线程栈和堆都分布在主内存中）。
Java内存模型和计算机硬件内存架构是一个相互交叉的关系。抽象概念与真实物理硬件的交叉，多线程执行最终会映射到硬件处理器上，部分线程栈和堆可能有时候会出现在CPU缓存中和CPU内部的寄存器中
image.png

并发编程的可见性、原子性、有序性问题与解决方案

原子性

一个或多个操作是不可中断的，（即使是多线程环境下）要么全部执行且在执行过程中不被任何因素打断，要么全部不执行。
在 Java 中，对基本数据类型的变量的读取和赋值操作是原子性操作（64位处理器，32位系统，long、double读写不是原子）。
不采取任何的原子性保障措施的自增操作并不是原子性的。
例如：x=10是原子操作，而y=x；非原子操作，先读后赋值，两步操作
保证原子性方案：

  1.         - 使用锁。（synchronized 关键字、Lock）
  2.         - CAS保证原子性

可见性

当一个线程修改某个变量的值，其他线程可以立刻感知修改后值。串行程序不存在可见性，因为单线程。
Java内存模型是变量修改后将新值同步回主内存，其他线程从主内存读取最新新变量值，这种依赖主内存作为传递媒介的方法来实现可见性的。
问题：
由于工作内存，存储的是副本，当某个线程修改变量，重新赋值后，其他线程不一定立刻感知。
保证可见性方案：

  1.         - 通过 volatile 关键字保证可见性。（内存屏障）
  2.         - 通过 内存屏障保证可见性。
  3.         - 通过 synchronized 关键字保证可见性。（内存屏障）
  4.         - 通过 Lock保证可见性。（内存屏障）
  5.         - 通过 final 关键字保证可见性
  6.         - Thread.yield，可以引发**上下文切换**，上下文切换期间从主内存中重新读取数据，间接保证可见性

总结保证可见性根本方法：1.内存屏障。2.上下文切换
image.png

有序性

对于单线程代码，代码执行时按顺序依次执行的，多线程情况下，因为【编译器\CPU]】指令重排可能出现乱序
指令重排发生阶段
1.jvm执行编译阶段（将字节码转化为汇编语言）
2.cpu执行时，可能也会进行指令重排。
保证有序性方案

  1.         - 通过volatile 关键字保证可见性。（内存屏障）
  2.         - 通过内存屏障证可见性。
  3.         - 通过synchronized关键字保证有序性。（内存屏障）
  4.         - 通过 Lock保证有序性。（内存屏障）

指令重排

Java语言规范规定JVM线程内部维持顺序化语义。即只要程序的最终结果与它顺序化情况的结果相等，那么指令的执行顺序可以与代码顺序不一致，此过程叫指令的重排序。
指令重排序的意义：JVM能根据处理器特性（CPU多级缓存系统、多核处理器等）适当的对机器指令进行重排序，使机器指令能更符合CPU的执行特性，最大限度的发挥机器性能。
在编译器与CPU处理器中都能执行指令重排优化操作
image.png
volatile重排序规则
image.png
volatile禁止重排序场景：

  1.   1. 第一个操作是**volatile读**，不管第二个操作是什么都不会重排序
  2.   1. 第一个操作是volatile写，第二个操作是volatile读，也不会发生重排序
  3.   1. 第二个操作是**volatile写**，不管第一个操作是什么都不会重排序

JMM内存屏障插入策略

  1. 在每个volatile写操作的前面插入一个StoreStore屏障
    2. 在每个volatile写操作的后面插入一个StoreLoad屏障
    3. 在每个volatile读操作的后面插入一个LoadLoad屏障
    4. 在每个volatile读操作的后面插入一个LoadStore屏障
    image.png

JVM层面的内存屏障

在JSR规范中定义了4种内存屏障：
LoadLoad屏障：（指令Load1; LoadLoad; Load2），在Load2及后续读取操作要读取的数据被访问前，保证Load1要读取的数据被读取完毕。
LoadStore屏障：（指令Load1; LoadStore; Store2），在Store2及后续写入操作被刷出前，保证Load1要读取的数据被读取完毕。
StoreStore屏障：（指令Store1; StoreStore; Store2），在Store2及后续写入操作执行前，保证Store1的写入操作对其它处理器可见。
StoreLoad屏障：（指令Store1; StoreLoad; Load2），在Load2及后续所有读取操作执行前，保证Store1的写入对所有处理器可见。它的开销是四种屏障中最大的。在大多数处理器的实现中，这个屏障是个万能屏障，兼具其它三种内存屏障的功能
由于x86只有store load可能会重排序，所以只有JSR的StoreLoad屏障对应它的mfence或lock前缀指令，其他屏障对应空操作

硬件层内存屏障

硬件层提供了一系列的内存屏障 memory barrier / memory fence(Intel的提法)来提供一致性的能力。拿X86平台来说，有几种主要的内存屏障：
1. lfence，是一种Load Barrier 读屏障
2. sfence, 是一种Store Barrier 写屏障
3. mfence, 是一种全能型的屏障，具备lfence和sfence的能力
4. Lock前缀，Lock不是一种内存屏障，但是它能完成类似内存屏障的功能。Lock会对CPU总线和高速缓存加锁，可以理解为CPU指令级的一种锁。它后面可以跟ADD, ADC, AND, BTC, BTR, BTS, CMPXCHG, CMPXCH8B, DEC, INC, NEG, NOT, OR, SBB, SUB, XOR, XADD, and XCHG等指令。
内存屏障有两个能力：
1. 阻止屏障两边的指令重排序
2. 刷新处理器缓存/冲刷处理器缓存
对Load Barrier来说，在读指令前插入读屏障，可以让高速缓存中的数据失效，重新从主内存加载数据；对Store Barrier来说，在写指令之后插入写屏障，能让写入缓存的最新数据写回到主内存。
Lock前缀实现了类似的能力，它先对总线和缓存加锁，然后执行后面的指令，最后释放锁后会把高速缓存中的数据刷新回主内存。在Lock锁住总线的时候，其他CPU的读写请求都会被阻塞，直到锁释放。
不同硬件实现内存屏障的方式不同，Java内存模型屏蔽了这种底层硬件平台的差异，由JVM来为不同的平台生成相应的机器码。

二、volatile关键字

java中作用

volatile是Java虚拟机提供的轻量级的同步机制。底层依赖于缓存一致性 协议。大量使用会导致总线风暴
两个作用（无法保证原子性）
1.可见性：保证被volatile修饰的共享变量对所有线程总是可见的，即当某线程修改volatile修饰的变量，新值总是可以被其他线程立即得知（其他线程工作内存中的值失效）

  1.      - 当写一个volatile变量时，JMM会把该线程对应的本地内存中的共享变量值刷新到主内存。
  2.      - 当读一个volatile变量时，JMM会把该线程对应的本地内存置为无效，线程接下来将从主内存中读取共享变量。

2.有序性：禁止指令重排（通过添加内存屏障）
JSR-133专家组决定增强volatile的内存语义：严格限制编译器和处理器对volatile变量与普通变量的重排序，确保volatile的写-读和锁的释放-获取具有相同的内存语义。
内存屏障，又称内存栅栏，是一个CPU指令，它的作用有两个，
一、是保证特定操作的执行顺序，
二、是保证某些变量的内存可见性

volatile可见性实现原理

JMM内存交互层面实现
volatile修饰的变量的read、load、use操作和assign、store、write必须是连续（未使用volatile修饰，仅保证顺序执行，不要求连续）的，连续意味着：修改后必须立即同步回主内存，使用时必须从主内存刷新，由此保证volatile变量操作对多线程的可见性。
硬件层面实现
通过lock前缀指令，会锁定变量缓存行区域并写回主内存，这个操作称为“缓存锁定”，缓存一致性机制会阻止同时修改被两个以上处理器缓存的内存区域数据。一个处理器的缓存回写到内存会导致其他处理器的缓存无效。

三、缓存一致性

CPU两个局部性原理

时间局部性（Temporal Locality）
如果一个信息项正在被访问，那么在近期它很可能还会被再次访问。比如循环、递归、方法的反复调用等。
空间局部性（Spatial Locality）
如果一个存储器的位置被引用，那么将来他附近的位置也会被引用。比如顺序执行的代码、连续创建的两个对象、数组等

一致性目标

在共享内存多处理器系统中，每个处理器都有一个单独的缓存内存，共享数据可能有多个副本。一个副本在主内存中，一个副本在请求它的每个处理器的本地缓存中。
当数据的一个副本发生更改时，其他副本必须反映该更改。缓存一致性是确保共享操作数(数据)值的变化能够及时地在整个系统中传播的规程。
如下结果：
27431.gif

缓存一致性的要求

写传播（Write Propagation）

对任何缓存中的数据的更改都必须传播到对等缓存中的其他副本(该缓存行的副本)。

事务串行化（Transaction Serialization）

对单个内存位置的读/写必须被所有处理器以相同的顺序看到。理论上，一致性可以在加载/存储粒度上执行。然而，在实践中，它通常在缓存块的粒度上执行。

一致性机制（Coherence mechanisms）

确保一致性的两种最常见的机制是窥探机制（snooping ）和基于目录的机制（directory-based），这两种机制各有优缺点。
窥探机制
如果有足够的带宽可用，基于协议的窥探往往会更快，因为所有事务都是所有处理器看到的请求/响应。
缺点是窥探是不可扩展的。每个请求都必须广播到系统中的所有节点，这意味着随着系统变大，(逻辑或物理)总线的大小及其提供的带宽也必须增加。
基于目录的机制
目录往往有更长的延迟(3跳 请求/转发/响应)，但使用更少的带宽，因为消息是点对点的，而不是广播的。由于这个原因，许多较大的系统(>64处理器)使用基于目录机制的缓存一致性。

总线仲裁机制

总线事务（Bus Transaction）
计算机中，数据通过总线在处理器和内存之间传递，处理器和内存之间传递数据发生的一系列步骤
总线事务包括读事务（Read Transaction）和写事务（WriteTransaction）。
读事务从内存传送数据到处理器，写事务从处理器传送数据到内存，每个事务会读/写内存中一个或多个物理上连续的字。这里的关键是，总线会同步试图并发使用总线的事务。在一个处理器执行总线事务期间，总线会禁止其他的处理器和I/O设备执行内存的读/写。
image.png
场景一
假设处理器A，B和C同时向总线发起总线事务，总线会对竞争做出裁决，假设处理器A在竞争中获胜（总线仲裁会确保所有处理器都能公平的访问内存）。则A继续它的总线事务，B、C等待处理器A的总线事务完成后才能再次执行内存访问。
场景二
假设在处理器A执行总线事务期间（不管这个总线事务是读事务还是写事务），处理器D向总线发起了总线事务，此时处理器D的请求会被总线禁止。

把所有处理器对内存的访问以串行化的方式来执行。在任意时间点，最多只能有一个处理器可以访问内存。这个特性确保了单个总线事务之中的内存读/写操作具有原子性。

总线锁定

就是使用处理器提供的一个 LOCK＃信号，当其中一个处理器在总线上输出此信号时，其它处理器的请求将被阻塞住，那么该处理器可以独占共享内存。

缓存锁定

总线锁定，粒度比较大、开销较大。因为阻止了被阻塞处理器和所有内存之间的通信，而输出LOCK#信号的CPU可能只需要锁住特定的一块内存区域。
为减小锁定的颗粒度，引入缓存锁定，指内存区域如果被缓存在处理器的缓存行中，并且在Lock操作期间被锁定，那么当它执行锁操作回写到内存时，处理器不会发出总线锁定信号（即：声言LOCK＃信号），而是修改内部的内存地址，并允许它的缓存一致性机制来保证操作的原子性，因为缓存一致性机制会阻止同时修改由两个以上处理器缓存的内存区域数据，当其他处理器回写已被锁定的缓存行的数据时，会使缓存行无效。

缓存锁定不能使用的特殊情况：

  1.      - 当操作的数据不能被缓存在处理器内部，或操作的数据跨多个缓存行时，则处理器会调用总线锁定。
  2.      - 有些处理器不支持缓存锁定。

总线窥探(Bus Snooping)

总线窥探(Bus snooping)是缓存中的一致性控制器(snoopy cache)监视或窥探总线事务的一种方案，其目标是在分布式共享内存系统中维护缓存一致性。包含一致性控制器(snooper)的缓存称为snoopy缓存。该方案由Ravishankar和Goodman于1983年提出。

工作原理

当特定数据被多个缓存共享时，处理器修改共享数据的值，更改必须传播到所有具有该数据副本的缓存中。这种更改传播可以防止系统违反缓存一致性。数据变更的通知可以通过总线窥探来完成。所有的窥探者都在监视总线上的每一个事务。如果一个修改共享缓存块的事务出现在总线上，所有的窥探者都会检查他们的缓存是否有共享块的相同副本。如果缓存中有共享块的副本，则相应的窥探者执行一个动作以确保缓存一致性。这个动作可以是刷新缓存块或使缓存块失效。它还涉及到缓存块状态的改变，这取决于缓存一致性协议（cache coherence protocol）。

窥探协议类型

根据管理写操作的本地副本的方式，有两种窥探协议:
Write-invalidate
当处理器写入一个共享缓存块时，其他缓存中的所有共享副本都会通过总线窥探失效。确保处理器只能读写一个数据的一个副本。其他缓存中的所有其他副本都无效。这是最常用的窥探协议。MSI、MESI、MOSI、MOESI和MESIF协议属于该类型。

Write-update
当处理器写入一个共享缓存块时，其他缓存中的所有共享副本都会通过总线窥探更新。将写数据广播到总线上的所有缓存中。它比write-invalidate协议引起更大的总线流量。这就是为什么这种方法不常见。Dragon和firefly协议属于此类别

四、一致性协议（Coherence protocol）

  • MSI protocol, the basic protocol from which the MESI protocol is derived.
  • Write-once (cache coherency), an early form of the MESI protocol.
  • MESI protocol
  • MOSI protocol
  • MOESI protocol
  • MESIF protocol
  • MERSI protocol
  • Dragon protocol
  • Firefly protocol

    MESI协议

    一个基于写失效的缓存一致性协议，是支持回写（write-back）缓存的最常用协议。
    MESI协议要求在缓存不命中且数据块在另一个缓存时，允许缓存到缓存的数据复制。与MSI协议相比，MESI协议减少了主存的事务数量。这极大改善了性能。
    缓存行有4种不同的状态:
    已修改Modified (M)
    缓存行是脏的（dirty），与主存的值不同。如果别的CPU内核要读主存这块数据，该缓存行必须回写到主存，状态变为共享(S).
    独占Exclusive (E)
    缓存行只在当前缓存中，但是干净的—缓存数据同于主存数据。当别的缓存读取它时，状态变为共享；当前写数据时，变为已修改状态。
    共享Shared (S)
    缓存行也存在于其它缓存中且是未修改的。缓存行可以在任意时刻抛弃。
    无效Invalid (I)
    缓存行是无效的
    Cache Line大小是64Byte
    image.png
    引入MESI缓存一致性协议
    多核CPU的情况下有多个一级缓存，为保证缓存内部数据的一致,不让系统数据混乱，

缓存一致性协议，通过锁定缓存行保证数据一致性。当多个cpu对同一变量进行同时锁定时，通过总线对另外cpu发送信号，总线进行裁决，决定那个cpu数据失效。
当变量所占空间，大于一个缓存行大小时，缓存一致性协议，无法保证缓存一致时。会升级为总线锁。

总线风暴

大量使用volatile和cas使用。
volatile将导致各个工作内存在总线进行嗅探。
cas导致工作内存和主内存进行比较