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

@Cryolite

"lock-free" という言葉が登場するたびに，「"lock-free" って何ですか？」と質問するだけの簡単なお仕事．

@kumagi

@Cryolite 「スタッドレススパイクタイヤ」の略称が「スタッドレス」でなんのこっちゃな物体になってるのに近いものを感じますよね＞lock-free

@Cryolite

@kumagi いえ， "lock-free" という言葉自体は，並列プログラミングの文脈で単独で登場した場合にはそれなりにちゃんとした定義のある terminology として使われていることを仮定できるんじゃないですかね．

くまぎ @kumagi

@Cryolite あー、はい。そうですね。そういう論文の中では既に定義のある用語のひとつとして使われています。obstruction-freeとの境目は意見が分かれるかも知れませんが目的に関しては共通の認識があると感じます。

Akso de la Malbono @Cryolite

@kumagi ありゃ？ あまり詳しくないのであれなんですが， lock-free と obstruction-free ってわりと明確に違いませんか？ 2つのスレッドを仮定した場合， 1つのスレッドがどの状況で停止してももう片方が progress を維持するのが後者ですよね？

Akso de la Malbono @Cryolite

@kumagi そういう (obstruction-free な) ものの中で，例えば特定の scheduling 下で全体の progress がないものを設計すれば，「obstruction-free だが lock-free ではない」になるので，この2つはわりと明確な気が

Akso de la Malbono @Cryolite

obstruction-free だけれど lock-free ではないものって実際に構成可能なのかな？ 練習問題として面白そうだから暇なときに実際にやってみようっと．

くまぎ @kumagi

@Cryolite な、なるほど。僕の勉強不足だったようです。ありがとうございます。

Akso de la Malbono @Cryolite

いかなる (どんな支離滅裂な) scheduling 下でもある1つのスレッドの progress が保証出来る (言い換えると，全体としての progress は保証出来る) のが lock-free で，

Akso de la Malbono @Cryolite

このうちの極端な scheduling の例，つまりたった1つのスレッドだけを走らせる scheduling において progress を保証出来るのが obstruction-free，従って「lock-free ⇒ obstruction-free」は自明，という理解．

くまぎ @kumagi

そうしてSTMまで作っちゃいそうなのが恐ろしい… QT @Cryolite obstruction-free だけれど lock-free ではないものって実際に構成可能なのかな？ 練習問題として面白そうだから暇なときに実際にやってみようっと．

Akso de la Malbono @Cryolite

"lock-free" の説明として「相互排他を使わない」としか言っていなかったり，あるいは lock-free の利点の説明として「重い相互排他を使わないから」としか言っていなかったりしている場面をちょこちょこ目にして，自分の理解が正しいのかしばしば不安になる．

Akso de la Malbono @Cryolite

自分の理解では，「mutex (critical section) を使うと lock-free ではない」は真だと思うけれど，一方で例えば CAS だけを使っても lock-free でないものを構成することはいくらだって可能なはずなので，

Akso de la Malbono @Cryolite

「lock-free とは mutex (critical section) を使わないことです」という説明では不足するはず．多分，説明端折っているだけか，あるいは独自の "lock-free" の定義について説明しているだけだろうけれど．

若年寄(もう若くない) @kikairoya

これはC(ry先生がlock-freeについてアツく語る流れかにゃー

Akso de la Malbono @Cryolite

あと， lock-free の利点としては「mutex の lock, unlock (critical section の入出) 自体のコストが重く (定量的に計測したこと無いので伝聞だけれど) ，これを避ける」だけじゃなくて，

でちまるさん（実際かわいい） @decimalbloat

rockman-three アルゴリズム

Akso de la Malbono @Cryolite

mutex (critical section) を使うと，あるスレッドが critical section 内で停止したときに，その停止が block されている全てのスレッドが停止することに等しい，ということのコストも非常に大きいはず．

Akso de la Malbono @Cryolite

スレッドが停止した場合云々と言うのは，別にシステムの堅牢性だけの話ではなくて，現代的なアーキテクチャ・OS 上ではスレッドは cache miss, page fault, preemption その他の予測困難な原因・タイミングで「停止」するので，

Akso de la Malbono @Cryolite

mutex (critical section) を用いるというのは，ある1つのスレッド上のこういったコストリスクを全スレッドで共有するということを意味し， lock-freedom はこれを回避するという意義があるはず．

Akso de la Malbono @Cryolite

分かっている人には別に説明を端折っても良いとは思うのだけれど， lock-freedom という概念に慣れていない人に「重い mutex (critical section) を使わない」という説明だけをしても，この種の lock-free の意義はまったく伝わらないはず．

やまさ @yamasa

見てる： Togetter - 「lock-freeとobstruction-freeの違い」 http://togetter.com/li/36803

やまさ @yamasa

Lock-freedom と Wait-freedom の違いがわかりません！助けてC(ry先生！！＞＜

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

@yamasa http://twitter.com/mskwt/status/19051113708

Akso de la Malbono @Cryolite

@yamasa スレッド A, B, C があったときに，どれでも良いのでとにかく1つのスレッドが操作を完了するのが lock-free で，lock-free は「ある特定のスレッド (例えば A) にだけ着目したらそいつは永遠に操作を完了できずにいる」みたいなのは許されます．