JAVA-并发编程（一）

sschrodinger

2018/11/28

引用

《Java 并发编程的艺术》 方腾飞，魏鹏，程晓明 著

JSR-133 标准

内存模型

JVM 内存结构

Java 虚拟机定义了在程序执行期间使用的各种运行时数据区域。其中一些数据区域是在 Java 虚拟机启动时创建的，仅在 Java 虚拟机退出时销毁。其他数据区域是每个线程。线程数据区域是在线程退出时创建和销毁线程时创建的。

下图展示了 JVM 运行时的内存结构。

Java 内存模型

note

• 每个Java虚拟机线程都有自己的 pc（程序计数器）寄存器。如果执行的方法不是 native，则 pc 寄存器包含当前正在执行的 Java 虚拟机指令的地址。如果线程当前正在执行 native 方法，则 Java 虚拟机 pc 寄存器的值未定义。
• 每个 Java 虚拟机线程都有一个私有 Java 虚拟机堆栈，与线程同时创建。Java 虚拟机堆栈存储帧。除了推送和弹出帧之外，永远不会直接操作 Java 虚拟机堆栈，因此可以对堆进行堆分配。Java 虚拟机堆栈的内存不需要是连续的。
• Java 虚拟机具有在所有 Java 虚拟机线程之间共享的堆。堆是运行时数据区，从中分配所有类实例和数组的内存。
• Java 虚拟机具有在所有 Java 虚拟机线程之间共享的方法区域。方法区域类似于传统语言的编译代码的存储区域或类似于操作系统进程中的“文本”段。它存储每类结构，例如运行时常量池，字段和方法数据，以及方法和构造函数的代码，包括类和实例初始化以及接口初始化中使用的特殊方法。
• 除了以上介绍的JVM运行时内存外，还有一块内存区域可供使用，那就是直接内存。Java虚拟机规范并没有定义这块内存区域，所以他并不由JVM管理，是利用本地方法库直接在堆外申请的内存区域。

Java 内存模型 (JMM)

Java 内存模型是一组虚拟的规定，用于屏蔽掉各种硬件和操作系统的内存访问差异，以实现让 Java 程序在各种平台下都能达到一致的并发效果。

JMM 模型中，将内存抽象成了共享内存和工作内存，每个线程有自己对应的工作内存，线程对变量的修改是在工作内存中，其他线程对这个修改不可见，如下图。

JMM 模型

在多线程程序中，为保证数据的安全，必须满足三条基本的规律：

1. 原子性：在一个操作中就是cpu不可以在中途暂停然后再调度，既不被中断操作，要不执行完成，要不就不执行。
2. 可见性：当多个线程访问同一个变量时，一个线程修改了这个变量的值，其他线程能够立即看得到修改的值。
3. 有序性：程序执行的顺序按照代码的先后顺序执行。

为了保证共享内存的正确性（可见性、有序性、原子性），内存模型定义了共享内存系统中多线程程序读写操作行为的规范。通过这些规则来规范对内存的读写操作，从而保证指令执行的正确性。它与处理器有关、与缓存有关、与并发有关、与编译器也有关。他解决了 CPU 多级缓存、处理器优化、指令重排等导致的内存访问问题，保证了并发场景下的一致性、原子性和有序性。

内存模型解决并发问题主要采用两种方式：限制处理器优化和使用内存屏障。

Java 对象模型

Java是一种面向对象的语言，而 Java 对象在 JVM 中的存储也是有一定的结构的。而这个关于 Java 对象自身的存储模型称之为 Java 对象模型。

HotSpot 虚拟机中，设计了一个 OOP-Klass Model。OOP（Ordinary Object Pointer）指的是普通对象指针，而 Klass 用来描述对象实例的具体类型。

每一个 Java 类，在被 JVM 加载的时候，JVM 会给这个类创建一个 instanceKlass，保存在方法区，用来在 JVM 层表示该 Java 类。当我们在 Java 代码中，使用 new 创建一个对象的时候，JVM 会创建一个 instanceOopDesc 对象，这个对象中包含了对象头以及实例数据。

实例如下所示。

Java 对象模型（HotSpot）

happens-before 原则

JSR-133 标准使用 happens-before 来描述操作之间的内存可见性。

如果一个操作的执行结果需要对另外一个结果可见，那么这两个操作之间必然存在 happens-before 关系。

如下一段单线程代码：

int a = 0;      // line 1
a = 10;         // line 2
printf("%d",a); // line 3

程序逻辑上必须满足 printf() 函数必须在 a = 10; 语句之后运行，那么我们可以说 line 2 happens-before line 3，即第二行必须在第三行之前运行。

happens-before 原则满足传递性，如果 A happens-before B，且 B happens-before C，那么 A happens-before C。

对于共享一个内存的机器，实现 happens-before 只需要禁止处理器的重排序就行，但是对于使用多个内存的机器来说，则需要保证内存的一致性，才能保证 happens-before 的正确执行。

在 JMM 中，定义了六种 happens-before 规则

1. 程序顺序规则：一个线程中的每个操作，happens-before 于该线程中的任意后续操作
2. 监视器锁规则：对一个线程的解锁，happens-before 于随后对这个锁的加锁
3. volatile 规则：对一个 volatile 变量的写，happens-before 于任意后续对这个 volatile 变量的读
4. 传递性：如果 A happens-before B，且 B happens-before C，那么 A happens-before C
5. start() 规则：如果线程 A 执行操作 ThreadB.start()，那么线程 A 的 ThreadB.start() 操作 happens-before 于线程 B 的任意操作
6. join() 规则：如果线程 A 执行操作 ThreadB.join() 并成功返回，那么于线程 B 的任意操作 happens-before 于线程 A 从 ThreadB.join() 成功返回

happens-before 实现原理

Java 在底层使用内存一致性协议保证变量对每一个 CPU 缓存可见。

在 X86 处理器上，使用 Lock 汇编指令前缀保证内存一致性。对于一个需要在所有工作线程可见的变量 singleton，每一个对该 singleton 进行修改的操作，如 singleton++，会增加 Lock指令。汇编指令如下：

0x01a3de1d:moveb $0X0,0x1104800(%esi);
0x01a3de24:lock add1 $0x0,(%esp);

该汇编指令前缀在多核处理器下引发两件事情：

1. 将当前处理器缓存的值写回到系统内存
2. 这个写回内存的操作会使其他 CPU 缓存中该内存地址失效，如果其他线程需要该数据，必须重新读取

happens-before 的实现利用内存屏障，而内存屏障在底层就是使用内存一致性完成的。

在 java 中，总共有4种类型的屏障，如下表所示：

这四个屏障都是相对于JMM模型来说的：Store指的是将数据从工作内存刷新到共享内存，Load指的是从共享内存中加载数据到主内存。

volatile 关键字

volatile 内存语义

volatile 变量有两个特性，一个是可见性，一个是原子性。

volatile

我们观察如上的多线程程序，根据程序顺序规则、volatile 规则和传递规则，我们可以看出，volatile 关键字不仅仅保证 volatile 变量的 happens-before 原则，同时还保证了 volatile 写之前的任意变量一定 happens-before volatile 读之后的任意变量读写。

以如下Demo为例：

public class Demo {
    
    public static void main(String[] args) throws InterruptedException {
        A a = new A();
        Thread thread = new Thread(a);
        thread.start();
        Thread.currentThread().sleep(1000);
        //a.a = false;
        a.a = false;
    }
}

class A implements Runnable {
    public volatile boolean a = true;
    public A() {}
    @Override public void run() {
        while (a);
        System.out.println("ok");
    }
    
}

当写一个 volatile 变量时，JMM 会把该线程对应的工作内存中的共享变量刷新到共享内存。这时，由语句a.a = false;会引发如下的情况。

graph LR
线程A-->工作内存a.a=false
工作内存a.a=false-->线程A
工作内存a.a=false-->主内存a.a=false
线程B-->工作内存a.a=true
工作内存a.a=true-->线程B

当读一个 volatile 变量时，JMM 会把该线程对应的工作内存中的共享变量置为无效，重新从共享内存中读取。这时，由语句while (a);会引发如下的情况。

graph LR
线程A-->工作内存a.a=false
工作内存a.a=false-->线程A
工作内存a.a=true-->线程B
线程B-->工作内存a.a=true
主内存a.a=true-->工作内存a.a=true

如果把 volatile 写和 volatile 读 两个步骤综合起来看的话，线程B读一个 volatile 变量后，线程 A 在写这个 volatile 变量之前所有可见的共享变量的值都将立即变得对读线程 B 可见。

volatile 内存语义实现

根据 volatile 的 happens-before 关系，JMM 会要求一定的重排序规则：

<table>
<tr>
<td>是否能重排序</td>
<td colspan="2">第二个操作数</td>
</tr>
<tr>
<td>第一个操作数</td>
<td>普通读/写</td>
<td>volatile 读</td>
<td>volatile 写</td>
</tr>
<tr>
<td>普通读写</td>
<td></td>
<td></td>
<td>NO</td>
</tr>
<tr>
<td>volatile 读</td>
<td>NO</td>
<td>NO</td>
<td>NO</td>
</tr>
<tr>
<td>volatile 写</td>
<td></td>
<td>NO</td>
<td>NO</td>
</tr>
</table>

JMM 使用最保守的方式给这些操作加上内存屏障，如下：

• 在每个 volatile 写操作的前面插入一个 StoreStore 屏障
• 在每个 volatile 写操作的后面插入一个 StoreLoad 屏障
• 在每个 volatile 读操作的后面插入一个 LoadLoad 屏障
• 在每个 volatile 读操作的后面插入一个 LoadLoad 屏障

写读的内存屏障分别如下图：

volatile 读

volatile 写

在实际执行时，只要保证内存语义，可以适当调整内存屏障。

锁

锁在保证原子性的基础上，也实现了类似于volatile的内存语义，以实现线程的可见性原则，这个锁包括 concurrent 包中提供的各种锁和利用 synchronized 关键词修饰的临界区代码。（底层利用volatile实现，或者利用CAS实现）

锁的内存语义

同 volatile 的分析，2 一定要 happens-before 5，即 线程 A 执行的临界区代码对线程 B 执行的临界区代码一定可见。

当线程释放锁时，JMM 会把该线程对应的本地内存中的共享变量刷新到主内存中。

当线程获得锁时，JMM 或把该线程对应的本地变量置为无效，并重新从主内存读取。

锁内存语义的实现主要也是依赖于 volatile 变量。

锁的内存语义

1. 当线程释放锁时，JMM 会把该线程对应的本地内存中的共享变量刷新到共享内存中。
2. 当线程获取锁时，JMM 会把该线程对应的本地内存设置为无效，使得临界区代码必须从主内存中读取共享变量

如下两个实例代码和 Demo 代码实现了相同的功能。

public class Demo1 {
    
    public static void main(String[] args) throws InterruptedException {
        A a = new A();
        Thread thread = new Thread(a);
        thread.start();
        Thread.currentThread().sleep(1000);
        a.setA(false);
    }
}

class A implements Runnable {
    public boolean a = true;
    public A() {}
    public synchronized setA(boolean a) {this.a = a;}
    public synchronized getA() {return a;}
    @Override public void run() {
        while (getA());
        System.out.println("ok");
    }
    
}

public class Demo2 {
    
    public static void main(String[] args) throws InterruptedException {
        A a = new A();
        Thread thread = new Thread(a);
        thread.start();
        Thread.currentThread().sleep(1000);
        a.setA(false);
    }
}

class A implements Runnable {
    public boolean a = true;
    public A() {}
    public void setA(boolean a) {
        lock.lock();
        this.a = a;
        lock.unlock();
    }
    public boolean getA() {
        lock.lock();
        try {
            return a;
        } finally {
            lock.unlock();
        }
    }
    @Override public void run() {
        while (getA());
        System.out.println("ok");
    }
    
    public final Lock lock = new ReentrantLock();
    
}

final 关键字

基本类型的 final 域的重排序规则

对于一个 final 域，编译器和处理器需要遵守两个重排序规则：

1. 在构造函数内对一个 final 域的写入，与随后把这个被构造函数的引用赋值给一个引用变量，这两个操作之间不能够重排序。
2. 初次读一个包含 final 域的对象的引用，与随后初次读这个 final 域，这两个操作之间不能重排序。

通过 final 域的重排序规则，可以保证 final 域被正确的初始化。下面通过一个例子讲解为何这两个重排序规则可以保证 final 域的正确初始化。

public class FinalDemo {
    int i;
    final int j;
    
    static FinalDemo obj;
    
    public FinalDemo () {
        i = 1; j = 2;
    }
    
    public static void writer() {
        obj = new FinalDemo();
    }
    
    public static void reader() {
        FinalDemo object = obj;
        int a = object.i;
        int b = object.j;
    }
}

写 final 域的重排序规则禁止把 final 域的写重排序到构造函数之外，通过限制处理器优化和使用内存屏障来完成这个目的：

1. JMM禁止编译器把 final 域的写重排序到构造函数之外；
2. 编译器会在 final 域的写之后，构造函数 return 之前，插入一个 StoreStore 屏障。这个屏障禁止处理器把 final 域的写重排序到构造函数之外，同时使这个构造函数对变量的赋值对所有线程可见。

如上代码的writer()，初始化一个 FinalDemo 变量，然后赋值给 obj，这样可以保证 final 域一定能够在别人访问之前完成初始化。

读 final 域会在读 final 域之前插入一个LoadLoad屏障，强制要求将工作内存置为无效，并从共享线程中重新读取数据。保证读取的数据一定是正确初始化的。

引用类型的 final 域重排序规则

如下代码所示：

public class FinalDemo2 {

    final int[] intArray;
    
    static FinalDemo2 obj;
    
    public FinalDemo2 () {
       intArray = new int[1]; intArray[0] = 1;
    }
    
    //线程A
    public static void writerOne() {
        obj = new FinalDemo2();
    }
    
    //线程B
    public static void writerTwo() {
        obj.intArray[0] = 2;
    }
    
    //线程C
    public static void reader() {
        if (obj != null) int temp1 = obj.intArray[0];
    }
}

对于引用类型，写 final 域的重排序规则对编译器和处理器增加了如下约束：

1. 在构造函数内对一个 final 引用的对象的成员域的写入，与随后在构造函数外把这个被构造对象的引用赋值给一个引用变量，这两个操作之间不能重排序。

对以上实例来说，则是线程A一定对线程C可见，但是线程B却不一定对线程C可见。

final 语义可以保证只要是正确构造的（被构造函数没有“溢出”），那么不需要同步，就可以保证任意线程都能看到这个 final 域在构造函数中初始化过的值，可用于在不同的线程中传递不可变对象

原子操作的实现

内存屏障解决了内存可见性的问题，原子操作使用 CAS 保证原子性。

硬件的原子操作实现

处理器保证系统内存中读取或写入一个字节是原子的。当一个处理器读取一个字节时，其他处理器不能访问这个字节的内存地址。

奔腾 6 和最新的处理器能够自动保证但处理器对同一缓存行里进行 16/32/64 位的操作是原子的。

对于跨总线宽度、跨多个缓存行和跨页表的访问，一般使用总线锁或者通过缓存锁定来保证原子性。

总线锁定是指使用处理器提供的一个 LOCK# 信号，当一个处理器在总线上输出此信号时，其他处理器的请求将被阻塞。

对于缓存锁定，我们首先来看看缓存一致性协议。

缓存一致性协议（Cache Coherence Protocol），最出名的就是Intel 的MESI协议，MESI协议保证了每个缓存中使用的共享变量的副本是一致的。

MESI的核心的思想是：++当CPU写数据时，如果发现操作的变量是共享变量，即在其他CPU中也存在该变量的副本，会发出信号通知其他CPU将该变量的缓存行置为无效状态，因此当其他CPU需要读取这个变量时，发现自己缓存中缓存该变量的缓存行是无效的，那么它就会从内存重新读取++。

在MESI协议中，每个缓存可能有有4个状态，它们分别是：

• M(Modified)：这行数据有效，数据被修改了，和内存中的数据不一致，数据只存在于本Cache中。
• E(Exclusive)：这行数据有效，数据和内存中的数据一致，数据只存在于本Cache中。
• S(Shared)：这行数据有效，数据和内存中的数据一致，数据存在于很多Cache中。
• I(Invalid)：这行数据无效。

缓存锁定是指内存区域如果被缓存在处理器的缓存行中并且在Lock期间被锁定，那么当他执行锁操作写回到内存时，处理器不在总线上声言 Lock# 信号，而是修改内部的内存地址，并允许使用缓存一致性来保证操作的原子性。

补充

但是，值得注意的是，传统的MESI协议中有两个行为的执行成本比较大。

1. 将某个Cache Line标记为Invalid状态，
2. 当某Cache Line当前状态为Invalid时写入新的数据。

所以CPU通过Store Buffer和Invalidate Queue组件来降低这类操作的延时。

如图：

cache_sync

当一个CPU进行写入时，首先会给其它CPU发送Invalid消息，然后把当前写入的数据写入到Store Buffer中。然后异步在某个时刻真正的写入到Cache中。

当前CPU核如果要读Cache中的数据，需要先扫描Store Buffer之后再读取Cache。

但是此时其它CPU核是看不到当前核的Store Buffer中的数据的，要等到Store Buffer中的数据被刷到了Cache之后才会触发失效操作。

而当一个CPU核收到Invalid消息时，会把消息写入自身的Invalidate Queue中，随后异步将其设为Invalid状态。

和Store Buffer不同的是，当前CPU核心使用Cache时并不扫描Invalidate Queue部分，所以可能会有极短时间的脏读问题。

MESI协议，可以保证缓存的一致性，但是无法保证实时性。

Java 的原子操作实现

在 JAva 中，原子操作使用锁或者 CAS 来实现。

CAS 实现

我们可以把 CAS 当成一个乐观锁，即假设没有冲突，尝试进行操作，如果有冲突，继续尝试。

举一个简单的例子 AtomicInterger 类，我们知道 i++ 这种操作并不是原子性的，他分成了三步，如下图所示：

三步

当有两个线程同时进行 i++ 操作的时候，就有可能出现意想不到的结果。

CAS 的全称为 CompareAndSwap，即比较并交换，是原子操作的一种（在 x86 的机器上，利用硬件的操作指令 CMPXCHG 加上 LOCK 前缀实现）。++该操作通过将内存中的值与指定数据进行比较，当数值一样时将内存中的数据替换为新的值++。

对于 AtomicInterger 类的自加操作，我们可以看到如下代码：

// atomicInteger
public final int getAndIncrement() {
    return unsafe.getAndAddInt(this, valueOffset, 1);
}

// Unsafe
public final int getAndAddInt(Object var1, long var2, int var4) {
    int var5;
    do {
        var5 = this.getIntVolatile(var1, var2);
    } while(!this.compareAndSwapInt(var1, var2, var5, var5 + var4));

    return var5;
}

// Unsafe
public native int getIntVolatile(Object var1, long var2);

// Unsafe
public final native boolean compareAndSwapInt(Object var1, long var2, int var4, int var5);

对 native 函数简单解释

• getIntVolatile(Object var1, long var2) 指的是以 volatile 的方式获得 var1 这个类的 在 var2 偏移量的值，即获得的值一定是最新的。并且这个 var 偏移量代表的就是 AtomicInteger 的 value 值在类中的偏移量。
• compareAndSwapInt(Object var1, long var2, int var4, int var5) 指的是比较 var1 这个类的 var2 偏移量的值和 var5 是否相等，如果相等，则将 var2 这个偏移量的值填成 var5 + var4，并返回 true，否则返回 false。即 compareAndSwapInt(obj, offset, expect, update)

具体到 compareAndSwapInt 函数的内部，他其实是用一个原子操作完成的，参见卡巴拉的树文章。

我们可以看到，CAS 使用自循环的方式尝试去更新自己的数据，我们可以举一个多线程的例子看看他的正确性。如下所示：

CAS

CAS 的三大问题：

1. ABA 问题
2. 循环时间开销长
3. 只能保证一个共享变量的原子操作

双重检查锁定域延迟初始化