非ブロッキングアルゴリズム

コンピュータサイエンスでは、あるスレッドの障害や中断が別のスレッドの障害や中断を引き起こさないアルゴリズムをノンブロッキングと呼びます。 ^{[1]一部の操作では、これらのアルゴリズムは従来の}ブロッキング実装 の便利な代替手段となります。ノンブロッキングアルゴリズムは、システム全体の進行が保証されている場合はロックフリー、スレッドごとの進行も保証されている場合は待機フリーです。2003年にオブストラクションフリーが導入されるまで、「ノンブロッキング」は「ロックフリー」の同義語として文献で使用されていました。^[2]

「ノンブロッキング」という言葉は、従来、「既存の通話を再調整することなく」一連のリレーを介して接続をルーティングできる通信ネットワークを表すために使用されていました^{[この引用には引用が必要です]} ( Clos ネットワークを参照)。また、電話交換機に欠陥がない場合は、「常に接続できます」^{[この引用には引用が必要です]} (ノンブロッキング最小スパニング スイッチを参照)。

マルチスレッド プログラミングの従来のアプローチは、ロックを使用して共有リソースへのアクセスを同期することです。ミューテックス、セマフォ、クリティカル セクションなどの同期プリミティブはすべて、共有メモリ構造が破損する可能性がある場合に、特定のコード セクションが同時に実行されないようにプログラマが保証できるメカニズムです。あるスレッドが、別のスレッドによって既に保持されているロックを取得しようとすると、そのスレッドはロックが解放されるまでブロックされます。

スレッドをブロックすることは、多くの理由で望ましくない場合があります。明らかな理由は、スレッドがブロックされている間は何も実行できないことです。ブロックされたスレッドが高優先度またはリアルタイムのタスクを実行していた場合、その進行を停止することは非常に望ましくありません。

その他の問題はそれほど明白ではありません。たとえば、ロック間の特定の相互作用により、デッドロック、ライブロック、優先順位の逆転などのエラー状態が発生する可能性があります。ロックの使用には、並列処理の機会を大幅に減らす可能性がある粗粒度のロックと、より慎重な設計が必要でロックのオーバーヘッドが増加し、バグが発生しやすくなる細粒度のロックとの間のトレードオフも伴います。

ブロッキングアルゴリズムとは異なり、ノンブロッキングアルゴリズムはこれらの欠点がなく、さらに割り込みハンドラで安全に使用できます。プリエンプトされたスレッドは再開できませんが、プリエンプトされたスレッドがなくても処理を進めることができます。対照的に、相互排他制御によって保護されたグローバルデータ構造は、プリエンプトされたスレッドがロックを保持している可能性があるため、割り込みハンドラで安全にアクセスできません。これは、クリティカルセクション中に割り込み要求をマスクすることで修正できますが、クリティカルセクションのコードの実行時間が制限されている（できれば短い）必要があります。そうしないと、過度の割り込みレイテンシが発生する可能性があります。^[3]

ロックフリーデータ構造はパフォーマンスを向上させるために使用できます。ロックフリーデータ構造では、共有データ構造へのアクセスを一貫性を保つためにシリアル化する必要がないため、シリアル実行ではなく並列実行に費やされる時間が増加し、マルチコアプロセッサでのパフォーマンスが向上します。^[4]

いくつかの例外を除き、非ブロッキング アルゴリズムは、ハードウェアが提供する必要があるアトミックな 読み取り、変更、書き込みプリミティブを使用します。その中で最も有名なのは、比較とスワップ (CAS)です。クリティカル セクションは、ほとんどの場合、これらのプリミティブの標準インターフェイスを使用して実装されます (一般的に、これらのプリミティブを使用して実装されている場合でも、クリティカル セクションはブロッキングになります)。1990 年代には、すべての非ブロッキング アルゴリズムは、許容できるパフォーマンスを実現するために、基礎となるプリミティブを使用して「ネイティブ」に記述する必要がありました。しかし、ソフトウェア トランザクション メモリという新興分​​野では、効率的な非ブロッキング コードを作成するための標準的な抽象化が期待されています。^{[5] [6]}

スタック、キュー、セット、ハッシュ テーブルなどの基本的なデータ構造を提供する研究も数多く行われてきました。これにより、プログラムはスレッド間で非同期的にデータを簡単に交換できるようになります。

さらに、一部の非ブロッキング データ構造は、特別なアトミック プリミティブなしで実装できるほど弱いものです。これらの例外には次のものが含まれます。

• 利用可能な符号なし整数型の1つのオーバーフローを均等に分割するサイズの、単一読み取り単一書き込みリングバッファ FIFOは、メモリバリアのみを使用して無条件に安全に実装できます。
• 単一のライターと任意の数のリーダーによる読み取り、コピー、更新。(リーダーは待機不要で、ライターはメモリの再利用が必要になるまで通常はロック不要です)。
• 複数のライターと任意の数のリーダーによる読み取り、コピー、更新。(リーダーは待機なしです。複数のライターは通常、ロックを使用してシリアル化され、妨害なしではありません)。

いくつかのライブラリは内部的にロックフリー技術を使用していますが^{[7] [8] [9]}、正しいロックフリーコードを書くのは困難です。^{[10] [11] [12] [13]}

非ブロッキング アルゴリズムは、一般的に、一連の読み取り、読み取り変更書き込み、および書き込み命令を慎重に設計された順序で実行します。最適化コンパイラは、積極的に操作を再配置できます。そうしない場合でも、多くの最新の CPU は、メモリ バリアを使用して CPU に再配置しないように指示しない 限り、このような操作を再配置することがよくあります (「弱い一貫性モデル」を備えています)。C ++11プログラマはで を使用でき、C11プログラマは を使用できます。どちらも、コンパイラにこのような命令を再配置しないように指示し、適切なメモリ バリアを挿入する型と関数を提供します。^[14]std::atomic<atomic><stdatomic.h>

待機フリーは、システム全体のスループットの保証と飢餓フリーを組み合わせた、最も強力なノンブロッキング進行保証です。すべての操作で、操作が完了するまでにアルゴリズムが実行するステップ数に制限がある場合、アルゴリズムは待機フリーです。^[15] この特性はリアルタイムシステムにとって非常に重要であり、パフォーマンスコストが高すぎない限り、常に備えておくと便利です。

^{1980年代[16]}には、すべてのアルゴリズムが待機なしで実装できることが示され、ユニバーサル構築と呼ばれるシリアルコードからの多くの変換が実証されました。しかし、結果として得られるパフォーマンスは、一般的には単純なブロッキング設計にさえ匹敵しません。それ以来、いくつかの論文でユニバーサル構築のパフォーマンスが向上しましたが、それでもそのパフォーマンスはブロッキング設計をはるかに下回っています。

待機なしのアルゴリズムを作成することの難しさについて調査した論文はいくつかある。例えば、広く利用可能なアトミック条件プリミティブであるCASとLL/SCは、スレッド数に応じてメモリコストが線形に増加することなく、多くの一般的なデータ構造の飢餓のない実装を提供できないことが^[17]で示されている。

ただし、これらの下限は実際には実際の障壁にはなりません。共有メモリ内のスレッドごとにキャッシュ ラインまたは排他予約グラニュル (ARM では最大 2 KB) のストアを費やすことは、実用的なシステムではそれほどコストがかからないと考えられるためです。通常、論理的に必要なストアの量は 1 ワードですが、物理的には同じキャッシュ ライン上の CAS 操作が衝突し、同じ排他予約グラニュル内の LL/SC 操作が衝突するため、物理的に必要なストアの量^{[引用が必要]}は大きくなります。^{[説明が必要]}

待機なしのアルゴリズムは、研究でも実践でも 2011 年まで珍しいものでした。しかし、2011 年に Kogan とPetrank ^{[18]は、一般的なハードウェアで一般的に利用可能な}CASプリミティブに基づく待機なしのキューを発表しました。彼らの構築は、Michael と Scott ^[19]のロックなしのキューを拡張したもので、これは実際によく使用される効率的なキューです。Kogan と Petrank によるフォローアップの論文^[20 ]では、待機なしのアルゴリズムを高速化する方法が提供され、この方法を使用して、待機なしのキューをロックなしのキューと実質的に同じ速度にしました。Timnat と Petrank によるその後の論文^[21]では、ロックなしのデータ構造から待機なしのデータ構造を自動的に生成するメカニズムが提供されました。したがって、現在では多くのデータ構造で待機なしの実装が利用可能です。

合理的な仮定の下では、Alistarh、Censor-Hillel、およびShavitは、ロックフリーアルゴリズムは実質的に待機フリーであることを示しました。^[22] したがって、厳しい期限がない場合、待機フリーアルゴリズムは、それがもたらす追加の複雑さに見合わない可能性があります。

ロックフリーにより、個々のスレッドが飢餓状態になることを許容しますが、システム全体のスループットは保証されます。プログラム スレッドが十分に長い時間実行されたときに、少なくとも 1 つのスレッドが進行する場合 (進行の合理的な定義による)、アルゴリズムはロックフリーです。待機フリー アルゴリズムはすべてロックフリーです。

特に、1 つのスレッドが中断された場合、ロックフリー アルゴリズムは残りのスレッドが引き続き進行できることを保証します。したがって、2 つのスレッドが同じミューテックス ロックまたはスピンロックを争う可能性がある場合、そのアルゴリズムはロックフリーではありません。(ロックを保持している 1 つのスレッドを中断すると、2 番目のスレッドはブロックされます。)

アルゴリズムがロックフリーであるのは、一部のプロセッサによる操作が有限数のステップで成功する回数が無限にある場合です。たとえば、N 個のプロセッサが操作を実行しようとしている場合、N個のプロセスのうちの一部は有限数のステップで操作を完了するのに成功しますが、他のプロセスは失敗して再試行する可能性があります。待機フリーとロックフリーの違いは、各プロセスによる待機フリー操作は、他のプロセッサに関係なく、有限数のステップで成功することが保証されていることです。

一般に、ロックフリー アルゴリズムは、独自の操作の完了、妨害操作の支援、妨害操作の中止、待機の 4 つのフェーズで実行できます。独自の操作の完了は、支援と中止が同時に発生する可能性があるため複雑ですが、完了までの最短のパスであることは間違いありません。

障害に遭遇したときにいつ支援するか、中止するか、または待機するかを決定するのは、競合マネージャの責任です。これは非常に単純なもの (優先度の高い操作を支援し、優先度の低い操作を中止する) の場合もあれば、スループットを向上させるために最適化されたもの、または優先度の高い操作の待ち時間を短縮したものの場合もあります。

正しい同時支援は、通常、ロックフリー アルゴリズムの最も複雑な部分であり、実行に非常にコストがかかることがよくあります。支援スレッドが遅くなるだけでなく、共有メモリのメカニズムにより、支援対象のスレッドも、まだ実行中の場合は遅くなります。

妨害フリーは、最も弱い自然なノンブロッキング進行保証です。アルゴリズムが妨害フリーであるとは、ある時点で、単一のスレッドが独立して（つまり、妨害するすべてのスレッドが一時停止された状態で）実行され、制限された数のステップでその操作を完了することです。^[15]すべてのロックフリーアルゴリズムは妨害フリーです。

障害フリーでは、部分的に完了した操作を中止し、変更をロールバックできることのみが求められます。同時実行支援を中止すると、検証が容易な、はるかに単純なアルゴリズムになることがよくあります。システムが継続的にライブロックするのを防ぐのは、競合マネージャの役割です。

一部の障害のないアルゴリズムでは、データ構造内で「一貫性マーカー」のペアを使用します。データ構造を読み取るプロセスは、最初に 1 つの一貫性マーカーを読み取り、次に関連データを内部バッファーに読み取り、次にもう 1 つのマーカーを読み取って、マーカーを比較します。2 つのマーカーが同一であれば、データは一貫しています。読み取りがデータ構造を更新する別のプロセスによって中断された場合、マーカーは同一でない可能性があります。このような場合、プロセスは内部バッファー内のデータを破棄して再試行します。

• デッドロック
• Java ConcurrentMap#ロックフリーの原子性
• ライブネス
• ロック（コンピュータサイエンス）
• 相互排除
• 優先順位の逆転
• 資源不足

• ロックフリープログラミング入門
• ノンブロッキングアルゴリズム