Understand std::atomic::compare_exchange_weak() in C++11(译文) | 知行一

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类似了。

 

 

发表评论