Lock-freeとWait-freeアルゴリズム Lock-freeとWait-freeアルゴリズムの概要

ウィキペディア

Lock-freeとWait-freeアルゴリズム

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/12/20 18:32 UTC 版)

意義

マルチスレッドプログラミングにおいて古典的な手法は、共有リソースにアクセスするときはロックをかけることである。ミューテックスやセマフォといった排他制御は、ソースコードにおいて共有リソースにアクセスする可能性のある領域（クリティカルセクション）を複数同時に実行しないようにすることで、共有メモリの構造を破壊しないようにする。もし、スレッドAが事前に獲得したロックを別のスレッドBが獲得しようとするときは、ロックが解放されるまでスレッドBの動作は停止する。

ロックの解放を待機するスレッドは、スリープやスピンといった手法で待機する。スリープ中はプロセッサを他のスレッドに空け渡すため、システム全体の負荷が下がるが、スリープの時間的な精度や分解能はオペレーティングシステムやプロセッサによって異なることがあり、またスリープから復帰する際に時間的オーバーヘッドが発生する。一方スピンによる待機（スピンロック）中は、スレッドはプロセッサを解放せず、システム全体に負荷をかけたままになる。

スレッドが停止することは多くの理由で望ましくない。まず、スレッドがブロックされている間は、そのスレッドは何もできない。そして、スレッドが優先順位の高い処理やリアルタイム処理を行っているならば、そのスレッドを停止することは望ましくない。また、複数のリソースにロックをかけることは、デッドロック、ライブロック、優先順位の逆転を起こすことがある。さらに、ロックを使うには、並列処理の機会を減らす粒度の粗い（すなわちクリティカルセクションが広い）ロックを選択するか、バグを生みやすく注意して設計しないといけない粒度の細かいロックを選択するかというトレードオフ問題を生む。

実装

一部の例外を除き、ノンブロッキング・アルゴリズムでは、ハードウェアが提供しなければならないアトミックなリード・モディファイ・ライトのプリミティブを使用している。クリティカルセクションは、ほとんどの場合、これらのプリミティブに対する標準的なインターフェースを使って実装されている（一般的なケースでは、これらのプリミティブを使って実装されていても、クリティカルセクションはブロック化される）。1990年代には、すべてのノンブロッキングアルゴリズムは、許容できる性能を得るために、基本的なプリミティブを用いて「ネイティブ」に記述する必要があった。しかしソフトウェア・トランザクショナル・メモリでは、効率的なノンブロッキング・コードを書くための標準的な抽象化が約束されている^[1][2]。

またスタック、キュー、セット、ハッシュテーブルなどの基本的なデータ構造の提供についても多くの研究がなされている。これらは、プログラムが非同期にスレッド間で簡単にデータを交換することを可能にする。

ノンブロッキングデータ構造の中には、特別なアトミックプリミティブを使用しなくても実装できるほど「弱い」ものもある。このような例外は以下の通りである。

• シングルリーダー・シングルライターのリングバッファFIFOは、利用可能な符号なし整数型のオーバーフローを均等に分割するサイズであれば、無条件にメモリバリアのみで安全に実装することができる。
• 一人のライターと任意の数のリーダーによる Read-copy-update。（リーダーは待ち時間がなく、ライターは通常、メモリの再利用が必要になるまでロックフリーである）
• 複数のライターと任意の数のリーダーによる Read-copy-update。（リーダーは待ち時間なし。複数のライターは一般的にロック付きでシリアル化され obstruction-free ではない）

いくつかのライブラリが内部的にロックフリー技術を使用しているが^[3][4][5]、正しくロックフリーのコードを書くことは困難である^[6][7][8][9] 。

ウェイトフリーダム（Wait-freedom）

Wait-freedom（ウェイトフリーダム）は、システム全体のスループット保証とスタベーション防止を組み合わせた、最強のノンブロッキング進行保証である。アルゴリズムはすべての操作に、その操作が完了するまでにアルゴリズムが取るステップ数の制限がある場合、ウェイトフリーとなる^[10]。この特性は、リアルタイムシステムにとって重要であり、性能コストが高すぎない限り、常にあった方が良いものである。

1980年代には、すべてのアルゴリズムがウェイトフリーで実装できることが示され、ユニバーサルコンストラクションと呼ばれるシリアルコードからの変換が数多く実証されている^[11]。しかし結果として得られる性能は、一般的にはナイーブなブロッキング設計にさえも及ばない。その後、いくつかの論文でユニバーサルコンストラクションの性能が改善されたが、それでも性能はブロッキングデザインを大きく下回っている。

ウェイトフリーなアルゴリズムを作ることの難しさについては、いくつかの論文で研究されている。例えば、広く利用されているアトミックな条件付きプリミティブであるCASやLL/SCでは、多くの一般的なデータ構造に対して、スレッド数に応じてメモリコストが線形に増加することなく、スタベーションのない実装を行うことができないことが示されている^[12]。

しかし実際には、この下限値は実際の障害にはならない。というのもスレッドごとに共有メモリにキャッシュラインや排他的予約グラニュール（ARMでは最大2KB）を使ってストアを行うことは、実用的なシステムではコストがかかりすぎるとは考えられていないからである。

ウェイトフリーなアルゴリズムは、2011年までは研究でも実践でも稀だった。しかし2011年、KoganとPetrank^[13]は、一般的なハードウェアで一般的に利用可能なCASプリミティブをベースにしたウェイトフリーキューを発表した。彼らの構築は、実際によく使われる効率的なキューであるMichaelとScott^[14]のロックフリーキューを拡張したものである。KoganとPetrankによる後続の論文では、ウェイトフリーのアルゴリズムを高速化するための手法を提供し、この手法を用いてウェイトフリーキューを実質的にロックフリーのものと同程度に高速化した。続くTimnat and Petrankの論文では、ロックフリーのデータ構造からウェイトフリーのデータ構造を自動的に生成するメカニズムを提供した。このようにして、現在では多くのデータ構造でウェイトフリーな実装が可能となっている。