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

Question

テストアンドセットを読んだ後 ウィキペディアの項目, 「Test-and-Set は何に使用するのでしょうか?」という疑問が残ります。

これを使用して Mutex (ウィキペディアで説明されているとおり) を実装できることはわかりましたが、他にはどのような用途がありますか?

Answer 1

何らかの作業を行った後、メモリにデータを書き込み、開始以降に別のスレッドが書き込み先を上書きしていないことを確認する場合に、これを使用します。たくさんの ロック/ミューテックスフリーのアルゴリズム この形を取ります。

Answer 2

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

2 つのスレッドが実行されるとします a = a + 1. 。言う a 値から始まります 100. 。両方のスレッドが同時に実行されている場合 (マルチコア)、両方がロードされます。 a として 100, 、に増分します 101, 、それを保存し直します a. 。間違っている！

テストアンドセットでは、「設定する」と言っています。 a に 101, ただし、現在その値がある場合に限ります。 100." この場合、1 つのスレッドはそのテストに合格しますが、もう 1 つのスレッドは失敗します。失敗した場合、スレッドはステートメント全体を再試行でき、今回はロードされます。 a として 101. 。成功。

一般に、これは次の理由により、ミューテックスを使用するよりも高速です。

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

Answer 3

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

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

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

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

Answer 4

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

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

Answer 5

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

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

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