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

Lock-freeとWait-freeアルゴリズム：並行処理の新たなアプローチ

マルチスレッドプログラミングにおいて、複数のスレッドが共有データに同時にアクセスする際、データの整合性を保つためにロックを使用することが一般的です。しかし、ロックの使用はデッドロックや優先順位の逆転といった問題を引き起こす可能性があり、並行処理の効率を低下させる要因となります。Lock-freeおよびWait-freeアルゴリズムは、ロックを使用せずに複数のスレッドが並行して共有データにアクセスすることを可能にし、これらの問題を回避するための有効なアプローチを提供します。

Lock-freeとWait-freeの概念

Lock-free (ロックフリー)

Lock-freeアルゴリズムは、スレッドがロックを取得せずに共有データにアクセスすることを意味します。このアルゴリズムでは、システム全体が常に進行することを保証します。言い換えれば、あるスレッドが中断された場合でも、他のスレッドが処理を進めることができます。Lock-freeアルゴリズムは、ミューテックスやセマフォといった排他制御のためのプリミティブを使用しません。なぜなら、これらのプリミティブは、ロックを保持しているスレッドの実行が中断した場合、全体の進行を妨げる可能性があるからです。

Wait-free (ウェイトフリー)

Wait-freeアルゴリズムは、さらに強力な保証を提供します。このアルゴリズムでは、あるスレッドが他のスレッドの動作に関係なく、有限のステップ数で処理を完了させることができます。つまり、あるスレッドが中断された場合でも、他のスレッドは影響を受けずに処理を進めることができます。Wait-freeアルゴリズムはLock-freeアルゴリズムの一種であり、より厳しい条件を満たしていると言えます。

Wait-freeなアルゴリズムはLock-freeですが、Lock-freeなアルゴリズムが必ずしもWait-freeであるとは限りません。

Lock-freeとWait-freeアルゴリズムの意義

従来のマルチスレッドプログラミングでは、共有リソースへのアクセス時にロックを使用することが一般的でした。ミューテックスやセマフォなどの排他制御メカニズムは、クリティカルセクションと呼ばれる共有リソースにアクセスする可能性のあるコード領域を複数同時に実行しないようにすることで、データの整合性を維持します。しかし、ロックの取得を待機するスレッドは、スリープやスピンといった手法で待機する必要があり、以下のような問題を引き起こす可能性があります。

スリープによるオーバーヘッド: スリープは、プロセッサを他のスレッドに明け渡すため、システム全体の負荷を下げることができますが、スリープの時間的な精度や復帰時のオーバーヘッドは、オペレーティングシステムやプロセッサに依存します。
スピンロックによる負荷: スピンロックは、スレッドがプロセッサを解放せずに待機するため、システム全体に負荷をかけ続けます。
スレッドの停止: スレッドがブロックされている間は何もできず、優先度の高い処理やリアルタイム処理が停止することは望ましくありません。
デッドロック、ライブロック、優先順位の逆転: 複数のリソースにロックをかけると、これらの問題が発生する可能性があります。
ロックの粒度: ロックの粒度を粗くすると、並列処理の機会が減少し、粒度を細かくすると、バグを生みやすくなるというトレードオフがあります。

Lock-freeおよびWait-freeアルゴリズムは、これらの問題を回避し、より効率的で信頼性の高い並行処理を実現するための手段を提供します。

実装

Lock-freeおよびWait-freeアルゴリズムの実装には、ハードウェアが提供するアトミックなリード・モディファイ・ライト操作が不可欠です。これらの操作は、複数のスレッドが同時に共有メモリにアクセスする際のデータの整合性を保証します。1990年代には、これらのアルゴリズムは、パフォーマンスを最大限に引き出すために、基本的なアトミック操作を用いて「ネイティブ」に実装する必要がありました。しかし、ソフトウェアトランザクショナルメモリの登場により、効率的なLock-freeおよびWait-freeコードを作成するための標準的な抽象化が提供されるようになりました。

基本的なデータ構造

スタック、キュー、セット、ハッシュテーブルなどの基本的なデータ構造のLock-freeおよびWait-free実装に関する研究も活発に行われています。これらのデータ構造は、スレッド間で非同期にデータを交換するための便利な手段を提供します。ただし、すべてのデータ構造が特別なアトミックプリミティブを使用せずに実装できるわけではありません。

シングルリーダー・シングルライターのリングバッファFIFO: メモリバリアのみで安全に実装できます。
Read-copy-update (RCU): 一人のライターと任意の数のリーダーによるRCUは、リーダーが待つことなく読み取りが可能であり、ライターはメモリの再利用が必要になるまでロックフリーです。
複数のライターと任意の数のリーダーによるRCU: リーダーは待つ必要がありませんが、複数のライターは通常ロックでシリアライズされ、obstruction-freeではありません。

Lock-freeのコードは記述が難しい場合があり、多くのライブラリが内部的にLock-free技術を使用しています。

ウェイトフリーダム (Wait-freedom)

ウェイトフリーダムは、最も強力なノンブロッキング進行保証であり、システム全体のスループットと飢餓の防止を保証します。アルゴリズムがウェイトフリーであるとは、すべての操作が完了するまでに実行されるステップ数の上限が存在することを意味します。これはリアルタイムシステムにとって重要であり、可能な限り備えているべき特性です。ただし、Wait-freeアルゴリズムの実装は難しい場合があり、パフォーマンスコストが高くなる可能性もあります。

1980年代に、すべてのアルゴリズムがウェイトフリーで実装可能であることが示されました。しかし、その結果得られるパフォーマンスは、ナイーブなブロッキング設計に劣ることが多かったため、実用化には課題がありました。近年では、ユニバーサルコンストラクションの性能が改善され、より実用的なWait-freeアルゴリズムが登場しています。

Wait-freeアルゴリズムの課題

Wait-freeアルゴリズムを作成する際の難しさは、いくつかの論文で研究されており、特に、広く利用されているアトミックな条件付きプリミティブであるCASやLL/SCでは、多くの一般的なデータ構造に対して、スレッド数に応じてメモリコストが線形に増加することなく、飢餓のない実装を行うことができないことが示されています。しかし、この理論的な限界は、実用的なシステムではあまり問題になりません。

Wait-freeアルゴリズムの進歩

2011年、KoganとPetrankは、一般的なハードウェアで利用可能なCASプリミティブをベースにしたWait-freeキューを発表し、Wait-freeアルゴリズムの研究に大きな進展をもたらしました。さらに、Wait-freeアルゴリズムを高速化するための手法や、ロックフリーなデータ構造からWait-freeなデータ構造を自動的に生成するメカニズムが開発され、Wait-freeの実用性が向上しています。

ロックフリーダム (Lock-freedom)

ロックフリーダムは、個々のスレッドの飢餓を許容する一方で、システム全体のスループットを保証します。アルゴリズムがロックフリーであるとは、プログラムのスレッドを十分に長い時間実行したときに、少なくとも1つのスレッドが処理を進めることを意味します。Wait-freeアルゴリズムはすべてLock-freeですが、その逆は必ずしも真ではありません。

Lock-freeアルゴリズムは、あるスレッドが中断された場合でも、他のスレッドが処理を進めることができるため、ロックを使用した場合と比較して柔軟性が高いという利点があります。

Lock-freeアルゴリズムの動作

Lock-freeアルゴリズムは、一般的に「自身の操作の完了」、「妨害された操作の補助」、「妨害された操作の中止」、「待機」の4つのフェーズで実行されます。コンテンションマネージャーは、いつアシストするか、中止するか、待つかを決定します。このコンテンションマネージャーの設計は、スループットやレイテンシに大きな影響を与えます。

オブストラクション・フリーダム (Obstruction-freedom)

オブストラクション・フリーダムは、最も弱いノンブロッキング進行保証です。アルゴリズムがオブストラクション・フリーであるとは、ある時点で、隔離された状態で実行された単一のスレッドが、有限のステップ数で処理を完了できることを意味します。すべてのLock-freeアルゴリズムはオブストラクション・フリーです。

オブストラクション・フリーアルゴリズムは、部分的に完了した操作を中止し、変更をロールバックするだけで済みます。この単純さにより、アルゴリズムの検証が容易になりますが、システムが継続的にライブロックしないように、コンテンションマネージャーが適切に設計されている必要があります。

Wait-freeなデータ構造の利用

Wait-freeのデータ構造は、マルチスレッド環境で非同期にデータをやり取りする際に非常に便利です。これらのデータ構造を利用することで、Lock-freeやWait-freeのアルゴリズムを自分で実装する必要がなくなり、より安全かつ簡単に並行処理を実装することができます。Java 5以降のjava.util.concurrentパッケージには、Wait-freeなデータ構造のクラスが用意されています。

銀行預金の例

銀行口座への預金処理を例に説明します。ロックを使用する場合、あるATMが預金処理を行う際に、他のATMが同時に預金残高を変更しないようにロックをかける必要があります。Lock-freeなアプローチでは、すべての預金要求を管理するスレッドを作成し、このスレッドがWait-freeキューから預金要求を受け取り、順次処理します。このアプローチでは、ATMはロックを取得することなく預金要求をキューに追加できます。さらに、このアプローチは、Wait-freeキューを使用しているため、Lock-freeであるだけでなく、Wait-freeでもあります。複数の並列処理が必要な場合は、複数のWait-freeキューを作成し、口座番号を分割して対応することができます。

コンペア・アンド・スワップ (CAS)

Lock-freeやWait-freeアルゴリズムの実装には、CPUが提供するアトミック命令が不可欠です。特に重要なのが、コンペア・アンド・スワップ（CAS）です。CASは、メモリアドレス、古い値、新しい値の3つの引数を取り、メモリアドレスに格納されている値が古い値と一致する場合にのみ、新しい値に置き換えます。この操作はアトミックに実行され、他のスレッドの干渉を受けることなく、値の変更が保証されます。

例えば、銀行口座の例で、ATMが現在の残高を読み出し、加算して、CASを使って書き込むというアプローチを考えてみましょう。この3ステップの間に、他のスレッドが残高を書き換えていなければ、CAS操作は成功します。しかし、他のスレッドが残高を書き換えた場合、CASは失敗し、ATMは最初から処理をやり直します。このアプローチはLock-freeですが、Wait-freeではありません。

Wait-Free Synchronization (1993) では、CASがなぜWait-freeにおいて必要かを証明しています。

まとめ

Lock-freeとWait-freeアルゴリズムは、ロックを使用しない並行処理の実現を可能にし、マルチスレッドプログラミングにおけるデッドロックや優先順位の逆転などの問題を回避します。これらのアルゴリズムは、システム全体のパフォーマンスと信頼性を向上させることが期待されます。Wait-freeなデータ構造を活用することで、より安全かつ効率的に並行処理を実装することができます。CASのようなアトミックなプリミティブは、これらのアルゴリズムの実装に不可欠な要素です。

外部リンク

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

もう一度検索