synchronization - テストアンドセットは何に使用されますか？

Question

テストアンドセットのウィキペディアのエントリを読んだ後も、「テストアンドセットは何に使用されるのか」という質問が残ります。

（ウィキペディアで説明されているように）Mutexを実装するためにそれを使用できることを理解していますが、他にどのような用途がありますか？

Answer 1

良い例は「インクリメント」です。

2 つのスレッドが実行されるとしa = a + 1ます。値aで始まるとします100。両方のスレッドが同時に実行されている場合 (マルチコア)、両方とも としてロードaされ100、 にインクリメントされ101、 に戻されaます。違う！

test-and-set を使用すると、「 に設定aしますが101、現在の値が の場合のみ」と言っています100。この場合、1 つのスレッドはそのテストに合格しますが、もう 1 つのスレッドは失敗します。失敗した場合、スレッドはステートメント全体を再試行できますが、今回は としてロードaし101ます。成功。

これは通常、mutex を使用するよりも高速です。その理由は次のとおりです。

1. ほとんどの場合、競合状態は発生しないため、何らかのミューテックスを取得しなくても更新が行われます。
2. 衝突中であっても、1 つのスレッドはまったくブロックされず、他のスレッドがスピンして再試行する方が、ミューテックスのために一時停止するよりも高速です。

Answer 2

何らかの作業を行った後にデータをメモリに書き込みたいときはいつでも使用し、開始してから別のスレッドが宛先を上書きしていないことを確認します。多くのロック/ミューテックス フリー アルゴリズムがこの形式をとっています。

Answer 3

あなたが銀行のアプリケーションを書いていて、そのアプリケーションが口座から 10 ポンド (はい、私は英語です ;)) を引き出すリクエストを持っていると想像してください。したがって、当座預金残高をローカル変数に読み込み、引き出しを差し引いてから、残高をメモリに書き戻す必要があります。

しかし、値の読み取りと書き込みの間に別の同時要求が発生した場合はどうなるでしょうか。そのリクエストの結果が最初のものによって完全に上書きされ、アカウントの残高が正しくない可能性があります。

テスト アンド セットは、上書きした値が想定どおりであることを確認することで、この問題を解決するのに役立ちます。この場合、残高が読み取った元の値であったことを確認できます。それはアトミックであるため、中断できないため、読み取りと書き込みの間で誰もあなたの下から敷物を引き出すことはできません.

同じ問題を解決する別の方法は、メモリ ロケーションのロックを解除することです。残念ながら、ロックは正しく設定するのが非常に難しく、推論するのが難しく、スケーラビリティの問題があり、障害が発生した場合の動作が悪いため、理想的な (しかし確実に実用的な) ソリューションではありません。テスト アンド セット アプローチは、すべてのトランザクションを楽観的に同時に実行できる一部のソフトウェア トランザクション メモリの基礎を形成しますが、競合する場合はすべてロールバックするという犠牲を払います。

Answer 4

基本的に、原子性が非常に重要であることを考えると、その使用はまさにミューテックスのためのものです。それでおしまい。

テスト アンド セットは、非アトミックでより高速な 2 つの他の命令で実行できる操作であるため (マルチプロセッサ システムの場合、アトミック性はハードウェア オーバーヘッドを負担します)、通常、他の理由で使用することはありません。

Answer 5

別のスレッドがまだ値を変更していないと仮定して、共有値を取得し、それを使用して何かを行い、値を変更する必要がある場合に使用されます。

実際の使用に関しては、最後に見たのは並行キュー (セマフォやミューテックスを必要とせずに複数のスレッドによってプッシュ/ポップできるキュー) の実装でした。

ミューテックスではなく TestAndSet を使用するのはなぜですか? 通常、ミューテックスよりも必要なオーバーヘッドが少ないためです。ミューテックスが OS の介入を必要とする場合、TestAndSet は CPU 上の単一のアトミック命令として実装できます。何百ものスレッドを持つ並列環境で実行する場合、コードのクリティカル セクション内の 1 つのミューテックスが深刻なボトルネックを引き起こす可能性があります。