编程宝库 - 技术改变世界

编程宝库

Rust高级编程

Rust 原子操作

Rust几乎全部抄袭了C11关于原子操作的内存模型。这么做并不是因为这个模型多么的优秀或者易于理解。事实上，这个模型非常的复杂，而且有一些已知的缺陷。不过，所有的原子操作模型其实都不怎么样，我们不得不因此做出一些妥协。至少，这么做可以让我们借鉴当前关于C的研究成果。

在本书中完整地介绍这个模型是不现实的。模型是基于一个让人神经错乱的因果关系图构建的，需要一整本书去实际地理解它。如果你想知道其中的细节，请看C's specification(Section 7.17)。不过，我们还是会尽量涵盖它的基本内容，以及Rust开发者会面对的问题。

C11的内存模型试图同时满足开发者对语义的要求、编译器对优化的要求、还有硬件对千奇百怪混乱状态的要求。而我们只希望能写一段程序做我们想让它做的事情，并且要做得快。是不是很不错？

编译器重排

编译器努力地通过各种复杂的变换，尽可能减少数据依赖和消除死代码。特别是，它可能会彻底改变事件的顺序，或者干脆让某些事件永远不会发生！如果我们写了这样的代码

x = 1;
y = 3;
x = 2;

编译器会发现这段程序最好能变成

x = 2;
y = 3;

事件的顺序变了，还有一个事件完全消失了。在单线程的情况下，我们不会察觉有什么区别：毕竟代码执行后可以得到和我们期望的完全相同的状态。但如果程序是多线程的，我们可能确实需要在y被赋值前将x赋值为1。我们希望编译器能做出这一类优化，因为这可以提升程序的性能。可另一方面，我们还希望我们写的程序能完全按照我们的指令行事。

硬件重排

即使编译器完全明白了我们的意图并且按照我们的期望去工作，硬件还是有可能来找麻烦的。麻烦来自于在内存分层模式下的CPU。你的硬件系统里确实有一些全局共享的内存空间，但是在各个CPU核心看来，这些内存都离得太远，速度也太慢。CPU希望能在它的本地cache里操作数据，只有在cache里没有需要的内存时才委屈地和共享内存打交道。

毕竟，这不就是cache存在的全部意义吗？如果每一次读取cache都要再去检查共享内存看看数据有没有变化，那么cache还有什么价值呢？最终的结果就是，硬件不能保证相同的事件在两个不同的线程里一定有相同的执行顺序。如果要保证这点，我们必须有一些特殊的方法告诉CPU稍微变笨一点。

比如，我们已经成功地让编译器保证下面的逻辑：

初始状态: x = 0, y = 1

线程1         线程2               
y = 3;       if x == 1 {
x = 1;           y *= 2;
             }

这段程序实际上有两种可能的结果：

y = 3：线程2在线程1完成之前检查了x的值
y = 6：线程2在线程1完成之后检查了x的值

但是硬件还会创造出第三种状态：

y = 2：线程2看到了x = 1，但是没看到y = 3，接下来用计算结果覆盖了y = 3

不同的CPU提供了不同的保证机制，但是详细区分它们没什么意义。一般来说只需要把硬件分为两类：强顺序的和弱顺序的。最明显的，x86/64平台提供了强顺序保证，而ARM提供弱顺序保证。对于并发编程来说，它们也会导致不同的结果：

在强顺序硬件上要求强顺序保证的开销很小，甚至可能为零，因为硬件本身已经无条件提供了强保证。而弱保证可能只能在弱顺序硬件上获得性能优势。
在强顺序硬件上要求过于弱的顺序保证有可能也会碰巧成功，即使你的程序是错误的。如果可能的话，在弱保证硬件上测试并发算法。

数据访问

C11的内存模型允许我们接触到程序的因果关系，希望以此满足多个方面的要求。一般来说，就是要确定程序的各个部分以及运行它们的多个线程之前的时间先后关系。在严格的先后关系没有确定的时候，硬件和编译器有足够的空间做一些激进的优化。而关系确定之后，它们的优化就必须很小心了。我们通过“数据访问”和“原子访问”来控制这种关系。

数据访问是程序设计世界的基础。它们都是非同步的，而且编译器可以做出一些激进的优化。尤其是，编译器认定数据访问都是单线程的，所以可以对它随意地重排。硬件也可以把数据访问的重排的结果移植到其他的线程上去，无论结果多么的滞后和不一致都可以。数据访问最严重的问题是，它会导致数据竞争。数据访问对硬件和编译器很友好，但是我们已经看到了编写和它相关的同步程序是十分可怕的。事实上，它的同步语义太弱了。

只依靠数据访问是不可能写出正确的同步代码的。

原子访问可以告诉硬件和编译器，我们的程序是多线程的。每一个原子访问都关联一种“排序方式”，以确定它和其他访问之间的关系。归根结底，就是告诉编译器和硬件什么是它们不能做的。对于编译器，主要指的是命令的重排。而对于硬件，指的是写操作的结果如何同步到其他的线程。Rust暴露的排序方式包括：

顺序一致性(SeqCst)
释放(Release)
获取(Acquire)
Relaxed

（注意：我们没有暴露C11的consume顺序）

TODO: negative reasoning vs positive reasoning? TODO: "can't forget to synchronize"

（译注：不知道TODO的都是什么，需要等到DO过了之后才能明白）

顺序一致性

顺序一致性是所有排序方式中最强大的，包含了其他所有排序方式的约束条件。直观上看，顺序一致性操作不能被重排：在同一个线程中，SeqCst之前的访问永远在它之前，之后的访问永远在它之后。只使用顺序一致性原子操作和数据访问就可以构建一个无数据竞争的程序，这种程序的好处是它的命令在所有线程上都有着唯一的执行流程。而且这个执行流程又很容易推导：它就是每个线程各自执行流程的交叉。如果你使用更弱的原子排序方式的话，这一点并不一定继续有效。

顺序一致性给开发者的便利并不是免费的。即使是在强顺序平台上，顺序一致性也会产生内存屏障(memory fence)。

事实上，顺序一致性很少是程序正确性的必要条件。但是，如果你对其他内存排序方式模棱两可的话，顺序一致性绝对是你正确的选择。程序执行得稍微慢一点总比执行出错要好！将它变为具有更弱一致性的原子操作也很容易，只要把SeqCst变成Relaxed就完工了！当然，证明这种变化的正确性就是另外一个问题了。

获取-释放

获取和释放经常成对出现。它们的名字就提示了它们的应用场景：它们适用于获取和释放锁，确保临界区不会重叠。

直观看起来，acquire保证在它之后的访问永远在它之后。可在它之前的操作却有可能被重排到它后面、类似的，release保证它之前的操作永远在它之前。但是它后面的操作可能被重排到它前面。

当线程A释放了一块内存空间，紧接着线程B获取了同一块内存，这时因果关系就确定了。在A释放之前的所有写操作的结果，B在获取之后都能看到。但是，它们和其他线程之间没有确定因果关系。同理，如果A和B访问的是不同的内存，它们也没有因果关系。

所以，释放-获取的基本用法很简单：你获取一块内存并进入临界区，然后释放内存并离开临界区。比如，一个简单的自旋锁可能是这样的：

use std::sync::Arc;
use std::sync::atomic::{AtomicBool, Ordering};
use std::thread;

fn main() {
    let lock = Arc::new(AtomicBool::new(false)); // 我上锁了吗？

    // ...用某种方式把锁分发到各个线程...

    // 设置值为true，以尝试获取锁
    while lock.compare_and_swap(false, true, Ordering::Acquire) {}
    // 跳出循环，表明我们获取到了锁！

    // ...恐怖的数据访问...

    // 工作完成了，释放锁
    lock.store(false, Ordering::Release);
}

在强顺序平台上，大多数的访问都有释放和获取的语义，释放和获取通常是无开销的。不过在弱顺序平台上不是这样。

Relaxed

Relaxed访问是最弱的。它们可以被随意重排，也没有先后关系。但是Relaxed操作依然是原子的。也就是说，它并不算是数据访问，所有对它的读-修改-写操作都是原子的。Relaxed操作适用于那些你希望发生但又并不特别在意的事情。比如，多线程可以使用Relaxed的fetch_add来增加计数器，如果你不使用计数器的值去同步其他的访问，这个操作就是安全的。

在强顺序平台上使用Relaxed没什么好处，因为它们通常都有释放-获取语义。不过，在弱顺序平台上，Relaxed可以获取更小的开销。

下一节：Rust 实现 Vec

Rust 高级编程

我们要把所有的内容汇总起来，从头开始写一个std::Vec。因为所有编写非安全代码的工具都是不稳定的，这个项目只保证短期有效（从Rust 1.9.0开始）。除了分配器API，我们要用到的大部分不稳定代码都尽量保证和最 ...

Rust Send和Sync

Rust 实现 Vec