dslztx
0%

happens-before规则

发表于 更新于 专题于 ， ， Disqus：

一、happens-before规则产生背景

根据《可见性与有序性》，编写Java程序存在“可见性”和“有序性”问题。为提供确定性编程环境，JMM提供了一系列happens-before规则，遵循happens-before规则可获得相对应的“可见性”和“有序性”语义保证，其语义是：假如操作A happens-before 操作B，那么“在可见性维度，操作A对操作B内存可见；在有序性维度，操作A先于操作B”。

备注：

  • 上述“可见性”指代“广义可见性”，“有序性”指代“广义有序性”，本文后续如无特别说明，都是该含义。而且根据《可见性与有序性》可知，“广义可见性”和“广义有序性”是等价的

二、happens-before规则的实现原理

happens-before规则的实现原理是：对于违背happens-before规则所提供“可见性/有序性”语义确保的“可见性/有序性”问题，通过各个指令/语言层级的内存屏障加以解决，比如“通过程序语言层级的内存屏障禁止程序语言编译/解释过程中的重排序”；而对于那些不违背happens-before规则所提供“可见性/有序性”语义确保的“可见性/有序性”问题，不作限制，即“法无禁则行”。

三、happens-before规则

以下是几个常见的happens-before规则：

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

四、happens-before规则应用

happens-before规则的语义理解起来其实不难，只是应用的时候有一个难点：对于happens-before规则而言，先有满足条件的A和B，再有“A happens-before B”关系，但是如何获得满足条件的A和B呢？

接下来探讨如何获得满足条件的A和B：

  • 程序顺序规则：在单线程语境中，能够简单获得满足条件的A和B
  • 传递性规则：逻辑推导规则，没有具体的满足条件
  • start()规则：经分析，能够简单获得满足条件的A和B
  • join()规则：经分析，能够简单获得满足条件的A和B
  • 监视器锁规则：在单线程语境中，满足条件的A和B简单可获得；在多线程语境中，满足条件的A简单可获得，满足条件的B非简单可获得，主要是如何定义和获得“随后”？结合锁的定义，分为3种情形：1）B中加锁前置于A中解锁对应的加锁，那么就不会存在A，此种情况无需探讨；2）B中加锁前置于A中解锁且后置于A中解锁对应的加锁，那么会阻塞直到使得B中加锁是“随后”的；3）B中加锁后置于A中解锁，那么B中加锁显而易见即是“随后”的
  • volatile变量规则：在单线程语境中，满足条件的A和B简单可获得。在多线程语境中，满足条件的A简单可获得，满足条件的B非简单可获得，主要是如何定义和达到“后续”？在多线程语境中，判定“后续”十分困难，但是在应用“volatile变量规则”的场景中，可以以另外一个视角来绕过这个判定问题，即如果“对这个volatile域的读”，能够读到“对该volatile域的写”，那么“对这个volatile域的读”就是“后续”的，这才是实际应用的立足点所在

五、基于happens-before规则推导新的happens-before规则

要想推导新的happens-before规则，须基于现有的happens-before规则，否则推导出的happens-before规则的正确性不能够得到保证。

5.1、例子1

比如有如下一个例子：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class ReorderExample {
    int a = 0;
    boolean flag = false;

    public void writer() {
        a = 1;               //1
        flag = true;         //2
    }

    public void reader() {
        if (flag) {          //3
            int i = a * a;   //4 
            // ......
        }
    }
}

根据程序顺序规则有“1 happens-before 2，3 happens-before 4”，当//3处读取到//2处值时，然后可能会错误认为有“2 happens-before 3”，接着再根据传递性规则，推导出有“1 happens-before 3，1 happens-before 4，2 happens-before 4”。但是，实际上“2 happens-before 3”未基于现有happens-before规则而是错误的结论，因此，最终也并没有“1 happens-before 3，1 happens-before 4，2 happens-before 4”，下面的两个可能执行时序也佐证了这个结论。

由于操作1和操作2没有数据依赖关系，编译器和处理器可以对这两个操作重排序。当操作1和操作2重排序时，可能的执行时序图如图1，此时，“1 happens-before 4”不成立。

图1

操作3和操作4没有数据依赖关系，但是存在控制依赖关系，控制依赖关系会影响指令执行的并行度，为克服该影响，编译器和处理器会采用猜测执行技术：提前读取并计算a*a，然后把计算结果临时保存到一个名为重排序缓冲（Reorder Buffer，ROB）的硬件缓存中。当操作3的条件判断为真时，把该计算结果写入变量i中。可以发现，猜测执行实质上是对操作3和4做了重排序，可能的执行时序图如图2，此时，“1 happens-before 4”不成立。

图2

如果给变量flag加上volatile关键词，那么基于volatile变量规则，的确有“2 happens-before 3（3是读取到flag变量写入值的3）”，最终也就有“1 happens-before 3，1 happens-before 4，2 happens-before 4”。

5.2、例子2

监视器锁规则中的“锁”包括“内置锁——synchronized关键词所对应锁”和“高级锁”，其中“内置锁”的该happens-before规则语义实现是JDK原生级别的，“高级锁”的该happens-before规则语义实现是非JDK原生级别，基于基础组件推导得的。
接下来以高级锁中的“ReentrantLock锁”为例进行推导演示，ReentrantLock锁可细分为“公平锁”和“非公平锁”。

另外需要说明的一点是，在查看源码的过程中可以发现，“unlock()”和“lock()”操作是方法，其显而易见是非原子的，因此可以知道，上述happens-before规则中的“操作”不一定是原子的。

5.2.1、公平锁

解锁代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
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;
}

加锁代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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，加锁时首先读取state变量，根据volatile变量规则，可推得“对一个锁的解锁，happens-before于随后对这个锁的加锁”，即满足监视器锁规则。

5.2.2、非公平锁

解锁代码同“5.2.1、公平锁”。
加锁代码如下：

1
2
3
4
5
6
final void lock() {
    if (compareAndSetState(0, 1))
        setExclusiveOwnerThread(Thread.currentThread());
    else
        acquire(1);
}

可发现：解锁时最后写volatile变量state，加锁时首先读取state变量（compareAndSetState是一个CAS操作含有先读取state变量的等价语义，acquire也是先读取state变量），根据volatile变量规则，可推得“对一个锁的解锁，happens-before于随后对这个锁的加锁”，即满足监视器锁规则。

六、其他

6.1、happens-before规则的现实意义

一个经典的多线程运行场景（线程A和线程B），如下。
线程A：

1
2
3
4
5
语句1
语句2
语句3
语句4
语句5

线程B：

1
2
3
4
语句11
语句22
语句33
语句44

如果需要分析跨线程的程序运行情况，那么需要考虑所有可能的“可见性，有序性”情形，脑力负担重，易出错，但是借助于happens-before规则就可以简单准确地完成上述分析任务。

通过如下一段示例代码进行说明：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
import java.util.HashSet;
import java.util.Set;
import java.util.concurrent.Executors;
import java.util.concurrent.ScheduledExecutorService;
import java.util.concurrent.TimeUnit;

public class DataReloader {

    private static ScheduledExecutorService threadPool = Executors.newScheduledThreadPool(10);

    Set<String> set = null;

    public static void main(String[] args) throws InterruptedException {
        final DataReloader dataReloader = new DataReloader();

        threadPool.scheduleAtFixedRate(new Runnable() {
            @Override
            public void run() {
                dataReloader.reload();
            }
        }, 0, 30, TimeUnit.MINUTES);

        dataReloader.run();
    }

    public void run() throws InterruptedException {
        while (true) {
            for (String s : set) {                   //5
                System.out.println(s);               //6
            }

            Thread.sleep(10000);
        }
    }

    public void reload() {
        set = reloadLogic();
    }

    private Set<String> reloadLogic() {
        // reload set logic
        Set<String> tmpset = new HashSet<String>();   //1
        tmpset.add("hello");                          //2
        tmpset.add("world");                          //3

        return tmpset;                                //4
    }
}

上述这段代码描述的程序逻辑是：1）主线程不断打印集合set内的元素；2）每隔30分钟运行另外一个线程重新加载集合set。
现在的实现方式存在的问题是：由于“重排序”的存在，可能出现一种情形——主线程在获得最新的set之后，里面的“hello”和“world”元素还没有添加完成。
假如给set加上volatile关键词，此时，定时线程中有“1 happens-before 2，2 happens-before 3，3 happens-before 4”，在主线程中有“5 happens-before 6”，根据volatile变量规则有“4 happens-before 5（5是读取到set变量写入值的5）”，再根据传递性规则，则最终有“1 happens-before 5，2 happens-before 5，3 happens-before 5”，因此上述描述的问题不会再出现。

备注：

  • Foreach语法的本质是迭代器，因此对于for (String s : set)来说，本质是遍历一个迭代器，并隐式含有“读取set变量 happens-before 生成一个迭代器”

参考文献

[1]https://stackoverflow.com/questions/18508786/for-each-vs-iterator-which-will-be-the-better-option

您的支持将鼓励我继续分享！