happens-before 俗解

学习 Java 并发编程时，最终总会接触到 happens-before 偏序关系。初接触这一概念时往往觉得不知所云，本文基于个人理解对其进行通俗解读，希望能对初学者有所帮助。如有不正确之处，欢迎指正。

众所周知，synchronized 及大部分锁机制的主要功能是实现多个线程互斥或串行地访问临界区（共享锁除外，如读锁允许多线程同时访问）。然而，它们的第二个重要功能——保证变量的可见性——却常被遗忘。

背景：为什么存在可见性问题

简单来说，相对于内存，CPU 的速度极高。如果 CPU 每次存取数据都直接与内存打交道，存取过程中 CPU 将一直空闲，这显然是极大的资源浪费。因此，现代 CPU 内部设计了大量寄存器和多级 Cache，它们的存取速度远高于内存。

当某个线程执行时，内存中的一份数据会存在于该线程的工作存储（Working Memory）中。这是 Cache 和寄存器的一个抽象概念（源于《Concurrent Programming in Java: Design Principles and Patterns, Second Edition》§2.2.7，原文：Every thread is defined to have a working memory (an abstraction of caches and registers) in which to store values.）。为避免混淆，此处称其为工作存储，每个线程都有独立的工作存储，数据会在特定时候回写到主内存。

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

什么是 happens-before

我们无法枚举所有场景来规定某个线程修改的变量何时对另一个线程可见，但可以制定一些通用规则，这就是 happens-before。它是 Java 内存模型（JMM）中定义的一种偏序关系。JMM 定义了许多动作（Action），有些动作之间存在 happens-before 关系（并非所有动作两两之间都有）。

"ActionA happens-before ActionB"这样的描述容易让人困惑。我们可以将其记作 hb(ActionA, ActionB) 或者 ActionA < ActionB。此处的 < 并非数学意义上的小于号，而是表示偏序关系。为了表述清晰，下文统一使用 hb(ActionA, ActionB) 的方式。

常见的 happens-before 规则

从 Java 内存模型中选取两条典型的 happens-before 规则：

  • Monitor 锁规则：对一个 monitor 的解锁操作 happens-before 后续对同一个 monitor 的加锁操作。
  • Volatile 变量规则：对某个 volatile 字段的写操作 happens-before 后续对同一个 volatile 字段的读操作。

直译过来可能是：“对一个 monitor 的解锁操作 happens-before 后续对同一个 monitor 的加锁操作”……这种表述依然晦涩。是否意味着解锁操作要先于锁定操作发生？这有违常规。实际上，happens-before 规则不是描述实际操作的物理先后顺序，而是用来描述可见性的规则。上述两条规则可以通俗地理解为：

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

核心逻辑其实很简单：如果 hb(a, b)，那么 a 及之前的写操作在另一个线程进行了 b 操作时，对该线程可见（同一个线程内不存在可见性问题，下文不再赘述）。

再看两条规则：

  • Thread Join 规则：线程中的所有动作 happens-before 其他线程成功从该线程的 join() 调用返回。
  • 程序顺序规则：线程中的每个动作 happens-before 该线程中的后续动作。

通俗版解释：

  • 线程 t1 写入的所有变量，在任意其它线程 t2 调用 t1.join() 成功返回后，都对 t2 可见。
  • 线程中上一个动作及之前的所有写操作，在该线程执行下一个动作时对该线程可见（即同一个线程中，前面的所有写操作对后面的操作可见）。

传递性

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

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

实例分析：CopyOnWriteArrayList

接下来用 hb 规则分析两个实际的可见性例子。首先看 CopyOnWriteArrayList 的例子。假设代码中的 list 对象是 CopyOnWriteArrayList 类型，a 是个静态变量，初始值为 0。

假设有以下代码与执行线程：

线程 1线程 2
a = 1;list.get(0);
list.set(1, "t");int b = a;

那么，线程 2 中 b 的值会是 1 吗？我们来分析执行轨迹。假设轨迹如下所示：

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

p1, p2 是同一个线程中的，p3, p4 是同一个线程中的，所以有 hb(p1, p2) 和 hb(p3, p4)。要使得 p1 中的赋值操作对 p4 可见，只需要有 hb(p1, p4)。前面说过，hb 关系具有传递性，那么若有 hb(p2, p3) 就能得到 hb(p1, p4)。p2, p3 是否存在 hb 关系？

查阅 javaapi，发现有如下描述：

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(0)
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 的，但 JMM 不保证最后 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，有何意义？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 来获取线程的运行结果。绝大部分时候，将结果写入 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 超时时间，或被中断抛出 InterruptedException。若是 releaseShared 执行了，则就变成了第一个轨迹；若是超时，那么返回值是 false，代码逻辑中就直接抛出了异常，不会去取 result 了。所以，这个地方设计得很精巧。

这就是所谓的"捎带同步（piggybacking on synchronization）”，即没有特意为 result 变量的读写设置同步，而是利用了其他同步动作时“捎带”的效果。但在我们自己写代码时，应该尽可能避免这样的做法，因为不好理解，对编码人员要求高，维护难度大。

总结

本文只是简单地解释了 hb 规则，文中还出现了许多名词没有做更多介绍。为何没介绍？因为展开来讲就是一本书了。相关定义与解释可参考《Java Memory Model》、《Java Concurrency in Practice》、《Concurrent Programming in Java: Design Principles and Patterns》等书籍。

说明：本文基于 Java 7 文档及经典 JMM 理论整理，核心概念适用于 Java 5 及以上版本。