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

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の場合、