テストとテスト＆セット

コンピュータ アーキテクチャでは、テスト アンド セットCPU命令(または命令シーケンス) は、 マルチプロセッサ環境で相互排他を実装するように設計されています。テスト アンド セットを使用して正しいロックを実装できますが、テストとテスト アンド セットの最適化により、バス ロックによって発生するリソース競合、特に競合ロックでのキャッシュ コヒーレンシ プロトコルのオーバーヘッドが軽減されます。

ロックが与えられた場合:

boolean closed := false // 共有ロック変数

入国プロトコルは次のとおりです。

手順EnterCritical() {
   do {
     while (locked == true)
          skip  // ロックが解放されるまで通常の命令を使用してスピンします
  } while ( TestAndSet (locked) == true) //テストアンドセット命令を使用して実際のアトミックロックを試みます
}

終了プロトコルは次のとおりです。

手順ExitCritical() {
  ロック:= false
}

単純なテスト アンド セット プロトコルとの違いは、エントリ プロトコルの開始時に通常のロード命令を使用する追加のスピン ループ (テストおよびテスト アンド セットのテスト) があることです。このループのロードは、アトミック操作 (またはロード排他的命令) に比べて、より少ないオーバーヘッドで実行されます。たとえば、 MESIキャッシュ コヒーレンシ プロトコルを使用するシステムでは、ロードされるキャッシュ ラインは共有状態に移行しますが、テスト アンド セット命令またはロード排他的命令はそれを排他状態に移行します。

これは、複数のプロセッサが同じロックを競合している場合に特に有利です。アトミック命令または排他的ロード命令では、そのプロセッサにキャッシュ ラインへの排他的アクセスを与えるためにコヒーレンシ プロトコル トランザクションが必要ですが (これにより、関係するプロセッサ間でそのラインがピンポン状態になります)、共有状態のラインに対する通常のロードではプロトコル トランザクションはまったく必要ありません。内側のループでスピンしているプロセッサは、完全にローカルで動作します。

キャッシュ一貫性プロトコル トランザクションは、最初のチェックで成功の可能性が高いことが確認された後、外側のループでのみ使用されます。

使用するプログラミング言語が短絡評価をサポートしている場合、エントリ プロトコルは次のように実装できます。

 手順EnterCritical() {
    while (locked == true または TestAndSet(locked) == true )
      skip  // ロックされるまでスピンする
 }

この最適化はシステム プログラミングでは役立ちますが、高レベルの並行プログラミングではテスト アンド セットは避けるべきです。アプリケーションでスピンすると、オペレーティング システムのスケジューラは誰が何をブロックしているかを把握できなくなります。その結果、スケジューラはスレッド間で CPU 時間を割り当てる方法を推測しなければならなくなり、通常はスレッドがタイミング クォータを使い切るのを許すだけになります。スレッドは結局、非生産的にスピンし、スケジュールされていないスレッドを待つことになります。

ミューテックスなどのオペレーティング システムが提供するロック オブジェクトを使用することで、OS はブロックされていないスレッドを正確にスケジュールできます。

• 並列プロセッサ
• 並列プログラミング
• 相互排除
• テストと設定
• フェッチアンド追加

• Gregory R. Andrews、「マルチスレッド、並列、分散プログラミングの基礎」、pp. 100–101。Addison-Wesley、2000年。ISBN 0-201-35752-6 。