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

Lock-freeとWait-freeアルゴリズムとは、共有データにロックをかけてアクセスを防ぐアルゴリズムとは違い、複数のスレッドが同時並行的に、ある対象データを壊すことなしに読み書きすることを可能にするアルゴリズムである。Lock-free とはスレッドがロックしないことを意味しており、全てのステップにおいてシステムが必ず進行する。これはLock-free ではミューテックスやセマフォといった、排他制御のためのプリミティブを使ってはならないことを意味する。なぜならロックを持っているスレッドの実行が中断した場合、全体の進行を阻止しうるからである。Wait-free とは、他のスレッドの動作に関係なく、スレッドがいかなる操作も有限のステップで操作を完了させられることを指す。あるアルゴリズムがLock-freeであるがWait-freeでないことはありうる。Wait-free なアルゴリズムは Lock-free である。

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

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

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

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

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

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

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

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

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の論文では、ロックフリーのデータ構造からウェイトフリーのデータ構造を自動的に生成するメカニズムを提供した。このようにして、現在では多くのデータ構造でウェイトフリーな実装が可能となっている。

ロックフリーは、個々のスレッドがスターブする（飢える）ことを許容するが、システム全体のスループットを保証する。アルゴリズムがロックフリーであるとは、プログラムのスレッドを十分に長い時間実行したときに、少なくとも1つのスレッドが進歩することを意味する（進歩の定義が適切である場合）。待ち時間のないアルゴリズムはすべてロックフリーである。

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

あるプロセッサによる無限回の操作が、有限回のステップで成功する場合、アルゴリズムはロックフリーとなる。例えばN個のプロセッサがある操作を実行しようとしている場合、N個のプロセスのうち、あるものは有限のステップ数で操作を終えることに成功し、他のものは失敗して失敗時に再試行する可能性がある。wait-freeとlock-freeの違いは、各プロセスによるwait-free操作は、他のプロセッサに関係なく、有限ステップで成功することが保証されている点である。

一般的にロックフリーのアルゴリズムは「自分の操作の完了」「妨害された操作の補助」「妨害された操作の中止」「待機」の4つのフェーズで実行できる。自身の操作の完了は、補助と中止が同時に発生する可能性があるため複雑になるが、常に完了までの最速の道のりである。

障害が発生したときに、いつアシストするか、中止するか、待つかを決めるのは、コンテンションマネージャーの責任である。これは非常に単純なもの（優先度の高い操作を支援し、優先度の低い操作を中止する）もあれば、より最適化してスループットを向上させたり、優先度の高い操作のレイテンシを下げたりするものもある。

正しいコンカレントアシスタンスは、一般的にロックフリーアルゴリズムの中で最も複雑な部分であり、実行するのに非常にコストがかかることが多い。アシストするスレッドが遅くなるだけでなく、共有メモリの仕組みのおかげで、アシストされるスレッドがまだ実行されている場合、そのスレッドも遅くなる。

オブストラクション・フリーダムは、最も弱い自然なノンブロッキング進行保証である。アルゴリズムは、ある時点で、隔離された状態で（つまり、障害となるスレッドをすべて停止させた状態で）、制限されたステップ数だけ実行された単一のスレッドがその処理を完了する場合、オブストラクションフリーと言える^[10]。すべてのロックフリー・アルゴリズムはオブストラクションフリーである。

オブストラクションフリーの条件は、部分的に完了した操作を中止し、加えられた変更をロールバックできることだけである。並行支援をやめれば、アルゴリズムがよりシンプルになり、検証も容易となる。システムが継続的にライブロックしないようにすることは、コンテンションマネージャの仕事である。

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

Wait-free のデータ構造を使ったプログラムを書くには、ミューテックスを使って書いてあるアルゴリズムを Wait-free のアルゴリズムに書き直すよりも、Wait-free のデータ構造の研究者が書いたスタック、キュー、セット、マップを使った方が望ましい。例えば、Java 5以降では、java.util.concurrentパッケージに Wait-free のデータ構造のクラスが入っている。Wait-free のデータ構造を使うことで、スレッド間で非同期にデータをやりとりするプログラムが書きやすくなる。

例えば、銀行口座への預金プログラムを作るとする。それぞれのスレッドをATMとする。預金預け入れをするには、現在の預金残高を読み出し、預入金額を足し算し、新しい預金残高を書き込むという処理が必要である。ロック方式のやり方の場合、1つ目のATMが預金をするとき、ほかのATMが同時に預金残高を変更しないよう、ロックをかける。さもないと、同時に処理してしまうと、最終的な預金残高に不整合が起きうる。この処理を Lock-free にするには、すべての預入要求を管理するスレッドを作り、そこに、Wait-free のキューを作り、ATMはそのキューに対して非同期にロックをかけることなく預入要求を入れ、預入要求を管理するスレッドはキューから順次取り出し、預金残高を更新する。このやり方の方が、わざわざ Lock-free の預金アルゴリズムを作るよりも、プログラミングは楽である。さらに、この手法は、キューがWait-freeであるので、Lock-free なだけでなく、Wait-freeでもある。預金残高の書き換え処理をn並列で行いたいなら、n個Wait-freeキューを作り、口座番号をnで割った余りでどのキューに入れるか決めるという方法で対応できる。

Lock-free や Wait-free アルゴリズムを作るには、CPUが専用のアトミックな命令を提供し、それを使う必要がある。最も重要なのは、コンペア・アンド・スワップ（Compare and Swap, CASと省略する）である。Java では、java.util.concurrent.atomicパッケージ内のクラスに、compareAndSetメソッドとして存在する。これは、メモリアドレス、古い値、新しい値の3つを使う。もし、メモリアドレスに保存したある値が、指定された古い値ならば、それを新しい値に置き換え、そうでない場合は、何もしない。そして、この処理が成功したかどうかをプログラムに返す。CPUはこれをアトミックに実装する必要がある。現在^[いつ?]のIntelプロセッサにはこの機能がある。この機能は、メモリからデータを読み出し、変更し、書き戻すという処理を、他のスレッドがその間に同時に変更を行っていない場合にのみ行う、というアルゴリズムを可能にする。

例えば、先ほどの銀行口座の例で、別なアルゴリズムを見てみる。ATMは現在の値を読み出し、加算し、書き込む、という3ステップにおいて、3ステップ目をコンペア・アンド・スワップを使って行う。この3ステップの間に他のスレッドが値を書き換えなければ、3ステップ目のコンペア・アンド・スワップは成功する。しかし、この3ステップにおいて預金処理が同時並行で起これば、1ステップ目の読み出した金額と、3ステップ目の書き込みで「比較して交換」を使って読んだ金額が一致しないため、失敗し、ATMは1ステップ目からやり直す。全てのATMは成功するまでこの3ステップを繰り返す。このアルゴリズムは Lock-free ではあるが、Wait-free ではない。なぜなら、他のATMが預金することにより、自分のATMが何度も挑戦する必要があるからである。

Wait-Free Synchronization (1993) では、コンペア・アンド・スワップがなぜ、Wait-freeにおいて必要か証明している。

• ABA問題
• リード・コピー・アップデート
• 線形化可能性
• 一貫性モデル

• Atomic Ptr Plus Project lock-freeアルゴリズムに関する特許について
• http://www.audiomulch.com/~rossb/code/lockfree/