理解 Java 内存模型的因果性约束

栏目: IT技术 · 发布时间: 4年前

内容简介:欢迎加入技术交流群186233599讨论交流,也欢迎关注笔者公众号:风火说。这部分的内容比较抽象,首先是一开始的定义,如下

理解 Java 内存模型的因果性约束

欢迎讨论

欢迎加入技术交流群186233599讨论交流,也欢迎关注笔者公众号:风火说。

规范理解

这部分的内容比较抽象,首先是一开始的定义,如下

理解 Java 内存模型的因果性约束

红色下划线的内容应该是理解的关键。首先,E 是一个特定的执行序列,其由指令集合 A 以及用于对集合 A 内部存在的 PO,SO,SW,HB 排序构成。C i 是被 E 包含的一个子集,也就是说 C i 中的指令全部都在执行 E 的指令集合 A 中存在。

来看第二,第三和第四个红线(忽略A是无限集合的情况,无限集合意味着线程出现了死循环,永不终止,这并不是一个合理的程序),这三者合在一起理解,可以认为是 C i 增加一个指令,就构成了 C i+1 ,也就形成了新的 A i+1 。而新的 A i+1 结合 PO,SO,SW,HB 关系就成为了新的 E i+1

接着来看后续的定义

理解 Java 内存模型的因果性约束

这 5 个约束合在一起实际上是说明如何构成一个 C 集合。简单而言,C i 是 A i 的一个子集,并且这个子集和执行轨迹E i 拥有相同的 HB,SO 关系,且 C i 中写入操作的写入值和 E i 中相同,C i 中对写入值的观察结果和 E i 中相同。而 E i 是逐步构成 E 的第 i 步骤,最终 E~n~ 等同于 E 。这实际上约束了 C 是如何构成的,它并不是凭空而来,而是不断的将 E 中的指令添加到 C 之中,并且这些添加的指令都和 E 拥有相关的观察效果,写入值,以及偏序关系。通过确保一系列的 E i 都是合法的,最终确定 E 是合法的。

再来剩下的两条规则

理解 Java 内存模型的因果性约束

第 6 条规则定义了要往集合 C 中添加读取指令时,该指令的观察结果。换句话说集合 C~i-1~ 中的写入操作产生的效果,能被任意未添加到该集合中的写入操作观察到。

第 7 条规则和上面的 5 条规则相同,也是在明确在集合 C 中产生的观察效果在执行轨迹 E 中也是存在的。

7个规则都在描述在集合 C 中的写入值,读取结果,指令排列顺序都是和 E 等同,因此通过不断的构建 C i ,最终 C~n~ 等同于 A~n~ ,再加上在 C~n~ 中的写入值,读取结果,指令排列顺序,就构成了最终的 E 。而如果这一系列的 C i 都是“合法”的话,则最终的执行轨迹 E 也是合法的。

当我们需要向集合新增一个读取指令时,其读取到的值只能在该集合中的写入值。提交指令到集合中时,如果存在HB 关系 或依赖关系的语句阻止其提交,则提交不能成功。

例子练习

例子1

首先来看一段代码,如下

nonvolatile global int a = 0, b = 0;
ThreadA()
{
    int aL = a;
    if(aL == 1) b = 1;
}
ThreadB()
{
    int bL = b;
    if(bL == 1) a = 1;
}

对于内存模型而言,其只关注操作内存的指令,在执行轨迹 E 的 A 集合的内容是

int aL = a;
b = 1;
bL = b;
a = 1;

由于 int aL = a;a = 1; 不存在 HB 关系,因此可以通过数据竞争的方式读取到该写入值,也就是 aL 的值是 1 。 bL = b;b = 1; 不存在 HB 关系,因此可以通过数据竞争的方式读取到该写入值,也就是 bL 的值是 1 。

一个读取操作可以读取的到值或者是通过 HB 关系得到,或者是通过数据竞争得到。也就是说,在没有 HB 关系阻止该读取结果时,该读取结果是允许的,这被称之为 HB 一致性。显然,上面的输出结果 aL==bL==1 是符合 HB 一致性的。

然而从顺序一致性执行的角度而言,这种输出结果就好像是因为 aL 读取到线程 B 写入的值,产生了 b=1 的结果,而这个结果导致了 bL==1 的结果,而这个结果导致了 a=1 的结果,而 a==1 导致了 aL=1 。形成了一个循环,显然这是违背直觉的。而 JMM 中因果性的要求就是用来判定这种执行轨迹是否合法的依据。

再用因果性分析这个执行之前,我们先看另外一个更简单一些的例子,代码如下

0: x == y == 0
 
Thread 1:
1: r1 = x;
2: y = 1;
 
Thread 2:
3: r2 = y;
4: x = r2;

这个例子反复出现,显然我们知道 r1==r2==1 是一个合法的输出结果。因为重 排序 的原因, y=1 被执行,而后 r2=y 观察到这个写入, x=r2 同样得到值 1, r1=x 观察到这个写入。下面我们使用因果性来分析这个执行轨迹。

首先我们将集合 C 中添加指令 2 。与指令 2 存在 HB 关系的是指令 0 和 1 。他们都不会阻止指令 2 的发生,因此指令 2 被允许添加到集合 C 中,此时有 C 1

我们用 W(variable,value) 来表达对一个变量 variable 写入 value 的值,用 R(variable,value) 表达从变量 variable 中读取到 value 的值。

因此目前我们有 C 0 = {W(x,0),W(y,0)} 的初始状态。而 C 1 =C 0 U {W(y,1)} 。然后我们添加指令 3 到 C 1 中,按照 HB 关系,指令观察到的值应该是指令 0 写入的。但是同时,它也允许观察到提交集合中已经写入的值,也就是存在于提交集合中指令 2 的写入值。因此我们有 C 2 =C 1 U {R(y,1)} 。

接着我们提交指令 4 ,显然此时有 C 3 =C 2 U {W(x,1)} 。

最后我们提交指令 1,按照 HB 关系,此时允许的观察值由指令 0 写入,也就是 0 。与上述相同,允许其观察到在提交集合中的写入值,因此 C 4 =C 3 U {R(x,1)} 。

C 4 =A 4 ,C 4 中的写入值,读取值,排列顺序都与 E 4 相同,也与 E 相同。因此判定该执行轨迹是合法的,其表现是符合 JMM 要求的。

接下来我们回到最开始的例子,如果我们要得到 bL==1 的结果,意味着我们需要执行 b=1 这个指令。而要执行该指令,我们需要执行 int aL = a; 指令并且读取到值 1 。 注意,因果性的判断是需要考虑条件判断因素的,而 HB 一致性则不考虑,它仅仅是提取所有的可能执行指令并且假定其执行。

从提交集合的角度出发,我们需要提交 int aL = a; 实际上是想提交 R(a,1) 。但是 C 0 ={W(x,0),W(y,0)} ,C 1 中的读取操作的读取值只能由 C 0 中的写入造成,因此 R(a,1) 无法被提交到 C 1 中。这就意味着达成 a==b==1 的提交集合不合法,因此对应的执行轨迹也是非法的。所以这种结果不被 JMM 允许。

例子2

int /* non-volatile */ a;
int /* non-volatile */ b;
ThreadA()
{
    int tmp = a;
    b = tmp;
}
ThreadB()
{
    int tmp = b;
    a = tmp;
}

对于上面的代码, a==b==1 的结果是符合 HB 一致性的。看起来这个比例子 1 中出现的情况更费解一些,因为 1 这个值似乎是无中生有的。但是我们首先假设 int tmp = a; 读取到了 1 ,此时 b = tmp; 将会写入 1 。而 int tmp = b; 又读取到了该值,这会导致 a = tmp; 写入值 1 ,恰恰满足了 int tmp = a; 读取到 1 的需要。HB 一致性中,如果没有 HB 关系阻止一个值被读取,则该读取都是被允许的,也就是可以认为 int tmp = a; 通过数据竞争的方式读取到了未来的写入值。按照这种方式考虑,这个例子实际上类似于例子1中的第二个示例。

但是显然,这个结果是违反直觉的,其结果也被 JMM 禁止。我们使用因果性的方式进行分析。

首先,显然我们有 C 0 ={W(a,0),W(b,0)} 。接着我们提交 int tmp = a; (不能先提交 b = tmp; 是因为 int tmp = a; 与其存在依赖关系,且有 HB 关系)。根据 C 0 的内容,显然此时只允许提交 R(a,0) 或 R(b,0) 。通过因果性分析,我们得到这个例子的合法输出只能是 a==b==1

总结

非正式的说,可以认为通过结合 HB 一致性和因果性要求得到 JMM 。这两个约束结合在一起,才有了 JMM 对 程序员 的保证:如果一个程序是正确同步的,其程序表现为顺序一致性。


以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

Python Machine Learning

Python Machine Learning

Sebastian Raschka / Packt Publishing - ebooks Account / 2015-9 / USD 44.99

About This Book Leverage Python' s most powerful open-source libraries for deep learning, data wrangling, and data visualization Learn effective strategies and best practices to improve and opti......一起来看看 《Python Machine Learning》 这本书的介绍吧!

随机密码生成器
随机密码生成器

多种字符组合密码

RGB HSV 转换
RGB HSV 转换

RGB HSV 互转工具

RGB CMYK 转换工具
RGB CMYK 转换工具

RGB CMYK 互转工具