テスト・アンド・セット
出典: フリー百科事典『ウィキペディア（Wikipedia）』
テスト・アンド・セット（Test-and-Set、TAS）命令は、あるメモリ位置へアトミックに書き込みを行うコンピュータの命令である。値をセットする前に何らかのテストを行い（例えば、そのメモリ位置の内容が指定された値と等しいかどうかなど）、テストが失敗した場合は値のセットは行われない。複数のプロセスが同じメモリ位置にアクセスする可能性があり、ひとつのプロセスがテスト・アンド・セットを実行中であれば、他のプロセスは最初のプロセスの命令が完了するまで、テスト・アンド・セット命令を実行開始することができない。CPUは他の電子部品（例えば、デュアルポートRAM; DPRAM）を使用してテスト・アンド・セット命令を実現していることもあるし、CPU自身で実現していることもある。
目次 |
[編集] ハードウェアの実装
DPRAMによるテスト・アンド・セット命令は様々な方式が考えられる。ここでは2種類のバリエーションを示す。いずれの場合もDPRAMは2ポートあって、2つの電子部品（例えば2つのCPU）がDPRAM内の任意のメモリ位置にアクセスできる。
[編集] バリエーション 1
CPU1がテスト・アンド・セット命令を発行すると、最初にDPRAM内の特別な場所にテスト・アンド・セットのターゲットとなっているメモリアドレスを「内部ノート」として記録する。ここでもしCPU2も同じアドレスにテスト・アンド・セット命令を発行しようとしていた場合、DPRAMにある「内部ノート」をチェックして状況を把握し、BUSY割り込みを発行する。BUSY割り込みにより、CPU2はCPU1の完了を待ってリトライすることになる。これは割り込み機構を利用したビジーウェイト（あるいはスピンロック）的実装である。これらは全て高速に処理されるので、CPU2が待っている時間は実際には非常に短い。
CPU2がアクセスを試みているかどうかに関わらず、DPRAMによってCPU1のためにテストが行われる。テストが成功すると、DPRAMはCPU1が指定した値をそのアドレスにセットする。DPRAMはCPU1が書き込んだ「内部ノート」をクリアし、CPU2がテスト・アンド・セット命令を発行できるようになる。
[編集] バリエーション 2
CPU1は、メモリアドレスA への書き込みのテスト・アンド・セット命令を発行する。DPRAMは即座にそのアドレスAに値を書き込まず、アドレスAの現在の値を特別なレジスタに移し、アドレスAの位置には特別なフラグをセットする。ここでCPU2が同じアドレスAへのテスト・アンド・セット命令を発行すると、DPRAMは特別なフラグがセットされていることを検出し、バリエーション1と同様にBUSY割り込みを発生させる。
CPU2がそのアドレスにアクセスしようとしていたかどうかに関わらず、DPRAMはCPU1のテストを実行する（特別なレジスタに格納された値とCPU1の指定した値を比較する）。テストが成功すると、DPRAMはアドレスAのメモリ位置にCPU1が指定した値を書き込む。テストが失敗するとDPRAMは特別なレジスタからアドレスAに値を戻す。どちらの操作によっても特別なフラグは消されるので、CPU2がテスト・アンド・セット命令を発行できるようになる。
[編集] 擬似コード
ブーリアン値によるテスト・アンド・セット命令は以下の関数のように動作する。この関数全体が必ずアトミックに実行される。つまり、他のプロセスがこの関数の実行中に割り込むことは出来ず、関数実行途中の状態を観測することはできない。これはテスト・アンド・セットがどのように働くのかを示すものであって、ハードウェアのサポートなしにアトミック性は実現できないし、このような単純な関数だけで正しく動作することはない。
function TestAndSet(boolean lock) {
boolean initial = lock
lock = true
return initial
}
ミューテックスはこれを利用すると以下のように実装できる。
boolean lock = false
function Critical(){
while TestAndSet(lock)
skip //ロックが獲得されていたらスピンする。
critical section //一度にひとつのプロセスだけがここに到達できる。
lock = false //クリティカルセクションが終了したらロックを解放する。
}
この関数は複数のプロセスから呼び出すことができるが、クリティカルセクションに入ることができるのは一度にひとつのプロセスだけであることが保証される。この方式は実際のマルチプロセッサマシンでは効率的ではない（定期的にロックを読み書きするため、キャッシュコヒーレンシ問題が発生する）。テスト・アンド・テストアンドセット（後述）がより効率的な解決策となる。ここで示した例はスピンロックであり、whileループでロック獲得をスピンしながら待つようになっている。
[編集] テスト・アンド・セットを利用したセマフォの実装
テスト・アンド・セット命令を使ってセマフォを実装することができる。シングルプロセッサシステムではセマフォの実装にこの技法は不要であり、単に割り込みを不可にしてセマフォにアクセスするだけで事足りる。しかし、マルチプロセッサシステムでは、全プロセッサで同時に割り込み不可にできたとしても、それだけでは不十分である。割り込み不可となっていても、複数のプロセッサが同時に同じセマフォにアクセスすることができる。この場合、テスト・アンド・セット命令が使われる可能性がある。
[編集] テスト・アンド・テストアンドセット
テスト・アンド・セット命令でスピンロックを実装する場合、テスト・アンド・セット命令によるアトミックなメモリアクセスによってバスがロックされ、キャッシュがインバリッドとなるため、性能に悪影響を与える。
このオーバヘッドを下げるため、「テスト・アンド・テストアンドセット」と呼ばれるロックプロトコルが使われる。アイデアの基本はテスト・アンド・セット命令をスピンの期間中に使わないで、成功すると予想されるときにのみテスト・アンド・セット命令を使うのである。以下に擬似コードでの例をあげる:
boolean locked := false // 共有ロック変数
procedure EnterCritical() {
while (locked == true) skip // ロックが解放されたように見えるまでスピン
while TestAndSet(locked) // 実際のアトミックなロック操作
while (locked == true) skip // テスト・アンド・セットが失敗したらロックが解放されるまで再び待つ
}
解放処理は以下の通り:
procedure ExitCritical() {
locked := false
}
クリティカルセクションに入る処理では、通常のメモリリードでスピンし、ロックが解放されるのを待つ。テスト・アンド・セットは実際にロックを獲得するときだけ使用する。従って、テスト・アンド・セットの回数が減り、バスをロックする回数も減る。
もし、プログラミング言語が最小評価方式(Minimal Evaluation)ならば、ロック獲得処理を以下のように実装することもできる:
procedure EnterCritical() {
while ( locked == true or TestAndSet(locked) == true )
skip // アンロックされるまでスピン
}
なお、この最適化が有益なのはシステムプログラムの分野のみである。アプリケーションレベルの並列処理ではこのような方式を採用すべきでない。このようなプログラムは「ダブルチェックされたロック」と呼ばれ、アンチパターンのひとつに挙げられている。
[編集] 関連項目
[編集] 外部リンク
いずれも英文
- Description Encyclopaedia of Delay-Insensitive Systems
- "Wait-free Test-and-Set" by Yehuda Afek
- int testandset(int *lock) - C言語から呼び出せる Sun Sparc アセンブリ言語のルーチン
- Techniques for mutual exclusion
