Hexo
0%

Atomic Variable & Memory Order

Posted on Edited on

这一篇文章, 我们浅谈一下原子变量以及内存序模型. 有什么问题欢迎留言指出, 我们可以一起讨论.

Atomic Variable

首先我们先来聊一下什么是”原子性”. 假如有这样一段代码

1
2
3
4
int v;
void add(){
    v = v + 2;
}

在执行add函数时, CPU需要先从内存中取出v的值, 然后计算+2, 最后写回到内存中. 如果只有一个执行序, 那当然无所谓. 但如果有并发呢? 那就比较麻烦了. 我们讨论最简单的情况, 即双线程并发执行一次这个函数.

这就可能出现多种情况. 比如, 其中一个线程先执行成功, 然后另一个线程执行. 那么当二者都执行成功后. v的值变为4.

或者, 它们一起开始执行. 线程1先读取到v的值, 开始计算+2, 但还没来得及写回; 而线程2已经开始运行, 开始读取v值, 为0, 开始计算+2. 最终, 无论这两个执行绪谁先执行完成, 都会只是向内存写入2. 而不是预期中的4. 就像下面这样

1
2
3
4
5
6
7
8
9
10
11
12
13
 T0             T1
┌──────────────┬───────────────┐
│  load v (=0) │               │
├──────────────┼───────────────┤
│              │  load v (=0)  │
├──────────────┼───────────────┤
│  add 2  (=2) │  add 2 (=2)   │
├──────────────┼───────────────┤
│              │  store v (=2) │
├──────────────┼───────────────┤
│ store v (=2) │               │
└──────────────┴───────────────┘

从这段代码来说, 这个+2的操作, 显然就不是原子性的. 如果是”原子性”的操作, 那就该这三个步骤合并为一个步骤, 一下子完成. 像这样

1
2
3
4
5
6
7
8
9
 T0             T1
┌──────────────┬───────────────┐
│     v+=2     │               │
├──────────────┼───────────────┤
│              │               │   // v == 2
├──────────────┼───────────────┤
│              │     v+=2      │   
└──────────────┴───────────────┘
                                   // v == 4

或者, 我们可以直接简单地加一个互斥锁, 让f不要并行执行, 也可以.

但是, 比较反直觉的是, 即使我们不讨论对变量修改并写回的操作, 只考虑单纯地读取一个变量或者加一个变量(Load/Store)也不一定是原子性的. 这个就涉及到一些硬件上的原理, 比如, 某种平台, 每次只能读取内存中4个字节, 那如果在这种平台上, 读取一个int64即8个字节的值, CPU就不得不读取两次, 先读取一半, 再读取另一半. 或者在普通我们常见的平台, 也可能出现这种问题, 比如变量没有对齐, 那么CPU就有可能也不得不将一次读取拆分为多次.

另外多说一句, 如果使用gcc/clang-x64并打开优化, 可以观察到add函数被编译为
    add():                                # @add()
    add     dword ptr [rip + v], 1
    ret
看起来像是一条单个的add汇编指令, 似乎是满足了上文提到的"原子性"加法, 将三个操作合并为一个, 但这并不意味着这个加法操作就是原子性的, 只是CPU内部将这一条指令分成多个步骤执行了而已. 对此感兴趣的朋友可以搜索一下关键词"CISC 微指令"

在类似于amd64这种强内存序(Strong memory order)下, 如果变量已经对齐, 那其实不需要纠结什么, 对于整数的读取和写入本身就已经是原子的. 现代的编译器在生成变量时会注意内存对齐的问题. 所以毫不夸张的说, 如果说我们只讨论单一变量的原子性读和写, 并且只讨论amd64或x86架构的话, 那么这个话题就结束了. 没有什么需要注意的, 它们天然就是原子性的. 就当是普通地读取变量即可.

那如果类似于aarch64这类的弱内存(Weak memory order)呢? 那就需要稍微注意一下了, 在这种架构下, 如果是没有对齐的存取, 就很有可能喜提Alignment fault.

比如MIPS和低版本的ARM会不支持对齐访问. 高版本的ARM比如aarch64倒是支持, 不过也很有限(栈和指令依旧必须对齐), 并且性能会有损失

那么好, 我记住了, 以后存取变量注意内存对齐, 结束, 下课~

别急, 还没讲完 :P

从我个人的观点来看, 所谓”原子变量”是一个很有迷惑性的术语, 它会让人误以为所谓”原子性”仅仅是指对于单个变量的原子性操作. 实际上, 当我们谈论原子变量时, 我们更多地是在讨论基于原子变量的缓存控制.
也就是并发编程的三要素–原子, 有序, 可见中的后面两位, 有序性&&可见性.

内存序模型

可见性

我们首先说可见性. 可见性是指, 当一个执行绪修改了内存上的一个变量, 其他执行绪应该能”看见”这次修改. 在现代CPU架构下, 这点其实并不是一定的, 比如Java下的volatile关键字, 就是要确保其他线程能看到这次变量的修改.

 不过, 在C/C++下, *volatile*有着其他的意义, 我的建议是, 在写C/++时, 如果你不是在处理硬件相关的东西, 就不要用.

那如何保证可见性呢? 这个我们和下面的有序性一起讲.

有序性

为了提高执行性能, 现代的编译器,以及CPU都会对执行指令进行重排. 不过重排还是有一个前提, 不影响单执行绪下的执行结果,我们可以看一下这一段代码:

1
2
3
4
5
6
int a;
int b;
void f(){
    a = a + 1 ;
    b = b + 2 ;
}

使用armv8-a clang 10.0.0开启O1优化, 可以得到下面的汇编

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
f():                                  // @f()
        adrp    x8, a
        adrp    x9, b
        ldr     w10, [x8, :lo12:a]
        ldr     w11, [x9, :lo12:b]
        add     w10, w10, #1            // =1
        add     w11, w11, #2            // =2
        str     w10, [x8, :lo12:a]
        str     w11, [x9, :lo12:b]
        ret
a:
        .word   0                       // 0x0

b:
        .word   0                       // 0x0

可以看到, 编译器生成的汇编指令先读取两个变量的值, 然后相加, 最后写回两个变量.
如果不优化, 那么生成的汇编就会是 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
f():                                  // @f()
        adrp    x8, a
        add     x8, x8, :lo12:a
        adrp    x9, b
        add     x9, x9, :lo12:b
        ldr     w10, [x8]
        add     w10, w10, #1            // =1
        str     w10, [x8]
        ldr     w10, [x9]
        add     w10, w10, #2            // =2
        str     w10, [x9]
        ret
a:
        .word   0                       // 0x0

b:
        .word   0                       // 0x0

这下, 编译器生成的汇编和我们写的c代码基本就是逐行对应的了.

不仅如此, 除了编译器, CPU内部在硬件层面上, 也会对指令进行重新排序, 所以, 如果以为加了编译屏障, 就万事大吉, 显然是不可能的. 

编译器屏障, 通常见到的都是这样的:
__asm__ __volatile__("": : :"memory")
这个东西, 还是那句话, 除非你真的知道自己在做什么再用, 如果希望使用它来禁止指令重排, 保证有序性, 那它大概率是做不到的.

相比于编译器造成的指令重排, 硬件造成的重排, 要更为棘手, 这不仅涉及到指令重排这么简单, 还会影响CPU多层缓存的更新.

比如, 因为有缓存的存在, CPU0修改了内存上的某个值, 但是因为配置的缓存策略是”Write Back”, 此次修改还没来得及写回到内存上, 只是CPU0独享的缓存中, 此时其他CPU核心就读不到最新的修改.

那是不是等这次写回完成后就可以了呢? 无非就是等一等而已. 但是问题要更复杂一些, 上文说到, 不仅是编译器, CPU本身还会对指令进行重排以提高性能. 假如有这样一段代码:

1
2
3
4
5
6
7
8
9
10
11
12
int v = 0;
int flag = 0;
void set_v(){
    v = 42;
    flag = 1;
}
int get_v(){
    while(flag == 0){
        continue;
    }
    return v;
}

在函数set_v中, 首先对v赋值, 然后对flag置位. 然后在get_v中, 会轮询标志位, 当标志位非0时, 代表变量v准备好, 可以被读取, 读取v的值后返回.

但是这段代码, 在一些CPU平台上, 大概率是不能运行的. 两个函数都可能存在问题.

首先说set_v, 因为CPU乱序执行以及缓存的缘故, 可能出现下面的情况

  1. flag = 1有可能先于v=42执行, 被写入到内存.
  2. v=42确实在flag=1之前执行了, 但只是写入到缓存中. 而随后的缓存写回时, flag所在的缓存先于v=42被写回. 导致其他线程先观察到了flag置位, 然后立即去读取v的值, 但是内存上v还没有被更新, 就会导致读出的值是错误的.

然后再说get_v, 在被乱序执行后, 可能它会有自己的关于v的缓存, 还未更新, 或者说, 更新的晚于flag所在的缓存, 这也可能导致读出错误.

当然, 你可能会提到缓存一致性协议, 会保证执行结果的. 但是, 缓存一致性协议是需要一些hint才会工作的, 不然所有核心全用同一个缓存算了. 具体是什么hint, 我们下面马上就讲

set_v可能出现的两种状况中, 如果我们作为一个观察者观察内存时, 看到的结果其实是一样的, 都是修改了flag, 后修改了v.

或者说, 我们如何定义store操作的完成呢? 是写到缓存就算执行完成呢? 还是写到内存才算一条store指令执行完成?

如果是后者的话, 那么其实那两种情况, 指的就是同一种, 即store flag的指令错误地先于store v的指令执行了. 那我们可以简化一下, 假设我们不知道缓存的存在, 就只考虑存取指令的乱序执行. 在这种情况下, 我们就只考虑指令之间的排列顺序即可. 假如一个指令完成, 那就意味着store已经将值写到内存.

只是简化理解噢, 实际上L2及以下的缓存是核心共享的, 那么就意味着这种store, load只要读取到缓存上的最新值即可. 但是对于总线上的其他设备, 可能又不行. 所以大家不必纠结这个, 暂时忘掉缓存即可:P

在这种简化模型下, 如果要保证存取指令之间执行的有序性, 我们可以简单地插入一些屏障指令, 禁止一些CPU的重排行为, 这样, 强制存取指令按照约定的顺序执行, 就不会再有莫名其妙的重排问题了, 这也就是下面讲的东西, 内存屏障.

内存屏障

上文提到了, 有编译器屏障, 那么自然, 也就存在CPU的指令屏障.

各个平台都会提供一些特别的汇编指令, 我们可以称之为”完全内存屏障”, 硬件保证: 这条指令之前的指令一定会在这条指令执行前执行完成, 这条指令之后的指令一定在这条指令完成之后开始执行. 

x86下是LFENCE,SFENCE,MFENCE,或者什么带有lock前缀的指令, 或者什么隐含锁语义的指令(比如exchg)
而aarch64下, 则是DMB, DSB, ISB指令

但是, 这种屏障指令, 有的时候可能粒度过大.

比如, 对于我们常见的内存变量存取, 我们只需要保证相应的load, store指令之间不要重排即可. 没必要让所有指令都跟着一起停下来. 因为这样需要让整个CPU流水线都会被排空, 同时缓存也要完全同步一次才能实现. 相对来说, 性能上还有进一步提升的空间.

所以, 因此就出现了更加细致的内存屏障指令. 在不少平台上, 都会存在类似这种细粒度的屏障指令, 只禁止某些特定的指令重排, 这样可以对缓存更新行为做更细粒度的控制, 也就相对可以获得更高的性能.

那么, 考虑最简单的情况, 即两个存取指令, 可以有4种情况. 那么根据这四种情况, 就需要四种内存屏障.

1
2
3
4
5
┌──────────────┬───────────────┐
│  load, load  │  load, store  │
├──────────────┼───────────────┤
│ store, load  │  store, store │
└──────────────┴───────────────┘

我们接下来, 用一些例子, 来尝试解释一些这些屏障的行为

load-load

load-load 屏障可以保证, 两个读取行为间不会被乱序. 但是要注意, 这其实并不保证读取到的就一定是最新的值. 准确来说, 它只保证第一次读取到的值, 比第二次读取到的更老. 

这个屏障就可以用来实现上面的get_v函数.像这样:
int get_v(){
    while(flag == 0){
        continue;
    }
    *LOAD_LOAD_FENCE();*
    return v;
}
只要读取到flag被置位, 再加上一个load-load屏障, 就可以确保接下来读取v的动作发生在读取flag之后.保证了读取行为的正确性

Store-store

Store-Store 屏障与load-load类似, 它保证两个写入行为间不会乱序. 并且和load-load一样, 它不保证屏障之前的值一定是完成了的, 只是保证, 在内存视角, 前面的修改一定是先于后面的修改.

这个屏障可以用来实现上面set_v函数
void set_v(){
    v = 42;
    *STORE_STORE_FENCE()*
    flag = 1;
}

Load-store

指令重排/乱序执行有一个重要前提, 那就是不会更改单线程下的执行结果. 所以, Load-Store的重排听起来可能有点奇怪? 假如, 必须先读取到一个特定的标志位, 才能开始写入. 那这种重排不就会影响单线程下的执行结果了.

比如

1
2
3
4
5
6
7
8
int l = 0;
int v = 1;

void f(){
    if(l == 0){
        v = 2;
    }
}

像是这种, 即使乱序执行, 也肯定不会影响语义.

所以, 这种重排只会发生在一些特殊情况. 当前面的load指令读取恰好遇到了cache miss并且load,store的变量之间完全没有联系的情况下. 还是可能发生这种重排的.

比如有下面f,g两个函数分别有core1和core2执行

1
2
3
4
5
6
7
8
9
10
int x = 0;
int y = 0;
void f(){ // execute by core 1
    int t0 = x;
    y = 1;
}
void g(){ // execute by core 2
    int t1 = y;
    x = 1;
}

如果f先执行, 那么可以得到

x y t0 t1
1 1 0 1

如果g先执行, 那么可以得到

x y t0 t1
1 1 1 0

或者二者交替执行, 即两个读取x,y的先执行, 对x,y后执行的可以得到

x y t0 t1
1 1 0 0

但是, 如果发生了load-store重排, 最终也可能获得x == y == t0 == t1 == 1的结果

Store-load

Store-load相对来说是最”重”的屏障, 它要确保load在Store执行完成之后才能读取. 还记得我们之前定义的Store操作吧? Store指令的完成, 意味着修改写入到内存, 让其他观察者可见. 并且, 读取到的值, 一定是最新可见的值.

以上, 就是各种单向内存屏障的定义. 但实际上, 我们实际在编程时极少直接使用这类屏障指令. 一方面, 不同平台的屏障指令特点都不尽相同, 不能完全和这些标准的屏障对应; 另一方面, 直接使用屏障对于使用高级语言编程来说, 可能过于底层了, 从这个角度来说, 我们应该告诉编译器我们想要达成什么效果, 而不是直接告诉编译器使用什么指令. 那这就引出我们今天最后的内容了—-内存序.

比如, x86, amd64, 安腾架构是所谓的"强内存序(Strong memory order)", 平台会保证在一些情况下不会乱序执行. 以amd64为例, 它只需要store-load屏障, 其余情况不会发生乱序执行.
或者类似于Aarch64, 它不提供任何保证, 所有执行情况必须由显式的屏障指令才能保证其不会重排, 也就是所谓的"弱内存序(Weak memory order)"

内存序 (memory order)

C++11定义了6种内存序(memory order), 用来控制对原子变量的读写. 当访问原子变量时, 需要给出一个内存序参数, 通过这个参数, 就可以控制以这个原子变量为分界线的内存乱序执行行为. 编译器会根据对应的内存序, 生成不同的屏障指令.

  1. relaxed
  2. acquire
  3. release
  4. acquire-release
  5. consume
  6. sequentially-consistent

我们接下来一个一个讲

relaxed

Relaxed 是最轻的内存序限制, 它只保证对于指定的原子变量的操作是原子的, 而对于在访问原子变量周围的同步或者内存重排行为, 则一概不管. 所以显而易见, 这也是原子变量中性能最好的内存序. 不过嘛, 似乎只能用来做计数器? 如果涉及到多个变量的同步都可能发生问题.

acquire

Acquire 要求, 在读取到此原子变量后面的所有读取/写入指令, 不可以被重排到读取此原子变量的前面. 这个就非常适合用于我们上面的get_v

相当于load-store+load-load两个屏障加在一起

release

与acquire相反, release要求, 在写入此变量之前的所有读取/写入指令, 不可以重排到写入此原子变量的后面. 适合我们刚才的set_v.

相当于store-store+load-store两个屏障相加

acquire-release

这个就是Acquire和release的相加在一起, 相当于一次完全内存屏障. 这种内存序需要一次read-modify-write操作, 既有acquire又有release. 用在两个线程交换什么东西的时候.

这个所谓的read-modify-write操作要和上面的计数器做一些区分. 计数器加1当然也是read-modify-wirte,但是只是相对于原子变量自身而言. 比如, 两个线程需要交换指针, 这种情况, 就需要acquire-release语义了.

sequentially-consistent

序列化一致性和acquire-release区别不大. 比如, 在单生产者单消费者的情况下, 二者没有区别. 区别在于多线程的情况下, 序列化一致性保证, 多个线程观察到修改时, 顺序是一致的.

比如有4个线程, 分别执行a, b, c, d四个函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int t1 = 0, t2 = 0;
int z = 0;
void a(){
    t1 = 1;
}
void b(){
    t2 = 1;
}
void c(){
    while(t1 == 0)continue;
    if(t2 == 1)z+=1;
}
void d(){
    while(t2 == 0)continue;
    if(t1 == 1)z+=1;
}

c函数执行时, 如果t1先于t2赋值, 是有可能不执行z+=1的. 同理, 对于d函数来说, 如果t2先于t1赋值, 也是有可能不执行z+=1的. 那么按照直觉来说, d或者c应该至少有一个将z+=1, 对吧? 其实不一定. 如果不使用序列化一致性模型, C++标准不保证两个线程观察到的赋值顺序是相同的.

多说一句, 如果用的是amd64, 硬件保证所有线程观察到的顺序是一定的, 在这个平台上, 是看不到z==0的, 硬件上没有这种灵活性...

consume

那这种内存序就比较高端了. 它和acquire-release类似, 但是粒度更细一点. 假如一个线程通过这个内存序load的一个值, 那么**与这个值相关(或者叫数据依赖 carries dependency)的load和store, 不能重排到前面; 如果通过这个内存序Store一个值, 那么与这个值相关(或者叫数据依赖 carries dependency)**的load和store, 不能重排到后面.

但是实际上, 好像还没有硬件平台支持这么细粒度的屏障. 所以这个内存序只会影响一些编译器优化的行为(比如编译器可能会禁止预加载依赖链上的数据).

END

这篇关于原子变量的文章到这里就结束了, emm 也没有完全结束, 还都是理论介绍, 没有实际的代码例子, 之后我会再写一篇实操的(咕咕咕咕).

但其实我最想说的是, 大部分情况, 除了计数器这种非常简单的需求, 没事不要折腾什么无锁编程, 性能不一定快多少, 但可以保证的是bug会很难调. 很多时候程序的瓶颈根本就不差这几个锁, 现在的Linux的futex什么的, 用锁其实也没慢多少的… 同理, 你确定一定要用原子变量的时候, 就直接用顺序一致性就好, 也没差多少, 尤其是在x86这种平台, 很多细粒度的屏障都是不支持的, 没有什么搞事的余地:(