Rust 内存模型

Memory model

在各类偏系统方向的面试宝典中，一个常见的知识点就是对于volatile关键词的理解。照本宣科的回答通常是说，加了这个关键词，会禁用编译器对这个变量的优化，如果面试官进一步压迫，到底是禁用了什么优化呢，有人会回答说如果不加这个修饰关键词，编译器可能会将该变量优化至寄存器，而加了这个关键词之后，编译器会保证每次读取该变量时，都从内存中重新读取，确保读到的值是最新鲜的。大多数人会止步于此，假如面试官继续压迫，加了这个关键词之后，是否能用于不同线程之间的同步，如果能的话，该怎么使用呢，如果不能的话，是因为什么原因呢。这个时候，如果不是对这个关键词有切身的体会，是很难讲清楚其中细节的。

纸上得来终觉浅，绝知此事要躬行。memory model可谓是在践行这句话方面最为杰出的代表。

首先来思考下，在计算机科学语境中的同步该如何理解？可以从两个方面来看：
1 可见性。当某个线程正在修改某个对象的状态，而另一个线程正在使用该对象时，使用该对象状态的线程能立即感知到这个对象状态的变化。
2 原子性。当某个线程正在修改某个对象的状态，而另一个线程正在使用该对象时，使用该对象的线程得到是该对象的完整状态，而不能存在中间状态。

只有同时满足上述两项，才符合我们对于“同步”的预期。

原子性相对好理解，“没有中间状态”就是原子性，比如在x86-64内存对齐的情况下，对于64位变量的读写就是符合原子性的，在不加锁读取变量时，只可能读取到老值与新值两者之一，而不会出现第三种情况。

通常来讲，原子类型会提供以下操作：

• Load：从原子类型读取值
• Store：为一个原子类型写入值
• CAS（Compare-And-Swap）：比较并交换
• Swap：交换
• Fetch-add（sub/and/or）：表示一系列的原子的加减或逻辑运算

可见性的概念则相对复杂。

Memory order

可见性概念的复杂性在于编译阶段与执行阶段均可能发生指令重排，而指令重排会带来一些非预期的变化。
先看一段简单的代码：

int status;
std::atomic_bool flag { false };

// run in thread1
void producer() {
    status = 7;  // (1)
    flag.store(true);  // (2)
}

// run in thread2
void consumer() {
    while (!flag.load());  // (3)
    assert(status == 7);  // (4)
}

启动两个线程，分别运行producer与consumer，上述断言将会有可能失败。直观看起来，flag变成true之后才进行断言，而在flag变成true之前，status就已经被更新。出现断言失败的原因是，执行的顺序并不完全与代码一致。

编译器会根据优化级别重排指令，cpu在执行时，也会调整指令顺序，CPU读写Cache也可能并没有写回内存，所以，企图在多线程环境中通过某原子量来做非原子量的同步是不可靠的。

为了使得断言成功，必须确保(1)在(2)之前执行，(4)在(3)之后执行。

int status;
std::atomic_bool flag { false };

// run in thread1
void producer() {
    status = 7;  // (1)
    flag.store(true, std::memory_order_release);  // (2)
}

// run in thread2
void consumer() {
    while (!flag.load(std::memory_order_acquire));  // (3)
    assert(status == 7);  // (4)
}

经过改造后，(1)不会被重排到(2)之后，(4)不会被提前到(3)之前，在执行(3)时，如果发现flag发生变化，此时(1)必然已经执行了，所以在执行(4)时断言就不会失败了。

回到volatile，其对应的汇编指令为:
__asm__ __volatile__ ("" ::: "memory");
这条指令仅禁用了编译阶段的重排，但是并没有阻止执行阶段的重排，并且也没有保证原子性，所以volatile无法在多线程执行环境中起到变量同步的作用。

C++ 11

为了简化应用程序直接控制内存顺序，C++ 11定义了6种可以用于原子变量的内存顺序：

• momory_order_relaxed
• memory_order_consume
• memory_order_acquire
• memory_order_release
• memory_order_acq_rel
• memory_order_seq_cst

利用这些预定义的模型，无需在应用代码中手动添加barrier等约束逻辑。

这6种情况实际上描述了三种内存模型：

• sequential consistent：memory_order_seq_cst，顺序一致次序，在这个模式下，多线程程序的行为就像是这些操作都以一种特定顺序被单线程程序执行
• relaxed：memory_order_seq_cst，不保证顺序，取决于编译器的优化结果与cpu的乱序执行情况。
• acquire/release：memory_order_consume, memory_order_acquire, memory_order_release, memory_order_acq_rel。

基础的内存模型其实是以下两种：

• Acquire：针对某个读操作，该读操作之后的读操作或写操作，这两种情况下的指令顺序不能改变
• Release：针对某个写操作，该写操作之前的读操作或写操作，这两种情况下的执行顺序不能改变

开发者可以要求编译器和硬件架构在上述四种情况下分别做出规约，即：

• 读读(LL)。读操作之后的读操作，顺序不能改变；
• 读写(LS)。读操作之后的写操作，顺序不能改变；
• 写读(SL)。写操作之后的读操作，顺序不能改变；
• 写写(SS)。写操作之后的写操作，顺序不能改变。

通常来说，越是要求强一致，就越是会损失性能，但在任何时候，首要目标都是要先确保功能的正确性。目前，现代的编译器与语言基本都会提供抽象的语义实现，简化编码过程。

LLVM

LLVM也定义了内存顺序：

• NotAtomic。
• Unordered
• Monotonic。对应于C++ 11中的memory_order_relaxed
• Acquire。对应于C++ 11中的memory_order_acquire
• Release。对应于C++ 11中的memory_order_release
• AcquireRelease。对应于C++ 11中的memory_order_acq_rel
• SequentiallyConsistent。对应于C++ 11中的memory_order_seq_cst

Rust

Rust原子操作中用到的内存顺序定义来自于std::sync::atomic::Ordering::SeqCst，定义为一个枚举类型。

pub enum Ordering {
    Relaxed,
    Release,
    Acquire,
    AcqRel,
    SeqCst,
}

• Relaxed。表示不进行顺序干涉，也就是开发者不会干预线程顺序，线程只进行原子操作
• Release。对于使用Release的store操作，在它之前所有使用Acquire的load操作都是可见的
• Acquire。对于使用Acquire的load操作，在它之前的所有使用Release的store操作也都是可见的
• AcqRel。它代表读时使用Acquire顺序的load操作，写时使用Release顺序的store操作
• SeqCst。它代表读时使用Acquire顺序的load操作，写时使用Release顺序的store操作

一般情况下，如果不是特别在意性能，可以使用SeqCst，如果需要考虑性能，那么选择满足需求的最低干预即可。

硬件平台支持

不同cpu arch支持的乱序执行模式是不同的，在进行跨平台支持时必须慎重考虑。

Type	Alpha	ARMv7	PA-RISC	x86	AMD64
Loads can be reordered after loads	Y	Y	Y
Loads can be reordered after stores	Y	Y	Y
Stores can be reordered after stores	Y	Y	Y
Stores can be reordered after loads	Y	Y	Y	Y	Y
Atomic can be reordered with loads	Y	Y	Y
Atomic can be reordered with stores	Y	Y
Dependent loads can be reordered	Y
Incoherent instruction cache pipeline	Y	Y

x86/amd64平台仅支持SL，属于强内存顺序平台，而ARM平台支持全部4种模式。

典型场景

事件通知

再回到前文生产者与消费者模型：

int status;
std::atomic_bool flag { false };

// run in thread1
void producer() {
    status = 7;  // (1)
    flag.store(true, std::memory_order_release);  // (2)
}

// run in thread2
void consumer() {
    while (!flag.load(std::memory_order_acquire));  // (3)
    assert(status == 7);  // (4)
}

生产者与消费者通过flag来同步status值，生产者先更新status，然后再修改状态，消费者先检测到状态变化，再读取status。

• 对于生产者：flag更新之前的行为不能对推迟到更新之后，所以LS乱序与SS乱序是不被允许的。
• 对于消费者：flag读取之后的行为不能提前到读之前，所以LL乱序与LS是不被允许的。

总结起来，仅有SL乱序是允许的，在x86与amd64两种架构下，cpu仅支持SL乱序，所以对于这个生产者消费者模型，仅需要确保编译阶段不出现乱序即可。

再回到volatile，这条指令禁用了编译阶段的重排，但是并没有阻止执行阶段的重排，并且也没有保证原子性，尽管如此，在这个场景下，确保原子性的前提下，使用来同步flag也是足够的。

无锁队列

无锁环形队列简单理解就是一个数组，通过头尾两个索引来控制读写，简化版定义如下：

struct simple_ring {
  int queue[SIZE]; 
  int head; 
  int tail;
}

约定head为队首元素索引，tail为队尾元素索引。
读写实现为：

ErrorType read(int *v) { 
    if (head == tail) { 
        return EMPTY; 
    } 
    *v = queue[head]; 
    head = (head + 1) % SIZE; 
    return SUCCESS; 
} 
ErrorType write(const int *v) { 
    if (head == (tail + 1) % SIZE) { 
        return FULL; 
    } 
    queue[tail] = *v; 
    tail = (tail + 1) % SIZE; 
    return SUCCESS; 
} 

为了实现无锁队列，对使用模型进行如下限制：

• 队列只能单读单写
• 头尾索引使用volatile修饰

在读写实现中，读操作只会读取head，读取tail与queue，而写操作只会读head，写tail与queue。在内存对齐的情况下，head与tail均为int型，两个值的读写是满足原子要求的，在这个前提下，无论读写在两个线程，或者是两个进程中执行时，无论遇到怎样的kernel层面的调度穿插，这两个值都不会出现冲突，顶多出现write线程更新后，read线程读到了老值，但是下次继续读的时候，还是能取到，并且不会冲乱当前正在写的数据。

下面来分析状态一致性，之所以两个并行的读写线程之间不会出现混乱，是因为两者在操作时，均按照读值-处理-修改的节奏进行，只要在处理之前，读取到的值是正确的，那么处理与修改阶段也是正确的，所以关键在于head与tail两个索引值如何能确保正确性。

对于head与tail两个变量而言，读写操作中的执行顺序必须严格遵守代码顺序。假设在读操作中，对指针v的赋值过程被推迟到了对head的修改之后，那么读取出来的值就不正确了。同理，在写操作中，如果tail的更新提前到了queue的赋值之前，写到队列中的数据也不正确了。

总结起来，无锁队列的读写操作需要满足以下条件：

• 读：先读head，再改head，改不能在读之前。
• 写：先读tail内存，再改tail，读不能在改之后。

事实上，由于x86与amd64下仅支持SL，所以，将head与tail进行volatile修饰即可达到目的。