並行プログラミングにおいて、配列ベース・キューイング・ロック（ABQL）は、共有リソースへのアクセスを制御し、競合するスレッド間の公平性を確保するために用いられる同期メカニズムです。これはチケットロックアルゴリズムの一種です。従来のロックメカニズムでは、多くの場合、スレッドが単一のロック変数（アクセス制御に使用される共有データ要素）を巡って競合します。一方、ABQLでは、待機中のスレッドのキューを表すために配列を使用します。各スレッドは、ロックを取得しようとすると、この配列内の固有の位置、つまり「スロット」を割り当てられます。このアプローチでは、スレッドが単一の共有位置ではなく、個々の配列スロット上でスピンするため、スケーラビリティと公平性が大幅に向上します。これにより、競合が軽減され、先着順の取得順序が保証されます。また、この分散スピンにより、キャッシュ・コヒーレンス・トラフィック（複数のプロセッサ・コアのキャッシュ間でデータの一貫性を維持するために必要な通信）も最小限に抑えられ、特にマルチコアおよびマルチプロセッサ・システムにおいてパフォーマンスがさらに向上します。
概要
同期は、共有メモリ[1]マルチプロセッサの設計とプログラミングにおいて重要な課題です。ロック実装における一般的な問題は、プロセッサが共有同期フラグまたはメモリ位置をスピンすることによるネットワーク競合の増加です。そのため、競合するプロセッサの数の観点で、ロックのスケーラビリティは著しく低下します。
アレイベース・キューイング・ロックは、チケットロック・アルゴリズムの拡張版であり、ロックが解放された際に1つのプロセッサだけがロックを取得しようとするため、キャッシュミスの回数が減少します。この効果は、すべてのプロセッサがそれぞれ異なるメモリ位置でスピンすることで実現されます。[2]ロック機構を説明する際に用いられる例えの一つは、リレー競技です。リレー競技では、選手がバトンを次の選手に渡すことで、一度に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 の動作は次の表のように表すことができます。
| 実行手順 | 次のチケット
|
提供できる | 私のチケット(P1)
|
私のチケット(P2)
|
マイチケット(P3)
|
マイチケット(P4)
|
コメント |
|---|---|---|---|---|---|---|---|
| 当初 | 0 | [1, 0, 0, 0] | 0 | 0 | 0 | 0 | すべての変数の初期値は0です |
| P1: フェッチとインク | 1 | [1, 0, 0, 0] | 0 | 0 | 0 | 0 | P1はロックの取得を試み、成功する |
| P2: フェッチとインク | 2 | [1, 0, 0, 0] | 0 | 1 | 0 | 0 | P2はロックを取得しようとする |
| P3: フェッチとインク | 3 | [1, 0, 0, 0] | 0 | 1 | 2 | 0 | P3はロックを取得しようとする |
| P4: フェッチとインク | 4 | [1, 0, 0, 0] | 0 | 1 | 2 | 3 | P4はロックを取得しようとする |
| P1: can_serve[1] = 1;
can_serve[0] = 0 |
4 | [0, 1, 0, 0] | 0 | 1 | 2 | 3 | P1がロックを解除し、P2がロックを取得する |
| P2: can_serve[2] = 1;
can_serve[1] = 0 |
4 | [0, 0, 1, 0] | 0 | 1 | 2 | 3 | P2がロックを解除し、P3がロックを取得する |
| P3: can_serve[3] = 1;
can_serve[2] = 0 |
4 | [0, 0, 0, 1] | 0 | 1 | 2 | 3 | P3がロックを解除し、P4がロックを取得する |
| P4: can_serve[3] = 0 | 4 | [0, 0, 0, 0] | 0 | 1 | 2 | 3 | P4がロックを解除する |
パフォーマンスメトリック
ロック実装を分析するには、次のパフォーマンス基準を使用できます。
- 非競合ロック取得レイテンシ- スレッド間の競合がない場合に、スレッドがロックを取得するのにかかる時間として定義されます。他のロック実装と比較して、実行される命令数が比較的多いため、ABQLの非競合ロック取得レイテンシは高くなります。
- トラフィック- 生成されるバストランザクションの数として定義され、ロックを競合するスレッドの数に依存します。ロックが解放されると、無効化されるキャッシュブロックは1つだけとなり、キャッシュミスは1回のみとなります。これにより、バストラフィックが大幅に削減されます。
- 公平性-ロック取得を待機しているすべてのプロセッサが、要求が発行された順序でロックを取得できることを保証します。各スレッドが個別のメモリ位置でスピンし、ロック取得をキューで待機するため、公平性が確保されます。
- ストレージ- ロック機構の処理に必要なメモリ量。ストレージ要件は、配列can_serveのサイズが増加するため、スレッド数に応じて増加します
利点
- ABQL では、ロックの解放と取得ごとに 1 つのキャッシュ ミスのみがトリガーされ、ブロックを再ロードするためのキャッシュ ミスの影響を受けるキャッシュ ブロックは 1 つだけになるため、スケーラビリティが向上します。
- キューを使用することで、スレッドが要求の発行順にロックを取得することが保証され、ロック取得の公平性が確保されます。
デメリット
- ABQL は、一時停止される可能性のあるスレッド (スリープまたはコンテキストスイッチ)では使用しないでください。ロックをすぐに取得する準備ができていないスレッドがあると、その後ろでロックを待機しているすべてのスレッドの待機時間が長くなります。
- 各ロックにはプロセッサ数に等しいエントリを持つ配列が必要であり、結果として空間計算量は線形になります。すべてのプロセッサが同じロックを同時に争奪することは稀であるため、これは一般的に無駄な処理となります。
参照
参考文献
- ^ 「共有メモリマルチプロセッサ上のスケーラブルな同期アルゴリズム」。
- ^ アンダーソン、ジェームズ・H.、キム、ヨンジク、ハーマン、テッド（2003年1月）[初版2001年6月]。「共有メモリ相互排除：1986年以降の主要な研究動向∗」（PDF）。
