ウェイトフリー性の証明について - くまメモ

気が向いたら書くと言ってしまったので忘れないうちに書く。 飢餓状態とは スレッドAが操作xを試みる スレッドBが操作yを試みる スレッドCが操作zを試みる という状況の時に、このアルゴリズムがLock-Freeである場合。すなわちスケジューラがどうスケジュールしても少なくともどれか1つのスレッドの操作が成功してしまう事が避けられない場合であってもスケジューラは特定のスレッドの操作だけを意図的に妨害する事は可能であることが多い。 例えば前回の記事のLock-Free Stackを例に話すと スレッドAがCAS（α→β）を試みようとする スケジューラがスレッドBのCASが成功するようスケジューリング 1〜2を繰り返し こうすれば理論上スケジューラはスレッドAに無限クロックのCPUを食わせながらも、無限にスレッドAのCASを成功させない事が可能だ。 このような状況の事をStarvation(飢餓

[fcicq]

Announce Array method to prove wait-free properties