简介

原子类型在构建无锁数据结构，跨线程共享数据，线程间同步等多线程并发编程场景中起到至关重要的作用。本文将从Rust提供的原子类型和原子类型的内存排序问题两方面来介绍。

Rust原子类型

Rust规范库提供的原子类型在std::sync::atomic模块下。Rust提供了AtomicBool, AtomicU8, AtomicU16, AtomicUsize等原子类型。上面咱们以AtomicUsize为例介绍原子类型提供的原子操作。根本的load，store， swap原子操作就不过多介绍了。第一个要介绍的就是重要的compare-and-swap(CAS)原子操作，绝大部分无锁数据结构都或多或少依赖CAS原子操作。Rust提供的compare_and_swap接口如下：

pub fn compare_and_swap(&self,    current: usize,    new: usize,    order: Ordering) -> usize

compare_and_swap承受一个冀望的值和一个新的值，这里咱们先疏忽掉Ordering，前面会具体介绍，如果变量的值等于冀望的值，就将变量值替换成新的值返回胜利，否则不做任何批改并返回失败。compare_and_swap从语义上蕴含了读(load)语义和写(store)语义，先读出变量的值，和期望值比拟，而后写入内存。原子操作保障了这三个步骤是原子的，在三个步骤之间不会插入其余指令从而导致变量值被批改。从1.50.0开始compare_and_swap被deprecated了，当初须要应用compare_exchange和compare_exchange_weak接口来实现CAS原子操作。

pub fn compare_exchange(    &self,    current: usize,    new: usize,    success: Ordering,    failure: Ordering) -> Result<usize, usize>pub fn compare_exchange_weak(    &self,    current: usize,    new: usize,    success: Ordering,    failure: Ordering) -> Result<usize, usize>

compare_exchange比compare_and_swap多了一个Ordering，两个Ordering别离作为CAS胜利的Ordering和失败的Ordering，前面会有解说，这里先跳过。从源代码能够看出compare_and_swap就是用compare_exchange实现的，只是compare_and_swap间接用胜利状况下的Ordering生成在失败状况下的Ordering，compare_exchange则有更高的灵活性。

pub fn compare_and_swap(&self, current: $int_type, new: $int_type, order: Ordering) -> $int_type {    match self.compare_exchange(current,                                new,                                order,                                strongest_failure_ordering(order)) {        Ok(x) => x,        Err(x) => x,    }}

既然有了compare_exchange，那compare_exchange_weak是做什么用的呢？从官网文档中能够看出两个API的惟一区别是compare_exchange_weak容许spuriously fail。那么什么是spuriously fail，在x86平台上CAS是一条指令实现的，这两个API在x86平台上成果没有区别，然而在arm平台上，CAS是由两条指令实现的LL/SC(Load-link/store-conditional)，在arm平台下会产生spuriously fail，来自Wikipedia的解释

Real implementations of LL/SC do not always succeed even if there are no concurrent updates to the memory location in question. Any exceptional events between the two operations, such as a context switch, another load-link, or even (on many platforms) another load or store operation, will cause the store-conditional to spuriously fail.

简略的翻译就是，即便变量的值没有被更新LL/SC也不是100%胜利，在LL/SC之间的异样事件如上下文切换，另外的LL，甚至load或者store都会导致spuriously fail。因为spuriously fail的存在，arm平台上compare_exchange是compare_exchange_weak加上一个loop实现的。通常咱们在应用CAS的时候会把它放在一个loop中，重复重试直到胜利，在这种状况下用compare_exchange_weak会取得肯定的性能晋升，如果用compare_exchange则会导致循环套循环。那咱们该如何抉择compare_change和compare_exchange_weak呢？如果你想在loop中应用CAS，绝大部分状况下应用compare_exchange_weak，除非你在每一次loop中做的事件很多，spuriously fail会导致很大的overhead即便它很少产生，这种状况下应用compare_exchange。再或者你应用loop就是为了防止spuriously fail，那间接应用compare_exchange就能够达到你的目标。

接下来介绍另外一个重要的原子操作fetch-and-add。

pub fn fetch_add(&self, val: usize, order: Ordering) -> usize

fetch_add也蕴含了读写两层语义，只是和CAS比起来它不关怀变量以后的值，所以它肯定胜利。fetch_add个别用来做全局计数器。Rust提供了一系列的fetch_and_xxx操作，其中比拟乏味的是fetch_update:

pub fn fetch_update<F>(    &self,    set_order: Ordering,    fetch_order: Ordering,    f: F) -> Result<usize, usize>where    F: FnMut(usize) -> Option<usize>,

它会承受一个函数，并将函数利用到变量上，把生成的值写回变量中，因为CPU不反对相似的指令，所以其实fetch_update是应用CAS来实现原子性的。源代码如下，咱们能够看这里应用的是compare_exchange_weak，因为它在一个loop中。

pub fn fetch_update<F>(&self,                       set_order: Ordering,                       fetch_order: Ordering,                       mut f: F) -> Result<$int_type, $int_type>where F: FnMut($int_type) -> Option<$int_type> {    let mut prev = self.load(fetch_order);    while let Some(next) = f(prev) {        match self.compare_exchange_weak(prev, next, set_order, fetch_order) {            x @ Ok(_) => return x,            Err(next_prev) => prev = next_prev        }    }    Err(prev)}

内存排序

Rust提供了五种内存排序，由弱到强如下，并且内存排序被标记为#[non_exhaustive]示意将来可能会退出新的类型。

#[non_exhaustive]pub enum Ordering {    Relaxed,    Release,    Acquire,    AcqRel,    SeqCst,}

Rust的内存排序和C++20保持一致。内存排序作用是通过限度编译器和CPU的reorder，来使得多个线程看到的内存程序和咱们程序所冀望的一样，所以内存排序次要针对的是内存的读(load)写(store)操作。编译器和CPU会在编译时和运行时来reorder指令来达到晋升性能的目标，从而导致程序中代码程序会和真正执行的程序可能会不一样，然而reorder的前提是不会影响程序的最终后果，也就是说编译器和CPU不会reorder互相有依赖的指令从而毁坏程序本来的语义。比方说两条CPU指令，指令A读取一块内存，指令B写一块内存，如果CPU发现指令A要读取的内容在cache中没有命中须要去内存中读取，须要花额定的CPU cycle，如果指令B要操作的内存曾经在cache中命中了，它能够抉择先执前面的指令B。这时候内存排序的作用就体现进去了，内存排序通知编译器和CPU哪些指令能够reorder哪些不能够。接下来别离介绍每一种内存排序的意义。

  • Relaxed：Relaxed Ordering不施加任何限度，CPU和编译器能够自在reorder，应用了Relaxed Ordering的原子操作只保障原子性。
// Global variblestatic x: AtomicU32 = AtomicU32::new(0);static y: AtomicU32 = AtomicU32::new(0);// Thread 1let r1 = y.load(Ordering::Relaxed);x.store(r1, Ordering::Relaxed);// Thread 2let r2 = x.load(Ordering::Relaxed); // Ay.store(42, Ordering::Relaxed); // B

这段程序是容许产生r1 == r2 == 42。依照失常的程序执行，这个后果看似不合理，然而因为应用了Relaxed Ordering，CPU和编译器能够自在reorder指令，指令B被reorder到指令A之前，那就会产生r1 == r2 == 42

  • Release：Release Ordering是针对写操作(store)的，一个应用了Release Ordering的写操作，任何读和写操作（不限于对以后原子变量）都不能被reorder到该写操作之后。并且所有以后线程中在该原子操作之前的所有写操作（不限于对以后原子变量）都对另一个对同一个原子变量应用Acquire Ordering读操作的线程可见。Release Ordering写和Acquire Ordering读要配对应用从而在两个或多个线程间建设一种同步关系。具体例子在介绍完Acquire之后一起给出。
  • Acquire：Acquire Ordering是针对读操作(load)的，一个应用了Acquire Ordering的读操作，任何读和写操作（不限于对以后原子变量）都不能被reorder到该读操作之前。并且以后线程能够看到另一个线程对同一个原子变量应用Release Ordering写操作之前的所有写操作（不限于对以后原子变量）。
    如果后面的例子中load应用Acquire Ordering，store应用Release Ordering，那么reorder就不会产生，r1 == r2 == 42的后果就不会产生。Acquire和Release动作特地像锁的加锁和开释锁的操作，因而Acquire Ordering和Release Ordering常被用在实现锁的场景。看上面的例子
// Global variblestatic DATA: AtomicU32 = AtomicU32::new(0);static FLAG: AtomicBool = AtomicBool::new(false);// Thread 1DATA.store(10, Ordering::Relaxed); // AFLAG.store(true, Ordering::Release); // B// Thread 2while !FLAG.load(Ordering::Acquire) {} // Cassert!(DATA.load(Ordering::Relaxed) == 10); // D

这段程序展现了两个线程之间同步的一种形式，在线程1中咱们在共享内存中写入数据，而后把FLAG置成true，表明数据写入实现，在线程2中，咱们用一个while循环期待FLAG被置成true，当FLAG被置成true之后，线程2肯定会读到共享内存中的数据。线程1中的Release Ordering写和线程2中的Acquire Ordering读建设了程序。当线程2跳出C行的循环表明它能够读到线程1在B行对FLAG的写入，依照Release-Acquire Ordering的保障，A行对DATA的写入不会被reorder到把FLAG置成true之后，并且对DATA的写入也会对线程2可见。如果这里没有应用Release-Acquire Ordering，那么线程对DATA的写入用可能会被reorder到写FLAG之后，那么线程2就会呈现读到了FLAG然而读不到DATA的状况。

  • AcqRel：AcqRel Ordering次要用于read-modify-write类型的操作，比方compare_and_swap，表明了它同时具备Acquire和Release的语义，读的局部用Acquire Ordering，写的局部用Release Ordering。
  • SeqCst：SeqCst是Sequential Consistent的缩写，是一种最强的Ordering，在对读应用Acquire Ordering，对写应用Release Ordering，对read-modify-write应用AcqRel Ordering的根底上再保障所有线程看到所有应用了SeqCst Ordering的操作是同一个程序，不管操作的是不是同一个变量。
    这里蕴含了两层意思，第一层意思SeqCst禁止了所有的reorder，针对内存读(load)写(store)的reorder一共有四种状况：
  1. loadload reorder：Arquire Ordering保障
  2. loadstore reorder：Arquire Ordering和Release Ordering保障
  3. storestore reorder：Release Ordering保障
  4. storeload reorder：SeqCst Ordering保障
    看上面的例子
// Global variblestatic x: AtomicU32 = AtomicU32::new(0);static y: AtomicU32 = AtomicU32::new(0);// Thread 1x.store(1, Ordering::SeqCst);  // Alet r1 = y.load(Ordering::SeqCst); // B// Thread 2y.store(1, Ordering::SeqCst); // Clet r2 = x.load(Ordering::SeqCst);  // D

这里如果不应用SeqCst Ordering就会呈现r1 == r2 == 0的后果，起因是每一个线程中的load能够被reorder到store之前，即便咱们别离对load和store应用Acquire Ordering和Release Ordering，因为它们都不保障storeload的reorder。

SeqCst Ordering的第二层意思是所有应用了SeqCst Ordering的操作在全局有一个程序，并且所有的线程都看到同样的程序。比如说全局的程序是A->B->C->D，那么r1 == 0 && r2 == 1，并且第三个线程如果看到了y == 1，那么它肯定能看到x == 1，这就是SeqCst Ordering全局惟一程序代表的意义。尽管应用SeqCst Ordering能够保障更严格的全局一致性，然而它也会带来性能损失，应用正确并且适合的内存排序能力取得最优的性能。

最初解释一下compare_exchange两个Ordering的含意，CAS蕴含1.读变量，2.和期望值比拟，3.写变量三个步骤，第一个Ordering示意CAS胜利下即变量以后的值等于期望值时候，整个操作的Ordering，第二个Ordering示意如果以后比拟失败了状况下，第一步读操作的Ordering。看一个用CAS实现自旋锁的例子

// Global lockstatic LOCK: AtomicBool = AtomicBool::new(false);// Thread 1// Get lockwhile(LOCK.compare_exchange_weak(false, true, Ordering::Acquire, Ordering::Relaxed).is_err()) {}do_something();// UnlockLOCK.store(false, Ordering::Release);// Thread 2// Get lockwhile(LOCK.compare_exchange_weak(false, true, Ordering::Acquire, Ordering::Relaxed).is_err()) {}do_something();// UnlockLOCK.store(false, Ordering::Release);

总结

本文介绍了Rust提供的原子类型，原子操作以及和原子操作配合应用的内存排序。深刻地了解内存排序能力写出正确并且性能最优的程序。内存排序是一个很深的话题，如有谬误，欢送斧正，欢送在评论区留言交换。