lock-freeとobstruction-freeとwait-freeの違い

Akso de la Malbono @Cryolite

@yamasa wait-free は A, B, C どのスレッドに着目したとしても，そのスレッドは有限回のステップで操作を完了する，という感じかと．なので「wait-free ならば lock-free である」は当然成り立ちます．

やまさ @yamasa

@mskwt あ、その記事は読んでるんですが、具体的なコードが与えられたときにそれが wait-free なのかただの lock-free なのか判別する方法がピンとこないんですよねえ。

野良猫＠がんばらない @mskwt

since 2003, the term has been weakened to only prevent progress-blocking interactions with a preemptive scheduler. とか言ってる時点で、もう…

やまさ @yamasa

@Cryolite その定義だと、ちょっと納得がいかないんですよ。たとえば、wait-freeなアルゴリズムの代表例として挙げられる http://j.mp/ay0hxU ですが、スレッド数が無限個だとすると有限回で終わらないスレッドがあり得ると思うんですよ。

やまさ @yamasa

@Cryolite 一方、スレッド数は有限だとすると、lock-freeの定義の「少なくとも一つのスレッドは有限回のステップで終了する」ってのを繰り返し適用すれば、最終的に全てのスレッドが有限回のステップで終了するんじゃないかと。

Akso de la Malbono @Cryolite

@yamasa 自分の足りていない理解では， wait-free, lock-free というのは「いかなる不当な scheduling の下で，かつスレッド間の速度差がどうであっても，かつスレッドの速度変化がどうあっても」というかなり厳しい条件下での成立を要求するので，

Akso de la Malbono @Cryolite

@yamasa 自分が仮に万物を支配していて，ある特定のスレッドだけを徹底的に不当に扱うように振舞うのだと想像すれば， lock-free だけれど wait-free じゃない，という状況は作れそうな気がします．

野良猫＠がんばらない @mskwt

CAS とか使うと CSいらなくね？ -> Non-blocking Algo(r を lock-free と呼ぼう！ -> いや待て CSなくても Spin したら意味なくね -> そのアルゴ（ｒ によって他のスレッドを巻き添えにしないって定義で ←いまここ

野良猫＠がんばらない @mskwt

lock-free でも loop している箇所があったら以下略で、終わらないので以下略。はいはい

Akso de la Malbono @Cryolite

自分が scheduling やらスレッド間の速度差やらスレッドの速度変化を自在に操れる幻想御手だとして，ある特定のスレッドの progress だけは絶対に許さないように adversary (adversary argument の意味で) として振舞えば……．

やまさ @yamasa

@Cryolite うーん、スケジューリングの偏りなどによって処理が進まないってのは livelock の例があるのでわかるんですよ。でも、Wikipediaによると livelock の可能性があるのが Obstruction-free で、可能性が無いのが Lock-free

野良猫＠がんばらない @mskwt

live-lock 怖いし、bus contention ひどいし、公平性を担保できないあたり、相当短期間か楽観的(略) でないと…

やまさ @yamasa

@Cryolite ということなので、「livelockが起こらず、少なくとも一つのスレッドが有限回で終わることが保証されている」のに「全てのスレッドが有限回で終わる保証は無い」というのは、どうしてもピンとこないんですよねえ。

野良猫＠がんばらない @mskwt

「このアルゴリズムでは T1, T2, ..., Tn が実行可能状態を保てる！だが停止性の保証はない！」「…お前のプロセス bus contention 激しいからさっさと Lock escalation して OS に調停してもらえよ」

Akso de la Malbono @Cryolite

俺の The Art of Multiprocessor Programming が火を噴くぜ！俺は口から泡を吹くがな！ガハハハハ！

やまさ @yamasa

@Cryolite そうやって特定のスレッドに対して極端に不利なスケジューリングをしたとしても、それ以外のスレッドが順次有限回のステップで終了していくはずなので、最終的にはそのスレッド一つだけになっちゃいますよね。

Akso de la Malbono @Cryolite

@yamasa 自分も同様に悩みましたが、結果、例えば関数が lock-free / wait-free だと言った時には、 progress のあった（つまり関数を出た）スレッドが有限ステップで対象の関数に再入することをも許した上での議論ではないかという理解になりました。

やまさ @yamasa

@Cryolite 再入もあり、とした場合、一般的に wait-free と呼ばれている http://j.mp/ay0hxU についても、有限ステップで終わらないスレッドが考えられると思うんですよねえ…

Akso de la Malbono @Cryolite

@yamasa ただこれは全く自信のない理解なので、もう一度一次ソースをひっくり返してきます。

野良猫＠がんばらない @mskwt

@Cryolite 先生が、http://j.mp/ay0hxU について分類を行ってもらえると理解しやすいです。。

野良猫＠がんばらない @mskwt

"Non-Blocking" and "Blocking" "Concurrent" って罠すぎる題名…

くまぎ @kumagi

@mskwt pseudo codeを読む限りはhttp://github.com/kumagi/lockfree/blob/master/queue.hpp と同じqueueに見えます。

野良猫＠がんばらない @mskwt

@kumagi これは wait-free, lock-free, obstruction-free のどの領域に属しますかっ

くまぎ @kumagi

@mskwt 運悪くcasが失敗し続ける事がありうるのでwait-freeの条件だけ満たさないと思います。知ってる中でwait-freeの条件を満たすアルゴリズムって数える程も無いような…。

くまぎ @kumagi

@mskwt queueは読み出すと同時に破壊するのが普通のオブジェクトなのでRCUやModifiedFlagを組み合わせる魅力がよくわかりません。DCASに関しても「DCAS有るなら作るの簡単だけど無いからどうにかしなきゃ」でこのqueueとかが発明されてるので…。