[解決済み] C++11でstd::atomic::comparse_exchange_weak()を理解する。

質問

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

compare_exchange_weak() はC++11で提供される比較交換プリミティブの一つです。 これは 弱い と等しい場合でも false を返すという意味で、このオブジェクトは expected . これは 偽の失敗 を実装するために、(x86 のように 1 つの命令ではなく) 一連の命令が使われるプラットフォームがあります。そのようなプラットフォームでは、コンテキストスイッチ、他のスレッドによる同じアドレス（またはキャッシュライン）の再ロードなどが、プリミティブを失敗させる可能性があります。これは spurious と等しくない)ため、オブジェクトの値として expected に等しくない) ためです。その代わり、タイミングの問題があります。

しかし、不可解なのはC++11規格(ISO/IEC 14882)で言われていることです。

29.6.5 .. 偽の失敗の結果、weakのほぼすべての使用はループになります。 compare-and-exchangeのほぼすべての使用がループになることです。

でのループである必要があるのはなぜですか？ ほぼすべての用途で ? ということは、スプリアスフェイルで失敗したときはループさせるということでしょうか？もしそうなら、なぜ私たちはわざわざ compare_exchange_weak() を使い、自分たちでループを書く必要があるのでしょうか？単に compare_exchange_strong() を使うだけで、偽の失敗を取り除くことができると思います。一般的な使用例として compare_exchange_weak() ?

もう一つの質問関連です。彼の本 "C++ Concurrency In Action" の中で 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など）。では、次の 2 つのループに違いはあるのでしょうか。あるとすれば、それはなぜでしょうか？(私には、それらは同じようなパフォーマンスを持っているはずです)。

// 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) でも言及されています。

比較交換がループ内にある場合、プラットフォームによっては、弱いバージョンの方がパフォーマンスが向上します。 より良いパフォーマンスを得ることができます。

しかし、上記で分析したように、ループ内の 2 つのバージョンは同じまたは類似のパフォーマンスをもたらすはずです。私が見逃しているものは何でしょうか？

どのように解決するのですか？

私は自分でこれに答えようとしているのですが、いろいろなオンライン資料（例えば。 これ と これ )、C++11 標準、およびここに記載されている回答が参考になります。

関連する質問はマージされます (例: " なぜ !expected ? と統合されました。 なぜ compare_exchange_weak() をループさせるのですか？ "）と、それに応じて回答があります。

compare_exchange_weak() はなぜほとんどすべての用途でループ内になければならないのですか?

典型的なパターンA

アトム変数の値に基づいてアトム更新を実現する必要がある。失敗は、変数が希望の値で更新されず、再試行したいことを示します。注意点として は、同時書き込みによる失敗か、偽の失敗かはあまり気にしていません。しかし、私たちは それは私たち この変化を起こすのは、私たちです。

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

実際の例としては、複数のスレッドが同時に単一リンクリストに要素を追加することが挙げられます。各スレッドは最初にheadポインタをロードし、新しいノードを割り当てて、headをこの新しいノードに追加します。最後に、新しいノードとヘッドをスワップしようとします。

他の例として、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() をループの外で使うことはほとんどないはずです。それどころか、strong版が使われているケースもある。例えば

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

compare_exchange_weak がここで適切でないのは、偽の失敗で戻ったとき、まだ誰もクリティカルセクションを占有していない可能性が高いからです。

スレッドの飢餓？

言及に値する 1 つのポイントは、偽の失敗が起こり続けてスレッドが枯渇した場合にどうなるかです。理論的には、次のようなプラットフォームで発生する可能性があります。 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 を返さないようにする必要があります。 演算が一貫して false を返さないようにする必要があります。 オブジェクトが期待される値とは異なる値を持つか、アトミックオブジェクトに同時に がない限り、一貫して false を返さないようにしなければなりません。

なぜわざわざ compare_exchange_weak() を使って、自分たちでループを書くのでしょうか？compare_exchange_strong()を使えばいいんです。

それは場合による

ケース1：ループの中で両方を使う必要がある場合。 C++11ではこうなっています。

compare-and-exchange がループ内にある場合、weak 版はいくつかのプラットフォームでより良いパフォーマンスをもたらします。 より良いパフォーマンスを得ることができます。

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() . もっと悪い？ この方法は、ハードウェアで非スプリアスな比較と交換を提供するマシンを十分に活用することができません。 .

最後に、他のもののためにループする場合 (たとえば、上記の "Typical Pattern A" を参照)、次のような可能性が高いです。 compare_exchange_strong() もループに入れなければならないので、前のケースに戻ることになります。