チケットロック

コンピュータ サイエンスにおいて、チケット ロックは同期メカニズム、またはロック アルゴリズムであり、実行のどのスレッドがクリティカル セクションに入ることができるかを制御するために「チケット」を使用するスピンロックの一種です。

チケット ロックの基本的な概念は、チケット キュー管理システムに似ています。これは、多くのパン屋やデリが、列に並ばせることなく、到着順に顧客にサービスを提供するために使用する方法です。一般的に、顧客が到着すると、何らかのディスペンサーから連続番号のチケットを引き出します。ディスペンサーの上または近くには、通常、「番号を取ってください」などの表示があります。また、通常、現在提供中のチケット番号を表示する動的な表示 (通常はデジタル) もあります。次のチケット番号 (顧客) が提供される準備ができるたびに、「現在提供中」の表示が増分され、番号が呼び出されます。これにより、待っているすべての顧客は、自分の前に何人の人が列またはラインに残っているかを知ることができます。

このシステムと同様に、チケット ロックは先入れ先出し (FIFO)のキュー ベースのメカニズムです。ロック取得の公平性という利点が追加され、次のように動作します。0 から始まる 2 つの整数値があります。最初の値はキュー チケット、2 番目の値はデキュー チケットです。キュー チケットはキュー内のスレッドの位置であり、デキュー チケットは現在ロックを持っている (現在処理中) チケット、またはキューの位置です。

スレッドが到着すると、キュー チケットをアトミックに取得し、その後増分します。この操作のアトミック性は、2 つのスレッドが同時に同じチケット番号を取得できないようにするために必要です。次に、増分前のチケット値をデキュー チケットの値と比較します。同じ場合、スレッドはクリティカル セクションに入ることができます。同じでない場合、別のスレッドがすでにクリティカル セクション内にいるため、このスレッドはビジー ウェイトまたは譲歩する必要があります。スレッドがロックによって制御されるクリティカル セクションを離れると、デキュー チケットをアトミックに増分します。これにより、次の待機中のスレッド (次の連続チケット番号を持つスレッド) がクリティカル セクションに入ることができます。^[1]

ロック取得の公平性の概念は、スレッドがロックを正常に取得する順序に適用されます。^[2] 何らかの公平性が実装されている場合、他のスレッドを優先してロックを取得できないために、スレッドが長時間実行不能になることを防ぎます。公平性が保証されていない場合、スレッド (または複数のスレッド) の実行時間が他のスレッドに比べて不釣り合いに長い場合があります。ここでは、ロック取得の公平性の欠如によりスレッドが過度に遅延する可能性があることを示す簡単な例を示します。

3 つのプロセッサのそれぞれで実行される 3 つのスレッドが、公平性を考慮せずにロックを使用する次の疑似コードを実行している場合を想定します。

while ( 1 ) {ロック{ …クリティカルセクション… }ロック解除}  
     
        
         
        
    
    

ここで、3 つのプロセッサ P1、P2、P3 の物理的な配置により、共有ロック変数の場所へのメモリ アクセス時間が不均一になると仮定します。3 つのプロセッサのロック変数へのアクセス時間の増加順は、P1 < P2 < P3 です。したがって、ロックを取得する際に P1 が常に最も有利で、次に P2、そして P3 が最も不利になります。公平性が保証されない場合にこの状況がスレッド不足につながる仕組みは、上記の 3 つのプロセッサによる疑似コードの実行を示す次の図に示されています。

最初はロックが空いていて、3 つのプロセッサすべてが同時にロックを取得しようとします (時間 1)。P1 はロックへのアクセス時間が最も速いため、最初にロックを取得してクリティカル セクションに入ります。P1 がクリティカル セクションにある間、P2 と P3 はスピンします (時間 2)。クリティカル セクションを終了すると (時間 3)、P1 はロックを解除してロックを解除します。P2 は P3 よりもロックへのアクセスが速いため、次にロックを取得してクリティカル セクションに入ります (時間 4)。P2 がクリティカル セクションにある間、P1 はもう一度ロックを取得しようとしますが、取得できず (時間 5)、P3 とともにスピン待機状態になります。P2 がクリティカル セクションを終了してロック解除を発行すると、P1 と P3 の両方が同時にもう一度ロックを取得しようとします (時間 6)。しかし、アクセス時間が速い P1 が再び勝ち、クリティカル セクションに入ります (時間 7)。 P3 がロックを取得できないというこのパターンは、P1 または P2 のいずれかがロックの取得の試行を停止するまで無期限に続きます。

これは、特定の状況ではロック取得においてある程度の公平性を確保する必要があることを示しています。すべてのロックに公平性を確保するメカニズムがあるわけではないため、上記のような状況が発生する可能性があります。公平性の保証を実装していないロックの例については、以下の「ロックの比較」セクションを参照してください。

非均一メモリアーキテクチャ (NUMA)システムでは、ロック取得の公平性をある程度保証するロック実装が重要です。チケットロックは、この望ましい属性を追加するスピンロックの実装です。次の疑似コード^{[1] [3] は、}ロックの初期化、ロックの取得、およびロックの解放の操作を示しています。ticketLock_acquire の呼び出しは、コードのクリティカルセクションの前にあり、ticketLock_release はその後にあります。各プロセッサは、各プロセッサの my_ticket の値を介して順番を追跡します。

ヤン・ソリヒンの擬似コードの例を下の図に示します。^[1]

ticketLock_init ( int * next_ticket 、int * now_serving )チケットロック初期化   
{
    *現在提供中= *次のチケット= 0 ;    
}

ticketLock_acquire ( int * next_ticket 、int * now_serving )を取得します。   
{
    my_ticket = fetch_and_inc ( next_ticket ) ;  
    while ( * now_serving != my_ticket ) {}    
}

チケットロック解除( int *現在提供中) 
{
    +*現在提供中;
}

上記の疑似コードに沿って進むと、プロセッサが でロックを取得しようとするたびにticketLock_acquire()、fetch_and_incが呼び出され、 next_ticket の現在の値がスレッドのプライベートな my_ticket に返され、共有の next_ticket が増分されることがわかります。フェッチと増分はアトミックに行われるため、他の同時アクセス試行は許可されないことに注意してください。 my_ticket を受信すると、now_serving が my_ticket と等しくない間、各スレッドは while ループ内でスピンします。 now_serving が特定のスレッドの my_ticket と等しくなると、それらのスレッドは ticketLock_acquire() から戻り、コードのクリティカル セクションに入ることができます。 コードのクリティカル セクションの後、スレッドは now_serving を増分する ticketLock_release() を実行します。これにより、次のシーケンシャルな my_ticket を持つスレッドは ticketLock_acquire() を終了し、クリティカル セクションに入ることができます。^[3] my_ticketの値はスレッドがロックに到達した順に取得されるため、その後のロックの取得も同じ順序で行われることが保証されます。このようにして、ロック取得の公平性が保証され、FIFO順序が強制されます。

次の表は、クリティカル セクションへのアクセスを競う 4 つのプロセッサ (P1、P2、P3、P4) があるシステムでチケット ロックが機能している例を示しています。「アクション」列に沿って進むと、上記の擬似コードに基づく結果を確認できます。各行に表示される変数値は、指定されたアクションが完了した後の値です。この例で注目すべき重要な点は、4 つのプロセッサすべてがロックを取得しようとする最初の試みでは、最初に到着したプロセッサだけが実際にロックを取得するという結果になるということです。最初のプロセッサがまだロックを保持している間、それ以降のすべての試みは、クリティカル セクションで順番を待つプロセッサのキューを形成する役割を果たします。その後、各プロセッサが順番にロックを取得し、前の保持者が去ると次のプロセッサがロックを取得できるようになります。また、他のプロセッサによるロックの取得/解放のシーケンス中に別のプロセッサが到着し、順番を待つだけであることに注意してください。

ロックを使用する前の最初のステップは、すべてのロック変数の初期化です (行 1)。 next_ticket と now_serving を 0 に初期化しておくと、ロックを取得しようとする最初のスレッドがチケット 0 を取得し、そのチケットが now_serving に一致するためロックを取得できます。 したがって、P1 がロックを取得しようとすると、すぐに成功し、next_ticket が 1 に増分されます (行 2)。 P3 がロックを取得しようとすると、my_ticket が 1 になり、next ticket が 2 に増分されますが、now_serving がまだ 0 であるため待機する必要があります (行 3)。 次に、P2 がロックを取得しようとすると、my_ticket が 2 になり、next_ticket が 3 に増分されますが、now_serving がまだ 0 であるため待機する必要があります (行 4)。 ここで、P1 は now_serving を 1 に増分してロックを解除し、my_ticket 値が 1 であるため P3 がロックを取得できるようにします (行 5)。ここで、P3 がロックを解放し、now_serving を 2 に増分して、P2 がロックを取得できるようにします (行 6)。P2 がロックを保持している間に、P4 はロックの取得を試み、my_ticket 値 3 を取得し、next_ticket を 4 に増分しますが、now_serving がまだ 2 であるため待機する必要があります (行 7)。P2 がロックを解放すると、now_serving が 3 に増分され、P4 がロックを取得できるようになります (行 8)。最後に、P4 がロックを解放し、now_serving を 4 に増分します (行 9)。現在待機中のスレッドにはこのチケット番号がないため、次に到着するスレッドはチケットに 4 を取得し、すぐにロックを取得します。

Linuxカーネル実装は、現代のマシンのより単純なテスト アンド セットまたは交換ベースのスピンロック アルゴリズムよりもレイテンシが低くなります。さまざまなタイプのスピン ベースのロックを比較する場合は、以下の表を考慮してください。より基本的なロック メカニズムは、高度なロック メカニズムよりも競合のないレイテンシが低くなります。^[1]

• チケット ロックが他のスピンロック アルゴリズムよりも優れている点の 1 つは、公平であることです。待機中のスレッドは、デキュー チケットの整数が増加するにつれて先入れ先出し方式で処理されるため、不足状態が防止されます。
• チケット ロック アルゴリズムでは、一度に 1 つのスレッドだけがクリティカル セクションに入ろうとするため、サンダーリング ハード問題の発生も防止されます。
• 配列ベースのキューイングロック（ABQL）ではスレッドが配列の個々の要素に対してスピンするのとは異なり、すべてのスレッドが1つの変数に対してスピンするため、ストレージは必ずしも問題になりません。 ^[1]

• 1つの欠点は、ロックが解除される前にすべてのスレッドがスピンしている値を読み取ってテストするために必要な追加の命令により、競合のないレイテンシが高くなることです。^[1]
• チケットロックのもう一つの大きな欠点は、スケーラブルではないことです。研究によると、チケットロックシステムにプロセッサが追加されると、パフォーマンスが指数関数的に低下するようです。^[4]
• もう一つの問題は、ロックを解除することから生じます。すべてのスレッドが 1 つの変数をスピンしているため、ロックが解除されると ڨ(p) の無効化 (および ڨ(p) の取得) が発生します。これは、すべてのスレッドがブロックをキャッシュに再ロードし、クリティカル セクションへのアドミッションを決定するためのテストを実行する必要があるためです。^[1]

チケットロックは、1991年にメラー・クラミーとスコットによって導入されました。^[3] このアルゴリズムは、その利点のために2008年にLinuxカーネルに導入されましたが、 ^[5]欠点があったため準仮想化環境では省略されました。 ^[6] 2010年7月現在^{[アップデート]}、準仮想化でチケットロックを使用できるようにするための作業が進行中です。^[7] 2015年3月現在、このタイプのロック方式は、Red Hat Enterprise Linuxのシステムで再採用されています。^[8]

• ランポートのベーカリーアルゴリズムは、「チケット」や「カウンター」の同様の概念を使用していますが、アトミックハードウェア操作は使用していません。これは、パフォーマンスよりもフォールトトレランスのために設計されました。すべてのプロセッサがリリースカウンターを継続的に検査するのではなく、ベーカリーロックはピアのチケットを検査しながら回転します。^[3]
• キューベースのスピンロックは、ウェイターのキューを維持し、ロック解除操作中に最初のウェイターにロックを許可することで公平性を保証します。^[9]

• フェッチと追加、チケットロックを実装するためにフェッチと増分の代わりに使用できる別のアトミック命令