理解C++ 11中的std :: atomic :: compare_exchange_weak()

Question

bool compare_exchange_weak (T& expected, T val, ..);

compare_exchange_weak()是C++ 11中提供的比较交换原语之一.它在某种意义上很弱,即使对象的值等于它也会返回false expected.这是由于某些平台上的虚假故障导致一系列指令(而不是x86上的指令)用于实现它.在这样的平台上,上下文切换,由另一个线程重新加载相同的地址(或高速缓存行)等可能使原语失败.这是spurious因为它不是expected操作失败的对象(不等于)的值.相反,这是一种时间问题.

但让我感到困惑的是C++ 11标准(ISO/IEC 14882)中所说的,

29.6.5 ..虚假失败的后果是几乎所有弱比较和交换的使用都将处于循环中.

为什么几乎所有用途都必须处于循环中？这是否意味着我们会因为虚假失败而失败？如果是这样的话,为什么我们compare_exchange_weak()自己打扰使用并编写循环？我们可以使用compare_exchange_strong()我认为应该摆脱我们的虚假失败.有哪些常见用例compare_exchange_weak()？

另一个问题有关.安东尼在他的书"C++ Concurrency In Action"中说,

//Because compare_exchange_weak() can fail spuriously, it must typically
//be used in a loop:

bool expected=false;
extern atomic<bool> b; // set somewhere else
while(!b.compare_exchange_weak(expected,true) && !expected);

//In this case, you keep looping as long as expected is still false,
//indicating that the compare_exchange_weak() call failed spuriously.

为什么!expected存在循环条件？是否可以防止所有线程在一段时间内挨饿并且没有任何进展？

编辑:(最后一个问题)

在没有单个硬件CAS指令的平台上,弱版和强版都使用LL/SC(如ARM,PowerPC等)实现.那么以下两个循环之间有什么区别吗？为什么,如果有的话？(对我来说,他们应该有类似的表现.)

// use LL/SC (or CAS on x86) and ignore/loop on spurious failures
while (!compare_exchange_weak(..))
{ .. }

// use LL/SC (or CAS on x86) and ignore/loop on spurious failures
while (!compare_exchange_strong(..)) 
{ .. }

我提出这个最后一个问题你们都提到在循环中可能存在性能差异.它也被C++ 11标准(ISO/IEC 14882)提及:

当比较和交换处于循环中时,弱版本将在某些平台上产生更好的性能.

但如上所述,循环中的两个版本应该提供相同/相似的性能.我想念的是什么？

Answer 1

为什么要在循环中进行交换？

通常,您希望在继续之前完成工作,因此,您compare_exchange_weak进入循环以便尝试交换直到成功(即返回true).

请注意,它也compare_exchange_strong经常用在循环中.它不会因为虚假故障而失败,但由于并发写入而失败.

为什么用weak而不是strong？

非常简单:虚假故障不会经常发生,所以它不会受到很大影响.相比之下,容忍这样的故障允许在某些平台上更高效地实现weak版本(与之相比strong):strong必须始终检查虚假故障并屏蔽它.这很贵.

因此,weak使用它是因为它比strong某些平台快得多

你何时应该使用weak何时strong？

该参考指出提示何时使用weak,何时使用strong:

当比较和交换处于循环中时,弱版本将在某些平台上产生更好的性能.当一个弱的比较和交换需要一个循环而一个强大的那个不需要时,强者更可取.

所以答案似乎很容易记住:如果你因为虚假失败而不得不引入一个循环,那就不要这样做了; 用strong.如果你有一个循环,那么使用weak.

为什么!expected在这个例子中

它取决于情况及其所需的语义,但通常不需要正确性.省略它会产生非常相似的语义.只有在另一个线程可能将值重置为的情况下false,语义可能会略有不同(但我找不到您想要的有意义的示例).有关详细解释,请参阅Tony D.的评论.

当另一个线程写入时,它只是一个快速通道true:然后我们中止而不是true再次尝试写入.

关于你的上一个问题

但如上所述,循环中的两个版本应该提供相同/相似的性能.我想念的是什么？

来自维基百科:

如果没有对所讨论的存储器位置进行并发更新,则LL/SC的实际实现并不总是成功.两个操作之间的任何异常事件(例如上下文切换,另一个加载链接,或甚至(在许多平台上)另一个加载或存储操作)将导致存储条件虚假地失败.如果通过内存总线广播任何更新,则较旧的实现将失败.

因此,例如,LL/SC将在上下文切换时虚假失败.现在,强大的版本将带来其"自己的小循环"来检测虚假故障并通过再次尝试来掩盖它.请注意,这个自己的循环也比通常的CAS循环更复杂,因为它必须区分虚假失败(并掩盖它)和由于并发访问导致的失败(导致返回值false).弱版本没有这样的循环.

由于您在两个示例中都提供了显式循环,因此没有必要为强版本提供小循环.因此,在strong版本的示例中,检查失败两次; 一次通过compare_exchange_strong(这是更复杂,因为它必须区分虚假故障和并发访问)和一次通过你的循环.这种昂贵的检查是不必要的,其原因weak在这里会更快.

另请注意,您的参数(LL/SC)只是实现此目的的一种可能性.有更多的平台甚至有不同的指令集.此外(更重要的是)请注意,std::atomic必须支持所有可能数据类型的所有操作,因此即使您声明了一个1000万字节的结构,也可以使用compare_exchange此方法.即使在具有CAS的CPU上,也不能有CAS一千万字节,因此编译器将生成其他指令(可能是锁定获取,然后是非原子比较和交换,然后是锁定释放).现在,想想在交换1000万字节时会发生多少事情.因此,虽然8字节交换可能非常罕见,但在这种情况下可能更常见.

简而言之,C++给你两个语义,一个"尽力而为"一个(weak)和一个"我肯定会这样做,无论在一个(strong)之间可能发生多少坏事.如何在各种数据类型和平台上实现这些是一个完全不同的主题.不要将您的心理模型与特定平台上的实现联系起来; 标准库旨在使用比您可能意识到的更多架构.我们可以得出的唯一一般结论是,保证成功通常比仅仅尝试并为可能的失败留出空间更困难(因此可能需要额外的工作).

Answer 2

为什么几乎所有用途都必须处于循环中？

因为如果你没有循环并且它失败了你的程序没有做任何有用的事情 - 你没有更新原子对象而你不知道它的当前值是什么(更正:见Cameron下面的评论).如果电话没有做任何有用的事情是什么意思呢？

这是否意味着我们会因为虚假失败而失败？

是.

如果是这样的话,为什么我们compare_exchange_weak()自己打扰使用并编写循环？我们可以使用compare_exchange_strong(),我认为应该摆脱我们的虚假失败.compare_exchange_weak()的常见用例有哪些？

在某些体系结构compare_exchange_weak上效率更高,虚假故障应该是相当罕见的,因此可以使用弱形式和循环编写更有效的算法.

通常,如果您的算法不需要循环,则可能更好地使用强版本,因为您不需要担心虚假失败.如果它仍然需要循环甚至强版本(并且许多算法确实需要循环),那么在某些平台上使用弱形式可能更有效.

为什么!expected存在循环条件？

该值可能true已由另一个线程设置,因此您不希望继续尝试设置它.

编辑:

但如上所述,循环中的两个版本应该提供相同/相似的性能.我想念的是什么？

当然,很明显,在可能存在虚假故障的平台上,实现compare_exchange_strong必须更加复杂,以检查虚假故障和重试.

弱形式只是在虚假失败时返回,它不会重试.

Answer 3

我在尝试通过各种在线资源(例如,这一个和这个),C++ 11标准以及这里给出的答案后自己回答这个问题.

相关的问题被合并(例如," 为什么!预期？ "与"为什么将compare_exchange_weak()置于循环中？ ")并且相应地给出答案.

为什么compare_exchange_weak()几乎在所有用途中必须处于循环中？

典型模式A.

您需要根据原子变量中的值实现原子更新.失败表示变量未使用我们所需的值更新,我们想重试它.请注意,由于并发写入或虚假故障 ,我们并不关心它是否会失败.但我们确实关心的是我们 做出这种改变.

expected = current.load();
do desired = function(expected);
while (!current.compare_exchange_weak(expected, desired));

一个真实的例子是几个线程同时向单个链表添加一个元素.每个线程首先加载头指针,分配一个新节点并将头部附加到这个新节点.最后,它尝试将新节点与头部交换.

另一个例子是使用mutex实现std::atomic<bool>.最多一个线程可以同时进入临界区,这取决于哪个线程先设置current到true和退出循环.

典型模式B.

这实际上是安东尼的书中提到的模式.与模式A相反,您希望原子变量更新一次,但您不关心是谁做的.只要它没有更新,你再试一次.这通常与布尔变量一起使用.例如,您需要为状态机实现触发器以继续前进.无论哪个线程拉动触发器.

expected = false;
// !expected: if expected is set to true by another thread, it's done!
// Otherwise, it fails spuriously and we should try again.
while (!current.compare_exchange_weak(expected, true) && !expected);

请注意,我们通常不能使用此模式来实现互斥锁.否则,多个线程可能同时位于关键部分内.

也就是说,compare_exchange_weak()在循环外使用它应该是罕见的.相反,有些情况下正在使用强版本.例如,

bool criticalSection_tryEnter(lock)
{
  bool flag = false;
  return lock.compare_exchange_strong(flag, true);
}

compare_exchange_weak 这里不合适,因为当它因虚假失败而返回时,很可能没有人占用临界区.

饥饿的线程？

值得一提的一点是,如果虚假失败继续发生,那么会发生什么？从理论上讲,它可以在平台compare_exchange_XXX()上实现,当实现为一系列指令(例如,LL/SC).在LL和SC之间频繁访问相同的高速缓存行将产生连续的虚假故障.一个更现实的例子是由于一个哑调度,其中所有并发线程以下列方式交错.

Time
 |  thread 1 (LL)
 |  thread 2 (LL)
 |  thread 1 (compare, SC), fails spuriously due to thread 2's LL
 |  thread 1 (LL)
 |  thread 2 (compare, SC), fails spuriously due to thread 1's LL
 |  thread 2 (LL)
 v  ..

会发生吗？

幸运的是,由于C++ 11的要求,它不会永远发生:

实现应该确保弱比较和交换操作不会始终返回false,除非原子对象具有与预期不同的值或者对原子对象进行并发修改.

为什么我们打扰使用compare_exchange_weak()并自己编写循环？我们可以使用compare_exchange_strong().

这取决于.

情况1:当两者都需要在循环内使用时.C++ 11说:

当比较和交换处于循环中时,弱版本将在某些平台上产生更好的性能.

在x86上(至少目前.当引入更多内核时,它可能会采用类似于LL/SC的类似方式来表现性能),弱版和强版基本相同,因为它们都归结为单指令cmpxchg.在其中一些其他平台compare_exchange_XXX()没有实现原子(这里指没有单一的硬件原始的存在),内循环弱版本可能会赢得这场战斗,因为强大的一个必须处理的假故障并相应地重试.

但,

很少,我们可能更喜欢compare_exchange_strong()在compare_exchange_weak()即使是在一个循环.例如,当加载原子变量和交换计算的新值之间有很多事情要做时(参见function()上文).如果原子变量本身不经常变化,我们不需要为每个虚假失败重复昂贵的计算.相反,我们可能希望compare_exchange_strong()"吸收"这样的失败,我们只会在失败时重复计算,因为真正的价值变化.

案例2:当只 compare_exchange_weak() 需要在循环内使用时.C++ 11还说:

当一个弱的比较和交换需要一个循环而一个强大的那个不需要时,强者更可取.

当您循环以消除弱版本的虚假故障时,通常就是这种情况.您重试,直到交换成功或由于并发写入而失败.

expected = false;
// !expected: if it fails spuriously, we should try again.
while (!current.compare_exchange_weak(expected, true) && !expected);

充其量,它重新发明轮子并执行相同的操作compare_exchange_strong().更差？这种方法无法充分利用在硬件中提供非虚假比较和交换的机器.

最后,如果你循环其他事情(例如,参见上面的"典型模式A"),那么很有可能compare_exchange_strong()也应该放在循环中,这将我们带回到前一种情况.

Answer 4

好吧,所以我需要一个执行原子左移的功能.我的处理器没有本机操作,标准库没有它的功能,所以看起来我正在编写自己的.开始:

void atomicLeftShift(std::atomic<int>* var, int shiftBy)
{
    do {
        int oldVal = std::atomic_load(var);
        int newVal = oldVal << shiftBy;
    } while(!std::compare_exchange_weak(oldVal, newVal));
}

现在,循环可能被执行多次的原因有两个.

1. 当我做左移时,有人改变了变量.我的计算结果不应该应用于原子变量,因为它会有效地擦除其他人的写入.
2. 我的CPU出现故障,而弱的CAS虚假失败了.

老实说,我不在乎哪一个.左移很快,我也可以再做一次,即使失败是假的.

什么是少快,虽然是额外的代码,强有力的CAS需要环绕弱CAS以坚强.当弱CAS成功时,该代码没有太大作用......但是当它失败时,强大的CAS需要做一些侦探工作来确定它是案例1还是案例2.该侦探工作采取第二个循环的形式,有效地在我自己的循环中.两个嵌套循环.想象一下你的算法老师现在瞪着你.

正如我之前提到的,我并不关心侦探工作的结果!无论哪种方式,我都要重做CAS.所以使用强大的CAS几乎没有任何收获,并且失去了一小部分但可测量的效率.

换句话说,弱CAS用于实现原子更新操作.当您关心CAS的结果时,会使用强CAS.