テストと設定

コンピュータサイエンスにおいて、テスト アンド セット 命令は、メモリの場所に 1 を書き込んで (設定して) 、その古い値を単一のアトミック(つまり、割り込み不可能) 操作として返すために使用される命令です。呼び出し元は、呼び出しによって状態が変更されたかどうかを確認するために、結果を「テスト」できます。複数のプロセスが同じメモリの場所にアクセスする可能性があり、プロセスが現在テスト アンド セットを実行している場合、最初のプロセスのテスト アンド セットが終了するまで、他のプロセスは別のテスト アンド セットを開始できません。中央処理装置(CPU) は、デュアルポート RAMなどの別の電子コンポーネントによって提供されるテスト アンド セット命令を使用することがあります。CPU 自体もテスト アンド セット命令を提供する場合があります。

ロックは次のようにアトミックテストアンドセット^[1]命令を使用して構築できます。

このコードでは、最初のテスト アンド セットの前のある時点でメモリ位置が 0 に初期化されていると想定しています。呼び出しプロセスは、古い値が 0 だった場合はロックを取得し、そうでない場合は while ループがスピンしてロックの取得を待機します。これは、スピンロックと呼ばれます。ロックの保持者は、いつでもメモリ位置を 0 に設定し直すだけで、別のプロセスがロックを取得できるように解放できます。保持者がこのメモリ位置を「所有」しているため、特別な処理は必要ありません。「テストとテスト アンド セット」は別の例です。

モーリス・ハーリヒ（1991）は、テスト・アンド・セット（1ビット比較対象）には有限の合意数があり、最大2つの同時プロセスに対して待機なしの合意問題を解決できることを証明しました。 ^[2]対照的に、比較・スワップ（32ビット比較対象）は、この問題に対するより一般的な解決策を提供し、一部の実装では、拡張ユーティリティとして比較・ダブル・アンド・スワップ（64ビット比較対象）も利用できます。

DPRAM のテスト アンド セット命令は、さまざまな方法で動作します。ここでは 2 つのバリエーションを示します。どちらも、2 つのポートを提供する DPRAM について説明しており、2 つの個別の電子コンポーネント (2 つの CPU など) が DPRAM 上のすべてのメモリ位置にアクセスできるようにします。

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 はテスト アンド セットを発行することができ、これは成功します。

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 のみであり、「値がゼロ以外」が唯一の許容テストである場合、これは DPRAM ハードウェアについて説明されているケースに相当します (または、より具体的には、これらの制約の下で DPRAM のケースはこれに縮小されます)。その観点から、これは、その用語の完全な従来の意味で「テスト アンド セット」と呼ぶことができます。注目すべき重要な点は、テスト アンド セットの一般的な意図と原則です。つまり、値は 1 つのアトミック操作でテストおよび設定されるため、テスト後、設定前は、他のプログラム スレッドまたはプロセスがターゲット メモリの場所を変更することはできません。(これは、場所が現在特定の値を持っている場合にのみ設定する必要があり、以前にその値を持っていたかどうかは設定する必要がないためです。)

C プログラミング言語では、実装は次のようになります。

#define ロック 1

int test_and_set ( int * lockPtr ) { int oldValue ;   
     

    // -- アトミック セグメントの開始 -- 
// これは説明目的のみの擬似コードとして解釈する必要があります。// このコードの従来のコンパイルでは、アトミック性、共有メモリの使用 (つまり、キャッシュされていない値)、コンパイラの最適化からの保護、またはその他の必要なプロパティは保証されません。oldValue = * lockPtr ; * lockPtr = LOCKED ; // -- アトミック セグメントの終了 --    
    
    
    
      
      
    

    古い値を返します; } 

また、このコードでは、実際には 2 つの操作 (アトミックな読み取り、変更、書き込みとテスト) があることも示されています。アトミックである必要があるのは、読み取り、変更、書き込みのみです。(これは、値の比較をいくら遅延しても、テストする値が取得された後はテストの結果が変わらないため、当てはまります。コードが初期値を書き込むと、テストの結果は確立されます。これは、たとえば == 演算子によってまだ計算されていない場合でも当てはまります。)

相互排他制御を実装する一つの方法は、次のようにテストアンドセットベースのロック^{[5] [6]}を使用することである。

揮発性整数ロック= 0 ;    

void critical () { // スピンロック: ロックを取得するまで永久にループします。この while ループを終了した後、test_and_set() 関数がロックをロックし、前のロック値を返すため、ロックが正常に取得されたことがわかります。前のロック値が 1 の場合、ロックは別のスレッドまたはプロセスによって **すでに** ロックされています。ただし、前のロック値が 0 だった場合、ロックはロックされる前に **ロックされていなかった** ことを示しますが、ロックしたためロックされ、ロックを所有していることを示します。while ( test_and_set ( & lock ) == 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 のフラグはゼロでしたか?  

  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 つだけなので、競合のないレイテンシも低くなります。

• フェッチアンド追加
• テストとテスト＆セット
• ロードリンク/ストア条件
• 比較と交換

• 遅延非敏感システム百科事典からの説明
• Wayback Machineの「Wait-free Test-and-Set」（2006-02-05 アーカイブ）、Yehuda Afek著
• int testandset(int *lock) - Sun SPARCアセンブリ言語で書かれたC呼び出し可能なルーチン
• Intel 開発者マニュアル