問題タブ [compare-and-swap]

while と do-while

while と do-while は、ブロックが空の場合は機能的に同等ですが、 while の方が自然に見えます:

空のブロックを使用した while/do-while の典型的な使用例の 1 つは、compareAndSet (CAS) を使用してアトミック オブジェクトを強制的に更新することです。たとえば、次のコードaはスレッドセーフな方法でインクリメントします。

環境

java.util.concurrent のいくつかの部分ではdo {} while (...)、CAS 操作にイディオムを使用しており、javadoc で次のようにForkJoinPool説明されています。

do {} while (!cas...)CAS された変数の更新を強制する最も簡単な方法である異常な現象がいくつか発生します。

彼らはそれが異常であることを認めているので、彼らは最も単純というよりも最良を意味していたと思います。

質問

do {} while (!cas)よりも効率的な状況はありwhile (!cas) {}ますか?その理由は何ですか?

ノンブロッキング CAS に関する記事を読んでいて、次のコードに出くわしました。

同期を使用する場合、この CAS 操作はどのようにノンブロッキングですか?

このクライアントがSimulatedCAS独自の同期を実装する必要がないことを意味する場合、ブロッキングを排除する代わりに移動しただけではありませんか?

Compare And Swapプログラミングの長所と短所をまとめてくれる人はいますか? (例: マルチコア CPU のパフォーマンス)

Java での例を次に示します。

===編集===

これについては、特にシングル/コア CPU で話してください。

インテル アーキテクチャで CMPXCHG の前にロック プレフィックスが必要なのはなぜですか。参照用に参照して ください http://courses.engr.illinois.edu/ece390/archive/spr2002/books/labmanual/inst-ref-cmpxchg.html

ロックを使用しないとどうなるかわかりません。値を eax にロードしてから LOCK CMPXCHG を実行するまでの間、eax への値のロードと LOCK CMPXCHG は 2 つの命令であるため、ロック プレフィックスに関係なく値が変更される可能性があるためです。

CMPXCHG を使用しないと、最悪の事態が発生する可能性があります。

InterlockedCompareExchangeWindows では、gcc と同様__sync_val_compare_and_swapにポインターを使用するため、共有メモリ ブロックを指すなど、任意のアドレスをそれらの関数に渡すことができます。

x86 以外のアーキテクチャでは、正確性のためにメモリ アライメントを確保する必要がある場合があり、x86 (およびその他のアーキテクチャ) では、パフォーマンスのためにキャッシュ ラインのアライメントを確保したい場合がありますが、正確性は問題にはなりません (-> x86LOCKプレフィックス) 。 .

コード内のプラットフォームに依存するもの (Windows VC++ と GCC) を取り除こうとして、C++11atomic_compare_exchange_weakとその仲間を調べました。しかし、それらはすべて type の変数で機能しますstd::atomic<T>*。

C++11 のアトミック関数で任意のポインターを使用する方法はありますか? std::atomic への単純なキャストがこれを解決するようには見えません。

以下は、Intel CPU で GNU 組み込みの比較およびスワップを使用して実装された並行スタックで発生している問題を示す簡略化された C プログラムです。何が起こっているのかを理解するのにしばらく時間がかかりましたが、今では、アトミックな比較とスワップによって提供される保証の範囲内であることがわかります.

ノードがスタックからポップされ、変更されてからスタックに戻されると、変更された値がスタックの新しい先頭になり、破損する可能性があります。test_get のコメントは、これを引き起こすイベントの順序を説明しています。

同じノードを同じスタックで確実に複数回使用する方法はありますか? これは誇張された例ですが、変更されていないノードを gHead に返すだけでも、他のノードがリークする可能性があります。このデータ構造の元のポイントは、同じノードを繰り返し使用することでした。

8 つの論理コアでこのテストを実行しています。4 つのスレッドのみを使用する場合、問題はめったに発生しませんが、8 の場合は簡単に再現できます。Intel Core i7 を搭載した MacBook を使用しています。

これを解決したライブラリやフレームワークを使用することに興味はありません。どのように解決されたか知りたいです。ありがとうございました。

編集：

私の場合、うまくいかない2つの解決策があります。

一部のアーキテクチャは、値ではなくアドレスに対してアトミック テストを実行する ll/sc 命令ペアを提供します。同じ値であっても、アドレスへの書き込みは成功を妨げます。

一部のアーキテクチャでは、ポインター サイズより大きい比較とスワップが提供されます。これにより、モノトニックカウンターは、使用されるたびにアトミックにインクリメントされるポインターとペアになり、値が常に変化します。一部の Intel チップはこれをサポートしていますが、GNU ラッパーはありません。

これが問題のプレイバイプレイです。2 つのスレッド A と B はtest_get、 で同じ値をresult持ち、 ではない点に到達しNULLます。次に、次のシーケンスが発生します。

1. スレッド A は比較とスワップを渡し、resultから戻ります。test_get
2. スレッド A は、result
3. スレッド B が逆参照resultし、スレッド A がそこに置いたものを取得します
4. スレッド A は終了しresult、呼び出しますtest_put
5. test_putスレッド A は結果を元に戻す際に比較とスワップを渡しますgHead
6. スレッド B は比較に到達し、スワップインtest_getしてパスします
7. gHeadスレッド B は、スレッド A からの値で破損しています

これは、スレッド A を変更する必要のない 3 つのスレッドを使用した同様のシナリオですresult。

1. スレッド A は比較とスワップを渡し、resultから戻ります。test_get
2. スレッド A はコンテンツを変更しません。result
3. スレッド B が逆参照resultし、有効な値を取得しますscratch
4. 無関係な値でスレッド C を呼び出しtest_put、成功する
5. スレッド A が呼び出し、元に戻すtest_putことに成功するresultgHead
6. スレッド B は比較に到達し、スワップインtest_getしてパスします
7. gHeadスレッド B は、スレッド C が追加したものを漏らして破損しました

どちらのシナリオでも、問題は、スレッド B が get の比較とスワップに到達する前に、スレッド A が比較とスワップを 2 回 (get で 1 回、次に put で) 渡すことです。スレッド B が持つスクラッチの値は破棄する必要がありますが、gHead の値が正しいように見えるため、破棄する必要はありません。

実際に防止せずにこの可能性を低くする解決策は、バグの追跡を困難にするだけです。

スクラッチ変数は、アトミック命令が開始する前に結果の参照解除された値が配置される場所の単なる名前であることに注意してください。名前を削除すると、中断される可能性のある逆参照と比較の間のタイム スライスが削除されます。

アトミックとは、全体として成功または失敗することを意味することにも注意してください。問題のハードウェアでは、ポインターのアライメントされた読み取りは暗黙的にアトミックです。他のスレッドに関する限り、ポインターの半分だけが読み取られた割り込み可能ポイントはありません。

.NET フレームワークでは、アトミック操作CompareAndExchangeintは、 、long、doubleおよび参照型に対してのみ定義されています。しかし、型には CompareAndExchange が必要ですbool。に実装するにはどうすればよいCompareAndSwapですboolか?

C++11 には、 と の 2 つのアトミック CAS 操作がありatomic_compare_exchange_weakますatomic_compare_exchange_strong。

cppreferenceによると:

関数の弱い形式は偽って失敗することが許可されています。比較交換がループしている場合、一部のプラットフォームでは弱いバージョンの方がパフォーマンスが向上します。弱い比較交換にはループが必要で、強いものには必要ない場合は、強いものをお勧めします。

以下は、弱いバージョンを使用するための例です。

強力なバージョンが望ましいように、比較と交換がループに入っていない例を誰かが挙げてもらえますか?

あるとしましょう:

私が必要としているbyteのは、4 番目と 5 番目の 2 つの隣接するビットに対してアトミック CAS (比較と交換) 操作を実行することです。

確かに、バイトより短いものをアドレス指定する方法はありませんが、バイト用の CAS 関数があるため、次のようになります。

はアトミックに と比較byteしexpected、それらが EQUAL の場合はに割り当てdesiredてbyte返します。truebyteexpectedbyteexpectedfalse

したがって、比較が EQUALITY をチェックするだけでなく、bitwise-and または bitwise-or などのビットごとの演算を実行することによって比較が行われるバイトの CAS 演算である場合、ビットに対して CAS を実行することが可能になります。

したがって、問題は、比較時に同等性を探すのではなく、bitwise-and または bitwise-or?