happens-before 俗解

java concurrent

学习 Java 并发，到后面总会接触到 happens-before 偏序关系。初接触这玩意儿看它的描述真是不知所云，下面是经过一段时间折腾后个人的一点浅薄理解，希望对初接触的人有所帮助，如有不正确的地方，欢迎指正。

synchronized 关键字和大部分锁，众所周知的一个功能就是使多个线程互斥/串行地（共享锁允许多个线程同时访问，如读锁）访问临界区，但他们的第二个功能 —— 保证变量的可见性 —— 常被遗忘。

为什么存在可见性问题？相对于内存，CPU的速度是极高的，如果CPU存取数据时都直接和内存打交道，存取过程中CPU将一直空闲，这是极大的浪费，妈妈说，浪费是不好的，所以，现代的CPU里有很多寄存器，多级cache，他们比内存的存取速度高很多。某个线程执行时，内存中的一份数据，会存在于该线程的工作存储（working memory，cache 和寄存器的抽象。有不少人觉得 working memory 是内存的某个部分，这可能是有些译作将 working memory 译为工作内存的缘故，为避免混淆，这里称其为工作存储。每个线程都有自己的工作存储）中，并在某个特定时间点回写到内存。

Every thread is defined to have a working memory (an abstraction of caches and registers) in which to store values.
--- 《Concurrent Programming in Java: Design Principles and Patterns, Second Edition》§2.2.7

单线程时，这没有问题，如果是多线程要同时访问同一个变量呢？内存中一个变量会存在于多个工作存储中，线程1修改了变量 a 的值什么时候对线程2可见？此外，编译器或运行时为了效率可以在允许的时候对指令进行重排序，重排序后的执行顺序就与代码不一致了。虽然代码顺序上写操作在前读操作在后，但线程2读取某个变量的时候线程1可能还没有进行写入操作，这就是可见性问题的由来。

我们无法枚举所有的场景来规定某个线程修改的变量何时对另一个线程可见。但可以制定一些通用的规则，这就是 happens-before，它是一个偏序关系。
Java内存模型中定义了许多 Action，有些 Action 之间存在 happens-before 关系（并不是所有 Action 两两之间都有 happens-before 关系）。“ActionA happens-before ActionB”这样的描述很扰乱视线，是不是？OK，换个描述，如 果ActionA happens-before ActionB，我们可以记作 hb(ActionA,ActionB) 或者记作ActionA < ActionB，这货在这里已经不是小于号了，它是偏序关系，是不是隐约有些离散数学的味道，不喜欢？嗯，我也不喜欢，so，下面都用 hb(ActionA,ActionB) 这种方式来表述。

从 Java 内存模型中取两条 happens-before 关系来瞅瞅：

• An unlock on a monitor happens-before every subsequent lock on that monitor.
• A write to a volatile field happens-before every subsequent read of that volatile.

“一个 monitor 的解锁操作 happens-before 后续的加锁操作”，“一个 volatile 字段的写操作 happens-before 后续的读操作”，莫名其妙、不知所云、不能理解…… 是不是说解锁操作要先于锁定操作发生？这有违常规啊。
其实不是这么理解的，happens-before 规则不是描述实际操作的先后顺序，它是用来描述可见性的一种规则，下面我给上述两条规则换个说法：

• 如果线程 t1 解锁了 monitor a，接着有线程 t2 锁定了 a，那么 t1 解锁 a 之前的写对 t2 可见（线程1和线程2可以是同一个线程）。
• 如果线程 t1 对 volatile 变量 v（这里和后续的“变量”指的是对象字段、类字段和数组元素）进行了写，接着有线程 t2 读取了 v，那么 t1 对 v 的写及之前的写对 t2 可见（线程1和线程2可以是同一个线程）。

是不是很简单，瞬间觉得这篇文章弱爆了，说了那么多，其实就是在说“如果 hb(a,b)，那么线程 t1 进行了 a 操作，该操作及之前的写操作在接下来的线程 t2 进行 b 操作时可见（同一个线程不会有可见性问题，下面就不再重复了）”。虽然弱爆了，但还得有始有终，是不？接下来，再看两条 happens-before 规则：

• All actions in a thread happen-before any other thread successfully returns from a join() on that thread.
• Each action in a thread happens-before every subsequent action in that thread.

通俗版：

• 线程 t1 写入的所有变量（所有 action 都与那个 join 有 hb 关系，当然也包括线程 t1 终止前的最后一个 action 了，最后一个 action 及之前的所有写入操作，所以是所有变量），在任意其它线程 t2 调用 t1.join() 成功返回后，都对 t2 可见。

• 线程中上一个动作及之前的所有写操作在该线程执行下一个动作时对该线程可见（也就是说，同一个线程中前面的所有写操作对后面的操作可见）

大致都是这个样子的解释。

happens-before 关系有个很重要的性质，就是传递性，即：如果hb(a,b), hb(b,c)，则有hb(a,c)。

Java 内存模型中只是列出了几种比较基本的 hb 规则，在 Java 语言层面，又衍生了许多其他 happens-before 规则，如 ReentrantLock 的 unlock 与 lock 操作，又如 AbstractQueuedSynchronizer 的 release 与 acquire，setState 与 getState 等等。

接下来用 hb 规则分析两个实际的可见性例子。

看个 CopyOnWriteArrayList 的例子，代码中的 list 对象是 CopyOnWriteArrayList 类型，a 是个静态变量，初始值为 0
假设有以下代码与执行线程：

线程1

a = 1;
list.set(1,"t");

线程2

list.get(0);
int b = a;

那么，线程2中 b 的值会是 1 吗？
分析下，假设执行轨迹为以下所示：

线程1                 线程2
p1:a = 1            
p2:list.set(1,"t")      
                     p3:list.get(2)
                     p4:int b = a;

p1,p2 是线程 1 中的，p3,p4 是同线程 2 中的，所以有 hb(p1,p2), hb(p3,p4)，要使得 p1 中的赋值操作对 p4 可见，那么只需要有 hb(p1,p4)，前面说过，hb关系具有传递性，那么若有 hb(p2,p3) 就能得到 hb(p1,p4)，p2,p3是不是存在 hb 关系？翻翻 java api，发现有如下描述:

Actions in a thread prior to placing an object into any concurrent collection happen-before actions subsequent to the access or removal of that element from the collection in another thread.

p2 是放入一个元素到并发集合中，p3 是从并发集合中取，符合上述描述，因此有 hb(p2,p3)。也就是说，在上面假设的执行轨迹下，可以保证线程 2 中 b 的值是 1。如果是下面的执行轨迹呢？

线程1                 线程2
p1:a = 1                
                     p3:list.get(2)
p2:list.set(1,"t")              
                     p4:int b = a;

依然有 hb(p1,p2)，hb(p3,p4)，但是没有了 hb(p2,p3)，得不到 hb(p1,p4)，虽然线程 1 给 a 赋值操作在执行顺序上是先于线程 2 读取 a 的，但 jvm 不保证最后 b 的值是 1。这不是说一定不是 1，只是不能保证。如果程序里没有采取手段（如加锁等）排除类似这样的执行轨迹，那么是无法保证 b 取到 1 的。像这样的程序，就是没有正确同步的，存在着数据争用（data race）。

既然提到了 CopyOnWriteArrayList，那么顺便看下其 set 实现吧：

public E set(int index, E element) {
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
            Object[] elements = getArray();
            Object oldValue = elements[index];
        if (oldValue != element) {
            int len = elements.length;
            Object[] newElements = Arrays.copyOf(elements, len);
            newElements[index] = element;
            setArray(newElements);
        } else {
            // Not quite a no-op; ensures volatile write semantics
            setArray(elements);
        }
        return (E)oldValue;
    } finally {
        lock.unlock();
    }
}

有意思的地方是 else 里的 setArray(elements) 调用，看看 setArray 做了什么：

final void setArray(Object[] a) {
    array = a;
}

一个简单的赋值，array是 volatile 类型。elements 是从 getArray() 方法取过来的，getArray() 实现如下：

final Object[] getArray() {
    return array;
}

也很简单，直接返回 array。取得 array，又重新赋值给array，有甚意义？setArray(elements) 上有条简单的注释，但可能不太容易理解。正如前文提到的那条 javadoc 上的规定，放入一个元素到并发集合与从并发集合中取元素之间要有 hb 关系。set 是放入，get 是取（取还有其他方法），怎么才能使得 set 与 get 之间有 hb 关系，set 方法的最后有 unlock 操作，如果 get 里有对这个锁的 lock 操作，那么就好满足了，但是 get 并没有加锁：

public E get(int index) {
    return (E)(getArray()[index]);
}

但是 get 里调用了 getArray，getArray 里有读 volatile 的操作，只需要 set 走任意代码路径都能遇到写 volatile 操作就能满足条件了，这里主要就是 if…else… 分支，if 里有个 setArray 操作，如果只是从单线程角度来说，else 里的 setArray(elements) 是没有必要的，但是为了使得走 else 这个代码路径时也有写 volatile 变量操作，就需要加一个 setArray(elements) 调用。

最后，以 FutureTask 结尾，这应该是个比较有名的例子了，随提一下。提交任务给线程池，我们可以通过 FutureTask 来获取线程的运行结果。绝大部分时候，将结果写入 FutureTask 的线程和读取结果的不会是同一个线程。写入结果的代码如下：

void innerSet(V v) {
    for (;;) {
        int s = getState();
        if (s == RAN)
            return;
        if (s == CANCELLED) {
            // aggressively release to set runner to null,
            // in case we are racing with a cancel request
            // that will try to interrupt runner
            releaseShared(0);
            return;
        }
        if (compareAndSetState(s, RAN)) {
            result = v;
            releaseShared(0);
            done();
            return;
        }
    }
}

获取结果的代码如下：

V innerGet(long nanosTimeout) throws InterruptedException, ExecutionException, TimeoutException {
    if (!tryAcquireSharedNanos(0, nanosTimeout))
        throw new TimeoutException();
    if (getState() == CANCELLED)
        throw new CancellationException();
    if (exception != null)
        throw new ExecutionException(exception);
    return result;
}

结果就是 result 变量，但 result 不是 volatile 变量，而这里又没有加锁操作，那么怎么保证写入到 result 的值对读取 result 的线程可见？这里是经过精心设计的，因为读写 volatile 的开销很小，但毕竟还是存在开销的，且作为一个基础类库，追求最后一点性能也不为过。因为无法预知所有可能的使用场景，这里利用了 AbstractQueuedSynchronizer 中的 releaseShared 与 tryAcquireSharedNanos 的 hb 关系。

线程1：                   线程2：
p1:result = v;
p2:releaseShared(0);
                         p3:tryAcquireSharedNanos(0, nanosTimeout)
                         p4:return result;

正如前面分析的那样，在这个执行轨迹中，有 hb(p1,p2),hb(p3,p4) 且有 hb(p2,p3)，所以有 hb(p1,p4)，因此，即使 result 是普通变量，p1 中的写操作也是对 p4 可见的。但，会不会存在这样的轨迹呢：

线程1：                  线程2：
p1:result = v;          
                        p3:tryAcquireSharedNanos(0, nanosTimeout)
p2:releaseShared(0);
                        p4:return result;

这也是一个关键点，这种情况是决计不会发生的。因为如果没有 p2 操作，那么 p3 在执行 tryAcquireSharedNanos 时会一直被阻塞，直到 releaseShared 操作执行结束或超过了给定的 nanosTimeout 时间或被中断，若是 releaseShared 执行了，则就变成了第一个轨迹，若是超时，那么返回值是 false，代码逻辑中就直接抛出了异常，不会去取 result 了，所以，这个地方设计的很精巧。这就是所谓的捎带同步（ piggybacking on synchronization），即没有特意为 result 变量的读写设置同步，而是利用了其他动作同步时“捎带”的效果。但在我们自己写代码时，应该尽可能避免这样的做法，因为不好理解，对编码人员要求高，维护难度大。

本文只是简单解释了下 hb 规则，文中许多名词没有作更多介绍，为啥没介绍？介绍开来就是一本书啦，他们就是《Java Memory Model》、《Java Concurrency in Practice》、《Concurrent Programming in Java: Design Principles and Patterns》等，去这些书里找定义与解释吧。

转载自：http://ifeve.com/easy-happens-before/