obstruction-free

wait-free/lock-free/obstruction-freeの定義について

▲全てに共通する概念
スレッドが他のスレッドの進行を禁止する事がないので、どれかのスレッドが
ロックを確保したままプリエンプションなどで全体の処理が停止する事態が発生しな
い。
これは必ずしもロックベースのアルゴリズムより高速であることを意味し
ない（現にロックの方が早い場合もある

wait-freeが一番強い条件で、それを弱める度に
lock-free,obstruction-freeと変化する。

☆ぶっちゃけどういうこと
ビーチフラッグに例えます。砂浜に寝そべってダッシュで旗を奪い合うアレで
す。

wait-free:整理券を発行して旗に触れる順番待ちを制御してくれてる。もはや
競技にもならないけど、二度目に旗に触れる人は整理券をもらうところからや
り直しなので、並べばいつかは自分の番がくる。
もしくは数万人でビーチフラッグしても勝ち抜け制なら最後には自分ひとりの
ビーチフラッグになって勝てるよね

lock-free:普通のビーチフラッグ。毎回必ず誰か一人が勝者になる、でもそれ
だからといっていつかは自分が勝てる、というわけでもない。数万人でビー
チフラッグしても誰かは勝つけど数万回やって自分が勝てるかどうかは謎だよね。

obstruction-free:勝った人が抜けないどころか、ところどころに「触ると旗
が爆発する機雷」が埋まっていたりして、レースそのものが台無しになることも
ある。その場合は仕切り直すので「勝者無きレース」になってしまう。
単体スレッドで走る時はその機雷は絶対回避できるんだけど、複数スレッドが
旗を取り合って押し合いへし合いしてるうちに機雷に触れちゃうんです。


lock:砂浜の途中に早押しスイッチがあって、押すとそれを押した人以外が入れない
バリアが旗の周りに展開される。そのバリア内で砂に足を取られたり（キャッシュミスヒット）
UFOにちょっとさらわれたり(OSによるプリエンプション)何らかの要因で足止めされると
バリアの外で待ってる全員が無益な待機をする羽目になる。これを「潜在的に進行可能」
という。実際には無益な待機が多少有ってもスループットの高い場面があるので変に
悪手扱いしたものでもない。


…冗長で中途半端な説明が増えただけとも言えますびくんびくん