顺序一致性

在顺序一致的并发执行中，动作似乎以全局总顺序发生，每个对特定变量的读取都会看到影响该变量的最后一个写入的值。动作的总顺序必须与程序顺序一致。当程序的某个顺序一致执行将两个冲突动作放在一起时，程序在该输入上存在数据竞态。

这是人类最容易理解的内存模型，尽管它并不能消除所有混乱，因为操作可能会在奇怪的地方被拆分。

先行发生一致性

程序包含一组同步动作，在 Python 中目前包括锁的获取和释放以及线程的启动和加入。同步动作以与程序顺序一致的全局总顺序发生（它们不必以总顺序发生，但它简化了模型的描述）。锁释放与同一锁的后续获取同步。类似地，给定 t = threading.Thread(target=worker)

• 调用 t.start() 与 worker() 中的第一个语句同步。
• 从 worker() 返回与从 t.join() 返回同步。
• 如果 t.start() 的返回发生在（见下文）一个返回 False 的 t.isAlive() 调用之前，则 worker() 的返回与该调用同步。

我们将同步边（synchronizes-with edge）的来源称为相关变量上的释放操作，将目标称为获取操作。

先行发生（happens-before）顺序是程序顺序与同步边（synchronizes-with edges）的传递闭包。也就是说，动作 A 先行发生于动作 B，如果

• A 在程序顺序中排在 B 之前（这意味着它们在同一个线程中运行）
• A 与 B 同步
• 你可以通过跟随 A 的先行发生边到达 B。

程序的执行是先行发生一致的，如果每次读取 R 看到变量 W 的写入值，满足以下条件：

• R 不先行发生于 W，并且
• 没有其他写入 V 在 R 有机会看到它之前覆盖了 W。（也就是说，不能出现 W 先行发生于 V，V 先行发生于 R 的情况。）

如果两个冲突动作不通过先行发生关联，你就遇到了数据竞态。

class Queue:
    def __init__(self):
        self.l = []
        self.cond = threading.Condition()

    def get():
        with self.cond:
            while not self.l:
                self.cond.wait()
            ret = self.l[0]
            self.l = self.l[1:]
            return ret

    def put(x):
        with self.cond:
            self.l.append(x)
            self.cond.notify()

myqueue = Queue()

def worker1():
    x = [7]
    myqueue.put(x)

def worker2():
    y = myqueue.get()
    print y

thread1 = threading.Thread(target=worker1)
thread2 = threading.Thread(target=worker2)
thread2.start()
thread1.start()

僵尸值

此示例来自 Java 内存模型

最初 p is q 且 p.x == 0。

线程 1	线程 2
r1 = p	r6 = p
r2 = r1.x	r6.x = 3
r3 = q
r4 = r3.x
r5 = r1.x

可能产生 r2 == r5 == 0 但 r4 == 3，证明 p.x 从 0 变为 3 再变回 0。

一个好的编译器会希望通过重用已加载到 r2 中的值来优化 r5 的初始化中冗余的 p.x 加载。如果我们得到以下结果，那么就会出现奇怪的结果：线程 1 按此顺序看到内存

评估	计算	原因
r1 = p
r2 = r1.x	r2 == 0
r3 = q	r3 是 p
p.x = 3		线程 2 的副作用
r4 = r3.x	r4 == 3
r5 = r2	r5 == 0	由于 r2 == r1.x，r5 = r1.x 被优化为 r5 = r2。

不一致的顺序

来自 N2177: Atomics 的顺序一致性，也称为独立读取独立写入 (IRIW)。

最初，a == b == 0。

线程 1	线程 2	线程 3	线程 4
r1 = a	r3 = b	a = 1	b = 1
r2 = b	r4 = a

我们可能得到 r1 == r3 == 1 和 r2 == r4 == 0，这证明 a 在 b 之前写入（线程 1 的数据），并且 b 在 a 之前写入（线程 2 的数据）。参见 狭义相对论 以了解真实世界的例子。

这可能发生在线程 1 和线程 3 运行在彼此靠近的处理器上，而线程 2 和线程 4 运行在远离它们的处理器上，并且写入在到达附近的线程可见之前并没有完全传输到机器的另一端。

获取/释放语义或显式内存屏障都无法解决此问题。在没有锁的情况下使顺序一致需要对体系结构内存模型有详细的了解，但 Java 对 volatile 有此要求，因此我们可以参考针对其实现者的文档。

一个非顺序一致性的先行发生竞态

来自关于 Java 内存模型的 POPL 论文 [#JMM-popl]。

最初，x == y == 0。

线程 1	线程 2
r1 = x	r2 = y
if r1 != 0	if r2 != 0
y = 42	x = 42

是否可以得到 r1 == r2 == 42？？？

在顺序一致的执行中，不可能出现对同一变量的相邻读写，因此程序应被视为正确同步（尽管脆弱），并且应只产生 r1 == r2 == 0。然而，以下执行是先行发生一致的：

语句	值	线程
r1 = x	42	1
if r1 != 0	真	1
y = 42		1
r2 = y	42	2
if r2 != 0	真	2
x = 42		2

WTF，你可能在想。因为原始程序中没有线程间的先行发生边，所以线程 1 中的 x 读取可以看到线程 2 中的任何写入，即使这些写入仅因为读取而发生。在先行发生模型中存在数据竞态。

我们不希望允许这种情况，因此先行发生模型不足以满足 Python。我们可以添加到先行发生模型中以防止此执行的一条规则是：

如果在程序的任何顺序一致执行中没有数据竞态，那么程序应该具有顺序一致的语义。

Java 通过一个复杂的因果关系定义获得了这个规则，但 Python 可能不希望包含所有证明它所需的机制。

自证其值

同样来自关于 Java 内存模型的 POPL 论文 [#JMM-popl]。

最初，x == y == 0。

线程 1	线程 2
r1 = x	r2 = y
y = r1	x = r2

是否可以得到 x == y == 42？？？

在顺序一致的执行中，不行。在先行发生一致的执行中，可以：线程 1 中的 x 读取允许看到线程 2 中写入的值，因为线程之间没有先行发生关系。如果编译器或处理器将代码转换为

线程 1	线程 2
y = 42	r2 = y
r1 = x	x = r2
if r1 != 42
y = r1

如果推测值是一个秘密对象，或者指向一个对象先前占用的内存，这可能会导致安全漏洞。Java 非常重视此类安全漏洞，但 Python 可能不需要。

未初始化值（直接）

来自几个经典的双重检查锁定示例。

最初，d == None。

线程 1	线程 2
while not d: pass	d = [3, 4]
assert d[1] == 4

这可能会引发 IndexError，断言失败，或者，如果没有在实现中进行一些处理，可能导致崩溃或其他未定义行为。

线程 2 可能实际实现为

r1 = list()
r1.append(3)
r1.append(4)
d = r1

由于对 d 的赋值和项的赋值是独立的，编译器和处理器可能会优化为

r1 = list()
d = r1
r1.append(3)
r1.append(4)

这显然是错误的，并解释了 IndexError。如果我们进一步深入 r1.append(3) 的实现，我们可能会发现它和 d[1] 不能并发运行而不引起它们自己的竞态条件。在 CPython（无 GIL）中，这些竞态条件会产生未定义的行为。

读取端也存在一个微妙的问题，可能导致 d[1] 的值过时。在 list 的实现中，它将内容存储在内存中的一个数组里。这个数组可能碰巧在线程 1 的缓存中。如果线程 1 的处理器从主内存重新加载 d 而不重新加载应该包含 3 和 4 的值的内存，它可能会看到过时的值。据我所知，这实际上只可能发生在 Alphas 和可能是 Itaniums 上，而且我们可能不得不阻止它以避免崩溃。

未初始化值（标志）

来自更多双重检查锁定示例。

最初，d == dict() 且 initialized == False。

线程 1	线程 2
while not initialized: pass	d[‘a’] = 3
r1 = d[‘a’]	initialized = True
r2 = r1 == 3
assert r2

这可能会引发 KeyError，断言失败，或者，如果没有在实现中进行一些处理，可能导致崩溃或其他未定义行为。

由于 d 和 initialized 是独立的（除了程序员的意图），编译器和处理器可以几乎任意地重新排列它们，除了线程 1 的断言必须保留在循环之后。

依赖数据依赖产生的意外保证

这是 Java final 变量和 C++0x 中提议的 数据依赖排序 的一个问题。

首先执行

g = []
def Init():
    g.extend([1,2,3])
    return [1,2,3]
h = None

然后在两个线程中

线程 1	线程 2
while not h: pass	r1 = Init()
assert h == [1,2,3]	freeze(r1)
assert h == g	h = r1

如果 h 具有类似于 Java final 变量的语义（除了是一次性写入），那么即使第一个断言保证成功，第二个断言也可能失败。

像 final 提供的那些数据依赖保证只有在访问通过 final 变量进行时才有效。即使通过不同的路径访问相同的对象也是不安全的。不幸的是，由于处理器的运行方式，final 的保证在它们很弱的时候才便宜。

无数据竞态的程序是顺序一致的

我们希望程序员能够像它们是顺序一致的一样来推理他们的程序。由于很难判断你是否编写了先行发生竞态，我们只想要求程序员防止顺序竞态。Java 模型通过复杂的因果关系定义来实现这一点，但如果我们不想包含它，我们可以直接断言这个属性。

不会因为“凭空读取”而产生安全漏洞

如果程序产生了一个自证其值，它可能会暴露用户不希望程序看到的对象的访问。同样，Java 的模型通过因果关系定义来处理这个问题。我们或许可以通过禁止对共享变量进行推测性写入来防止这些安全问题，但我没有证明，而且 Python 可能也无需这些安全保证。

限制重排序，而不是定义先行发生

.NET [#CLR-msdn] 和 x86 [#x86-model] 的内存模型基于定义编译器允许哪些重排序。我认为，相比于推理程序的所有可能重排序，以先行发生模型进行编程更容易，并且通过插入足够的先行发生边来使程序正确比插入足够的内存屏障来做到这一点更容易。因此，尽管我们可以将一些重排序限制叠加在先行发生的基础上，但我认为 Python 的内存模型不应该完全是重排序限制。

原子、无序赋值

基本类型的赋值已经是原子的。如果你将 3<<72 + 5 赋给一个变量，没有线程可以看到该值的一部分。Jeremy Manson 建议我们将此扩展到所有对象。这允许编译器为了优化而重排序操作，而不会允许一些更令人困惑的未初始化值。基本思想是，当你为共享变量赋值时，读取者不能看到在新值赋给之前对新值所做的任何更改，也不能看到在新值赋给之后对旧值所做的任何更改。因此，如果我们有一个程序，如下所示：

最初，(d.a, d.b) == (1, 2)，并且 (e.c, e.d) == (3, 4)。我们还有 class Obj(object): pass。

线程 1	线程 2
r1 = Obj()	r3 = d
r1.a = 3	r4, r5 = r3.a, r3.b
r1.b = 4	r6 = e
d = r1	r7, r8 = r6.c, r6.d
r2 = Obj()
r2.c = 6
r2.d = 7
e = r2

(r4, r5) 可以是 (1, 2) 或 (3, 4)，但仅此而已。而 (r7, r8) 可以是 (3, 4) 或 (6, 7)，但仅此而已。与写入是释放而读取是获取不同，线程 2 可以看到 (e.c, e.d) == (6, 7) and (d.a, d.b) == (1, 2)（乱序）。

这给了编译器很大的优化灵活性，而不会让用户看到一些奇怪的值。然而，因为它依赖于数据依赖，它会带来一些它自己的惊喜。例如，编译器可以将上面的例子自由地优化为

线程 1	线程 2
r1 = Obj()	r3 = d
r2 = Obj()	r6 = e
r1.a = 3	r4, r7 = r3.a, r6.c
r2.c = 6	r5, r8 = r3.b, r6.d
r2.d = 7
e = r2
r1.b = 4
d = r1

只要它不让 e 的初始化移到 r2 的任何成员初始化之上，并且对 d 和 r1 类似。

这也帮助巩固了先行发生一致性。要看到问题，可以想象用户一拿到对象的引用就将其不安全地发布出去。该模型需要限制通过该引用可以读取的值。Java 说每个字段在任何人第一次看到对象之前都初始化为 0，但 Python 在定义“每个字段”时会遇到困难。如果我们改为说对共享变量的赋值必须看到至少与赋值发生时一样新的值，那么我们就不会遇到早期发布的任何问题。

两层保证

大多数其他具有未锁定变量保证的语言区分普通变量和 volatile/atomic 变量。它们为 volatile 变量提供更多保证。Python 很难做到这一点，因为我们不声明变量。这可能重要，也可能不重要，因为 Python 锁的开销并不比普通 Python 代码显著得多。如果我们想恢复这些层次，我们可以

1. 引入一组类似于 Java 的 [5] 或 C++ 的 [6] 的原子类型。不幸的是，我们不能用 = 来赋值。
2. 在不要求变量声明的情况下，我们也可以指定给定对象上的所有字段都是原子的。
3. 将 __slots__ 机制 [7] 扩展到一个并行的 __volatiles__ 列表，也许还有一个 __finals__ 列表。

顺序一致性

我们可以直接为 Python 采用顺序一致性。这可以避免上面提到的所有危险，但它也禁止了许多优化。据我所知，这是 CPython 当前的模型，但如果 CPython 能够优化掉一些变量读取，它将失去这个属性。

如果我们采用这个，Jython 的 dict 实现可能无法再使用 ConcurrentHashMap，因为后者只承诺创建适当的先行发生边，而不保证顺序一致性（尽管也许 Java volatile 完全有序的事实会传递过来）。Jython 和 IronPython 都可能需要为任何 __slots__ 数组使用 AtomicReferenceArray 或等效物。

适应 x86 模型

x86 模型是

1. 加载不会与其他加载重排序。
2. 存储不会与其他存储重排序。
3. 存储不会与较早的加载重排序。
4. 加载可能与不同位置的较早存储重排序，但不能与同一位置的较早存储重排序。
5. 在多处理器系统中，内存排序遵循因果关系（内存排序尊重传递可见性）。
6. 在多处理器系统中，同一位置的存储具有总顺序。
7. 在多处理器系统中，锁定的指令具有总顺序。
8. 加载和存储不会与锁定的指令重排序。

在获取/释放术语中，这似乎表明每个存储都是一个释放，每个加载都是一个获取。这比顺序一致性稍弱，因为它允许 不一致的顺序，但它禁止了 僵尸值 和产生它们的编译器优化。我们可能需要某种程度地削弱模型，以明确允许编译器消除冗余的变量读取。x86 模型在其他平台上实现起来也可能很昂贵，尽管由于 x86 非常普遍，这可能关系不大。

升级或降级到备用模型

我们可以采用一个初始内存模型，而不完全限制未来的实现。如果我们从一个弱模型开始，并希望以后变得更强，我们只需要改变实现，而不是程序。单个实现也可以保证比语言要求的更强的内存模型，尽管这可能会损害互操作性。另一方面，如果我们从一个强模型开始，并希望以后削弱它，我们可以添加一个 from __future__ import weak_memory 语句来声明某些模块是安全的。

CPython

使用 GIL 来保证其他线程不会看到奇怪的重排序，并且进行的优化很少，我相信它在字节码级别上实际上是顺序一致的。线程可以在任何两个字节码之间切换（而不是仅在语句之间），因此两个线程并发执行

i = i + 1

当 i 最初为 0 时，很容易得到 i==1 而不是预期的 i==2。如果它们执行

i += 1

相反，CPython 2.6 总是会给出正确的答案，但很容易想象另一个实现，在这个实现中，这个语句将不是原子的。

PyPy

也使用 GIL，但可能进行了足够的优化，违反了顺序一致性。我对这个实现知之甚少。

Jython

提供真正的并发，符合 Java 内存模型，并将所有对象字段（除了 __slots__ 中的字段？）存储在 ConcurrentHashMap 中，它提供相当强的顺序保证。函数中的局部变量可能保证较少，如果它们被捕获到闭包中然后传递给另一个线程，这些保证就会显现出来。

IronPython

在 CLR 内存模型下提供真正的并发，这可能保护它免受未初始化值的影响。IronPython 使用锁定的映射来存储对象字段，提供的保证至少与 Jython 一样多。