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

Question

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

105

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

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

但是令我困惑的是C++11标准（ISO/IEC 14882）中的一段话：

29.6.5 .. 虚假失败的一个结果是，几乎所有使用弱比较交换的情况都会在循环中。

为什么几乎所有的用法都要使用循环呢？这是否意味着当由于虚假失败而失败时，我们应该进行循环？如果是这样的话，为什么我们还要使用compare_exchange_weak()并自己编写循环呢？我们可以直接使用compare_exchange_strong()，我认为这样可以消除虚假失败。compare_exchange_weak()的常见用例有哪些？

另一个相关的问题。在他的书《C++并发编程实战》中，Anthony说，

//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）中提到过：

当一个比较和交换操作在循环中时，弱版本在某些平台上会有更好的性能。

但是根据上面的分析，循环中的两个版本应该具有相同/相似的性能。我错过了什么？

- Eric Z

5

关于第一个问题，在许多情况下，您无论使用强版本还是弱版本都需要进行循环，而弱版本可能比强版本具有更好的性能。 - T.C.

3

弱和强的比较交换操作（CAS）都使用“LL/SC”实现，就像冒泡排序和快速排序都使用“swap”一样。也就是说，这是用于完成任务的基本操作。它们包装在“LL/SC”周围的内容非常不同。弱比较交换操作只是“LL/SC”。强比较交换操作则是带有大量其他内容的“LL/SC”。 - Sneftel

1

https://forums.manning.com/posts/list/33062.page 这个有帮助吗？ - Tu Xiaomi

通过那个链接中@TuXiaomi的回答，我看不出为什么标准中会说“弱版本在某些平台上会产生更好的性能”。 - Deqing

@Deqing 在其他平台上，由于中断或其他处理器或线程的操作，compare_exchange_weak 可能会出现虚假失败。在这些平台上，compare_exchange_strong 实际上是对 compare_exchange_weak 的循环 - 如果它虚假失败了，那么它会再次循环。这有帮助吗？也许我错了。 - Tu Xiaomi

5个回答

22

通过查阅各种在线资源（例如这篇和这篇），以及C++11标准和此处给出的答案，我尝试自己回答这个问题。

相关问题被合并了（例如"为什么!expected?"与"为什么将compare_exchange_weak()放在循环中？"合并在一起），并相应地给出了答案。

为什么几乎所有使用compare_exchange_weak（）的情况都必须在循环中进行？

典型模式A

您需要基于原子变量中的值实现原子更新。失败表明变量没有使用我们的期望值更新，并且我们想重试它。我们并不真正关心它是否由于并发写入或虚假失败而导致失败。但是，我们确实关心的是是我们进行了这个更改。

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

一个现实世界的例子是多个线程同时向单链表添加元素。每个线程首先加载头指针，分配一个新节点并将头部附加到此新节点。最后，它尝试交换新节点和头部。

另一个例子是使用 std::atomic<bool> 实现互斥锁。最多只能有一个线程进入关键区域，这取决于哪个线程首先将 current 设置为 true 并退出循环。

典型模式B

这实际上是Anthony的书中提到的模式。与模式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()放在循环中，这将使我们回到之前的情况。

- Eric Z

关于这一点：“幸运的是，由于C++11的要求：实现应该确保……”我的理解是，这里的“应该”并不意味着这是一个要求（如果是要求的话，应该会用“必须”）。所以，这个从句实际上并不能保证它不会无限循环，对吗？ - undefined

18

为什么几乎所有用法都需要循环？

因为如果你不循环，它会出现偶然失效，那么您的程序就没有任何有用的操作-您没有更新原子对象，并且不知道其当前值是多少（更正：请参见Cameron下面的评论）。如果调用没有任何有用的作用，那么进行调用有什么意义呢？

这是否意味着我们在失败时应该循环？

是的。

如果是这样，为什么要使用compare_exchange_weak()并自己编写循环呢？我们可以使用compare_exchange_strong()，我认为它应该为我们摆脱虚假失败。compare_exchange_weak()的常用用例是什么？

在某些体系结构上，compare_exchange_weak比较高效，并且虚假失败应该相当罕见，因此可以使用弱形式和循环编写更高效的算法。

一般来说，如果您的算法不需要循环，最好使用strong版本，因为您不需要担心虚假故障。如果无论如何都需要循环（许多算法确实需要循环），则在某些平台上使用弱形式可能更有效。

循环条件中为什么有“！expected”？

值可能已被另一个线程设置为true，因此您不希望继续循环尝试设置它。

但正如上面分析的那样，循环中的这两个版本应该具有相同/类似的性能。我错过了什么？

显然，在可能出现虚假失败的平台上，compare_exchange_strong的实现必须更加复杂，以检查虚假失败并重试。

弱形式只会在虚假失败时返回，而不会重试。

- Jonathan Wakely

2

+1 在所有方面都准确无误（这是Q急需的）。 - Tony Delroy

关于第一点中的“您不知道其当前值是什么”，当发生虚假故障时，当前值是否应该等于该瞬间的预期值？否则，这将是一个真正的故障。 - Eric Z

在我看来，无论是弱版本还是强版本，在没有单个CAS硬件原语存在的平台上都是使用LL/SC实现的。那么对我来说，“while(!compare_exchange_weak(..))”和“while(!compare_exchange_strong(..))”之间为什么会有性能差异呢？ - Eric Z

抱歉，各位，我又加了一个最后一个问题。 - Eric Z

即使当前值等于期望值，虚假失败仍然可能发生。Sneftel的答案解释了为什么强形式会做额外的工作，但是如果它必须检查虚假失败并重试，那肯定比只返回false更费力吧？ - Jonathan Wakely

1

@Jonathan：只是一个小问题，但如果它出现偶发性故障，您确实知道当前值（当然，无论您何时读取变量，该值是否仍然是当前值都是另一个问题，但这与弱/强无关）。我曾经尝试过使用这种方法来设置一个变量，假设其值为null，如果失败（无论是偶发性的还是不是），则继续尝试，但仅取决于实际值是什么。 - Cameron

14

好的，所以我需要一个函数来执行原子左移操作。我的处理器没有本地的这个操作，标准库也没有相应的函数，看起来我需要自己写一个。下面就开始吧：

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));
}

现在，循环执行超过一次可能有两个原因：

当我进行左移操作时，其他人更改了变量。我的计算结果不应该被应用于原子变量，因为这将有效地抹掉其他人的写入。
我的CPU出现错误，弱CAS误报了。

老实说，我并不关心是哪一个原因。左移操作足够快，所以即使失败是虚假的，我也可以再试一次。

但更慢的是强CAS需要包装在弱CAS周围的额外代码以使其强大。当弱CAS成功时，这些代码不会做太多事情...但是当它失败时，强CAS需要进行一些侦探工作来确定是情况1还是情况2。这个侦探工作采用第二个循环的形式，实际上在我自己的循环内部。两个嵌套的循环。想象一下你的算法老师此刻盯着你。

正如我之前提到的，我不关心那个侦探工作的结果！无论如何，我都将重新进行CAS。因此，在效率上使用强CAS没有任何好处，并且会损失一些小但可衡量的效率。

换句话说，弱CAS用于实现原子更新操作。当你关心CAS的结果时，使用强CAS。

- Sneftel

你的示例代码正确吗？乍一看，这段代码似乎从来没有对函数的调用者可观察到的任何东西进行操作。特别是，似乎只读取了*var的旧值，但从未向*var或调用者之后可见的任何其他地方写入新值，这意味着该函数是一个空操作（因此可能会被编译器根据as-if规则省略）。另一方面，我在寻找std::compare_exchange_weak的参考资料时找不到任何内容，所以我在想也许你是想说var->compare_exchange_weak？ - undefined

0

我认为上面大部分的答案都涉及到“虚假失败”作为某种问题，即性能与正确性之间的权衡。

它可以被看作是弱版本在大多数情况下更快，但在出现虚假失败的情况下会变慢。而强版本是一种没有虚假失败可能性的版本，但几乎总是更慢。

对我来说，主要区别在于这两个版本如何处理ABA问题：

弱版本只有在加载和存储之间没有人触碰缓存行时才会成功，因此它将100％检测到ABA问题。

强版本仅在比较失败时失败，因此如果没有额外措施，它将无法检测到ABA问题。

因此，理论上，如果您在弱排序架构上使用弱版本，则不需要ABA检测机制，实现将更简单，从而提供更好的性能。

但是，在x86（强排序架构）上，弱版本和强版本是相同的，它们都受到ABA问题的影响。

因此，如果您编写一个完全跨平台的算法，您仍然需要解决ABA问题，因此使用弱版本没有性能优势，但处理虚假失败会有性能惩罚。

总之，出于可移植性和性能的原因，强版本始终是更好或相等的选择。

仅当弱版本使您完全跳过ABA对策或者您的算法不关心ABA时，它才可能是更好的选择。

- Damir Shaikhutdinov

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- gexicide · Accepted Answer

为什么要在循环中执行交换操作？

通常情况下，您希望在继续之前完成工作，因此，您将compare_exchange_weak放入循环中，以便它尝试进行交换直到成功（即返回true）。

请注意，compare_exchange_strong也经常在循环中使用。它不会由于虚假失败而失败，但是由于并发写入而失败。

为什么要使用`weak`而不是`strong`？

很简单：虚假失败并不经常发生，因此它不会对性能造成太大的影响。相反，容忍这种失败可以在某些平台上比strong版本（与strong相比）实现更高效：strong必须始终检查虚假失败并屏蔽它。这很昂贵。

因此，在某些平台上，weak比strong快得多，因此使用weak。

何时应该使用`weak`和`strong`？

reference中提到了使用weak和strong的提示：

当比较和交换在循环中时，某些平台上弱版本将提供更好的性能。当弱比较和交换需要一个循环而强版本不需要时，强版本是首选。

因此，答案似乎很容易记住：如果只是因为虚假失败而不得不引入循环，则不要这样做；使用strong。如果您无论如何都有一个循环，则使用weak。

为什么示例中会出现`！expected`

这取决于情况和所需的语义，但通常不需要它来保证正确性。省略它会产生非常相似的语义。只有在另一个线程可能将值重置为false的情况下，语义才可能略有不同（但我找不到想要的有意义的示例）。有关详细说明，请参见Tony D.的评论。

当另一个线程写入true时，它只是一个快速跟踪：然后我们中止尝试再次写入true。

关于你的最后一个问题

但如上所述，在循环中的两个版本应该具有相同/类似的性能。我错过了什么吗？

来自Wikipedia：

实际的 LL/SC 实现并不总是成功，如果涉及到的内存位置没有并发更新。在两个操作之间发生任何异常事件，如上下文切换、另一个加载链接或甚至（在许多平台上）另一个加载或存储操作，都将导致条件存储失败。旧版实现将在存在内存总线广播更新时失败。

因此，例如在上下文切换时 LL/SC 会出现错误。现在，强版本将带来自己的“小循环”来检测这种错误并通过再次尝试掩盖它。请注意，这个自己的循环也比通常的 CAS 循环更复杂，因为它必须区分虚假的失败（并掩盖它）和由于并发访问而导致的失败（结果返回值为 false）。弱版本没有这样的自己的循环。

由于两个示例中都提供了一个明确的循环，因此在strong版本中不需要小循环。因此，在具有strong版本的示例中，失败检查会被执行两次；一次是由compare_exchange_strong执行的(这更加复杂，因为它必须区分虚假失败和并发访问)，另一次是通过您的循环执行的。这种昂贵的检查是不必要的，也是weak在这里更快的原因。

另外，请注意，您的参数(LL/SC)只是实现这一点的一种可能性。还有更多平台具有不同的指令集。此外（更重要的是），请注意，std::atomic必须支持所有可能的数据类型的所有操作，因此即使您声明一个千万字节的结构体，也可以在其上使用compare_exchange。即使在具有CAS的CPU上，您也不能对一千万字节进行CAS，因此编译器将生成其他指令（可能是锁获取，然后是非原子比较和交换，然后是锁释放）。现在，想象一下在交换一千万字节时会发生多少事情。因此，虽然对于8字节的交换来说虚假错误可能非常罕见，但在这种情况下它可能更为常见。

简而言之，C++提供了两种语义，一种是“尽力而为”的语义（weak），另一种是“无论中途发生多少糟糕的事情，我都会成功”的语义（strong）。如何在不同的数据类型和平台上实现这些语义是完全不同的话题。不要将你的思维模式与特定平台上的实现绑定在一起；标准库是设计用于处理比你所知道的更多的架构。我们唯一可以得出的普遍结论是，保证成功通常比仅尝试并留有失败可能的空间更加困难（因此可能需要额外的工作）。

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

为什么要在循环中执行交换操作？

为什么要使用weak而不是strong？

何时应该使用weak和strong？

为什么示例中会出现！expected

关于你的最后一个问题

为什么几乎所有使用compare_exchange_weak（）的情况都必须在循环中进行？

线程饥饿？

为什么我们要使用compare_exchange_weak()并自己编写循环呢？我们可以使用compare_exchange_strong()。

为什么要使用`weak`而不是`strong`？

何时应该使用`weak`和`strong`？

为什么示例中会出现`！expected`