配列ベースのキューイングロック

配列ベースのキューイング ロック( ABQL ) は、スレッドが固有のメモリ位置でスピンすることを保証する高度なロックアルゴリズムであり、これにより、ロック取得の公平性が確保され、スケーラビリティが向上します。

同期は、共有メモリ^[1]マルチプロセッサの設計とプログラミングにおける主要な問題です。ロック実装の一般的な問題は、プロセッサが共有同期フラグまたはメモリ位置でスピンすることによるネットワーク競合の増大です。そのため、競合するプロセッサの数の点で、ロックのスケーラビリティは大幅に低下します。

配列ベースのキューイングロックはチケットロックアルゴリズムの拡張版で、ロックが解放されたときに1つのプロセッサだけがロックを取得しようとするため、キャッシュミスの数が減ります。この効果は、すべてのプロセッサが固有のメモリ位置でスピンすることで実現できます。^[2]ロックメカニズムを説明するために使用される例えの1つは、リレー競技で選手がキュー内の次の選手にバトンを渡すことです。これにより、一度に1人の選手だけがバトンを取得できるようになります。

ABQL は、先入れ先出し(FIFO) キューベースのメカニズムを使用して、ロック取得の公平性も保証します。さらに、ロック解放時にキャッシュ ミスが発生するプロセッサは 1 つだけなので、無効化の量はチケットベースのロック実装よりも大幅に少なくなります。

配列ベースのキューイング ロックの実装における最も重要な要件は、すべてのスレッドが一意のメモリ位置でスピンするようにすることです。これは、ロックを争うスレッドの数と同じ長さの配列で実現されます。配列の要素は、最初の要素を除いてすべて 0 に初期化され、最初の要素は値 1 になります。これにより、キューの最初のスレッドによるロックの取得が確実に成功します。ロックが解放されると、配列の次の要素を 1 に設定することで、キュー内の次のスレッドにロックが渡されます。要求は FIFO 順序でスレッドに許可されます。

疑似コードの例を以下に示します。

ABQL_init ( int * next_ticket 、int * can_serve ) { * next_ticket = 0 ; for ( int i = 1 ; i < MAXSIZE ; i ++ ) can_serve [ i ] = 0 ; can_serve [ 0 ] = 1 ; }   

      
            
          
       


ABQL_acquire ( int * next_ticket 、int * can_serve ) { * my_ticket = fetch_and_inc ( next_ticket ); while ( can_serve [ * my_ticket ] != 1 ) ; }   

      
          


ABQL_release ( int * can_serve ) { can_serve [ * my_ticket ] = 0 ; // 次回に備えるcan_serve [ * my_ticket + 1 ] = 1 ; }  

       
        

上記の疑似コードで ABQL を実装するために、can_serve、next_ticket、my_ticket という 3 つの変数が導入されています。それぞれの役割は次のとおりです。

• can_serve配列は、ロック取得のためにキューで待機しているスレッドがスピンする一意のメモリ位置を表します。
• next_ticket は、新しいスレッドに割り当てられる次の利用可能なチケット番号を表します。
• my_ticket は、キュー内の各一意のスレッドのチケット スレッドを表します。

初期化メソッド (ABQL_init) では、変数next_ticketが 0 に初期化されます。can_serve配列の最初の要素を除くすべての要素は 0 に初期化されます。配列 can_serve の最初の要素を 1 に初期化すると、キューの最初のスレッドによるロックの取得が成功することが保証されます。

acquire メソッドは、アトミック操作fetch_and_inc を使用して、新しいスレッドがスピンに使用する次の使用可能なチケット番号 (その後、チケット番号は 1 ずつ増加します) を取得します。キュー内のスレッドは、前のスレッドによって my_ticket の値が 1 に設定されるまで、それぞれの場所でスピンします。ロックを取得すると、スレッドはコードの 重要なセクションに入ります。

スレッドによるロックの解放時に、配列 can_serve の次の要素を 1 に設定することで、制御が次のスレッドに渡されます。ロックの取得を待機していた次のスレッドは、ロックの取得を正常に実行できるようになります。

スレッドがクリティカル セクションに 1 回だけ入るという仮定のもと、4 つのプロセッサがクリティカル セクションに入るために競合していると仮定すると、ABQL の動作は次の表に表すことができます。

ロック実装を分析するには、次のパフォーマンス基準を使用できます。

• 競合のないロック取得待ち時間- スレッド間に競合がない場合に、スレッドがロックを取得するのにかかる時間として定義されます。他のロック実装と比較して、実行される命令の数が比較的多いため、ABQL の競合のないロック取得待ち時間は長くなります。
• トラフィック- ロックを争うスレッドの数に応じて生成されるバス トランザクションの数として定義されます。ロックが解放されると、1 つのキャッシュ ブロックのみが無効になるため、キャッシュ ミスは 1 回だけになります。これにより、バス トラフィックが大幅に減少します。
• 公平性-ロックの取得を待機しているすべてのプロセッサが、要求が発行された順序でロックを取得できるようにします。スレッドがキュー内でロックの取得を待機し、各スレッドが個別のメモリ位置でスピンするため、公平性が保証されます。
• ストレージ- ロック メカニズムの処理に必要なメモリの量。ストレージ要件は、配列 can_serve のサイズの増加により、スレッド数に応じて増加します。

• ABQL では、ロックの解放と取得ごとに 1 つのキャッシュ ミスのみがトリガーされるため、ブロックを再ロードする際にキャッシュ ミスの影響を受けるキャッシュ ブロックは 1 つだけとなり、スケーラビリティが向上します。
• キューを使用することで、スレッドが要求の発行順にロックを取得することが保証され、ロック取得の公平性が確保されます。

• ABQL は、一時停止される可能性のあるスレッド (スリープまたはコンテキストスイッチ)では使用しないでください。ロックを取得する準備がすぐに整わないスレッドがあると、その後ろでロックを待機しているすべてのスレッドの待ち時間が長くなるためです。
• 各ロックには、プロセッサの数と同じ数のエントリを持つ配列が必要であり、その結果、線形空間の複雑さが生じます。すべてのプロセッサが同時に同じロックを争うことはまれであるため、これは通常無駄です。

• チケットロック
• ロック
• フェッチとインクリメント
• アトミックオペレーション
• 共有メモリマルチプロセッサ
• 同期