Memory Ordering

对于每个 atomic 操作，都需要显示的指定 Ordering，Rust 提供了 Relaxed，Release，Acquire，AcqRel，以及 SeqCst 这些 Ordering 的支持，使用不同的 Ordering 会让编译器或者 CPU 对某些指令进行重新排序执行，所以为了更正确的写出 lock-free 的代码，了解这些 Ordering 是如何工作的，就显得非常重要了。

rust 提供的 Ordering 支持有： Relaxed，Release，Acquire，AcqRel，以及 SeqCst。

关键字

描述atomic 操作之间关系的概念，synchronizes-with 和 happens-before。

synchronizes-with

简单来说，两个线程 A 和 B，以及一个支持原子操作的变量 x，如果 A 线程对 x 写入了一个新的值（store），而 B 线程在 x 上面读取到了这个新的值（load），我们就可以认为，A 的 store 就是 synchronizes-with B 的 load 的。

操作 A synchoronizes-with 操作 B（A->B）

Happens-before

如果一个操作 B 能看到之前操作 A 产生的结果，那么 A 就是 happens-before B 的。譬如在单线程里面，如果一个操作 A 的语句在操作 B 的前面执行，通常叫做 sequenced-before，那么 A 就是 happens-before B 的。

几种 Order 的介绍

Relaxed ordering

适用场景：需要对某个变量进行原子操作，而不需要考虑多个线程同步的情况，譬如，reference counter。

Acquire-Release ordering

Acquire 和 Release 通常都是需要成对使用的。
当对 store 使用 Release ordering 之后，后续任何的 Acquire ordering 的 load 操作，都会看到之前 store 的值。
通过 Acquire-Release，我们能支持 synchronizes-with。

fn write_x_then_y() {
    X.store(true, Ordering::Relaxed);
    Y.store(true, Ordering::Release);
}
fn read_y_then_x() {
    while !Y.load(Ordering::Acquire) {}
    if X.load(Ordering::Relaxed) {
        Z.fetch_add(1, Ordering::SeqCst);
    }
}
fn main() {
    let t1 = thread::spawn(move || {
        write_x_then_y();
    });
    let t2 = thread::spawn(move || {
        read_y_then_x();
    });
    t1.join().unwrap();
    t2.join().unwrap();
    assert_ne!(Z.load(Ordering::SeqCst), 0);
}

Sequence ordering

不光提供了 Acquire 和 Release 的 ordering 支持，同时也确保所有的线程看到完全一致的原子操作顺序。

fn write_x() {
    X.store(true, Ordering::SeqCst);    // 1
}
fn write_y() {
    Y.store(true, Ordering::SeqCst);    // 2
}
fn read_x_then_y() {
    while !X.load(Ordering::SeqCst) {}
    if Y.load(Ordering::SeqCst) {       // 3
        Z.fetch_add(1, Ordering::SeqCst);  
    }
}
fn read_y_then_x() {
    while !Y.load(Ordering::SeqCst) {}
    if X.load(Ordering::SeqCst) {       // 4
        Z.fetch_add(1, Ordering::SeqCst); 
    }
}
fn main() {
        let t1 = thread::spawn(move || {
        write_x();
    });
    let t2 = thread::spawn(move || {
        write_y();
    });
    let t3 = thread::spawn(move || {
        read_x_then_y();
    });
    let t4 = thread::spawn(move || {
        read_y_then_x();
    });
    t1.join().unwrap();
    t2.join().unwrap();
    t3.join().unwrap();
    t4.join().unwrap();
    assert_ne!(Z.load(Ordering::SeqCst), 0);
}

上面的例子中，只有使用 SeqCst ordering，才能保证 Z 最后的值不为 0，任何其他的 ordering，都不能保证。
Write X，Y 发生在不同的线程中，当 t3 线程先读到 X，后读到 Y，那么 t4 线程也肯定会先读到 X，后读到 Y。
SeqCst 在有些时候会有性能瓶颈。因为它要确保操作在所有线程之前全局同步。

Memory fence

还可以使用 memory fence 来保证 synchronizes-with，如下：

fn write_x_then_y() {
    X.store(true, Ordering::Relaxed); // 1
    fence(Ordering::Release);         // 2
    Y.store(true, Ordering::Relaxed); // 3   
}
fn read_y_then_x() {
    while !Y.load(Ordering::Relaxed) {}  // 4
    fence(Ordering::Acquire);            // 5
    if X.load(Ordering::Relaxed) {       // 6
        Z.fetch_add(1, Ordering::SeqCst);
    }
}
fn main() {
    let t1 = thread::spawn(move || {
        write_x_then_y();
    });
    let t2 = thread::spawn(move || {
        read_y_then_x();
    });
    t1.join().unwrap();
    t2.join().unwrap();
    assert_ne!(Z.load(Ordering::SeqCst), 0);
}

2 Release fence 是 synchronizes-with 5 Acquire fence，所以 1 肯定会在 6 之前执行。

Epilogue

要弄清楚 memory ordering，其实并不是一件容易的事情，不过多数时候，为了不出错，使用 SeqCst 就成。

Go memory model

Dekker’s test - Litmus test

Litmus test is a tool to enumerate all the possibilities of CPU execution.
http://diy.inria.fr/www/?recore=aarch64#

Go 夜读笔记
不同的编译器以及微处理器结果不一样。
编译器行为包括：

• Constant folding（常量提前计算）
• Code motion（不影响函数的情况下会对一些执行顺序做移动）

注：

1. No clear defintion for atomics so far；
2. Some operaions will set up Happens-Before relationsship；
3. Extended discussion: Dose explicit synchronization always be slower than atomic? Yes, in most cases. But…(以后的 hardware transcation 的方式如果没有资源竞争时，性能会更好)

For Gophers

• Do not communicate by sharing memory; instead, share memory by communicating.
• Go race dector may help to exam some memory coherency issues.(Note: There might be false positives and false negatives!)
• Don’t be clever!