ウェイトフリー性の証明について
気が向いたら書くと言ってしまったので忘れないうちに書く。
飢餓状態とは
- スレッドAが操作xを試みる
- スレッドBが操作yを試みる
- スレッドCが操作zを試みる
という状況の時に、このアルゴリズムがLock-Freeである場合。すなわちスケジューラがどうスケジュールしても少なくともどれか1つのスレッドの操作が成功してしまう事が避けられない場合であってもスケジューラは特定のスレッドの操作だけを意図的に妨害する事は可能であることが多い。
例えば前回の記事のLock-Free Stackを例に話すと
- スレッドAがCAS（α→β）を試みようとする
- スケジューラがスレッドBのCASが成功するようスケジューリング
- 1〜2を繰り返し
こうすれば理論上スケジューラはスレッドAに無限クロックのCPUを食わせながらも、無限にスレッドAのCASを成功させない事が可能だ。
このような状況の事をStarvation(飢餓状態)と呼ぶ。
スケジューラが意図的に最悪のスケジューリングをしてくる環境下において「アルゴリズムが進行する」ことは必ずしも「全てのスレッドの1タスクが有限時間に終わる」事を意味しない*1。
この飢餓状態が起きない、つまりスケジューラがどうあがいても有限のクロック数で全てのスレッドが目的を達成できる。という条件を満たす場合そのアルゴリズムはWait-Freeと呼ばれる。
有限時間とはいえ、待つ事に変わりは無いのだからWait-Freeという名前は変だなと思っていたら 1974年のLamportの論文が初めてこのWait-Freeという言葉を使ったとTAoMP本に書いてあった。Lamport先生がそう言うんだから仕方ない。
ちなみに、有限のクロックで操作が完了できれば良いのだから「ただ単にメモリの値を読む」とか「ダイクストラ法で最小コストのパスを探す」「クイックソート」とかのシングルスレッドで解決できる問題をシングルスレッドで普通に書いている分にはそれはWait-Freeに分類される。
飢餓状態の回避方法
並行でWait-Freeで線形化可能*2なデータ構造の一般的な作り方というのはよく知られている。
universal constructionなどと呼ばれ、2010年のこの論文が手頃であるがもちろん読む必要はない*3。
その一つの方法は簡単に言うとAnnounce Arrayという配列を用意して運用することである。
配列はスレッド数と同じだけの長さがあり、全てのスレッドは何かを操作する前に操作したい内容をその配列中の自分に割り当てられた場所に記述する。
全てのスレッドは自分の操作を実行する前にこの配列全体を調べ、既に自分以外のスレッドが操作を開始している場合にはそいつの操作を手伝う。
この手伝うというのが厄介で、自分自身の実行しようとした操作と全く同一の操作が自分以外のスレッドに1クロック前に達成されてしまう場合などもあるのでコードが非常に複雑になる。
詳しくは僕の魔導書に書かれたWait-Free Stackや、Wait-FreeなKP-Queueの論文あたりを読んでみると良い。
操作内容を書き込む歳にデータ構造の論理クロック*4を一緒に添えて置く事で、どの操作が最初に登録されたのか比較できるので、より古いものから優先的に実行できる。
証明の形
そうやって作ったWait-Freeな操作と、先ほどの「スレッド1の操作が未来永劫実行されなくなるよう配慮するがスレッド1にもCPU時間を割り当てないといけないスケジューラ」が対立した場合*5の最大動作クロックの1例は以下である。
- スレッドはn本走っている
- 操作は邪魔されなければkクロックで済むものとする
- スレッド1が操作xを行いたいとAnnounce Arrayに書き込む。aクロックかかる。この時の論理クロックはt。
- スレッド1の他にスレッド2からスレッドnの全スレッドがAnnounce Arrayに操作(論理クロックt未満)を書き込んでいるので先にそれらを手伝う。(n-1) * kクロックかかる。
- スレッド1が自分の操作xを実行しようとしたがスケジューラはそれを止めて他のスレッドに割り当てる。
- スレッドpが何か操作を行おうとしたが、スレッド1よりあとに開始したので論理クロックはt+1以上であり、Announce Arrayに操作x(論理クロックt)が先に入っているのを発見するのでそちらを手伝う事になる。aクロックかかる。
- 操作xが行われてしまうとスケジューラはスレッド1を足止めできた事にならないので、操作xを行おうとしたスレッドpも止める
- 上記4と5をn-1スレッド分繰り返す
- スケジューラはどのスレッドにCPUを割り当てても操作xが実行される事を見届けなくてはならなくなるので、どう転んでも操作x（=スレッド1）が進行する。結果として合計(n-1)*k + n * aクロック消費してスケジューラは投了。
- (n-1)*k + n * aは無限ではないので、このアルゴリズムはWait-Freeの条件を満たす
という証明をする。
発展的話題
個人的にはKP-Queueの次の年にでた論文、A methodology for creating fast wait-free data structuresが中々好きである。これは上記アルゴリズムを改造して、常時はLock-Freeなデータ構造の様に動かすが予め設定した上限に達しそうになったらWait-Freeに切り替えるという方法。上記アルゴリズムなら他スレッドがAnnounce Array内に居たら即手伝っていたが、こちらは各スレッドがローカルなカウンタを持っていて、予め設定した回数mに至るまではAnnounce Arrayにスレッドが居ても無視するという方法である。更に、自分がLock-Free的にトライした操作がk回失敗続きの場合にやっとAnnounce Arrayにデータを登録し始める、という方法を採用している。これによって各スレッドの操作完了までの最悪時間は「最初にk回Lock-Free的にトライするクロック数」や「他の全てのスレッドにm回見逃されるクロック数」を加算することになるのでクロック上限値が大きくなってしまうが有限の範囲なので依然としてWait-Freeの条件を満たしつつ、実測上Lock-Freeデータ構造に逼迫する性能が出る。という結果が出ている論文である。ここまでしてWait-Freeを実現する意義がいまいちな所も良い。
