コンピュータサイエンスにおいて、テストアンドセット命令とは、フラグ値をメモリの特定の位置に書き込み（設定し） 、その前の値を単一のアトミック（つまり割り込み不可能）操作として返す命令である。呼び出し元は、その結果を「テスト」して、呼び出しによって状態が変更されたかどうかを確認できる。複数のプロセスが同じメモリ位置にアクセスする可能性があり、あるプロセスが現在テストアンドセットを実行している場合、最初のプロセスのテストアンドセットが完了するまで、他のプロセスは別のテストアンドセットを開始できない。中央処理装置（CPU）は、デュアルポートRAMなどの他の電子部品が提供するテストアンドセット命令を使用することがある。また、CPU自体もテストアンドセット命令を提供する場合がある。
ロックは次のようにアトミックテストアンドセット[ 1 ]命令を使って構築できる。
このコードでは、最初のテスト・アンド・セットの前に、メモリ位置が0に初期化されていることを前提としています。呼び出しプロセスは、以前の値が0だった場合ロックを取得し、そうでない場合はwhileループがロックの取得を待機します。これはスピンロックと呼ばれます。ロックの所有者は、いつでもメモリ位置を0に戻すだけでロックを解放し、別のプロセスが取得できるようにすることができます。ロックの所有者はこのメモリ位置を「所有」しているため、特別な処理は必要ありません。「テストとテスト・アンド・セット」もその一例です。
モーリス・ハーリヒー（1991）は、テスト・アンド・セット（1ビットの被比較対象）には有限の合意数があり、最大2つの同時プロセスに対して待機なしの合意問題を解決できることを証明しました。 [ 2 ]対照的に、比較・スワップ（32ビットの被比較対象）は、この問題に対するより一般的な解決策を提供し、実装によっては、拡張ユーティリティのために、より広い比較・スワップ（64ビットまたは128ビットの被比較対象）も利用できます。
テスト・アンド・セットのハードウェア実装
DPRAMのテスト＆セット命令は様々な方法で動作します。ここでは2つのバリエーションを紹介します。どちらも、2つのポートを備えたDPRAMを記述しており、2つの独立した電子部品（例えば2つのCPU）がDPRAM上のすべてのメモリ位置にアクセスできるようにします。
バリエーション1
CPU 1がテストアンドセット命令を発行すると、DPRAMはまず、そのメモリ位置のアドレスを特別な場所に格納することで、この命令の「内部メモ」を作成します。この時点でCPU 2が同じメモリ位置に対してテストアンドセット命令を発行した場合、DPRAMはまず「内部メモ」をチェックして状況を認識し、BUSY割り込みを発行します。BUSY割り込みはCPU 2に待機と再試行を指示します。これは、割り込みメカニズムを用いたビジー待機またはスピンロックの実装です。これらはすべてハードウェア速度で実行されるため、CPU 2がスピンロックから抜け出すまでの待機時間は非常に短くなります。
CPU 2がメモリ位置にアクセスしようとしていたかどうかに関わらず、DPRAMはCPU 1から与えられたテストを実行します。テストが成功した場合、DPRAMはメモリ位置をCPU 1から与えられた値に設定します。その後、DPRAMはCPU 1がそこに書き込んでいた「内部メモ」を消去します。この時点で、CPU 2はテストアンドセットを発行することができ、これは成功します。
バリエーション2
CPU 1は「メモリ位置A」への書き込みを行うテストアンドセット命令を発行します。DPRAMはメモリ位置Aに値を即座に格納するのではなく、同時に現在の値を特殊レジスタに移動し、メモリ位置Aの内容を特別な「フラグ値」に設定します。この時点でCPU 2がメモリ位置Aにテストアンドセット命令を発行すると、DPRAMは特別なフラグ値を検出し、バリエーション1と同様にBUSY割り込みを発行します。
CPU 2がメモリ位置にアクセスしようとしていたかどうかに関わらず、DPRAMはCPU 1のテストを実行します。テストが成功した場合、DPRAMはメモリ位置AをCPU 1が指定した値に設定します。テストが失敗した場合、DPRAMは特殊レジスタからメモリ位置Aに値をコピーします。どちらの操作も特殊フラグの値を消去します。CPU 2がテストアンドセットを発行すると、成功します。
テストアンドセットのソフトウェア実装
一部の命令セットには、アトミックなテスト・アンド・セット機械語命令があります。例としては、x86 [ 3 ]やIBM System/360およびその後継機種（z/Architectureを含む）[ 4 ]などがあります。これらの命令セットを持たない場合でも、リード・モディファイ・ライト命令やコンペア・アンド・スワップ命令 を用いてアトミックなテスト・アンド・セットを実装できます。
ブール値と共に使用されるテスト＆セット命令は、以下の関数に示すようなロジックを使用します。ただし、関数はアトミックに実行する必要があります。つまり、他のプロセスが関数の実行中に割り込むことができず、関数の実行中のみ存在する状態を見ることができないようにする必要があります。これにはハードウェアのサポートが必要であり、図のように実装することはできません。ただし、図に示すコードはテスト＆セットの動作を説明するのに役立ちます。注: この例では、「lock」は参照渡し（または名前渡し）されることを想定していますが、「initial」への代入は新しい値を作成します（参照のコピーではありません）。
関数TestAndSet(boolean_ref lock) { ブール値初期値 = ロック; ロック = true; 初期値を返します。 } 示されているコードは、テスト・アンド・セット命令の意味でアトミックではないだけでなく、上記のDPRAMハードウェア・テスト・アンド・セットの説明とも異なります。ここでは、設定される値とテストは固定かつ不変であり、テストの結果に関わらず値が更新されます。一方、DPRAMテスト・アンド・セットでは、テストが成功した場合にのみメモリが設定され、設定する値とテスト条件はCPUによって指定されます。ここで設定できる値は1のみですが、メモリ位置の有効な値が0と1のみであり、「値が0以外」であることが唯一のテストであると仮定すると、これはDPRAMハードウェアで説明したケースと同等になります（より具体的には、これらの制約の下ではDPRAMのケースはこれに帰着します）。この観点から、これは「テスト・アンド・セット」という用語の完全な意味で正しく呼ぶことができます。注目すべき重要な点は、テストアンドセットの一般的な意図と原則です。つまり、値のテストと設定は1回のアトミック操作で行われるため、テスト後、設定前には、他のプログラムスレッドやプロセスが対象のメモリ位置を変更することはできません。（これは、その位置が現在特定の値を持っている場合にのみ設定する必要があるためであり、以前にその値を持っていたかどうかは関係ないためです。）
C プログラミング言語では、実装は次のようになります。
#define ロック 1int test_and_set ( int * lock_ptr ) { int old_value ;// -- アトミック セグメントの開始 -- // これは説明目的のみの擬似コードとして解釈してください。// このコードの従来のコンパイルでは、アトミック性、共有メモリの使用 (つまり、キャッシュされていない値)、コンパイラの最適化からの保護、またはその他の必要なプロパティは保証されません。old_value = * lock_ptr ; * lock_ptr = LOCKED ; // -- アトミック セグメントの終了 --古い値を返す; }このコードは、実際には2つの操作、つまりアトミックな読み取り・変更・書き込みとテストがあることも示しています。アトミックである必要があるのは、読み取り・変更・書き込みのみです。（これは、値の比較をいくら遅延させても、テスト対象の値が取得されていればテストの結果は変わらないためです。コードが初期値を書き込むと、テストの結果は確定します。これは、例えば==演算子によってまだ計算されていない場合でも当てはまります。）
テストアンドセットを使用した相互排除
相互排他性を実装する1つの方法は、次のようにテストアンドセットベースのロック[ 5 ] [ 6 ]を使用することです。
スピンロックの擬似C実装
揮発性intロック= 0 ;voidクリティカル（）{// スピン ロック: ロックを取得するまで永久にループします。//この while ループを終了した後、ロックが正常に取得されたことがわかります。これは、test_and_set() 関数がロックをロックしますが、_以前の_ロック値を返すためです。//以前のロック値が 1 の場合 (その場合のみ)、ロックは別のスレッドまたはプロセスによって **既に** ロックされているため、ループに留まり再試行します。//以前のロック値が 0 の場合、ロックする前はロックが **ロックされていなかった**ことを示します。_私たちが_ロックしたため、今はロックされています。そのため、ロックを所有し、スピン ループを終了できます。while ( test_and_set ( & lock ) == 1 );クリティカルセクション// このセクションには一度に 1 つのプロセスしか存在できません// クリティカル セクションが終了したらロックを解除します。//ロックは 1 でした (ロックしたため)。//それ以降にロックを「変更」した他のプロセスは、クリティカル セクション内にはいなかったため、他のプロセスもロックを 1 に設定しましたが、ロックを取得せず、クリティカル セクションに入らず、(諦めるか) // 独自のスピンループで待機しています。lock = 0 ; }ロック変数は共有変数です。つまり、すべてのプロセッサ／スレッドからアクセスできます。volatileキーワードに注意してください。volatile がない場合、コンパイラやCPUはロックへのアクセスを最適化したり、キャッシュされた値を使用したりするため、上記のコードはエラーになります。逆に、残念ながら、volatile を指定しても、読み取りと書き込みがメモリにコミットされることは保証されません。一部のコンパイラは、操作がメモリにコミットされることを保証するためにメモリバリアを発行しますが、C/C++におけるvolatileのセマンティクスは非常に曖昧であるため、すべてのコンパイラがこれを実行するわけではありません。
このスピンロック関数は複数のプロセスから呼び出すことができますが、クリティカルセクションに同時に存在するプロセスは1つだけであることが保証されています。残りのプロセスは、ロックを取得するまでスピンを続けます。プロセスがロックを取得できない可能性もあります。その場合、無限ループが発生します。これはスピンロック実装の欠点であり、公平性が保証されません。これらの問題については、パフォーマンスのセクションでさらに詳しく説明します。
アセンブリ実装
enter_region: ; 「ジャンプ先」タグ; 関数のエントリ ポイント。tsl reg 、flag ; テストとロックの設定; flag は共有変数です;レジスタ reg と flag にコピーされ、その後自動的に 1 に設定されます。cmp reg , #0 ; entry_region のフラグは 0 でしたか?jnz enter_region ; reg がゼロ以外の場合、つまり、エントリ時に flag がゼロ以外の場合、enter_region にジャンプします。ret ; 終了。つまり、フラグはエントリ時にゼロでした。ここまで来たら、tsl ; はそれをゼロ以外の値に設定します。つまり、フラグに関連付けられたリソースを要求したことになります。leave_region:フラグを#0に移動し、フラグretに 0 を格納し、呼び出し元に戻ります。これtslはアトミック命令であり、flagはロック変数です。プロセスはロックを取得しない限り戻りません。
テストアンドセットロックの性能評価
ロック全般の評価指標として、競合のないロック取得のレイテンシ、バストラフィック、公平性、ストレージの4つが挙げられます。[ 7 ]
テスト・アンド・セットのスコアは、バスの交通量が多いことと不公平さという 2 つの項目で低かった。
プロセッサP1がロックを取得し、プロセッサP2もロックを待機している場合、P2はロック取得を試行するためにバストランザクションを継続的に実行します。プロセッサがロックを取得すると、同じロックを取得しようとする他のすべてのプロセッサは、ロックを取得するまでバストランザクションを繰り返し開始することでロック取得を試行し続けます。これにより、テストアンドセットに必要なバストラフィックが大幅に増加します。これにより、キャッシュミスやコヒーレンスミスによる他のすべてのトラフィックの速度が低下します。ロック取得の試行の失敗によってトラフィックが飽和状態になるため、セクション全体の速度が低下します。テストアンドテストアンドセットは、ロック取得要求を継続的に開始しないため、TSLよりも優れています。
公平性を考慮する際、プロセッサがロックが解放された際に、そのロックを取得する公平な機会を得られるかどうかを考慮します。極端な状況では、プロセッサがリソース不足に陥る可能性があり、つまり、ロックが解放されたにもかかわらず、長期間にわたってロックを取得できない可能性があります。
TSLでは、必要なロックが1つだけなので、ストレージオーバーヘッドはほぼゼロです。また、アトミック命令と分岐が1つだけなので、競合のないレイテンシも低くなります。
参照
参考文献
- ^ Anderson, TE (1990-01-01). 「共有マネー型マルチプロセッサにおけるスピンロック代替手法の性能」. IEEE Transactions on Parallel and Distributed Systems . 1 (1): 6– 16. doi : 10.1109/71.80120 . ISSN 1045-9219 .
- ^ Herlihy, Maurice (1991年1月). 「Wait-free 同期」(PDF) . ACM Trans. Program. Lang. Syst . 13 (1): 124– 149. CiteSeerX 10.1.1.56.5659 . doi : 10.1145/114005.102808 . S2CID 2181446. 2007年5月20日閲覧.
- ^ 「BTS—ビットテストとセット」 www.felixcloutier.com . 2016年11月21日閲覧。
- ^ 「IBM Knowledge Center」 . www.ibm.com . 2016年11月21日閲覧。
- ^ Remzi H. Arpaci-Dusseau と Andrea C. Arpaci-Dusseau (2015). 『オペレーティングシステム: 3つの簡単なピース』（バージョン0.91）. Arpaci-Dusseau Books.
- ^ Solihin, Yan (2009).並列コンピュータアーキテクチャの基礎：マルチチップおよびマルチコアシステム. p. 252. ISBN 9780984163007。
- ^ヤン・ソリヒン (2016).並列アーキテクチャの基礎。フロリダ州ボカラトン：CRC Press。ISBN 978-1-4822-1118-4。
外部リンク
- 遅延非感受性システム百科事典からの説明
- Wayback Machineの「Wait-free Test-and-Set」（2006年2月5日アーカイブ）、Yehuda Afek著
- int testandset(int *lock) - Sun SPARCアセンブリ言語で書かれたC呼び出し可能なルーチン
- インテル開発者マニュアル
