理解使用内存访问排序的原子操作 | 知行一

理解使用内存访问排序的原子操作

数据竞争与乱序执行

当至少两个线程并发的访问一块没有任何保护的内存,并至少有一线程执行写操作,这个时候会发生数据竞争。为了避免这种情况的发生,我们可以在每个线程中分别加入一个临界区,通常是一个互斥锁,来保护该线程的读或写的代码段。事情似乎很简单,当线程要访问这块内存的时候,先加锁进入临界区,操作完成之后再解锁退出临界区。全部的事情只多了一个加锁和解锁的操作。可是,在使用无锁编程的场景下,事情就没有这么简单了。

如果我们不使用临界区保护我们的代码段,就会导致数据竞争条件成立。我们对内存的操作才完成了一半,就会因线程调度等原因轻而易举地让另外一个线程开始对相同的内存进行读或写操作。这时会发生截断读写(torn read and write)的问题。还有比这个更糟糕的,程序并不是按照你编码的那样运行。

编译器看到我们的代码,觉得如果程序按照这样运行太糟糕了,便吐槽到,“噢,我想你的这些代码并不是这个意思,就按照我的修改来执行吧”!结果,我们的代码逻辑,就这样被调整了顺序。然后事情扔给了处理器,可是处理器跟人类一样“聪明”,并不会老老实实地一条一条指令挨着执行下去,它会按照自己的方式调整处理事情的顺序让程序更快。

以上在实际中无时无刻都在发生。虽然对于单线程而言,这些乱序都是透明的,等价的。但是当我们从另外一个线程,来看这个线程的时候,可想而知事情全乱套了。另外一个线程在这个时候再访问这块内存,可能会导致未定义的行为。这里有一个测试乱序执行的小代码。

unorder

事实上,从源代码到最终的执行,除了编译器优化和处理器乱序执行之外,各级缓存没有即使刷到内存与处理单元的私有缓存都会导致乱序的结果。参考[1]中的解释,我们无法分辨到底是其中的哪一个环节导致乱序的发生。这时,为了避免数据竞争,我们要介入代码的生成与执行规则,让它们按照一定的顺序来访问这块内存。

顺序

先看一个栗子,这个栗子出自于[2]中5.3节。

reader线程是执行reader_thread()的线程;writer线程是执行writer_thread()的线程。reader线程,一直在等待writer线程把data_ready变量置为true,并访问data中第一个元素的变量。而writer线程向空的data中插入一个元素,并把data_ready置为true. 利用注释中对操作的字母编号,我们来列举一下这里栗子中操作的顺序关系:

1. A发生在B之前(A happens before B);
2. C发生在D之前(C happens before D);
3. B与C同步(B synchronizes with C);
4. 可以保证A发生在D之前(A inter-threaded happens before D).

这里出现了好几个术语,happens-before,synchronizes-with和inter-thread happens-before等关系。下面逐个解释。

同步关系 – synchronizes-with

同步关系是反应原子变量之间的顺序关系,且仅对原子变量。引用[2]中的一句定义,a suitably tagged atomic write operation W on a variable x synchronizes-with a suitably tagged atomic read operation on x that reads the value stored by either that write(W), or a subsequent atomic write operation on x by the same thread that performed the initial write W, or a sequence of atomic read-modify-write operations on x by any thread, where the value read by the first thread in the sequence is the value written by W. 讲人话就是指,对同一个原子变量的两个操作读和写,如果他们都标上了正确的内存访问排序(memory ordering)的标识,那么读操作和写操作在各种情况下就是同步的,也就是说对原子变量的读取的值,就是同步的写操作写进去的值。

下一章再解释什么是内存访问排序。同步关系并没有明确地指明一个先后顺序关系,它只是能够保证读取操作的值,如果是写入操作的结果,就可以确定一个严格的先后顺序,写发生在读之前。而这是需要我们用代码来保证的,比如上一个示例中C操作的while循环,还有自旋锁的实现。

除了确定一个先后顺序关系之外,同步关系影响着事发优先(happens-before)优先,序列优先(sequenced-before)关系和线程间的事发优先(inter-threaded happens-before)关系。同步关系可以链接各个优先关系,并把优先关系传递下去。稍后我们就可以看到它是如何传递的。而同步关系对其他优先关系作用的细节,稍后再做讨论。

序列优先 – sequenced-before

序列优先明确的指出了一个先后关系。参考[3]给出的定义,序列优先是针对单线程而言的,即在同一个线程中有两个操作X,Y,当X的求值在Y的求值开始之前就完成了,X就是序列优先于Y. 对这一章一开始给出的例子而言,C就是序列优先与D,而A是序列优先于B的。序列优先关系比较简单。

事发优先(包括线程间的) – (inter-threaded) happens-before

这里把happens-before与inter-threaded happens-before放在一起讲。首先它们都明确的指出了一个先后关系。它们之间的关系,参考[3]中的定义,我给出了下图。

prior

 

上图给出的定于与[3]略有不同,因为[3]中有循环定义的行为。但是[3]中的某些定义可以归纳到优先顺序的传递性质。上图中多出了一个依赖优先(dependency-ordered before)关系,这个关系也是可以跨线程的,我们也放到下一章来讲解。

从上图可以看出事发优先与跨线程的事发优先关系都是由同步关系,序列优先关系组合构造出来的,还有依赖优先关系。结合本章一开始给出的例子,我们可以得出:

1. A事发优先于B – A序列优先与B,B与C同步;
2. B事发优先与D – B同步于C,C序列优先于D;

优先顺序的传递

事发优先顺序是可以安全传递的。A事发优先于B,B事发优先于C,就能够得出A事发优先于C的结论。如果我们把事发优先和跨线程的事发优先定义展开,还能得出更丰富的结论。

1. X与Y同步,Y事发优先于Z << X事发优先与Z;
2. X跨线程事发优先于Y, Y跨线程事发优先与Z << X事发优先于Z,有可能X与Z在同一个线程;
3. A与B同步,B跨线程事发优先于C << A事发优先于C;
//…

在实际应用场景中,我们通常需要使用优先顺序的传递来确保操作的先后关系,来保证并发访问共享数据的可见性。然而,在文章的一开始提到过乱序执行的问题。对于本章一开始给出的示例中,操作A是如何保证序列优先与操作B的,B可能乱序到A之前;还有C是如何保证序列优先与D?前面提到过,同步操作是标记上了正确的内存访问排序标识的。并且还提到过,同步关系影响着这些优先关系。接下来的章节,将对这个问题做详细讨论。

C++11中的memory ordering

同步关系除了在一定条件下,保证了自身原子变量的先后关系之外,还通过标记一个同步语义,内存访问顺序标识,来构造与其他原子或非原子变量操作的顺序关系。在c++11的标准中,有六种原子变量操作的内存访问排序标识,定义在enum std::memory_order枚举变量中。详细见下表。

memory_order

 

顺序一致 & memory_order_seq_cst

先来谈谈最简单的排序类型,顺序一致的访问排序。这也是原子操作默认的行为。load操作如std::atomic<T>::load(),store操作如std::atomic<T>::store(),还有read-modify-write操作如std::atomic<T>::compare_exchange_weak(),都可以使用这个标识。再看上一节的示例中,使用的都是默认的原子操作的排序,也就是顺序一致的。示例展示了一个线程的load操作如何与另外一个线程的store操作同步。但是,顺序一致的排序,功能更为强大。我们把文章最开始测试乱序的代码稍作修改,就能够说明。

顺序一致保证了原子操作,不会被乱序执行,并且更进一步。标识了memory_order_seq_cst的原子操作,只要执行完成了,对其他各个线程都是可见的!就如上面的代码,t1线程的x.store(1)与t2线程的y.store(2)必有一个先执行。如果t1的先执行,那么由于顺序一致的保障,t2对x的load操作一定与t1对x的store操作同步,反之亦然。绝对不会出现不使用原子变量时,发生由乱序或者缓存导致的r1与r2同时为0的情况。顺序一致如此强大,它们阻止了编译的部分优化和处理器的乱序执行,并及时同步缓存与内存。从而,当一个线程的store操作发生完成后,其他各个线程对这个原子变量的读取能够达到一致。可想而知,它们的性能开销也是很大的。

这里也可以做出一个推论,一个线程中的两个顺序一致的原子操作,存在一个严格的序列优先关系。这也是为什么上一章示例中,操作A肯定优先于操作B,操作C优先于操作D的原因。

松弛的排序 & memory_order_relaxed

介绍的第二种内存访问排序标识,就是memory_order_relaxed. 事实上它不负责任何synchronizes-with语义。它仅仅只能保证,对原子变量的读写的原子性,没有截断读取的问题。如果我们把上面顺序一致的代码改成松弛的,它的行为将会与不使用原子变量的行为一样。

Acquire & Release语义

memory_order_acquire同memory_order_release是成对使用的。acquire只能对原子变量的load操作使用,而release只能对原子变量的store操作使用。在我看来,acqurie与release只能实现顺序一致下的一个场景,就是读与写同步,并构造一个store事发优先于load的关系,并保证store之前所有内存操作对load之后的内存操作可见。它比顺序一致要轻量,所以在某些架构平台下,它的性能比顺序一致要好很多。改造一下ordering一章中的示例,把顺序一致的操作变为acquire&release,是等价的。

这就是我为什么杜撰它们为acquire & release语义的原因。只有当操作B与C同步了之后,才能保证操作A对操作D可见。借用[4]中的一个比喻,操作A就好像是你在对自己本地的私有代码仓库实现新的功能,操作B就好比是使用git push,向远程仓库提交;当你第二天要开始新的代码任务前,也就是操作D,你需要从远程仓库git pull最新的代码,也就是操作C. 这也是acquire & release语义唯一正确的使用场景。值得一提的是,store之前的内存操作既可以是原子操作也可以是非原子操作。

memory_order_acq_rel也是为acquire & release语义服务的,只是它被限定在rmw操作上使用。我们再改造一下读写同步的栗子。

有了acquire & release语义后,这个栗子就很好理解了。compare_exchange_weak()会先执行一个load操作,如果比较成功再执行一个store操作。那么memory_order_acq_rel就告诉这个rmw操作,load时使用acquire,store时使用release. 在上面的栗子中,B1操作与C1的load操作部分,形成了一个acquire & release语义;而C1的store操作部分与D1形成了一个acquire & release语义。这样,使得rwm_thread线程成为了一个承上启下的作用。当然在实际应用中,不会这么实现,这里是为了说明,memory_order_acq_rel是为rmw操作量身定做的,本质上也是为acquire & release语义服务。

依赖优先与依赖携带关系(dependency-ordered before & carries dependency into)

上一章介绍事发优先关系的时候,提到过依赖优先。递延到此时此刻,是因为需要借助acquire & release语义来解释,就会简单许多。首先来介绍一下依赖携带关系。

根据[3]给出的定义,操作X与操作Y之间有依赖携带关系的必要条件,是A序列优先与B. 此外,还需要满足一个条件。A的求值结果作为B的操作数,或者A在求值过程中对一个scalar变量M有修改,并且B使用了M.定义的细节请参阅[3]中的文档。memory_order_consume就是用来暗示代码的依赖关系来约束先后顺序的,同memory_order_acquire一样,它也只能用在原子变量的load操作。

有了依赖携带关系,接着来看依赖优先关系。与acquire & release语义类似,consume & release也是成对使用的,只是它release store操作之前的内存操作约束更少。如果一个原子变量的release store操作同另外一个线程的同一个原子变量的consume load操作同步,并且release store之前的内存操作X与release store操作携带依赖关系,那么consume load操作之后的任何内存操做都能看见X. 我们再通过一个栗子说明。

结合这个栗子,reader_thread线程中的C2操作一旦判断成功,即ptr不为空指针,那么C2就与writer_thread中的B2操作同步。这时的同步是consume & release语义的同步。这意味着依赖优先于B2全部操作,对D2都是可见的。前面的A21,A22,A23的操作对D2都是可见的。

内存访问排序小结

我们看到了六种C++11标准库的内存访问排序的标识。列举了一些synchronizes-with的场景,顺序一致、acqurie & release和consume & release三种场景。松弛的原子操作并不负责任何synchronizes-with的关系。三种不同的同步关系,会影响旁边代码的事发先后关系,如acquire与consume的不同,还有顺序一致与其他非顺序一致同步的不同。此外,同步关系也是连接事发优先与序列优先的纽带。通过控制对共享内存的访问顺序,帮助我们保证代码在运行时对共享内存的访问安全。

参考文献

[1] https://channel9.msdn.com/Shows/Going+Deep/Cpp-and-Beyond-2012-Herb-Sutter-atomic-Weapons-1-of-2
[2] c++ concurrency in action
[3] http://en.cppreference.com/w/cpp/atomic/memory_order
[4] http://preshing.com/20130922/acquire-and-release-fences/
[5] http://preshing.com/20140709/the-purpose-of-memory_order_consume-in-cpp11/

 

《理解使用内存访问排序的原子操作》有2个想法

发表评论