問題タブ [compare-and-swap]

HTTP標準に従いながら、特定のリソースを変更する唯一の方法として、コンペアアンドスワップスタイルのメカニズムを作成する方法はありますか？

正しい動作を実装するIf-Matchヘッダーがありますが、このヘッダーはオプションです。私が知る限り、If-Match提供されていない場合、サーバーはを尊重する必要がありますPUT。（つまり、コンペア・アンド・スワップを行うか、単にスワップするかを決定するのはクライアントの責任です。）クライアントがヘッダーを提供412 Precondition FailedしようとしているかどうPUTかにかかわらず、応答することは許容されますか？POSTIf-Match

「N」個のスレッドが AtomicInteger 変数を CAS しようとしているとします。CAS が正確に 1 つのスレッドで成功しなければならないことが保証されていますか?

「N」個のスレッドすべてが試みに失敗する可能性はありますか?

マルチスレッドコードで問題を引き起こすABA問題の実例を探しています。

ABA問題は、アトミックなコンペアアンドスワップ命令を実行するときに並行コードで発生します。コンペアアンドスワップを実行する直前にスレッドが中断された場合、2番目のスレッドは、コンペアアンドスワップのターゲットを初期値Aから別の値Bに変更する可能性があります。その後、値をAに戻します。最初のスレッドが再開する前に、ターゲット値が変更されても、コンペアアンドスワップは成功します。

多くの場合、ABAは問題ではありません。共有参照カウントを例にとると、refcountが同時に変更されても、すでに0に低下したrefcountから増加しない限り、問題はありません。したがって、ターゲットがターゲットと一致するかどうかにのみ関心があることは明らかです。スワップ時の期待値であり、過去に変更されたかどうかではありません。

ウィキペディアのページには、ABAに悩まされているロックフリースタック実装の例がありますが、私は個人的にこれまでのところ本番コードで問題に遭遇していません。誰かがABAについて共有するいくつかの素晴らしい戦争の話を持っているかどうか私はちょうど興味がありました。

私は C でプログラムを書いています。簡単に言うと、多くのスレッドが読み書きできる変数がいくつかあります。これらのいずれかが書き込まれるたびに、アトミック スワップ (GCC アトミック操作、同期およびスワップ) を介して書き込まれます。これらの変数のいずれかを読み取るたびにアトミック ロードを使用する必要がありますか?それとも、アトミック ライトは書き込み中のデータの読み取りを回避するのに十分ですか?

これらの変数のいずれかからのデータを使用する必要がある場所では、最初に値をコピーすることに注意してください。

私の質問はデータ競合に関するものではありません。つまり、データが失われる可能性はありません。私の懸念は、shared_x の値が読み取りの途中で変わる可能性があることです。これが 8 バイト整数であるとします。これは潜在的な問題になるでしょうか。shared_x が 64 ビット整数、8 バイトであるとします。my x = shared_x が最初の 4 バイトをコピーし、次に何かがアトミックに shared_x に書き込み、このステートメントが 2 番目の 4 バイトの読み取りを終了する可能性はありますか。これにより、x には、shared_x の古い値の最初の 4 バイトと、新しい shared_x の最後の 4 バイトが含まれます。アトミック スワップ ( http://gcc.gnu.org/onlinedocs/gcc-4.1.1/gcc/Atomic-Builtins.html - __sync_bool_compare_and_swap を使用) のメモリ バリアは、これを防ぐのに十分だと思います... しかし、私はわかりません。

新しいタイプの compare&swap(a,b) (CAS) オブジェクト (新しいタイプを CAS2 と呼びましょう) を実装 (疑似コード) する必要があります。

CAS および CAS2 オブジェクトはどちらも、オブジェクト値を返す読み取り操作をサポートしています。

どちらもcompare&swap(a,b)操作をサポートしていますが、CASではこの操作はtrue/falseを返し、aと等しい場合はオブジェクト値をbに変更しますが、CAS2ではこの操作は同じ効果がありますが、trueを返す代わりに/false、操作の前に常にオブジェクト値を返す必要があります。

例えば：

CAS オブジェクトの値が 4 の場合、compare&swap (4,5) は true を返し、値を 5 に変更しますが、CAS2 オブジェクトでは、compare&swap (4,5) は 4 を返し、値を 5 に変更します。CAS オブジェクトの値が 4 の場合、compare&swap (5,6) は false を返し、何もしませんが、CAS2 では、compare&swap (5,6) は 4 を返し、何もしません。CAS2 オブジェクトは、1 つの CAS オブジェクトのみを使用して実装する必要があり、実装はウェイトフリーで線形化可能でなければなりません。

前もって感謝します！

私は最近、同時実行同期メカニズムとして使用されるトリプル バッファーの std::atomic を使用して、C++11 へのポートを作成しました。このスレッド同期アプローチの背後にある考え方は、プロデューサーとコンシューマーの状況で、より高速に実行されているプロデューサーを使用することです。コンシューマを待たなければならないことでプロデューサ スレッドが「遅くなる」ことがないため、トリプル バッファリングにはいくつかの利点があります。私の場合、~120fps で更新される物理スレッドと、~60fps で実行されるレンダリング スレッドがあります。明らかに、レンダー スレッドが常に可能な限り最新の状態を取得することを望んでいますが、レートの違いにより、物理スレッドから多くのフレームをスキップすることもわかっています。一方で、物理スレッドが一定の更新レートを維持し、データをロックする遅いレンダリング スレッドによって制限されないようにしたいと考えています。

元の C コードは remis-thinking によって作成され、完全な説明は彼のブログにあります。元の実装をさらに理解するために、この文書を読むことに興味のある人をお勧めします。

私の実装はここにあります。

基本的な考え方は、3 つの位置 (バッファ) を持つ配列と、いつでもどの配列要素がどの状​​態に対応するかを定義するために比較および交換されるアトミック フラグを持つことです。このように、1 つのアトミック変数のみを使用して、配列の 3 つのインデックスすべてとトリプル バッファリングの背後にあるロジックをモデル化します。バッファの 3 つの位置は、Dirty、Clean、および Snap と名付けられています。プロデューサは常に Dirty インデックスに書き込み、ライターを反転して Dirty を現在の Clean インデックスと交換できます。コンシューマは、最新のバッファを取得するために現在のスナップ インデックスをクリーン インデックスと交換する新しいスナップを要求できます。コンシューマーは、常にスナップ位置でバッファーを読み取ります。

フラグは 8 ビットの unsigned int で構成され、ビットは以下に対応します。

(未使用) (新規書き込み) (2x ダーティ) (2x クリーン) (2x スナップ)

newWrite エクストラ ビット フラグは、ライターによって設定され、リーダーによってクリアされます。リーダーはこれを使用して、最後のスナップ以降に書き込みがあったかどうかを確認できます。書き込みがない場合は、別のスナップは実行されません。フラグとインデックスは、単純なビット演算を使用して取得できます。

コードは次のとおりです。

実装：

ご覧のとおり、メモリの順序付けにRelease-Consumeパターンを使用することにしました。ストアのリリース(memory_order_release) は、現在のスレッドの書き込みがストア後に並べ替えられないことを保証します。一方、消費は、現在ロードされている値に依存する現在のスレッドの読み取りが、このロードの前に並べ替えられないことを保証します。これにより、同じアトミック変数を解放する他のスレッドの従属変数への書き込みが、現在のスレッドで確実に表示されます。

私の理解が正しければ、フラグをアトミックに設定するだけでよいため、フラグに直接影響を与えない他の変数に対する操作は、コンパイラーによって自由に並べ替えられ、より多くの最適化が可能になります。新しいメモリ モデルに関するいくつかのドキュメントを読んで、これらの緩和されたアトミックが ARM や POWER などのプラットフォームにのみ顕著な影響を与えることも認識しています (それらは主にそれらのために導入されました)。私は ARM をターゲットにしているので、これらの操作の恩恵を受けて、パフォーマンスをもう少し引き出すことができると信じています。

質問は次のとおりです。

この特定の問題に対して Release-Consume の緩和された順序付けを正しく使用していますか?

ありがとう、

アンドレ

PS: 長い投稿で申し訳ありませんが、問題をよりよく理解するには、適切なコンテキストが必要であると考えていました。

編集: @Yakk の提案を実装:

• flagsread onnewSnap()とflipWriter()直接代入を使用していたため、 default を使用していたのを修正しましたload(std::memory_order_seq_cst)。
• わかりやすくするために、ビット操作を専用関数に移動しました。
• boolに戻り値の型が追加されましnewSnap()た。新しいものがない場合は false を返し、それ以外の場合は true を返します。
• = deleteが使用されている場合、コピー コンストラクターと代入コンストラクターの両方が安全ではないため、イディオムを使用してクラスをコピー不可として定義しTripleBufferました。

EDIT 2： 間違っていた説明を修正しました（@Uselessに感謝します）。新しいスナップを要求し、スナップ インデックスから読み取るのはコンシューマーです (「ライター」ではありません)。気を散らして申し訳ありません。それを指摘してくれた Useless に感謝します。

EDIT 3: @Display Name の提案に従ってnewSnap()and関数を 最適化し、ループ サイクルごとに 2 つの冗長な を効果的に削除しました。flipriter()load()

ArrayList の特定の位置で値を変更するのに問題があります。より明確にするために、ここに状況があります：

1 つのリストに productID を追加し、別のリストにその数を追加したいと考えています。しかし、ユーザーがすでにproductListにある製品を選択した場合、countListのカウントを新しい選択カウンターで更新したいと考えています。

コードは次のとおりです。

問題は、for ループに入らず、チェックを行わないことです。アイテムをリストに入れるだけです。助けてください。よろしくお願いします!!!

クライアント側コードの一部のパフォーマンスを測定するために、マルチスレッド コードでincrementAndGetメソッドを使用しています。AtomicLong

上記のコードでは、時間を測定しようとしています-

client.getAttributes(columnsList);

とっている。

私の知る限り、incrementAndGetメソッドは現在の値をアトミックに 1 ずつ増やします。これは、各スレッドが他のスレッドが値をインクリメントするのを待つ可能性があることを意味します。私は正しいですか？ブロックされるということでしょうか？

また、これはメソッドのパフォーマンスを測定する方法にも影響しますか? その測定にも余分な時間が追加されるということですか？

私がこれを尋ねている理由は、クライアント側コードとサーバー側コードのほとんどをベンチマークしようとしているからです。各メソッドにかかる時間を測定する必要がある場合は、次のように単純に実行しています-

測定したいコードが何であれ、通常はそのメソッドのすぐ上に以下の行を置きます

long start = System.nanoTime();

そして、これらの2行は同じ方法の後にありますが、ConcurrentHashMap

メソッドを使用しincrementAndGetていて、パフォーマンス測定に余分な時間を追加している場合、正確な結果が得られない可能性がありますか?

アップデート：-

これは以下の方法で、 で行ったときに取得しF3ましincrementAndGetたeclipse。

ここに同期ブロックがあります。つまり、各スレッドはここで他のスレッドを待機します。そして、それはブロッキングコールです。

ああ。JVM を確認したところ、IBM JVMと比較して実行されていSUN JVMます。私はこの特定のことを変えることができない会社で働いているので.

このロックベースのソリューションを回避して、メソッドのパフォーマンス/ベンチマークを測定する方法はありますか? 私は IBM JVM を実行していることに留意してください。

助けてくれてありがとう。

C++11 CAS 操作の多く (例: , atomic_compare_exchange_weak)atomic_compare_exchange_strongは、次のように 2 つのポインターと 1 つの値を取ります。

対照的に、Microsoft、gcc、Intel の CAS 操作はすべて、1 つのポインターと 2 つの値を取ります。

C++11 の CAS 関数は、従来の 1 つのポインターと 2 つの値のように見えるものではなく、2 つのポインターと 1 つの値を取るのはなぜですか?

ミューテックスよりもアトミックを使用する主な理由は、ミューテックスが高価であるということですが、デフォルトのメモリモデルが でatomicsあるためmemory_order_seq_cst、これは同じくらい高価ではありませんか?

質問: ロックを使用する並行プログラムは、ロックのない並行プログラムと同じくらい高速にできますか?

memory_order_acq_relもしそうなら、アトミックに使いたくない限り、努力する価値はないかもしれません。

編集：私は何かが欠けているかもしれませんが、各ロックも完全なメモリバリアでなければならないため、ロックベースはロックフリーよりも高速ではありません。しかし、ロックフリーを使用すると、メモリ バリアよりも制限の少ない手法を使用できます。

私の質問に戻りますが、ロックフリーは新しい C++11 標準に基づくロックよりも高速memory_modelですか?

「パフォーマンスで測定するとロックフリー>=ロックベース」は本当ですか? 2 つのハードウェア スレッドがあるとします。

編集 2: 私の質問は、進行の保証に関するものではありません。おそらく、コンテキスト外で「ロックフリー」を使用している可能性があります。

基本的に、共有メモリを持つ2つのスレッドがあり、必要な唯一の保証は、一方のスレッドが書き込みを行っている場合、もう一方のスレッドが読み書きできないということです。私の仮定は、単純なアトミックcompare_and_swap操作の方がミューテックスをロックするよりもはるかに高速であるということです.

1 つのスレッドが共有メモリにまったく触れない場合、理由もなく何度もロックとロック解除を繰り返すことになりますが、アトミック操作では毎回 1 CPU サイクルしか使用しません。

コメントに関しては、競合がほとんどない場合、スピンロックとミューテックスロックは大きく異なります。