理解std :: atomic :: compare_exchange_weak（）在C ++ 11 [英] Understanding std::atomic::compare_exchange_weak() in C++11
问题描述
bool compare_exchange_weak（T& expected，T val，..）;
compare_exchange_weak（）交换原语在C ++ 11提供。 ，即使对象的值等于 expected ，它也会返回false。这是由于某些平台上的 错误而导致的，其中使用一系列指令（而不是x86上的指令）来实现它。在这样的平台上，上下文切换，由另一线程重新加载相同地址（或高速缓存行）等可能会失败该原语。这是 spurious ，因为它不是该操作失败的对象的值（不等于 expected ）。
但是令我困惑的是C ++ 11标准（ISO / IEC 14882），
29.6.5
..
假故障的结果是几乎所有使用弱
的比较和交换
为什么它必须在 > ？这是否意味着，当它失败，由于虚假失败，我们将循环？如果是这样，为什么我们打扰 compare_exchange_weak（）并自己写循环？我们可以使用 compare_exchange_strong（），我认为应该摆脱我们的虚假失败。 compare_exchange_weak（）？
的另一个问题是什么？在他的书C ++并发在行动Anthony说，
//因为compare_exchange_weak b $ b //在循环中使用：
bool expected = false;
extern atomic< bool> b; // set somehere else
while（！b.compare_exchange_weak（expected，true）&&！expected）;
//在这种情况下，只要预期仍为false，就保持循环，
//表示compare_exchange_weak（）调用失败。
为什么在循环中有！expected 条件？
(最后一个问题）
>在没有单一硬件CAS指令的平台上，弱和强版本都是使用LL / SC（如ARM，PowerPC等）实现的。那么下面两个循环之间有什么区别吗？为什么，如果有？ （对我来说，他们应该有类似的性能。）
//使用LL / SC（或x86上的CAS）循环对假故障
while（！compare_exchange_weak（..））
{..}
//使用LL / SC（或x86上的CAS）伪失败
while（！compare_exchange_strong（..））
{..}
我出来w /这最后一个问题你们都提到在循环内可能有性能差异。它也由C ++ 11标准（ISO / IEC 14882）提到：
当比较交换处于循环，弱版本将在某些平台上产生
的更好的性能。
但是如上所述，给出相同/相似的性能。
我想通过各种在线资源a href =http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2008/n2748.html>这一个和这一个），C ++ 11标准，以及这里给出的答案。
相关问题已合并（例如， 为什么！预期 与
为什么要在比较结果中加入compare_exchange_weak >
典型模式A
您需要根据原子变量中的值实现原子更新。失败表示变量未更新为所需的值，我们希望重试该变量。请注意，我们并不真正关心它是否由于并发写入或虚假故障而失败。但我们非常关心 是这样做的。
expected = current.load（）;
do desired = function（expected）;
while（！current.compare_exchange_weak（expected，desired））;
一个现实世界的例子是几个线程同时添加一个元素到单个链表。每个线程首先加载头指针，分配一个新节点并将头附加到这个新节点。
另一个例子是使用 std :: atomic< bool> code>。根据哪个线程首先将当前设置为 true 并退出，线程最多可以一次进入临界段
这实际上是上面提到的模式。 安东尼的书。与模式A相反，您希望原子变量更新一次，但您不关心是谁。只要没有更新，您就可以重试。这通常与布尔变量一起使用。例如，您需要实现一个触发器，让状态机继续前进。
expected = false;
//！expected：如果期望被另一个线程设置为true，它就完成了！
//否则，它会失败，我们应该再试一次。
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
饥饿的线程？
$ b这是一个很好的例子，因为当它由于虚假的失败返回时，很可能没有人占据关键部分。 $ b
值得一提的是，如果虚假故障继续发生，那么会发生什么，从而使线程挨饿？理论上，当 compare_exchange_XXX（）被实现为指令序列（例如，LL / SC）时，它可能发生在平台上。在LL和SC之间频繁访问相同的高速缓存线将产生连续的假故障。一个更现实的例子是由于一个哑调度，所有并发线程以下列方式交错。
时间
|线程1（LL）
|线程2（LL）
|线程1（比较，SC），由于线程2的LL
|而错误地失败线程1（LL）
|线程2（比较，SC），由于线程1的LL
|而错误地失败线程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（） over compare_exchange_weak c>即使在循环中。例如，当在原子变量被加载并且计算的新值被交换出来之前有很多事情要做（参见 function（）上面）。如果原子变量本身不经常改变，我们不需要对每个假失败重复昂贵的计算。相反，我们可能希望 compare_exchange_strong（）吸收这样的失败，我们只在失败时重复计算，因为实际的价值变化。
情况2：只有 compare_exchange_weak（） 需要在循环内使用 C ++ 11还说：
当一个弱比较和交换需要一个循环而一个强的
这是典型的情况，当你循环只是为了消除虚假失败从弱版本。您重试，直到交换成功或失败，因为并发写入。
expected = false;
//！expected：如果它失败了，我们应该再试一次。
while（！current.compare_exchange_weak（expected，true）&&！expected）;
最好的方法是重新发明轮子并执行 compare_exchange_strong 更差？ 此方法无法充分利用提供非虚假比较 - 硬件交换。
最后，如果你循环其他的东西（例如，见上面的典型模式A），那么很有可能 compare_exchange_strong ）也应该放在一个循环中，这使我们回到前一种情况。
bool compare_exchange_weak (T& expected, T val, ..);
compare_exchange_weak() is one of compare-exchange primitives provided in C++11. It's weak in the sense that it returns false even if the value of the object is equal to expected. This is due to spurious failure on some platforms where a sequence of instructions (instead of one as on x86) are used to implement it. On such platforms, context switch, reloading of the same address (or cache line) by another thread, etc can fail the primitive. It's spurious as it's not the value of the object (not equal to expected) that fails the operation. Instead, it's kind of timing issues.
But what puzzles me is what's said in C++11 Standard (ISO/IEC 14882),
29.6.5 .. A consequence of spurious failure is that nearly all uses of weak compare-and-exchange will be in a loop.
Why does it have to be in a loop in nearly all uses ? Does that mean we shall loop when it fails because of spurious failures? If that's the case, why do we bother use compare_exchange_weak() and write the loop ourselves? We can just use compare_exchange_strong() which I think should get rid of spurious failures for us. What are the common use cases of compare_exchange_weak()?
Another question related. In his book "C++ Concurrency In Action" Anthony says,
//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.
Why is !expected there in the loop condition? Does it there to prevent that all threads may starve and make no progress for some time?
Edit: (one last question)
On platforms that no single hardware CAS instruction exist, both the weak and strong version are implemented using LL/SC (like ARM, PowerPC, etc). So is there any difference between the following two loops? Why, if any? (To me, they should have similar performance.)
// 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(..))
{ .. }
I come up w/ this last question you guys all mention that there maybe a performance difference inside a loop. It's also mentioned by the C++11 Standard (ISO/IEC 14882):
When a compare-and-exchange is in a loop, the weak version will yield better performance on some platforms.
But as analyzed above, two versions in a loop should give the same/similar performance. What's the thing I miss?
I'm trying to answer this myself, after going through various online resources (e.g., this one and this one), the C++11 Standard, as well as the answers given here.
The related questions are merged (e.g., "why !expected ?" is merged with "why put compare_exchange_weak() in a loop ?") and answers are given accordingly.
Why does compare_exchange_weak() have to be in a loop in nearly all uses?
Typical Pattern A
You need achieve an atomic update based on the value in the atomic variable. A failure indicates that the variable is not updated with our desired value and we want to retry it. Note that we don't really care about whether it fails due to concurrent write or spurious failure. But we do care that it is us that make this change.
expected = current.load();
do desired = function(expected);
while (!current.compare_exchange_weak(expected, desired));
A real-world example is for several threads to add an element to a singly linked list concurrently. Each thread first loads the head pointer, allocates a new node and appends the head to this new node. Finally, it tries to swap the new node with the head.
Another example is to implement mutex using std::atomic<bool>. At most one thread can enter the critical section at a time, depending on which thread first set current to true and exit the loop.
Typical Pattern B
This is actually the pattern mentioned in Anthony's book. In contrary to pattern A, you want the atomic variable to be updated once, but you don't care who does it. As long as it's not updated, you try it again. This is typically used with boolean variables. E.g., you need implement a trigger for a state machine to move on. Which thread pulls the trigger is regardless.
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);
Note that we generally cannot use this pattern to implement a mutex. Otherwise, multiple threads may be inside the critical section at the same time.
That said, it should be rare to use compare_exchange_weak() outside a loop. On the contrary, there are cases that the strong version is in use. E.g.,
bool criticalSection_tryEnter(lock)
{
bool flag = false;
return lock.compare_exchange_strong(flag, true);
}
compare_exchange_weak is not proper here because when it returns due to spurious failure, it's likely that no one occupies the critical section yet.
Starving Thread?
One point worth mentioning is that what happens if spurious failures continue to happen thus starving the thread? Theoretically it could happen on platforms when compare_exchange_XXX() is implement as a sequence of instructions (e.g., LL/SC). Frequent access of the same cache line between LL and SC will produce continuous spurious failures. A more realistic example is due to a dumb scheduling where all concurrent threads are interleaved in the following way.
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 ..
Can it happen?
It won't happen forever, fortunately, thanks to what C++11 requires:
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.
Why do we bother use compare_exchange_weak() and write the loop ourselves? We can just use compare_exchange_strong().
It depends.
Case 1: When both need to be used inside a loop. C++11 says:
When a compare-and-exchange is in a loop, the weak version will yield better performance on some platforms.
On x86 (at least currently. Maybe it'll resort to a similiar scheme as LL/SC one day for performance when more cores are introduced), the weak and strong version are essentially the same because they both boil down to the single instruction cmpxchg. On some other platforms where compare_exchange_XXX() isn't implemented atomically (here meaning no single hardware primitive exists), the weak version inside the loop may win the battle because the strong one will have to handle the spurious failures and retry accordingly.
But,
rarely, we may prefer compare_exchange_strong() over compare_exchange_weak() even in a loop. E.g., when there is a lot of things to do between atomic variable is loaded and a calculated new value is exchanged out (see function() above). If the atomic variable itself doesn't change frequently, we don't need repeat the costly calculation for every spurious failure. Instead, we may hope that compare_exchange_strong() "absorb" such failures and we only repeat calculation when it fails due to a real value change.
Case 2: When only compare_exchange_weak() need to be used inside a loop. C++11 also says:
When a weak compare-and-exchange would require a loop and a strong one would not, the strong one is preferable.
This is typically the case when you loop just to eliminate spurious failures from the weak version. You retry until exchange is either successful or failed because of concurrent write.
expected = false;
// !expected: if it fails spuriously, we should try again.
while (!current.compare_exchange_weak(expected, true) && !expected);
At best, it's reinventing the wheels and perform the same as compare_exchange_strong(). Worse? This approach fails to take full advantage of machines that provide non-spurious compare-and-exchange in hardware.
Last, if you loop for other things (e.g., see "Typical Pattern A" above), then there is a good chance that compare_exchange_strong() shall also be put in a loop, which brings us back to the previous case.
这篇关于理解std :: atomic :: compare_exchange_weak（）在C ++ 11的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
