lock和open哪个是开是关?下篇说说无锁Lock-Free
lock和open哪个是开是关?下篇说说无锁Lock-Free6.3.1 有条件的顺序保证```[2]、从包含所有cpu的sharebility domain的角度看,所有cpu对一个共享变量的访问应该服从若干个全局存储顺序[3]、memory barrier需要成对使用[4]、memory barrier的操作是构建互斥锁原语的基石
6.3 How Memory Barriers?
memory barrier的语义在不同CPU上是不同的,因此,想要实现一个可移植的memory barrier的代码需要对形形色色的CPU上的memory barrier进行总结。幸运的是,无论哪一种cpu都遵守下面的规则:
```
[1]、从CPU自己的视角看,它自己的memory order是服从program order的
[2]、从包含所有cpu的sharebility domain的角度看,所有cpu对一个共享变量的访问应该服从若干个全局存储顺序
[3]、memory barrier需要成对使用
[4]、memory barrier的操作是构建互斥锁原语的基石
```
6.3.1 有条件的顺序保证
要保证程序在多核CPU中执行服从program order,那么我们需要成对使用的memory barrier,然而成对的memory barrier并不能提供绝对的顺序保证,只能提供有条件的顺序保证。那么什么是有条件的顺序保证?考虑下面一个访问例子(这里的access可以是读或写):
从CPU1角度来看,对A的访问总是先于对B的访问。但是,关键的是从CPU2的角度来看,CPU1对A、B的访问顺序是否就一定是A优先于B呢?假如在CPU2感知CPU1对A的访问结果的情况下,是否可以保证CPU2也能感知CPU1对B的访问结果呢?这是不一定的,例如执行时序如下,那么显然,在CPU2感知CPU1对A的访问结果的情况下,是并不能感知CPU1对B的访问结果(CPU2对A的访问要早于CPU1对B的访问)。
另外,如果CPU1对B的访问结果已经被CPU2感知到了,那么,在这个条件下,CPU1对A的访问结果就一定能够被CPU2感知到。这就是观察者(CPU2)在满足一定条件下才能保证这个memory的访问顺序。
对于上面例子中的access操作,在内存上包括load和store两种不同操作,下面列出了CPU1和CPU2不同的操作组合共16个,下面来详细描述一下,在不同的操作组合下memory barrier可以做出怎样的保证。
由于CPU架构千差万别,上面的16种组合可以分成3类
```
[1] Portable Combinations -- 通杀所有CPU
[2] Semi-Portable Combinations -- 现代CPU可以work,但是不适应在比较旧的那些CPU
[3] Dubious Combinations -- 基本是不可移植的
```
6.3.1.1 通杀所有CPU
(1) Pairing 1
情况3,CPU执行代码如下:(A和B的初值都是0)
| CPU1 | CPU2 |
| ------ | ------ |
| X = A; | B = 1; |
| smp_mb(); | smp_mb(); |
| Y = B; | A = 1; |
对于这种情况,两个CPU都执行完上面的代码后,如果X的值是1,那么我们可以断定Y也是等于1的。也就是如果CPU1感知到了CPU2对A的访问结果,那么可以断定CPU1也必能感知CPU2对B的访问结果。但是,如果X的值是0,那么memory barrier的条件不存在,于是Y的值可能是0也可能是1。
对于情况C,它是和情况1是对称,于是结论也是类似的:(A和B的初值都是0)
同样,两个CPU都执行完上面的代码后,如果Y的值是1,那么可以断定X的值也是1。
(2) Pairing 2
情况5,CPU执行代码如下:(A和B的初值都是0)
两个CPU都执行完上面的代码后,在不影响逻辑的情况下,在CPU2的A=1;前面插入代码Z=X,根据情况C,如果Y的值是1,那么Z的值就一定是A,由于Z=X执行在A=1前面,那么Z的值是A的初始值0,于是X的值一定是0。同样,如果X等于1,那么我们一定可以得到Y等于0;
(3) Pairing 3
情况7,CPU执行代码如下:(A和B的初值都是0)
两个CPU都执行完上面的代码后,在不影响逻辑的情况下,在CPU1的B=1;前面插入代码Z=B,根据情况3,如果X等于1,那么可以断定Z等于2,也就是在CPU1执行完毕Z=B代码前,B的值是2,由于CPU1在执行完Z=B后会执行B=1,于是对CPU1而已,最后B的值是1。
通过上面(1) ,如果CPU1执行的全是store操作,而CPU2执行的全是load操作(对称下,CPU2执行的全是store操作,而CPU1执行的全是load操作),那么会有一个memory barrier条件使得执行得到一个确定的顺序,并且是通吃所有CPU的。而,(2)和(3)经过插入代码也可以转换成(1)的情况。
情况D,CPU执行代码如下:(A和B的初值都是0)
该情况是情况7是类似的。在Y等1的时候,最终A等于2.
6.3.1.2 现代CPU可以work,但是不适应在比较旧的那些CPU
(1) Ears to Mouths
情况A,CPU执行代码如下:(A和B初值都是0,其他变量初始值是-1)
这种情况下,比较容易推算出X等1的时候,Y可能为0也可能为1,当X等于0的时候,也比较容易推算出Y值可以为1。但是,X等0的时候,Y有没可能也是0呢?
我们通过插入代码(Z=X),这样就转换成情况C,在X等于0,Z等于0的时候,那么memory barrier条件成立,于是Y必然等1。然而,如果X等于0的时候,Z不等于0,这个时候memory barrier条件就不能成立了,这个时候Y就可能为0。
下面我们来讲下,上面情况下会出现X和Y同时为0。在一个有Invalidate queue和store buffer的系统中,B和X在CPU1的local cache中并且是独占的,A和Y在CPU2的local cache中并且也是独占的。CPUs的执行序列如下:
```
[1] CPU1对A发起store操作,由于A不在CPU1的cache中,CPU1发起invalidate message,当然,CPU1不会停下它的脚步,将A的新值'1'放入store buffer,它就继续往下执行
[2] smp_mb使得CPU1对store buffer中的entry进行标注(当然也对Invalidate Queue进行标注,不过和本场景无关),store A的操作变成marked状态
[3] CPU2对B发起store操作,由于B不在CPU2的cache中,CPU2发起invalidate message,当然,CPU2不会停下它的脚步,将B的新值'1'放入store buffer,它就继续往下执行
[4] CPU2收到CPU1的invalidate message将该message放入Invalidate Queue后继续前行。
[5] smp_mb使得CPU2对store buffer中的entry进行标注(当然也对Invalidate Queue进行标注),store B的操作变成marked状态
[6] CPU1收到CPU2的invalidate message将该message放入Invalidate Queue后继续前行。
[7] CPU1前行执行load B,由于B在CPU1的local cache独占的(CPU1并不需要发送任何MESI协议消息,它并不需要立即处理Invalidate Queue里面的消息),于是CPU1从local cache中得到B的值'0',接着CPU1继续执行store X,由于X也在CPU1的local cache独占的,于是,CPU1将X的新值修改为B的值'0'并将其放入store buffer中。
[8] CPU2前行执行load A,由于A在CPU2的local cache独占的(CPU2并不需要发送任何MESI协议消息,它并不需要立即处理Invalidate Queue里面的消息),于是CPU2从local cache中得到A的值'0',接着CPU2继续执行store Y,由于Y也在CPU2的local cache独占的,于是,CPU2将Y的新值修改为B的值'0'并将其放入store buffer中。
[9] CPU1开始处理Invalidate Queue里面的消息,将本local cache中的B置为Invalide,同时响应Invalidate response message给CPU2
[10] CPU2收到Invalidate response message后,这个时候可以将store buffer里面的B和Y写回cache line,最后B为1,Y为0。
[11] CPU1和CPU2类似,最终A为1,X为0.
```
(2) Pass in the Night
情况F,CPU执行代码如下:(A和B初值都是0,其他变量初始值是-1)
| CPU1 | CPU2 |
| ------ | ------ |
| A = 1; | B = 2;|
| smp_mb(); | smp_mb(); |
| B = 1; | A = 2; |
情况F,正常情况下,无论如何,但是无论如何,在两个CPU都执行完上面的代码之后{A==1 B==2} 这种情况不可能发生。不幸的是,在一些老的CPU架构上,是可能出现{A==1 B==2} 的,出现这种情况和上面的原因有点类似,下面也简单描述一下,在一个有Invalidate queue和store buffer的系统中,B在CPU1的local cache中并且是独占的,A在CPU2的local cache中并且也是独占的。CPUs的执行序列如下:
```
[1]~[6]和 (1) Ears to Mouths中的基本一样
[7] CPU1继续前行,由于B在CPU1的local cache独占的(CPU1并不需要发送任何MESI协议消息,它并不需要立即处理Invalidate Queue里面的消息),于是,CPU1将B的新值'1'放入store buffer中。
[8] CPU2继续前行,由于A在CPU2的local cache独占的(CPU1并不需要发送任何MESI协议消息,它并不需要立即处理Invalidate Queue里面的消息),于是,CPU2将A的新值'2'放入store buffer中。
[9] CPU1开始处理Invalidate Queue里面的消息,将本local cache中的B置为Invalide(这个时候store buffer里面B的新值'1'也被invalidate了),同时响应Invalidate response message给CPU2
[9] CPU2开始处理Invalidate Queue里面的消息,将本local cache中的置为Invalide(这个时候store buffer里面A的新值'2'也被invalidate了),同时响应Invalidate response message给CPU1
[10] CPU1收到Invalidate response message,这个时候可以将store buffer中的A=1刷到cache line,最终A的值为1
[11] CPU2收到Invalidate response message,这个时候可以将store buffer中的B=2刷到cache line,最终B的值为2
```
到这来,大家应该会发现,第一个赋值(对于CPU1而言是A = 1,对于CPU2而言是B = 2)其实是pass in the night,静悄悄的走过,而第二个赋值(对于CPU1而言是B = 1,对于CPU2而言是A = 2)则会后发先至,最终导致第一个赋值先发而后至覆盖第二个赋值。
其实,只要符合下面的使用模式,上面描述的操作顺序(第二个store的结果被第一个store覆盖)都是有可能发生的:
| CPU1 | CPU2 |
| ------ | ------ |
| A = 1; | B = 2;|
| smp_mb(); | smp_mb(); |
|xxxx; | xxxx; |
前面说的'ears to mouths'也是这种模式,不过,对于21世纪的硬件系统而言,硬件工程师已经帮忙解决了上面的问题,因此,软件工程师可以安全的使用Stores “Pass in the Night”。
6.3.1.3 基本不可移植
剩下的情况0、1、2、4、6、8、9这7种情况的组合,即使是在21世纪的那些新的CPU硬件平台上,也是不能够保证是可移植的。当然,在一些硬件平台上,我们还是可以得到一些确定的执行顺序的。
(1) Ears to Ears
情况0,CPUs上全是load操作
| CPU1 | CPU2 |
| ------ | ------ |
| load A; | load B;|
| smp_mb(); | smp_mb(); |
| load B; | load A; |
由于load操作不能改变memory的状态,因此,一个CPU上的load是无法感知到另外一侧CPU的load操作的。不过,如果CPU2上的load B操作返回的值比CPU 1上的load B返回的值新的话(即CPU2上load B晚于CPU1的load B执行),那么可以推断CPU2的load A返回的值要么和CPU1上的load A返回值一样新,要么加载更新的值。
(2) Mouth to Mouth Ear to Ear
这个组合的特点是一个变量只是执行store操作,而另外一个变量只是进行load操作。执行序列如下:
| CPU1 | CPU2 |
| ------ | ------ |
| load A; | store B;|
| smp_mb(); | smp_mb(); |
| store B; | load A; |
这种情况下,如果CPU2上的store B最后发生(也就是,上面代码执行完毕后,在执行一次load B得到的值是CPU2 store B的值),那么可以推断CPU2的load A返回的值要么和CPU1上的load A返回值一样新,要么加载更新的值。
(3) Only One Store
| CPU1 | CPU2 |
| ------ | ------ |
| load A; | load B;|
| smp_mb(); | smp_mb(); |
| load B; | store A; |
这种情况下,只有一个变量的store操作可以被另外的CPU上的load操作观察到,如果在CPU1上运行的load A感知到了在CPU2上对A的赋值,那么,CPU1上的load B必然能观察到和CPU2上load B一样的值或者更新的值。
6.3.2 memory barrier内存屏障类型
6.3.2.1 显式内存屏障
6.3.1章节列举的16种情况的例子中内存屏障smp_mb()指的是一种全功能内存屏障(General memory barrier),然而全功能的内存屏障对性能的杀伤较大,某些情况下我们可以使用一些弱一点的内存屏障。在有Invalidate queue和store buffer的系统中,全功能的内存屏障既会mark store buffer也会mark invalidate queue,对于情况3,CPU1全是load它只需要mark invalidate queue即可,相反CPU2全是store,它只需mark store buffer即可,于是CPU1只需要使用读内存屏障(Read memory barrier),CPU2只需使用写内存屏障(Write memory barrier)。
情况3,修改如下
| CPU1 | CPU2 |
| ------ | ------ |
| X = A; | B = 1; |
| read_mb(); | write_mb(); |
| Y = B; | A = 1; |
到这来,我们知道有3种不同的内存屏障,还没有其他的呢?我们来看一个例子:
初始化
int A = 1;
int B = 2;
int C = 3;
int *P = &A;
int *Q = &B;
通常情况下,Q最后要么等于&A,要么等于&B。也就是说:Q == &A, D == 1 或者 Q == &B, D == 4,绝对不会出现Q == &B, D == 2的情形。然而,让人吃惊的是,DEC Alpha下,就可能出现Q == &B, D == 2的情形。
于是,在DEC Alpha下,CPU2上的Q=P下面需要插入一个memory barrier来保证程序顺序,这来用一个读内存屏障(read_mb)即可,但是我们发现CPU2上的Q = P和D = \*Q是一个数据依赖关系,是否可以引入一个更为轻量的内存屏障来解决呢?
于是这里引入一种内存屏障-数据依赖内存屏障dd_mb(data dependency memory barrier),dd_mb是一种比read_mb要弱一些的内存屏障(这里的弱是指对性能的杀伤力要弱一些)。read_mb适用所有的load操作,而ddmb要求load之间有依赖关系,即第二个load操作依赖第一个load操作的执行结果(例如:先load地址,然后load该地址的内容)。ddmb被用来保证这样的操作顺序:在执行第一个load A操作的时候(A是一个地址变量),务必保证A指向的数据已经更新。只有保证了这样的操作顺序,在第二load操作的时候才能获取A地址上保存的新值。
在纯粹的数据依赖关系下使用数据依赖内存屏障dd_mb来保证顺序,但是如果加入了控制依赖,那么仅仅使用dd_mb是不够的,需要使用read_mb,看下面例子:
由于加入了条件if (t)依赖,这就不是真正的数据依赖了,在这种情况下,CPU会进行分支预测,可能会"抄近路"先去执行*Q的load操作,在这种情况下,需要将data_dependency_mb改成read_mb。
到这来,我们知道有4中不同的内存屏障种类:
```
[1] Write (or store) memory barriers -- 写内存屏障
[2] Data dependency barriers -- 数据依赖内存屏障
[3] Read (or load) memory barriers -- 读内存屏障
[4] General memory barriers -- 全功能内存屏障
```
6.3.2.2 隐式内存屏障
有些操作可以隐含memory barrier的功能,主要有两种类型的操作:一是加锁操作,另外一个是释放锁的操作。
```
[1] lock operations -- 加锁操作
[2] UNLOCK operations -- 释放锁操作
```
(1) 加锁操作被认为是一种half memory barrier,加锁操作之前的内存访问可以任意渗透过加锁操作,在其他执行,但是,另外一个方向绝对是不允许的:即加锁操作之后的内存访问操作,必须在加锁操作之后完成。
(2) 和lock操作一样,unlock也是half memory barrier。它确保在unlock操作之前的内存操作先于unlock操作完成,也就是说unlock之前的操作绝对不能越过unlock这个篱笆,在其后执行。当然,另外一个方向是OK的,也就是说,unlock之后的内存操作可以在unlock操作之前完成。
我们看下面一个例子:
```
1 *A = a;
2 LOCK
3 C = 1;
4 UNLOCK
5 *B = b;
```
上面的程序有可能按照下面的顺序执行:
```
2 LOCK
3 C = 1;
5 *B = b;
1 *A = a;
4 UNLOCK
```
通过上面,我们得知,经LOCK-UNLOCK对不能实现完全的内存屏障的功能,但是,它们也的确会影响内存访问顺序,参考下面的例子:
多个CPU对一把锁操作的场景:
这种情况下,CPU1或者CPU2,只能有一个进入临界区,如果是CPU1进入临界区的话,对A B C的赋值操作,必然在对F G H变量赋值之前完成。如果CPU2进入临界区的话,对E F G的赋值操作,必然在对B C D变量赋值之前完成。
6.3.3 C 11 memory order
要编写出正确的lock free多线程程序,我们需要在正确的位置上插入合适的memory barrier代码,然而不同CPU架构对于的memory barrier指令千差万别,要写出可移植的C 程序,我们需要一个语言层面的Memory Order规范,以便编译器可以根据不同CPU架构插入不同的memory barrier指令,或者并不需要插入额外的memory barrier指令。
有了这个Memory Order规范,我们可以在high level language层面实现对在多处理器中多线程共享内存交互的次序控制,而不用考虑compiler,CPU arch的不同对多线程编程的影响了。
C 11提供6种可以应用于原子变量的内存顺序:
```
[1] memory_order_relaxed
[2] memory_order_consume
[3] memory_order_acquire
[4] memory_order_release
[5] memory_order_acq_rel
[6] memory_order_seq_cst
```
上面6种内存顺序描述了三种内存模型(memory model):
```
[1] sequential consistent(memory_order_seq_cst)
[2] relaxed(momory_order_relaxed)
[3] acquire release(memory_order_consume memory_order_acquire memory_order_release memory_order_acq_rel)
```
6.3.3.1 C 11中的各种关系
C 11引入上面6种内存顺序本质上是为了解决"visible side-effects"的问题,也就是读操作的返回值问题,通俗来讲:
```
线程1执行写操作A之后,如何可靠并高效地保证线程2执行的读操作B,load A的结果是完整可见的?
```
为了解决"visible side-effects"这个问题,C 11引入"happens-before"关系,其定义如下:
```
Let A and B represent operations performed by a multithreaded process. If A happens-before B then the memory effects of A effectively become visible to the thread performing B before B is performed.
```
OK,现在问题就转化为:如何在A、B两个操作之间建立起happens-before关系。在推导happens-before关系前,我们先描述下面几个关系:
6.3.3.1.1 Sequenced-before 关系
定义如下:
```
Sequenced before is an asymmetric transitive pair-wise relation between evaluations executed by a single thread which induces a partial order among those evaluations.
```
Sequenced-before是在同一个线程内,对求值顺序关系的描述,它是非对称的,可传递的关系。
```
[1] 如果A is sequenced-before B,代表A的求值会先完成,才进行对B的求值
[2] 如果A is not sequenced before B 而且 B is sequenced before A,代表B的求值会先完成,才开始对A的求值。
[3] 如果A is not sequenced before B 而且 B is not sequenced before A,这样求值顺序是不确定的,可能A先于B,也可能B先于A,也可能两种求值重叠。
```
6.3.3.1.2 Carries a dependency 关系
定义如下:
```
Within the same thread evaluation A that is sequenced-before evaluation B may also carry a dependency into B (that is B depends on A) if any of the following is true
1) The value of A is used as an operand of B except
a) if B is a call to std::kill_dependency
b) if A is the left operand of the built-in && || ?: or operators.
2) A writes to a scalar object M B reads from M
3) A carries dependency into another evaluation X and X carries dependency into B
```
简单来讲,carries-a-dependency-to 严格应用于单个线程,建立了 操作间的数据依赖模型:如果操作 A 的结果被操作 B 作为操作数 那么 A carries-a-dependency-to B(一个直观的例子:B=M[A] ), carries a dependency具有传递性。
######6.3.3.1.3 Dependency-ordered before 关系
该关系描述的是线程间的两个操作间的关系,定义如下:
```
Between threads evaluation A is dependency-ordered before evaluation B if any of the following is true
1) A performs a release operation on some atomic M and in a different thread B performs a consume operation on the same atomic M and B reads a value written by any part of the release sequence headed by A.
2) A is dependency-ordered before X and X carries a dependency into B.
```
case 1指的是:线程1的操作A对变量M执行“release”写,线程2的操作B对变量M执行“consume”读,并且操作B读取到的值源于操作A之后的“release”写序列中的任何一个(包括操作A本身)。
case 2描述的是一种传递性。
6.3.3.1.4 Synchronized-with 关系
定义如下:
```
An atomic operation A that performs a release operation on an atomic object M synchronizes withan atomic operation B that performs an acquire operation on M and takes its value from any side effect in the release sequence headed by A.
```
该关系描述的是,对于在变量 x 上的写操作 W(x) synchronized-with 在该变量上的读操作 R(x) 这个读操作欲读取的值是 W(x) 或同一线程随后的在 x 上的写操作 W’ 或任意线程一系列的在 x 上的 read-modify-write 操作(如 fetch_add()或
compare_exchange_weak())而这一系列操作最初读到 x 的值是 W(x) 写入的值。
例如:A Write-Release Can Synchronize-With a Read-Acquire,简单来说, 线程1的A操作写了变量x,线程2的B操作读了变量x,B读到的是A写入的值或者更新的值,那么A B 间存在 synchronized-with 关系。
6.3.3.1.5 Inter-thread happens-before 关系
定义如下:
```
Between threads evaluation A inter-thread happens before evaluation B if any of the following is true
1) A synchronizes-with B
2) A is dependency-ordered before B
3) A synchronizes-with some evaluation X and X is sequenced-before B
4) A is sequenced-before some evaluation X and X inter-thread happens-before B
5) A inter-thread happens-before some evaluation X and X inter-thread happens-before B
```
Inter-thread happens-before 关系具有传递性。该关系描述的是,如果A inter-thread happens-before B,则线程1的A操作对memory的访问结果,会在线程2的B操作执行前对线程2是可见的。
######6.3.3.1.6 Happens-before 关系
定义如下:
```
Regardless of threads evaluation A happens-before evaluation B if any of the following is true:
1) A is sequenced-before B
2) A inter-thread happens before B
```
Happens-before 指明了哪些指令将看到哪些指令的结果。
对于单线程,sequenced-before关系即是Happens-before 关系,表明了操作 A 排列在另一个操作 B 之前。
对于多线程,则inter-thread happens before关系即是Happens-before 关系。
Happens-before 关系推导图总结如下:
6.3.3.2 6种memory order描述
下面我们分别来解析一下上面说的6种memory order的作用以及用法。
6.3.3.2.1 顺序一致次序 - memory_order_seq_cst
SC是C 11中原子变量的默认内存序,它意味着将程序看做是一个简单的序列。如果对于一个原子变量的操作都是顺序一致的,那么多线程程序的行为就像是这些操作都以一种特定顺序被单线程程序执行。
从同步的角度来看,一个顺序一致的 store 操作 synchroniezd-with 一个顺序一致的需要读取相同的变量的 load 操作。除此以外,顺序模型还保证了在 load 之后执行的顺序一致原子操作都得表现得在 store 之后完成。
顺序一致次序对内存序要求比较严格,对性能的损伤比较大。
6.3.3.2.2 松弛次序 - memory_order_relaxed
在原子变量上采用 relaxed ordering 的操作不参与 synchronized-with 关系。在同一线程内对同一变量的操作仍保持happens-before关系,但这与别的线程无关。在 relaxed ordering 中唯一的要求是在同一线程中,对同一原子变量的访问不可以被重排。
我们看下面的代码片段,x和y初始值都是0
```
// Thread 1:
r1 = y.load(std::memory_order_relaxed); // A
x.store(r1 std::memory_order_relaxed); // B
// Thread 2:
r2 = x.load(std::memory_order_relaxed); // C
y.store(42 std::memory_order_relaxed); // D
```
由于标记为memory_order_relaxed的atomic操作对于memory order几乎不作保证,那么最终可能输出r1 == r2 == 42,造成这种情况可能是编译器对指令的重排,导致在线程2中D操作先于C操作完成。
Relaxed ordering比较适用于“计数器”一类的原子变量,不在意memory order的场景。
6.3.3.2.3 获取-释放次序 --memory_order_release memory_order_acquire memory_order_acq_rel
Acquire-release 中没有全序关系,但它供了一些同步方法。在这种序列模型下,原子 load 操作是 acquire 操作(memory_order_acquire),原子 store 操作是release操作(memory_order_release) 原子read_modify_write操作(如fetch_add(),exchange())可以是 acquire release 或两者皆是(memory_order_acq_rel)。同步是成对出现的,它出现在一个进行 release 操作和一个进行 acquire 操作的线程间。一个 release 操作 syncrhonized-with 一个想要读取刚才被写的值的 acquire 操作。
也就是,如果在线程1中,操作A对原子M使用memory_order_release来进行atomic store,而在另外一个线程2中,操作B对同一个原子变量M使用memory_order_acquire来进行atomic load,那么线程1在操作A之前的所有写操作(包括操作A),都会在线程2完成操作B后是可见的。
我们看下面一个例子:
```
std::atomic<std::string*> ptr;
int data;
void producer()
{
std::string* p = new std::string("Hello");//A
data = 42;//B
ptr.store(p std::memory_order_release);//C
}
void consumer()
{
std::string* p2;
while (!(p2 = ptr.load(std::memory_order_acquire)))//D
;
assert(*p2 == "Hello"); //E
assert(data == 42); //F
}
int main()
{
std::thread t1(producer);
std::thread t2(consumer);
t1.join(); t2.join();
}
```
首先,我们可以直观地得出如下关系:A sequenced-before B sequenced-before C、C synchronizes-with D、D sequenced-before E sequenced-before F。利用前述happens-before推导图,不难得出A happens-before E、B happens-before F,因此,这里的E、F两处的assert永远不会fail。
6.3.3.2.4 数据依赖次序 memory_order_consume
memory_order_consume是轻量级的memory_order_acquire,是 memory_order_acquire 内存序的特例:它将同步数据限定为具有直接依赖的数据。能够用memory_order_consume的场景下就一定能够使用memory_order_acquire,引入memory_order_consume的目的是为了在一些已知的PowerPC和ARM等weakly-ordered CPUs上,对于在对有数据依赖的数据进行同步的时候不要插入额外memory barrier,因为它们本身就能保证在有数据依赖的情况下机器指令的内存顺序,少了额外的memory barrier对性能提升还是比较大的。
memory_order_consume描述的是dependency-ordered-before关系。我们看上面的例子,把D中memory_order_acquire改成memory_order_consume会怎样呢?
这个时候,由于p2和ptr有数据依赖,上面例子基本的关系对是:A sequenced-before B sequenced-before C、C dependency-ordered before D、D carries a dependency into E, E sequenced-before F。
根据关系推导,由C dependency-ordered before D && D carries a dependency into E得到C dependency-ordered before E,进一步得到C Inter-thread happens-before E,继而A sequenced-before C && C Inter-thread happens-before E得到A Inter-thread happens-before E,于是得到A Happens-before E,E永远不会assert fail。对于F,由于D、F间不存在 carries a dependency关系,那么F的assert是可能fail的。
通常情况下,我们可以通过源码的小调整实现从Release-Acquire ordering到Release-Consume ordering的转换,下面是一个
例子:
7. 总结
本文通过一个无锁队列为引子,介绍了无锁编程涉及的6个技术要点,其中内存屏障是最为关键,使用什么样的memory barrier,什么时候使用memory barrier又是其中的重中之重。memory barrier不容易理解,要想正确高效地使用memory barrier就更难了,通常情况下,能不直接用memory barrier原语就不用,最好使用锁(互斥量)等互斥原语这样的隐含了memory barrier功能的原语。锁在在很长一段时间都被误解了,认为锁是慢的,由于锁的引入,给性能带来巨大的瓶颈是很常见的。但这并不意味着所有的锁都是缓慢的,当我们使用轻量级锁并控制好锁竞争的时候,锁依然有非常出色的性能表现,锁不慢,锁竞争慢。