什么是指令序和原子操作

阅读量：6311 次

发布时间：2019-06-22

本文共 9588 字，大约阅读时间需要 31 分钟。

不管是高级C++程序员，还是底层汇编程序员，都必须知道指令序和原子操作，这是构建内核锁、库无锁API的最底层积木。可是你真的了解么？

指令序

现代处理器都支持多发射、猜测执行等机制，再加上编译器对指令的重新摆放, 这是导致不同线程（core)对多个共享变量看到修改顺序不一致的根本原因。

x86 reorder规则

单处理器中的规则如下：

• Writes are not reordered with older reads.• Writes to memory are not reordered with other writes, with the following exceptions:— streaming stores (writes) executed with the non-temporal move instructions (MOVNTI, MOVNTQ, MOVNTDQ, MOVNTPS, and MOVNTPD); and— string operations • No write to memory may be reordered with an execution of the CLFLUSH instruction; • Reads may be reordered with older writes to different locations but not with older writes to the same location.• Reads or writes cannot be reordered with I/O instructions, locked instructions, or serializing instructions.• Reads cannot pass earlier LFENCE and MFENCE instructions.• Writes and executions of CLFLUSH and CLFLUSHOPT cannot pass earlier LFENCE, SFENCE, and MFENCE instructions.• LFENCE instructions cannot pass earlier reads.• SFENCE instructions cannot pass earlier writes or executions of CLFLUSH and CLFLUSHOPT.• MFENCE instructions cannot pass earlier reads, writes, or executions of CLFLUSH and CLFLUSHOPT

多处理器中还有额外的规则：

• Individual processors use the same ordering principles as in a single-processor system.• Writes by a single processor are observed in the same order by all processors.• Writes from an individual processor are NOT ordered with respect to the writes from other processors.• Memory ordering obeys causality (memory ordering respects transitive visibility).• Any two stores are seen in a consistent order by processors other than those performing the stores• Locked instructions have a total order.

序列化指令

LFENCE

load fence

load fence 指令之后的load 操作不会reorded到load fence之前执行；

SFENCE

store fence

store fence 指令之后的store 操作不会reorded到store fence之前执行；

MFECE

load and store fence

MFECE 指令之后的load/store操作不会reordeded 到mfence之前执行。

fence指令都需要注意的一点就是：

UC （uncache )类型的memory 上禁止推测访问和乱序执行，通常这种类型的内存用来映射设备空间（PCIE IO/Memory space)

对于弱一致性的内存空间，支持猜测读和write buffer/write combiling，原子操作可以触发lock local cache，不会扩散到整个cache line ，有助于减小性能代价，比如XCHG指令。

其他指令
```
• Privileged serializing instructions — INVD, INVEPT, INVLPG, INVVPID, LGDT, LIDT, LLDT, LTR, MOV (to control register, with the exception of MOV CR83), MOV (to debug register), WBINVD, and WRMSR4.• Non-privileged serializing instructions — CPUID, IRET, and RSM.
```
注意事项

序列化指令并不能把write back数据到内存中，只是写到data cache。在很多场合中还需要数据写回，为此可以使用WBINVD 序列化指令。但这里需要注意的是，这个指令会影响中断、 event响应时间。

内存屏障

对于编译器已经产出的指令，上面序列化指令能够避免不期望的reorder。但程序员通常和高级语言打交道，编译器还可能从中重新安排汇编语言指令，以便最大化利用内部寄存器。

X86中能够起到内存屏障的操作：

IO端口操作的所有指令

有lock前缀的指令

写控制器寄存器、系统寄存器或调试寄存器（cli/sti/ 修改eflags)

iret

mb()

rmb()

rmb()

asm volatile ("lock; addl $0, 0(%%esp)":::"memory")

volatile: 禁止asm后面的指令与程序中的其他指令重新组合

memory关键字：强制编译器假定所有内存单元已经被汇编语言指令修改，不使用存放在CPU寄存器中的内存单元的值优化asm指令前的代码

wmb()

由于x86不对写内存重新排序，防止编译器重新摆放指令就好：

asm volatile ("":::"memory")

原子操作的特点

实际应用中的一些场景需要保证指令执行序列，保证原子操作。原子类型的对象的主要特点：

从不同线程访问原子对象顺序合理，不会导致数据行为不可预期；

原子对象所在的线程可以通过 memory order指定对其他非原子对象的同步；

需要保证的四个要求：

对所有原子操作保证下列四个要求：

1) 写写连贯：
move [M] X;  // A move [M] Y;  // B
若修改某原子对象 M 的求值（写） A 先发生于修改 M 的求值 B ，则 A 在 M 的修改顺序中早出现于 B 。
2) 读读连贯:

move [M] X;move Y [M]; // Amove Z [M]; // B

若某原子对象的值计算（读） A 先发生于 M 上的值计算 B ，且若 A 的值来自 M 上的写入 X ，则 B 的值是 X 所存储的值，或在 M 的修改顺序中后出现于 X 的 M 上副效应 Y 所存储的值。

3) 读写连贯：

move X [M]; //Amove [N] X; // B

若某原子对象 M 的值计算（读） A 发生先于 M 上的操作 B （写），则 A 的值来自 M 的修改序列中早出现于 B 的副效应（写） X 。

4) 写读连贯：
move [M] X; //Amove Y [M]; //B
若原子对象 M 上的副效应（写） X 先发生于 M 的值计算（读） B ，则求值 B 应从 X 或从 M 的修改顺序中后随 X 的副效应 Y 取得其值。

应用程序看到的原子操作需要内存控制器、CPU指令、cache一致性协议以及编译器的协调实现。

底层硬件和指令的支持

memory controller的支持

load/store 操作本身在内存控制器级别是原子的，控制器保证不会同时对同一个地址进行读写。同样也需要支持下面这些指令是原子的：

• Reading or writing a byte• Reading or writing a word aligned on a 16-bit boundary• Reading or writing a doubleword aligned on a 32-bit boundary• Reading or writing a quadword aligned on a 64-bit boundary• 16-bit accesses to uncached memory locations that fit within a 32-bit data bus

LOCK# 总线信号支持

lock 指令和有lock前缀的指令保证:只有当前一个core或者agent在访问指令指定的内存地址

CPU指令支持

汇编指令自带加锁语义：

• When executing an XCHG instruction that references memory.• When setting the B (busy) flag of a TSS descriptor • When updating segment descriptorsset.• When updating page-directory and page-table entriesset.• When updating page-directory and page-table entries

软件添加加锁前缀

下面的指令前加上加锁前缀就可以实现带锁执行了：

• The bit test and modify instructions (BTS, BTR, and BTC).• The exchange instructions (XADD, CMPXCHG, and CMPXCHG8B).• The LOCK prefix is automatically assumed for XCHG instruction.• The following single-operand arithmetic and logical instructions: INC, DEC, NOT, and NEG.• The following two-operand arithmetic and logical instructions: ADD, ADC, SUB, SBB, AND, OR, and XOR.

cache coherence

MESI类协议

支持lock/fence 等指令在不同处理器核之间看到一致性的数据；

支持invalid/write back 等cache操作；

原子操作的应用

原子操作在内核、基础库中得到广泛应用。

构建内核spin lock

这里首先需要了解的是：GNU汇编器使用 AT&T 样式的语法，所以其中的源和目的操作数和 Intel 文档中给出的顺序是相反的。

MOV指令的基本格式：

movx source, destination

source 和 destinatino 的值可以是内存地址，存储在内存中的数据值，指令语句中定义的数据值，或者是寄存器。

xaddw指令的基本格式：

xaddw source, destination

source 和 destinatino 的值可以是内存地址，先交换source destionation 的值，然后把两者之后写入destionation。

.arch/x86/include/asm/spinlock.h:

static __always_inline void __ticket_spin_lock(arch_spinlock_t *lock){        short inc = 0x0100;        asm volatile (                LOCK_PREFIX "xaddw %w0, %1\n" //交换之后，%1指向lock->slock, %0 指向inc, 值为0x100 + 之前锁的值。而lock 的高位值为0x01，低为值保持之前的值不变）;                "1:\t"                "cmpb %h0, %b0\n\t" // 始终通过inc 高位和低位是否相同判断。如果lock-slock = 0x0101 就表示第一次拿到锁; 否则lock->slock = 0x0100; 此时如果下一个人来抢锁，得等r0=0x0200，只有等前一个锁释放才能抢到！第三个人，依次类推！                "je 2f\n\t"                 "rep ; nop\n\t" //空转循环                "movb %1, %b0\n\t" //没有拿到锁，读slock低位的值，給inc1的低位                /* don't need lfence here, because loads are in-order */                "jmp 1b\n"                "2:" // 拿到锁：比如 lock->slock =0x0101, 高位、低位相等                : "+Q" (inc), "+m" (lock->slock)                :                : "memory", "cc");}

初始化： lock-slock == 1 表示没人拿到锁，资源可用；

%0 存储 inc的值；

%1 存储 lock->slock的值

xaddw:

%1 存储 lock->slock的值； %0 存储 inc的值

求和之后
%1 存储 inc的值， %0存储lock->slock的值，同时slock的高位的值加1 （0x100)
FLAG1:
比较上面%0的值高字节和低字节的值是否相同
如果相同，表示抢到锁，提出到标号2处执行；
否则循环空指令；
然后又把%0存储的低位字段传给 %1；
调整到标号1处执行；
标号 2:
.....

如果%0的高位和低位的值相等，表示抢到锁。上面slock的高位已经加1，什么情况下

低位会加1呢？原来是之前抢到锁的人释放锁的时候，低位执行加1，并且是有LOCK 前缀的带锁操作，这样修改完后其他核就能看到了，从而抢到锁。

static __always_inline void __ticket_spin_unlock(arch_spinlock_t *lock){        asm volatile(UNLOCK_LOCK_PREFIX "incb %0"                     : "+m" (lock->slock) // 第一次释放的时候lock-slock == 0x0102，第二次0x0203; 第三次0x0304                     :                     : "memory", "cc");}

这里有人可能会问，如果是

基于spin lock实现全局关中断

cli() __save_flags(flags);if (flags & 0x0200) / * 检查IF标志 */ {   __cli();if (!local_irq_count[smp_processor_id()]) {   get_irqlock(smp_processor_id());}

提供C/C++中原子操作API

memory_order_relaxed

操作类型：load/store

reorder限制：无

适用场景：多个线程之间只需要共享一个变量，保证对这个变量的操作的原子性就好（加lock前缀）

可见性：只看到原子变量的修改，其他变量的修改不一定看得到

memory_order_consume

操作类型：load

reorder限制：当前线程中依赖于当前加载的该值的读或写不能被重排到此加载前

适用场景：需要保证共享变量及其依赖的变量的修改其他线程可见

可见性：释放同一原子变量的线程的对数据依赖变量的写入

memory_order_acquire

操作类型：load

reorder限制：当前线程中读或写不能被重排到此加载前

适用场景：

可见性：释放同一原子变量的线程的所有写入

memory_order_release

操作类型：store

reorder限制：当前线程中的读或写不能被重排到此存储后

适用场景：需要保证共享变量及其更新之前的其他变量的修改其他线程d可见

可见性：当前线程的所有写入，可见于获得该同一原子变量的其他线程释放获得顺序），并且对该原子变量的带依赖写入变得对于其他消费同一原子对象的线程可见（见下方释放消费顺序）

memory_order_acq_rel

操作类型：store

reorder限制：当前线程中读或写不能被重排到此加载前

适用场景：

可见性：所有释放同一原子变量的线程的写入可见于修改之前，而且修改可见于其他获得同一原子变量的线程。

memory_order_seq_cst

操作类型：读修改写操作

reorder限制：有此内存顺序的加载操作进行获得操作，存储操作进行释放操作，而读修改写操作进行获得操作和释放操作，存在一个单独全序

适用场景：

可见性：所有线程以同一顺序观测到所有修改

C++中的序

宽松顺序
只要求全局变量的更新在所有线程可见

释放获得顺序
只要求全局变量的更新在所有线程可见，且其依赖的变量的修改也可见

释放消费顺序
要求全局变量的更新在所有线程可见，且全局变量更新前的所有修改也可见

序列一致顺序
带标签 memory_order_seq_cst 的原子操作不仅以与释放/获得顺序相同的方式排序内存（在一个线程中先发生于存储的任何结果都变成进行加载的线程中的可见副效应），还对所有带此标签的内存操作建立单独全序。

释放获得序与释放消费序的比较

#include 
    
     #include 
     
      #include 
      
       #include 
       
        std::atomic
        
          ptr;int data;void producer(){    std::string* p  = new std::string("Hello");    data = 42;    ptr.store(p, std::memory_order_release);}void consumer1(){    std::string* p2;    while (!(p2 = ptr.load(std::memory_order_consume)))        ;    assert(*p2 == "Hello"); // 绝无出错： *p2 从 ptr 携带依赖    assert(data == 42); // 可能也可能不会出错： data 不从 ptr 携带依赖}/*void consumer(){    std::string* p2;    while (!(p2 = ptr.load(std::memory_order_acquire)))        ;    assert(*p2 == "Hello"); // 绝无问题    assert(data == 42); // 绝无问题}*/int main(){    std::thread t1(producer);    std::thread t2(consumer);    t1.join(); t2.join();}

释放消费序与序列一致顺序的比较

释放消费顺序不负责多个原子变量之间的顺序，可能reorder,无法还对所有带此标签的内存操作建立单独全序;

序列一致顺序要求根据规则建立顺序;

看下面例子：由于read_y_then_x()和read_x_then_y 内两条语句可能被reorder，在此情况下任何其他顺序都可能导致线程c和d观测到原子对象x和y以相反顺序更改。

#include 
    
     #include 
     
      #include 
      
       std::atomic
       
         x = {false};std::atomic
        
          y = {false};std::atomic
         
           z = {0};void write_x(){ x.store(true, std::memory_order_seq_cst);}void write_y(){ y.store(true, std::memory_order_seq_cst);}void read_x_then_y(){ while (!x.load(std::memory_order_seq_cst)) ; if (y.load(std::memory_order_seq_cst)) { ++z; }}void read_y_then_x(){ while (!y.load(std::memory_order_seq_cst)) ; if (x.load(std::memory_order_seq_cst)) { ++z; }}int main(){ std::thread a(write_x); std::thread b(write_y); std::thread c(read_x_then_y); std::thread d(read_y_then_x); a.join(); b.join(); c.join(); d.join(); assert(z.load() != 0); // 决不发生}