obstruction-free

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

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

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

▲wait-freeとは
全ての処理が有限ステップで終わる物。と定義。走っているスレッド数には影
響されないけど、物理コア数には影響される。CASとか抜きにして100個のコ
アが同一のアドレスにデータをストアしようとした場合、自分以外の99コアが
書き込むのを待たなくてはいけない事は確定なので、その時点で「wait」して
は居るけれど、「最大99コア」という事は明示できるのでこの操作は
wait-freeに分類される。

▲wait-freeとlock-freeの違い
スレッドの追い越しを保証するかどうかが最大の違い。
実際のlock-freeアルゴリズムの実装を見ると「多少の競合があってもすぐ終わ
るのでwait-freeではないか」という声を聞くこともあるけど、重要なのは
「最悪の場合での計算量」であって、リアルタイムシステムではそこを保証す
ることがリアルタイムであるために大事、という事になっていたりする。
例えば同一のアドレスに100コアぐらいのCPUが同時に書き込もうとした場合当
然取り合いになるんだけど、CPUは「後から来た奴は後に書き込む」スケジュー
リングをしてくれている前提で話をするので、「全部のCPUが断続的に書き込
みを行い続けても、先行したCPUが次に行う同一アドレスへの書き込みは必ず
自分より後にスケジューリングされる事は確定なので少なくとも99コアが書き
込む時間だけ待てば絶対書き込みが終わる」事は保証できる。これを
wait-freeと言う。実際のCPUの実装がどうなっているかは分からないけどそう
いう前提がないとただの代入文ですらlock-free以下にしかなれないのでそういう
事にしましょう、とlock-freeの提唱者であるMaulice先生(？)が定義した。
「ひょっとしたら最大20コアにまでは追い抜かれるかも…」という場合でも最
悪計算量は保証できるのでwait-freeに分類。追い抜くコア数の上限を定義で
きなくなった瞬間にlock-freeに格下げされる。

▲なにがややこしいのか
・計算可能性（停止性問題？）を語る時にもwait-freeという言葉が出てきてそ
こと混線しているような気がする。
・CPUもOSも、同一のアドレスに複数のコアが何かしようとした場合には現実
には順序の公平性(fairness)なんて保証してくれてないのでここを分類する事
には現実的には意味が無い。という考えは一理あって、現実のシステムに詳
しい人ほどそういう実情を知ってるので混乱しやすい。でもここでは「仮にそ
ういう公平性を保証してくれるCPU&OSの上であっても各スレッドの公平性が保
たれないのだ」というlock-freeの挙動を説明するために持ち出しているので、
意味が無い、とまでは言い切れないと思う。意味が無いのは公平性を保証しき
るCPUやOSが実在していないからであって、現在でもそれを切り分けて議論す
る価値はあるのではないかと。
・依然として「lock-freeはベンチ取ればwait-freeと言っても良いぐらいの挙
動を示す」のでやっぱり無意味とも言えるけどCPUコアが数十・数百の単位の
世界になったら無視しきれない問題になるかも。

▲lock-freeとは
全部のコアが同一のアドレスに書き込み続けた場合、必ずどれかのスレッドは
試みに成功し、全体で見た時にどこかで処理が進んでいる事が保証できる。
具体的には自分のCASが失敗した事がそのまま他者のCAS成功を意味している場
合などがここに分類される。wait-freeから公平性が失われた位置づけ。

▲lock-freeとobstruction-freeの違い
live-lockするかしないか。live-lockとは2つ以上のスレッドがお互いがお互
いを回避するために取った行動で膠着状態になること。向かい合って歩く二
人がどちらに避けるか決めきれず、すれ違いに失敗する場面に近い。
lock-freeと違って自分の失敗が他者の成功を意味していないのが最大の特徴。
lock-freeから進行保証が失われた位置づけ。

▲何がややこしいのか
・現実のobstruction-freeと呼ばれているアルゴリズム（というかソフトウェ
アトランザクショナルメモリ）ではトランザクションマネージャを工夫するこ
とでlive-lockが起こる場面を最小限に抑えた物があり（practical lock-free
なんて呼んだりする）進行を大体保証できるのでlock-freeとも呼べるんじゃ
ないかと混乱していた。
・実際には1回でもlive-lockが起こる可能性があるならlock-freeには分類さ
れないと気づいた。それを一番端的に示す言葉が「誰かが必ず成功している」
という区分。

▲live-lockって？
dead-lockに響きが似てるので「対策しないと未来永劫停止しっぱなし」と早
とちりしたりもするけど、公平でランダムなスケジューリングが行われる前提
の上でなら、ほっとけば確率の問題で抜けてくれる。もちろんビザンチン障害
的にスケジューラに嫌がらせされ続けるなら終わらない。

▲live-lockする場合って？
SoftwareTransactionalMemoryの実装で見かける。データをread-lockするため
に読み出しor書き込み両方でデータのバージョンをインクリメントする場合な
ど
（あ、lockって言葉を使ってるけど実際にlockするわけではなくて、トランザ
クションの世界から言葉を借りてきただけ

transaction{
    local_a = a;
    local_b = b;
    a = local_a + 10;
    b = local_b + 20;
};

1.スレッド1がaを読む（aのバージョン++
2.スレッド2がaを読む（aのバージョン++
3.スレッド2がbを読む（bのバージョン++
4.スレッド1がbを読む（bのバージョン++
5.スレッド1はa+10を書こうとするもスレッド2がバージョンを変更してしまっ
たのでabort
6.スレッド2はa+10は成功するものの、スレッド1がbのバージョンを上げてし
まっているのでabort
7.結果として両方のスレッドがabortして仕切り直し

▲どうしてこうなった
・read-lockはトランザクションの線形一貫性を保証するために必要らしい
（トランザクションは良くわかりません
・そもそもトランザクショナルメモリの哲学が「先行したスレッドに追いつい
たということはそいつが何らかの理由で停止している事を意味する。そいつが
復帰する推定数百クロックか、自分がトランザクションを終える推定数十クロッ
クかで比較すれば自分が先行を踏み越えていくべきなのは確定的に明らか」と
いう考え方であり、近年のCPU&OS上では実質だいたいそんなところなので、踏
み越えが正義。
・さらにsolarisなどのOSでは「スレッドが停止してもスイッチしない」（プ
リエンプション延期？）機能が実装されているので、それとmutexなどの排他
制御を組み合わせて「lock-based」で「誰かが必ず成功する」なんてのが普通
のSTMよりスケーラビリティに優れたりとカオス
・さらにややこしくなるけどハードウェアトランザクショナルメモリの世界ではハー
ドウェアのサポートを受けられるので「本当に踏み越えるべきか」の見積もり
が少ないオーバーヘッドでできてだいぶ考え方が異なる。

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

wait-free:整理券を発行して旗に触れる順番待ちを制御してくれてる。もはや
競技にもならないけど、二度目に旗に触れる人は整理券をもらうところからや
り直しなので、並べばいつかは自分の番がくる。

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

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



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