java 内存模型之重排序

java 内存模型之重排序

happens-before

在 JMM 中，如果一个操作执行的结果需要对另一个操作可见，那么这两个操作之间必须要存在 happens-before 关系。这里提到的两个操作既可以是在一个线程之

内，也可以是在不同线程之间。

• 程序顺序规则：一个线程中的每个操作，happens-before 于该线程中的任意后续操作。

• 监视器锁规则：对一个锁的解锁，happens-before 于随后对这个锁的加锁。

• volatile 变量规则：对一个 volatile 域的写，happens-before 于任意后续对这个 volatile 域的读。

• 传递性：如果 A happens-before B，且 B happens-before C，那么 A happens-before C。

两个操作之间具有 happens-before 关系，并不意味着前一个操作必须要在后一个操作之前执行！happens-before 仅仅要求前一个操作（执行的结果）对后一个操作

可见，且前一个操作按顺序排在第二个操作之前（the first is visible to and ordered before the second）。

重排序

as-if-serial 语义

as-if-serial 语义的意思是：不管怎么重排序（编译器和处理器为了提高并行度），（单线程）程序的执行结果不能被改变。编译器、runtime 和处理器都必须遵守 as-if-serial 语义。

重排序对多线程的影响

public class ReorderExample {    int a = 0;    volatile boolean flag = false;    public void writer() {        a = 2; // 1    }    public void reader() {        if (flag) { // 3            int i = a * a; // 4            System.out.println(i);        }    }
}

假设有两个线程 A 和 B，A 首先执行 writer()方法，随后 B 线程接着执行 reader()方法。线程 B 在执行操作 4 时，能否看到线程 A 在操作 1 对共享变量 a 的写入呢？

答案是：不一定能看到。

操作 1 和操作 2 做了重排序。程序执行时，线程 A 首先写标记变量 flag，随后线程 B 读这个变量。由于条件判断为真，线程 B 将读取变量 a。此时，变量 a 还没有被线程 A 写入，在这里多线程程序的语义被重排序破坏了！

操作 3 和操作 4 存在控制依赖关系。当代码中存在控制依赖性时，会影响指令序列执行的并行度。为此，编译器和处理器会采用猜测（Speculation）执行来克服控制相关性对并行度的影响。以处理器的猜测执行为例，执行线程 B 的处理器可以提前读取并计算 a*a，然后把计算结果临时保存到一个名为重排序缓冲（Reorder Buffer，ROB）的硬件缓存中。当操作 3 的条件判断为真时，就把该计算结果写入变量 i 中。

对操作 3 和 4 做了重排序。重排序在这里破坏了多线程程序的语义！

在单线程程序中，对存在控制依赖的操作重排序，不会改变执行结果（这也是 as-if-serial 语义允许对存在控制依赖的操作做重排序的原因）；但在多线程程序中，对存在控制依赖的操作重排序，可能会改变程序的执行结果

volatile

volatile 写-读建立的 happens-before 关系

public class VolatileExample {    int a = 0;    volatile boolean flag = false;    public void writer() {        a = 1; // 1        flag = true; // 2    }    public void reader() {        if (flag) { // 3            int i = a; // 4        }    }}

假设线程 A 执行 writer()方法之后，线程 B 执行 reader()方法。根据 happens-before 规则，这个过程建立的 happens-before 关系可以分为 3 类：1）根据程序次序规则，1 happens-before 2;3 happens-before 4。2）根据 volatile 规则，2 happens-before 3。3）根据 happens-before 的传递性规则，1 happens-before 4。

volatile 写-读的内存语义

volatile 写的内存语义：当写一个 volatile 变量时，JMM 会把该线程对应的本地内存中的共享变量值刷新到主内存。

volatile 读的内存语义如下：当读一个 volatile 变量时，JMM 会把该线程对应的本地内存置为无效。线程接下来将从主内存中读取共享变量。

线程 A 写一个 volatile 变量，实质上是线程 A 向接下来将要读这个 volatile 变量的某个线程发出了（其对共享变量所做修改的）消息。

线程 B 读一个 volatile 变量，实质上是线程 B 接收了之前某个线程发出的（在写这个 volatile 变量之前对共享变量所做修改的）消息。

线程 A 写一个 volatile 变量，随后线程 B 读这个 volatile 变量，这个过程实质上是线程 A 通过主内存向线程 B 发送消息。

基于保守策略的 JMM 内存屏障插入策略：

• 在每个 volatile 写操作的前面插入一个 StoreStore 屏障。

• 在每个 volatile 写操作的后面插入一个 StoreLoad 屏障。

• 在每个 volatile 读操作的后面插入一个 LoadLoad 屏障。

• 在每个 volatile 读操作的后面插入一个 LoadStore 屏障。

public class VolatileBarrierExample {    int a;    volatile int v1 = 1;    volatile int v2 = 2;    void readAndWrite() {        int i = v1; // 第一个volatile读        int j = v2; // 第二个volatile读        a = i + j; // 普通写        v1 = i + 1; // 第一个volatile写        v2 = j * 2; // 第二个 volatile写    }}

线程 A 释放一个锁，实质上是线程 A 向接下来将要获取这个锁的某个线程发出了（线程 A 对共享变量所做修改的）消息。线程 B 获取一个锁，实质上是线程 B 接收了之前某个线程发出的（在释放这个锁之前对共享变量所做修改的）消息。

线程 A 释放锁，随后线程 B 获取这个锁，这个过程实质上是线程 A 通过主内存向线程 B 发送消息。

ReentrantLock 分为公平锁和非公平锁，我们首先分析公平锁

使用公平锁时，加锁方法 lock()调用轨迹如下。

1）ReentrantLock:lock()。

2）FairSync:lock()。

3）AbstractQueuedSynchronizer:acquire(int arg)。

4）ReentrantLock:tryAcquire(int acquires)。

private volatile int state;
protected final boolean tryAcquire(int acquires) {    final Thread current = Thread.currentThread();    int c = getState();    if (c == 0) {        if (!hasQueuedPredecessors() &&            compareAndSetState(0, acquires)) {            setExclusiveOwnerThread(current);            return true;        }    }    else if (current == getExclusiveOwnerThread()) {        int nextc = c + acquires;        if (nextc < 0)            throw new Error("Maximum lock count exceeded");        setState(nextc);        return true;    }    return false;}

从上面源代码中我们可以看出，加锁方法首先读 volatile 变量 state。

在使用公平锁时，解锁方法 unlock()调用轨迹如下。

1）ReentrantLock:unlock()。

2）AbstractQueuedSynchronizer:release(int arg)。

3）Sync:tryRelease(int releases)。

protected final boolean tryRelease(int releases) {    int c = getState() - releases;    if (Thread.currentThread() != getExclusiveOwnerThread())        throw new IllegalMonitorStateException();    boolean free = false;    if (c == 0) {        free = true;        setExclusiveOwnerThread(null);    }    setState(c);    return free;}

从上面的源代码可以看出，在释放锁的最后 setState 写 volatile 变量 state。

公平锁在释放锁的最后写 volatile 变量 state，在获取锁时首先读这个 volatile 变量。根据 volatile 的 happens-before 规则，释放锁的线程在写 volatile 变量之前可见的共享变量，在获取锁的线程读取同一个 volatile 变量后将立即变得对获取锁的线程可见。

非公平锁的释放和公平锁完全一样，所以这里仅仅分析非公平锁的获取。使用非公平锁时，加锁方法 lock()调用轨迹如下。

1）ReentrantLock:lock()。

2）NonfairSync:lock()。

3）AbstractQueuedSynchronizer:compareAndSetState(int expect,int update)。

/** * Sync object for non-fair locks */static final class NonfairSync extends Sync {    private static final long serialVersionUID = 7316153563782823691L;
    /**     * Performs lock.  Try immediate barge, backing up to normal     * acquire on failure.     */    final void lock() {        if (compareAndSetState(0, 1))            setExclusiveOwnerThread(Thread.currentThread());        else            acquire(1);    }
    protected final boolean tryAcquire(int acquires) {        return nonfairTryAcquire(acquires);    }}

protected final boolean compareAndSetState(int expect, int update) {    // See below for intrinsics setup to support this    return unsafe.compareAndSwapInt(this, stateOffset, expect, update);}

该方法以原子操作的方式更新 state 变量，Java 的 compareAndSet()方法调用简称为 CAS。JDK 文档对该方法的说明如下：如果当前状态值等于预期值，则以原子方式将同步状态设置为给定的更新值

cas 原理：如果程序是在多处理器上运行 就在指令加上 lock 前缀

lock 前缀作用：

1）确保对内存的读-改-写操作原子执行。在 Pentium 及 Pentium 之前的处理器中，带有 lock 前缀的指令在执行期间会锁住总线，使得其他处理器暂时无法通过总线访问内存。很显然，这会带来昂贵的开销。从 Pentium 4、Intel Xeon 及 P6 处理器开始，Intel 使用缓存锁定（Cache Locking）来保证指令执行的原子性。缓存锁定将大大降低 lock 前缀指令的执行开销。

2）禁止该指令，与之前和之后的读和写指令重排序。

3）把写缓冲区中的所有数据刷新到内存中。

所以 CAS 同时具有 volatile 读和 volatile 写的内存语义

总结：公平锁和非公平锁释放时，最后都要写一个 volatile 变量 state。

公平锁获取时，首先会去读 volatile 变量。

非公平锁获取时，首先会用 CAS 更新 volatile 变量，这个操作同时具有 volatile 读和 volatile 写的内存语义。

锁释放-获取的内存语义的实现至少有下面两种方式：

1）利用 volatile 变量的写-读所具有的内存语义。

2）利用 CAS 所附带的 volatile 读和 volatile 写的内存语义。

current 并发包

由于 Java 的 CAS 同时具有 volatile 读和 volatile 写的内存语义，因此 Java 线程之间的通信现在有了下面 4 种方式。1）A 线程写 volatile 变量，随后 B 线程读这个 volatile 变量。2）A 线程写 volatile 变量，随后 B 线程用 CAS 更新这个 volatile 变量。3）A 线程用 CAS 更新一个 volatile 变量，随后 B 线程用 CAS 更新这个 volatile 变量。4）A 线程用 CAS 更新一个 volatile 变量，随后 B 线程读这个 volatile 变量。

concurrent 包的源代码通用化的实现模式：

首先，声明共享变量为 volatile。

然后，使用 CAS 的原子条件更新来实现线程之间的同步。

同时，配合以 volatile 的读/写和 CAS 所具有的 volatile 读和写的内存语义来实现线程之间的通信。

AQS，非阻塞数据结构和原子变量类（java.util.concurrent.atomic 包中的类），这些 concurrent 包中的基础类都是使用这种模式来实现的，而 concurrent 包中的高层类又是依赖于这些基础类来实现的