顺序一致性

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

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

先行一致性

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

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

我们将同步于边界的来源称为相关变量上的释放操作，并将目标称为获取操作。

先行发生顺序是程序顺序与同步于边界的传递闭包。也就是说，如果操作A先于操作B发生，则

• A 在程序顺序中位于 B 之前（这意味着它们在同一线程中运行）
• A 同步于 B
• 您可以通过遵循从 A 开始的先行发生边到达 B。

如果每个读取R都看到对同一变量的写入W的值，则程序的执行是先行一致的

• R 不会先于W发生，并且
• 没有其他写入V在R有机会看到它之前覆盖了W。（也就是说，不可能出现W先于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。

一个好的编译器希望优化掉初始化 r5 时冗余的加载 p.x 操作，只需重复利用已加载到 r2 中的值即可。如果线程 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	由 r5 = r1.x 优化而来，因为 r2 == r1.x。

不一致的排序

来自 N2177: 原子操作的顺序一致性，也称为独立读写（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
如果 r1 != 0	如果 r2 != 0
y = 42	x = 42

可以 r1 == r2 == 42？？？

在顺序一致的执行中，无法获得对同一变量的相邻读写操作，因此程序应被视为正确同步（尽管很脆弱），并且应该只产生 r1 == r2 == 0。但是，以下执行是先行一致的。

语句	值	线程
r1 = x	42	1
如果 r1 != 0	真	1
y = 42		1
r2 = y	42	2
如果 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
如果 r1 != 42
y = r1

如果推测的值是秘密对象，或者指向对象曾经占据的内存，则可能会产生安全漏洞。Java 非常关心此类安全漏洞，但 Python 可能不关心。

未初始化的值（直接）

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

最初，d == None。

线程 1	线程 2
当 d 为假时：通过	d = [3, 4]
断言 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 的内存，它可能会看到陈旧的值。据我所知，这实际上只可能发生在 Alpha 和可能 Itanium 上，我们可能无论如何都必须防止它以避免崩溃。

未初始化的值（标志）

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

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

线程 1	线程 2
当 initialized 为假时：通过	d[‘a’] = 3
r1 = d[‘a’]	initialized = True
r2 = r1 == 3
断言 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
当 h 为假时：通过	r1 = Init()
断言 h == [1,2,3]	freeze(r1)
断言 h == g	h = r1

如果 h 的语义类似于 Java 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 很难定义“每个字段”。如果我们改为说对共享变量的赋值必须看到至少与赋值发生时一样最新的值，那么我们就不会遇到早期发布带来的任何问题。

两层保证

大多数其他对未加锁变量有任何保证的语言都区分普通变量和易变/原子变量。它们为易变变量提供了更多保证。Python 无法轻松做到这一点，因为我们不声明变量。这可能重要也可能不重要，因为 Python 锁的开销并不比普通的 Python 代码高出很多。如果我们想找回这些层级，我们可以

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

顺序一致性

我们可以简单地为 Python 采用顺序一致性。这避免了上面提到的所有 风险，但也禁止了很多优化。据我所知，这是当前 CPython 的模型，但如果 CPython 学会优化掉一些变量读取，它就会失去此属性。

如果我们采用这种方法，Jython 的 dict 实现可能无法再使用 ConcurrentHashMap，因为后者仅承诺创建适当的先行发生边，而不是顺序一致（尽管 Java 易变变量完全有序的事实可能得以保留）。Jython 和 IronPython 可能都需要使用 AtomicReferenceArray 或等效项来处理任何 __slots__ 数组。

采用 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 一样多的保证。