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

数据竞争与乱序执行

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

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

A Fast General Purpose Lock-Free Queue for C++(译文)

原文标题:A Fast General Purpose Lock-Free Queue for C++
中文标题:一个快速通用的C++无锁队列

原文地址:http://moodycamel.com/blog/2014/a-fast-general-purpose-lock-free-queue-for-c++
作      者:Cameron Desrochers
翻      译:郭子

前言

各位,我一直被无锁编程的bug所困扰。在完成我的单生产者-单消费者的无锁队列 (single-producer, single-consumer lock-free queue) 以后,我决定设计和实现一个更通用的多生产者-多消费者的队列,并且跟市面上已有的C++无锁队列比较,看能提升多少。经过一年左右业余时间的开发和测试,终于完成了公开发行的版本。 TL;DR:你可以在我的 GitHub 上找到C++11的实现代码(或者跳到下面的benchmarks部分)。

我想,这个队列的工作方式是有趣的,所以这就是这个博客文章要说的东西。顺便说一下,一个更详细和完整(但也更烦杂)的描述内容在另一个姐妹博客文章里。

数据共享:哦,好麻烦

乍一看,一个通用的无锁队列似乎相当容易实现,事实并非如此。问题的根源在于,一个相同的变量一定需要与几个线程共享。例如,使用常用的基于链表的方法:至少有一点,列表的head和tail指针都需要共享,因为所有消费者都必须读取或更新head指针,所有的生产者都需要更新tail指针。

到目前为止,这听起来还不算太糟糕,但真正的问题出现在,当一个线程需要更新多于一个变量来保持队列的一致状态的时候。真正的矛盾是,原子操作只能保证单个变量的原子性(具体长度由硬件的最大原子变量的字节长度决定),对于复合变量(结构体)的操作几乎肯定需要一把锁才能保证其原子性(在大多数操作系统上,视复合变量或结构体的字节长度,若超过硬件最大原子变量的字节长度就必须用锁)。例如,如果一个消费者从一个队列中读取仅剩的最后一个元素的时候,只需要更新head指针就行了吗?当然不,tail指针此时也不应该再指向它,因为弹出的元素(对象)很快就要被释放了(此时 tail指针应该置为空)!但是消费者在更新tail指针之前,可能会被操作系统中断并且被挂起几毫秒,在这个期间,tail指针的值可能会被别的线程修改,然而,等被挂起的线程被重新唤醒后,并且把tail指针置为空,但这一切已经太迟了。

这个对共享数据这一基本问题的解决方案是无锁编程的关键所在。通常情况下,最好的办法是构思一个算法,并不需要更新多个变量来保证第一个位置的一致性,或者使用一个增量式的更新后,依然能让数据结构保持一致性状态。各种招数都可以使用,比如对象分配以后就再也不释放(这有助于从那些不是最新的线程读取数据,当然不释放其实是不可能的,我们可以延迟释放,在一个适当的时间释放它),存储额外的状态在指针地址的最低的两个bit里(这个方法在指针地址是4字节对齐的时候有效),或者使用引用计数指针等等。但是,这些技巧只能走这么远,真正的关键还是要看开发的算法本身。

我的队列

越少的线程争夺同一个数据,就越好。所以,我们宁可使用一组子队列(一个Producer线程对应一个子队列),而不是使用一个单一的数据结构来线性化所有操作。这意味着,不同的线程可以完全并行的执行元素的入队操作,它们之间是彼此独立的。

当然,这会让出队稍微变得复杂:现在当我们出队时,不得不检查每一个子队列的元素。有趣的是,事实证明,该元素从子队列出队的顺序其实并不重要。所有来自一个给定的Producer线程的元素一定还会保持着入队时同样的相对顺序出队(因为子队列保留了该顺序),尽管来自其他子队列的元素可能会交错。元素顺序上的交错是可以接受的,因为即使是在传统的单队列模式下,从不同的Producer线程执行读取 get() 和写入put() 操作的时候,顺序本来就是不确定的(因为在不同的Producer线程之间,有一个条件竞争)。(修正:这只有在Producer线程是独立的时候才能成立,不是一定都成立的,详细请看文章后面的回复。)

这种方式的唯一缺点就是,如果队列是空的时候,每一个子队列不得不按顺序一个个检测一遍,以确定是否真的为空(并且,一个子队列在被检测的时候,之前已经被认为是空的子队列可能会变成非空队列,但实际上,这并不会造成问题)。然而,在队列非空的情况下,会减少许多全局竞争,因为子队列可以跟Consumers配对。这减少了数据共享并达到了最优水平(此时,每一个Consumer会恰好匹配一个Producer),并且又不会失去处理一般情况的能力。这个配对可以使用启发式,考虑从一个Producer成功拉取元素的最后一个子队列(实质上,他给了Consumers一个亲和度)。当然,为了实现这个配对,在调用出队操作之间,某些状态必须保持,这是依赖于使用者负责给Consumer 分配和指定“tokens”来完成的。请注意,这些tokens完全是可选的,队列仅仅只是恢复搜索每一个子队列的元素直到为空为止,这是正确的,只是当多个线程调用的时候会稍微慢一些。

所以,这是高层次的设计。那么在每一个子队列里面使用的核心算法是什么呢?当然,我们不会选择基于节点的链表(这意味着,不断的分配、释放或重新使用元素,并且通常依赖于一个Compare-And-Swap循环,当重度竞争的情况下,这样会比较慢),我让我的queue基于一个数组,而不是链接单个元素,我定义了一个”Block”(块)的概念,它由N个元素组成,比如N等于32。队列的逻辑头部(head)和尾部(tail)的索引使用一个原子变量(整型)递增来表示,在这些逻辑索引和Block块之间存在着一个每一个索引映射到它的Block块和这些Block块的子索引的方案。一个入队操作简单的递增tail变量(请记住,对于每一个子队列,有且只有一个Producer线程),一个出队操作递增head变量,如果它看到head小于tail的值时,它会检查,看它是否意外递增head并超过了tail的值(这可能会在一个子队列有多个Consumer竞争的情况下发生)。如果这种情况发生了,一个校正计数器会被递增(为了保证队列最终的一致性);如果没有发生,它会往前走,递增另一个Integer原子值(final index,这是它得到的实际最终逻辑索引值)。这个final index的增量总是在实际的队列中产生一个有效的索引,不管其他线程正在做什么或者已经做完什么;这能成立的原因是因为当保证至少有一个元素出列时,final index永远是单调递增的(当first index被递增的时候,这个会被检测)。

所以你有了它以后,仅用一个原子递增即可完成一个入队操作,使用快速路径的两个原子递增和一个额外的If判断即可完成一个出队操作(当然,这是扣除了所有block的分配/重用/引用计数/block映射的,这里,它们虽然重要,但不是非常有趣,在任何情况下,大部分的成本都分摊在一个完整的Block块的元素价值。这种设计真正有趣的部分是,他允许非常有效的批量操作,就原子指令而言,这往往是一个瓶颈。在一个Block块压入X个元素的开销完全等价于压入一个元素(同理,对于出队也是一样),只要它们是在同一个块。

我听说这里有代码

因为我认为对于C++,必须有一个高质量的无锁队列,所以我基于我自己提出的设计思路写了一个。(虽然还有其他选择,特别是Boost和Intel’s TBB(Thread Building Blocks)的实现,但我的有更多的细节,比如对元素类型没有严格的限制,并且启动更快一点。)你可以在 GitHub 上找到它,这一切代码都包含在一个头文件里,并且是基于简化的BSD license,把它拉下来放在你的项目里,并且享受它吧。

Github地址:https://github.com/cameron314/concurrentqueue

性能测试

因此,创建数据结构最有趣的部分是写一个综合测试,然后看你的是否比别的实现更快。在我的测试项目里,使用了Boost 1.55的lock-free queue,Intel’s TBB 4.3 concurrent_queue,另一个我自己写的基于链表实现的lock-free queue(一个native设计),一个基于std::mutex实现的有锁队列,以及一个标准的 std::queue(仅使用一个线程,防止引用一个常规的数据结构)。注意,下面的图只展示了测试结果的一个子集,并且省略了native lock-free queue和单线程std::queue的实现的测试数据。

测试结果如下,在漂亮的图表后面是详细的原始数据(注意,由于绝对吞吐量的巨大差异,我不得不使用一个对数来显示差值。)[译者注:由于测试结果的原始数据太长了,这里就不贴了,如有兴趣,请看原文链接。]

下面是在亚马逊的AWS 8核CPU的虚拟机上得到的测试结果:

Intel(R) Xeon(R) Dual E5506 @ 2.13GHz, 8 Cores, 64 bit OS

下面是在亚马逊的AWS 32核CPU的虚拟机上得到的测试结果:

Intel(R) Xeon(R) Dual E5-2670 @ 2.60GHz, 32 Cores, 64 bit OS

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.