Loading article…
コンピュータサイエンスでは、あるスレッドの障害や中断が他のスレッドの障害や中断を引き起こさない場合、そのアルゴリズムは非ブロッキングと呼ばれます。 [ 1 ]一部の操作では、これらのアルゴリズムは従来のブロッキング実装 に代わる有用な選択肢となります。非ブロッキングアルゴリズムは、システム全体の進行が保証されている場合はロックフリーであり、スレッドごとの進行も保証されている場合は待機フリーです。「非ブロッキング」は、2003年に障害フリーが導入されるまで、文献では「ロックフリー」の同義語として使用されていました。[ 2 ]
「ノンブロッキング」という言葉は、従来、既存の通話を再編成することなく、一連のリレーを経由して接続をルーティングできる電気通信ネットワークを説明するために使用されていました（Closネットワークを参照）。また、電話交換機が「故障していなければ、常に接続を確立できる」という特徴もあります（ノンブロッキング最小スパニングスイッチを参照）。
マルチスレッドプログラミングの従来のアプローチは、共有リソースへのアクセスを同期するためにロックを使用することです。ミューテックス、セマフォ、クリティカルセクションなどの同期プリミティブはすべて、プログラマがコードの特定のセクションが同時に実行されないようにするためのメカニズムです。これは、同時に実行すると共有メモリ構造が破損する可能性があるためです。あるスレッドが、別のスレッドによって既に保持されているロックを取得しようとすると、そのスレッドはロックが解放されるまでブロックされます。
スレッドをブロックすることは、多くの理由から望ましくない場合があります。明白な理由の一つは、スレッドがブロックされている間は何も実行できないことです。ブロックされたスレッドが優先度の高いタスクやリアルタイムタスクを実行していた場合、その進行を停止させることは非常に望ましくありません。
その他の問題は、それほど明白ではありません。例えば、ロック間の特定の相互作用によって、デッドロック、ライブロック、優先度逆転などのエラー状態が発生する可能性があります。また、ロックを使用する際には、並列処理の機会を大幅に減少させる粗粒度ロックと、より慎重な設計が必要で、ロックのオーバーヘッドが増加し、バグが発生しやすい細粒度ロックとの間でトレードオフが生じます。
ブロッキングアルゴリズムとは異なり、ノンブロッキングアルゴリズムはこれらの欠点がなく、さらに割り込みハンドラでの使用も安全です。プリエンプトされたスレッドは再開できませんが、それでも処理を進めることができます。対照的に、相互排他によって保護されたグローバルデータ構造には、プリエンプトされたスレッドがロックを保持している可能性があるため、割り込みハンドラ内では安全にアクセスできません。これは、クリティカルセクション中に割り込み要求をマスクすることで修正できますが、そのためにはクリティカルセクション内のコードの実行時間が制限されている（できれば短い）必要があり、そうでない場合は過剰な割り込み遅延が発生する可能性があります。[ 3 ]
ロックフリーのデータ構造は、パフォーマンスを向上させるために使用できます。ロックフリーのデータ構造は、共有データ構造へのアクセスを一貫性を保つためにシリアル化する必要がないため、シリアル実行ではなく並列実行に費やす時間を増やし、マルチコアプロセッサでのパフォーマンスを向上させます。[ 4 ]
ごく少数の例外を除き、ノンブロッキング アルゴリズムは、ハードウェアが提供する必要のあるアトミックな読み取り・変更・書き込みプリミティブを使用します。その中でも最も有名なのが比較交換 (CAS)です。クリティカル セクションは、ほぼ常にこれらのプリミティブ上の標準インターフェースを使用して実装されます (一般的には、これらのプリミティブを使用して実装した場合でも、クリティカル セクションはブロッキングになります)。1990 年代には、すべてのノンブロッキング アルゴリズムは、許容できるパフォーマンスを達成するために、基盤となるプリミティブを使用して「ネイティブ」に記述する必要がありました。しかし、ソフトウェア トランザクショナル メモリの新興分野は、効率的なノンブロッキング コードを記述するための標準的な抽象化を約束しています。[ 5 ] [ 6 ]
スタック、キュー、セット、ハッシュテーブルといった基本的なデータ構造を提供する研究も数多く行われてきた。これらを用いることで、プログラムはスレッド間でデータを非同期的に容易に交換できるようになる。
さらに、一部の非ブロッキングデータ構造は、特別なアトミックプリミティブなしで実装できるほど脆弱です。これらの例外には以下が含まれます。
いくつかのライブラリは内部的にロックフリー技術を使用していますが、[ 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では最大2KB）分のストア領域を使用することは、実用的なシステムにとってコストが高すぎるとは考えられていないからです。通常、論理的に必要なストア領域は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つのスレッドが同じミューテックスロックまたはスピンロックを競合する可能性がある場合、そのアルゴリズムはロックフリーではありません。（ロックを保持しているスレッドを中断すると、もう一方のスレッドはブロックされます。）
アルゴリズムがロックフリーであるのは、どのプロセッサ上で行われる操作も有限ステップで必ず成功する場合です。例えば、N個のプロセッサが操作を実行しようとする場合、N個のプロセスのうちいくつかは有限ステップで操作を完了できますが、他のプロセスは失敗して再試行する可能性があります。待機フリーとロックフリーの違いは、待機フリーの場合、各プロセスによる操作は、他のプロセッサの状態に関係なく、有限かつ限定されたステップ数で必ず成功することが保証される点です。
一般的に、ロックフリーアルゴリズムは、自身の操作の完了、妨害操作の支援、妨害操作の中止、および待機という4つのフェーズで実行されます。自身の操作の完了は、同時実行される支援と中止の可能性によって複雑になりますが、常に完了までの最短経路となります。
障害物に遭遇した際に、支援するか、中止するか、待機するかを決定するのは、競合マネージャの責任です。これは非常に単純な場合（優先度の高い操作を支援し、優先度の低い操作を中止する）もあれば、スループットの向上や、優先度の高い操作のレイテンシの低減のために最適化される場合もあります。
適切な並行支援は、通常、ロックフリーアルゴリズムの中で最も複雑な部分であり、実行コストが非常に高くなることが多い。支援するスレッドの速度が低下するだけでなく、共有メモリの仕組み上、支援を受けるスレッドがまだ実行中であれば、そのスレッドの速度も低下してしまうからである。
障害フリーは、自然な非ブロッキング進行保証の中で最も弱いものです。アルゴリズムは、任意の時点で、単一のスレッドが（つまり、すべての障害スレッドが中断された状態で）一定数のステップで実行され、その操作が完了する場合、障害フリーであると言えます。[ 15 ]ロックフリーのアルゴリズムはすべて障害フリーです。
障害のない処理を実現するには、部分的に完了した操作を中止し、変更をロールバックできることが求められます。並行処理の支援をなくすことで、検証が容易な、よりシンプルなアルゴリズムを実現できる場合が多くあります。システムが継続的にロック状態になるのを防ぐのが、競合マネージャの役割です。
障害のないアルゴリズムの中には、データ構造内に一対の「整合性マーカー」を使用するものがあります。データ構造を読み取るプロセスは、まず一方の整合性マーカーを読み取り、次に関連データを内部バッファに読み込み、その後もう一方のマーカーを読み取り、最後にマーカーを比較します。2つのマーカーが同一であれば、データは整合していると判断されます。読み取りが別のプロセスによるデータ構造の更新によって中断された場合、マーカーは同一でない可能性があります。このような場合、プロセスは内部バッファ内のデータを破棄し、再度読み取りを試みます。