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

数据竞争与乱序执行

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

如果我们不使用临界区保护我们的代码段,就会导致数据竞争条件成立。我们对内存的操作才完成了一半,就会因线程调度等原因轻而易举地让另外一个线程开始对相同的内存进行读或写操作。这时会发生截断读写(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/

 

C++中怎么对野指针进行防护

一直从事C++底层库的开发,这里以监听模式来示例野指针的防护。底层通知上层,一种方式是,底层提供一个监听接口类,上层实现,然后注册下来,一般是有注册就有反注册,可是把下层安全压在上层使用者,期望他们在释放这个监听接口类之前总是进行反注册,这个就太不明智,那么我们就需要基于框架设计能防护野指针破坏,这里我们提供一个Guard机制。
Guard翻译过来的意思就是警卫,顾名思义就是用来防护的。先看其实现:

一个Guard对象正常的通过其构造函数实例化的时候,那我们就认为这个Guard是一个主Guard,m_host设置为true,其实例化一个GuardHelper对象,这个对象有一个引用计数的标识和标识这个主Guard是否有效的标识位。我们再来分析其析构函数,如果是主Guard,其在析构的时候,会将Guard有效标识为设置为false,当引用计数为0时,释放m_guard实例。这里介绍最关键的副Guard概念,借由主Guard构建的Guard都是副Guard,在复执构造函数和赋值中m_host都是false。为了方便使用使Guard可以转化为bool。
其实说到这,我们怎么来防护野指针的思路也就有了,在类型中实例化一个主Guard,在其他需要保存这个指针的地方,保存一份其主Gurad的副Guard,那么在这个指针析构的时候,主Guard也就析构了,那么其他的副Gurad的m_vaild值就为false,那么我们在使用这个指针时就可以知道这个指针已经是野指针了。
那么主Guard该放在那里了,放在库框架的基类再合适不过,这个就可以在整个框架中的指针就行防护。

使用Guard的时候一般都是这样,保存指针和其副Guard。

这种结构过于丑陋,这里我们提供一个包裹类,将其作成一个Guard指针,和平常的指针一样使用。

使用示例:

运行结果:

对上层的野指针就行了防护,使用Guard的唯一一个需要特别注意的就是一定要值传递,不然你会挂的很惨。

Understand std::atomic::compare_exchange_weak() in C++11(译文)

 

原文地址:http://www.codeproject.com/Articles/808305/Understand-std-atomic-compare-exchange-weak-in-Cpl

背景

本文源自爆栈网上的一个提问。Compare-and-swap(CAS)是一个原子操作指令。在多线程中充当同步的组件模块。C++11在语言级别上支持原子操作,让我们能够写出可移植的多线程代码,并可以跨越支持标准的全部平台。

了解CAS到底是什么,在维基百科上有一篇很好的文章。简而言之,CAS操作从内从中读取值,并与一个预期(expected)的值做比较(compare),如果相等,就把一个预先定义好的所需的(desired)值存到那个内存地址。最重要的是,所有这些都是在以一个原子的方式进行的。从这个意义上讲,如果另外一个线程改变了这个值,那么CAS会失败。

C++11中的CAS

当预期的值与对象真正持有的值相等,那么它将返回成功并把所需的值写入内存。否则,预期值会被内存中实际的值覆盖更新,并返回失败。这在绝大多数情况下都是正确的,除了一个列外情况:CAS的weak版本即使是在内存的值与期望值相等的情况,也可能返回失败。在这种情况下,所需的值不会同步到内存当中。

伪失败(Spurious Failiure)

上述的例外情况是因为伪失败。在一些平台上面,CAS操作是用一个指令序列来实现的,不同与x86上的一个指令。在这些平台上,切换上下文,另外一个线程加载了同一个内存地址,种种情况都会导致一开始的CAS操作失败。称它是假的,是因为CAS失败并不是因为存储的值与期望的值不相等,而是时间调度的问题。CAS的strong版本的行为不同,它把这个问题包裹在其中,并防止了这种伪失败的发生。

为什么大多数情况要在循环中使用compare_exchange_weak()?

C++11 §29.6.5
A consequence of spurious failure is that nearly all uses of weak compare-and-exchange will be in a loop

典型示例A

你需要根据原子变量的值来实现原子变量的更新。更新失败意味着我们的期望值并不是原子变量的最新值,我们需要重试。注意,我们不关心失败是否是由伪失败或者并行写导致的。我们只关心是我们成功更新了原子变量的值。

在实际生产中的例子,几个线程同时并行地向同一个链表添加一个元素。每个线程首先获取头节点的指针,分配一个新的节点并把头结点指针赋值到新节点的next指针变量。最后,算法会尝试用新的节点更新为头指针。

另外一个例子就是用std::atomic<bool>来实现互斥锁。最多只有一个线程可以进入临界区,这取决于哪一个线程抢先把current值设置为true并退出CAS循环。

典型示例B

这个例子实际上是从Anthony的书中提到过的(C++ concurrency in Action). 与A的情况相反,你可能只希望原子变量更新一次,但你不关心是谁更新了它。只要变量没有更新,那么你才重试。这种情况经常使用在bool型变量中。比如,你需要为一个状态机的转移实现一个触发器,但是哪个线程触发的是不重要的。

注意,上面这种情况是不能拿来实现互斥锁的。因为多个线程可能同时进入临界区。

这就是说,在循环之外几乎绝不使用compare_exchange_weak()函数。因为有一个strong版本可以使用。例如

这里使用compare_exchange_weak()就不合适了,它会由于伪失败的原因返回false,而很可能并没有人占用临界区。

线程饥饿?

有一点值得提一下,伪失败是否会一直发生并让线程饿死,形成一个活锁?理论上这种情况是有可能发生的,一般是当compare_exchange_xxx()函数是用一个指令序列实现的,例如LL/SC. 频繁地访问同一个LL与SC之间的缓冲行会发生连续不断的伪失败。一个更切合实际的例子,是在线程调度中,所有的并发线程被调度成如下这种交错执行的模式。

上面的情况会发生吗?幸运的是,这不可能发生。C++11的标准保证了这一点。

§ 29.6.5
Implementations should ensure that weak compare-and-exchange operations do not consistently return false unless either the atomic object has value different from expected or there are concurrent modifications to the atomic object.

为什么要这样繁琐地使用compare_exchange_weak()并自己实现循环?为什么不使用compared_exchange_strong()?

这取决于具体的情况。

情况1:如果两种版本都在循环中使用,哪一个更好?

C++11标准中提到:

§ 29.6.5
When a compare-and-exchange is in a loop, the weak version will yield better performance on some platforms.

在x86平台(至少是到目前为止,也许将来的某一天,当更多的核心加入进来,出于效率目的改为LL/SC),weak和strong的两个版本本质上是一样的,因为他们都归结为一个cmpxchg指令。在其他的平台中,compare_exchange_xxx()的实现并不是原子的). Weak版本在循环中的性能会更好,因为strong版本会处理伪失败并在某些情况下重试。

但是

在极少数情况下,会是用strong版本来代替使用循环的weak版本。比如在我们获取原子变量的值与最后更新原子变量之间,有许多事情要做的情景。如果原子变量自身变化并不是很频繁,我们没有必要为每一次的伪失败做开销很大的计算。反而期望compare_exchange_strong()吸收这些失败,而仅在由于值的改变而失败的情况下做重试。

情况2:strong版本代替weak版本循环

C++11标准中提到:

§ 29.6.5
When a weak compare-and-exchange would require a loop and a strong one would not, the strong one is preferable.

这种情况是当你做循环只是为了排除伪失败。你可能在exchange操作成功或者因为值的修改而失败的情况下,不再重试了。

上面的代码充其量,是在重复造轮子而且行为跟compare_exchange_strong()一样。上面的代码段使用的方法,没有充分利用在硬件中的排除伪失败的compare-and-exchange的机制。

最后,如果你因为其他原因而循环重试(比如前面典型示例A),那么把strong版本放到循环可能效果也会更好,这就跟情况1类似了。

 

 

recurse lambda in c++14

如果用std::function则需要在上下文环境中捕获这个function

lambda则可以作为一个变量

 

 

Copy Protected by Chetan's WP-Copyprotect.