問題タブ [compare-and-swap]

std::atomic_compare_exchangeおよびそのすべての兄弟姉妹が、渡された期待値を更新するのはなぜですか?

ループで与えられた単純さ以外に理由があるかどうか疑問に思っています。たとえば、パフォーマンスを向上させるために1回の操作でそれを実行できる組み込み関数はありますか?

アトミック操作を行うためにアドレスから 2 つの MSB を盗むにはどうすればよいですか? 私は単一の単語CASをやろうとしています

例

AtomicReference追加のフラグが 1 つだけ必要な場合に使用できます。 AtomicStampedReferenceを使用できますが、timeStamp と参照を含む余分なボックスが作成されるため、効率的ではありません。

C での同様の問題は 、ポインターからビットを盗むで説明されています。

Martin Thompsonは、CAS に依存する参照に依存する STM は、最終的にアムダールの法則によって制限されると主張しています。アムダールの法則は、並列プログラムの最大パフォーマンスは、プログラムの順次 (非並列) 部分によって制限されるというものです。Martin Thompson は、CAS は本質的に非並列であると言っていますか?

マルチスレッドとミューテックスは初めてなので、初心者向けにウィキペディアを調べていました。私はこの部分に出くわしました：

CAS を使用すると、実行する必要のある操作を各ノードが表すリンク リストを作成することで、共有データ構造の待機なしの相互排除を実現できます。次に、CAS を使用して、新しいノードの挿入中にリンク リスト内のポインターを変更します。その CAS で成功できるプロセスは 1 つだけです。同時にノードを追加しようとする他のすべてのプロセスは、再試行する必要があります。その後、各プロセスはデータ構造のローカル コピーを保持し、リンクされたリストをトラバースすると、そのローカル コピーでリストから各操作を実行できます。

これで、基本的に値を所定の値と比較し、一致する場合はそれらを交換するアトミック操作を使用する CAS の基本概念を理解しました。しかし、ここで「目的の操作のリンクされたリスト」が何を意味するのかを理解できませんでしたか? また、すべてのプロセスが同じ操作のリンク リストに従うのはなぜでしょうか。

次の 2 つの引用は矛盾しているように見えます。

https://www.kernel.org/doc/Documentation/atomic_ops.txt

int atomic_cmpxchg(atomic_t *v, int old, int new);

これは、指定された古い値と新しい値を使用して、原子値 v に対して原子比較交換操作を実行します。すべての atomic_xxx 操作と同様に、atomic_cmpxchg は、*v の他のすべてのアクセスが atomic_xxx 操作によって実行される限り、その原子性セマンティクスのみを満たします。

atomic_cmpxchg では、操作の周りに明示的なメモリ バリアが必要です。

対

https://www.kernel.org/doc/Documentation/memory-barriers.txt

メモリ内のいくつかの状態を変更し、状態 (古いまたは新しい) に関する情報を返すアトミック操作は、実際の操作の両側で SMP 条件付きの一般的なメモリ バリア (smp_mb()) を意味します (明示的なロック操作を除き、説明されています)。後で）。これらには以下が含まれます：

これらは、LOCK クラスおよび UNLOCK クラスの操作の実装や、オブジェクトの破棄に向けた参照カウンターの調整などに使用されるため、暗黙的なメモリ バリア効果が必要です。

それでは、メモリバリアをatomic_xchg()手動で配置する必要がありますか?

Intel x86 プロセッサで、特定のメモリ位置である値を別の値と比較し、比較が成功した場合はマルチスレッド/プロセッサの問題を気にせずにメモリをリセットすることはできますか? CMPXCHG という指示が表示されますが、これは機能しますか? または、比較して設定するユースケースに何かありますか?