ロックフリー性の証明について

http://www.slideshare.net/kumagi/lock-free-safe?next_slideshow=1

とか過去に自分で書いておきながら、その当時の自分の認識が甘かった事もあるのでここに一度書き出しておく。

Lock-Freeは「ロックを使わない事」ではない

STMの事をもってしてLock-Freeと呼んでる文脈はいっぱいあるけれど、STMの実装にロックを使う事は一般的だし、それは正しい専門用語で言う所のLock-Freeとは呼ばない。

Lock-Freeとは「どんなスケジューリングが為されようともどれかの操作が進行する」という進行保証(Progress Guarantee)を表している。

スケジューリング？

マルチコアCPUでもシングルコアCPUでも、OSは実行中のプログラムを任意のタイミングで強制的に一時停止させて他のプログラムにCPUリソースを割り当てる事ができる*1。実行中スレッドからのOSによるCPUの引き剥がし・割り付けの事を並行プログラムの世界ではスケジューリングと呼ぶ。
シングルCPUコアの環境でついうっかりC言語あたりで無限ループを記述してもkillできるのはこの仕組みのお陰である。

普通の排他ロックは悪意あるスケジューリングに対して無力

悪意あるスケジューリング、という状況は世の中には普通無いが、最悪の場合を想定してシステムが満たす特性の下限を保証する必要がある状況というのはある*2。
例えばあるスレッドが共有資源に対する排他ロックXを獲得した後にOSがそのスレッドを強制的に一時停止させて、他のプログラムやスレッドだけにCPUリソースを割り当て続けた場合、他のスレッドは何兆クロックのCPUサイクルを与えられようが排他ロックXが確保されたままの資源にアクセスしてはならないので、利用可能なCPUサイクル全てをドブに捨てる事になる。これを専門用語でブロッキングと呼ぶ。

悪意あるスケジューリングに対して耐性のあるロックの使い方例

他のスレッドが排他ロックを獲得したままであってもプログラムを進行させる使い方はありうる。
try_lock()を用いて「ロックを取ろうとは試みるけど、ロックが取れなかったら別の手段を講じる」というパターンはブロッキングが発生しないのでLock-Freeと呼べる事がある、ロックを利用しているにも関わらず、だ。典型的にはがちゃぴん先生のmallocの話がそれに該当するアルゴリズムの一例。

Lock-Freeの進行保証について

スケジューラの立場からLock-Freeというのを解釈し直すと「どんなスケジューリングを行っても絶対に進行してしまう」アルゴリズムであって、Lock-Freeであることを証明するためには「考えうる限り最悪のスケジューリングを行った場合に、アルゴリズム側が何らかの操作を実現するまでに必要なクロック数の上限が無限でない」という事を示せば良い。

例えばシンプルなLock-Free Stackの場合、

• t個のスレッドで実行している
• スケジューラはpushã‚‚popã‚‚1つでも実行させないよう最悪ケースのスケジュールを行おうとする

という状況にて

1. headポインタのアドレスPを読むのにaクロック(有限)
2. mallocにbクロック(有限)
3. mallocしたメモリ領域Qk*3に必要なデータを書き込むのにcクロック(有限)
4. P→QkのCASを試みるのにdクロック(有限)
5. スケジューラはCASを失敗させたいのでCAS実行の直前で他のスレッドにCPU時間を割り当てる
6. ↑の1〜5の動作をt個のスレッド全部の分繰り返す
7. スケジューラはどのスレッドにCPU時間を割り当ててもP→QkのCASを実行しようとしているスレッドばかり
8. t個のスレッドのうちどれかが必ずCAS成功する。スケジューラは t * (a + b + c + d)クロックで投了
9. t * (a + b + c + d)は有限なのでこのアルゴリズムには進行保証がある

というようにLock-Free性(=進行保証)を証明できる。

Wait-Freeに関してはまた気が向いたら書く。

*1:当然OSのレベルでプリエンプティブな機能を実現している場合だが、WindowsもLinuxもMacOSもいまどきのOSはデフォルトでは大抵これを実装している。スパコンだとこの機能のオーバーヘッドを気にしてノンプリエンプティブなOSを利用する場合もあるらしいが詳しくない

*2:銀行のシステムだと全ての操作がキャッシュミスした場合を想定してそこでも性能がちゃんと出るように血を吐くような努力をしていると聞いたことがある

*3:kはそのスレッド固有の数字