内容简介:欢迎加入技术交流群186233599讨论交流,也欢迎关注笔者公众号:风火说。这部分的内容比较抽象,首先是一开始的定义,如下
理解 Java 内存模型的因果性约束
欢迎讨论
欢迎加入技术交流群186233599讨论交流,也欢迎关注笔者公众号:风火说。
规范理解
这部分的内容比较抽象,首先是一开始的定义,如下
红色下划线的内容应该是理解的关键。首先,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 。
接着来看后续的定义
这 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 是合法的。
再来剩下的两条规则
第 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 对 程序员 的保证:如果一个程序是正确同步的,其程序表现为顺序一致性。
以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网
猜你喜欢:- AI特别企划四:遵循因果性的可解释AI预测
- 可靠的因果保证
- 因果关系到底存不存在:反事实和平行宇宙
- 图灵奖得主Judea Pearl:从“大数据革命”到“因果革命”
- MongoDB是第一个支持因果一致性的数据库商业产品
- 让智能体主动交互,DeepMind提出用元强化学习实现因果推理
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
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》 这本书的介绍吧!