0%

happens-before规则

一、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

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