Chapter4 因果性——向Java内存模型进发
在2.1节我们描述过顺序一致性。它过于严格，不能用作Java内存模型，因为它禁止编译器和处理器的优化。我们必须建立一个更好的内存模型。本章中，我们通过仔细验证非同步代码的必要条件来解决这一问题。换言之，我们解决这样的一个问题：对于一个多线程程序，什么是可以接收的行为。回答这一问题可以让我们将必要条件综合起来并建立一个可以工作的内存模型。
4.1 顺序一致性内存模型
2.1节所讨论的顺序一致性。为了，方便这里再次称述并对其进行规范。
在顺序一致性中，所有操作都发生在一个总体顺序中（执行顺序）。操作的执行顺序和他们在程序中出现的顺序一样（也就是说他们和程序顺序一致）。此外，对变量v的每个读r可以观察到对变量v的写w，这样：
- 在执行顺序中，w在r之前，并且
- 在执行顺序中，没有其它写w’，使得w在w’之前，并且w’在r之前。
4.2 前置发生内存模型
通过对锁和解锁使用一点抽象，使用第3章介绍的HB必要条件，我们可以描述一个简单，有趣的内存模型。我们称之为前置发生内存模型。我们的简单内存模型的许多必要条件都来自于2章和3章。
- 在所有同步操作上有一个总体顺序，称为同步顺序（synchronization order）。
- 同步操作在匹配的操作间引入了同步（synchronizes-with）边界。和程序顺序一起，这两种关系形成了前置发生关系。
- 在同步顺序中，一个volatile读观察到前一个volatile写。
前置发生内存模型唯一额外的约束是，一个普通读所观察到的值由前置发生一致性（happens-before consistency）决定。正式地，我们说对一个变量v的一个读r对观察到对v的写w是前置发生一致的：
- w由前置发生排在r之前，并且没有中间的对v的写w’。
- w和r不由前置发生进行排序。
不那么正式地，在一个程序执行中，有两种情况下一个写对于观察到一个读是前置发生一致的。第一，如果写前置发生于读并且没有中间的对同一变量的写，那么这个写是前置发生一致的。因此，如果一个将1写到x的操作前置发生于将2写到x，并且将2写入前置发生于一个读，那么读不能观察到值1。换言之，如果这个读与写之间不由前置发生进行排序，那么对于这个读操作，观察到写操作是前置发生一致的。
初始 x == y == 0
Thread 1 | Thread 2
---------------|----------------
1: r2 = x; | 3: r1 = y
2: y = 1; | 4: x = 2
可能返回 r2 == 2, r1 == 1
图4.1 意外的行为
作为示例，考虑图4.1（和图3.2以及图2.1一样），图中的代码有两个写和两个读，对同一变量的读和写不由前置发生所排序。因此写观察到读是前置发生一致的。
如果一个执行中所有的读对写的观察都是前置发生一致的，那么我们就说执行是前置发生一致的。注意，前置发生一致意味着每个读必须观察到程序中某处的写。
只要第一个近似行得通，那么前置发生内存模型就不是一个坏事。它提供了一些必要的保证。例如，图4.1中的代码是前置发生一致的：没有任何前置发生关系阻止读观察到写。
初始 x == y == 0
Thread1 | Thread2
---------------|-------------
r1 = x; | r2 = y;
---------------|-------------
if (r1 != 0) | if (r2 != 0)
y = 42; | x = 42;
正确同步的，因此r1 == r2 == 0是唯一合法的行为
图 4.2 意外正确同步的程序
不幸的是，前置发生一致性不是一个好的内存模型，它仅仅不是充分的。图4.2（和图3.2一样）展示了一个前置发生一致但并没有产生期望的结果。记住，改代码是正确同步的，如果是并发执行的，对x或y的写都不会发生，因为对这些变量的读只会观察到0.因此，这些代码中没有数据竞争。然而，在前置发生一致内存模型中，如果两个写都发生了，那么读观察到写是前置发生一致的。尽管这是一个正确同步的程序，在前置发生一致性下，非顺序一致的执行是合法的。因此，前置发生一致的执行会违反DRF保证。
虽然这样，前置发生一致性为我们的模型提供了一个好的外部边界。基于HB，所有的执行必须是前置发生一致的。
4.3 因果性
基本概念
初始，x == y == 0
Thread 1 | Thread 2
-------------|---------------
r1 = x; | r2 = y;
y = r1; | x = r2;
未正确同步的，但r1 == r2 == 42仍然不可能发生
图 4.3：一个无中生有（Out Of Thin Air）的结果
因此，前置发生内存模型在我们最终内存模型上提供了必要的约束，但它并不完整。我们会看到为什么是这样的，检查图4.2，写操作控制依赖于读操作。一个类似的例子见图4.3。这种情况下，写总是会发生，并且值的写操作数据依赖于读操作。
前置发生内存模型也允许非期望结果的发生。如果线程2中将42写到x，那么，在前置发生内存模型下，线程1中读取x为该值是合法的。然后，线程1会将42写入y，然后线程2读取到y为42也是合法的。使用一个循环的推理，不期望的结果得到自证了。
它不再是一个正确同步的程序，因为线程1和线程2间存在数据竞争，然而，有许多类似的例子，我们希望提供一个类似的保证。这种情况下，我们说值42不能凭空出现。
事实上，相比图4.2中的行为，图4.3的行为更值得考察。如果，例如凭空出现的值是一个对象引用，并且该线程本不应该持有它，那么这种转换就是一个严重的安全违例。编译器没有理由产生这种结果。
初始，x = null, y = null
o是一个对象，有一个引用o的域f
Thread 1 | Thread 2
--------------|--------------
r1 = x; | r3 = y;
r2 = x.f; | x = r4;
y = r2; |
r1 == r2 == o不是一个可以接受的行为
图4.4 一个不期望的重排序
这样的一个例子如图4.4所示。我们假设有一个对象o，我们不希望线程1或线程2观察到。o有一个保存在域f中的自引用。如果编译器决定进行一个分析，假设每个线程中的读可以观察到其它线程中的写，并且观察到一个对o的引用，那么r1 == r2 == o就是一种可能的结果。这个值并不是来自某个地方，它仅仅是凭空出现的一个随机值。
确定是什么造成了一个无中生有的读是非常复杂的。一个（不精确）近似就是，在一些顺序一致的执行中，对一个变量，我们不希望读观察到一个不能被写入的值。因为图4.3中，42从来没有被写入，没有读能够观察到它。
对这种问题的解决办法就是一个程序可以包含在任何顺序执行中都没有出现的语句。想象以下，作为一个例子，图4.1中读操作只在r1+r2等于3时进行。这个写没有在任何顺序一致执行中出现，但我们仍然希望一个读可以观察到它。
一种思考这一问题的方式就是考虑什么时候操作会出现在一个执行中。我们考查的转换都涉及将操作移动到它们出现之前的位置。例如，为了消除图4.3中的无中生有，在某种程度上我们将42写入y的操作移到Thread1中前面的位置，那么线程2对y的读就可以观察到它并且允许对x的写发生。然后，线程1中对x的读可以观察到值42，并且证实了对y的写操作。
如果我们假设这些问题的关键就是考虑什么时候操作可以被移到前面，那么我们必须小心谨慎地考虑这一问题。需要回答的问题是，导致一个操作发生的原因是什么？什么时候操作可以提到前面进行？对这一问题的潜在答案涉及到我们希望执行操作的开始点，然后考虑如果我们从这个点以顺序一致的方式执行时会发生什么。如果我们这样做了，有可能操作在之后已经发生了，那么或许该操作可以认为是有原因的。
在上述情形中，通过鉴定一些行为良好的执行，我们鉴定出一个动作是否可以在它出现的地方之前进行，并且使用这一执行来判定说进行的操作。因此我们的模型建立了一个执行迭代；如果一个操作（或者一组操作）发生在一些行为良好的执行中，并且这些执行中也已经包含了到目前为止所提交的操作，它允许这个操作的提交（本质上，提前执行）。显然这需要一个基本情形：我们仅仅假设没有操作被提交。
因此，最终的模型可以描述为两个、迭代的、阶段。以操作集的一些提交开始，产生所有可能的“行为良好”的执行。然后，使用这些行为良好的执行来确定进一步的操作可以合理地提前执行。提交这些动作，反复直到所有动作被提交。
识别什么是一个“行为良好的”执行对我们的模型相当重要，并且是通往因果性概念的钥匙。例如，在图4.1中我们有一个控制依赖于r1+r2=3的写，我们知道，在r1+r2的结果确定后，程序表现出顺序一致方式的行为，这个写的执行会发生。
我们可以将这种行为良好的概念应用到其它例子中，同样的。在图4.1中，对x和y的写可以首先发生，因为他们总是会以顺序一致的方式执行。图3.3总，对b的写可以提前，因为当r1和r2观察到同一个值时，它发生在一个顺序一致执行中。在图4.3中，将42写到y和x不可能发生，因为它们不在任何顺序一致执行中发生。那么，这是我们第一个（但非唯一的）“无中生有（out of thin air）”保证：
ThinAir1 在一个执行中，一个写可以发生在它在程序顺序之前。然而，必须假设随后的任意的读都没有观察到非顺序一致的的值。
这只是对因果性的第一个近似：它也是一个好的开始，但并没有包含我们所有的基础。
近期评论