test-and-setとcompare-and-swap

くまぎ @kumagi

test-and-setだとnコンセンサス問題に置いてn=2までしか対応できないのに対しcompare-and-swapだと無限のnに対応できる！さすが百獣の王CASさんやで！

SKS rep @repeatedly

コンセンサス問題って，分散環境における値の一致云々だったっけ？

M.K @ryutorion

@repeatedly それぞれのプロセスが値を提案して，そのうちの一つに合意をする，という問題だったと思います

SKS rep @repeatedly

TASがコンセンサス問題でn=2までしか扱えないのは，成功 or 失敗しか分からないから？

くまぎ @kumagi

@repeatedly ですね。boolしか扱えないからです。ハードウェアコストの関係上バランスが良かったという歴史なんでしょうね。

SKS rep @repeatedly

CASにはABA問題があったか…

SKS rep @repeatedly

TASやCASに関してまとまった知識が欲しいなぁ．書籍しかないのか？

くまぎ @kumagi

@repeatedly 読んでる限りだと英語のwikipediaがまとまってて良さげです。Java並行本だと時間の見積もりだとか他で見ない情報もあります。 http://en.wikipedia.org/wiki/Test-and-set

SKS rep @repeatedly

@kumagi なるなる

くまぎ @kumagi

test-and-setでできなくてcompare-and-swapにできる事がある！ってのが数学的に証明されたのが僕が3歳の頃。本当にこの世界は怖い。

SKS rep @repeatedly

Java並行本全部読めてないんだよな

SKS rep @repeatedly

TASもCAS同様最初にチェックが入ると思うんだけど，ABA問題起こりそうな？

SKS rep @repeatedly

ABA問題が起こるシチュエーションが今の実装絡めたらないってことなのか？後バスを占有するというのがよく分かってなかったり．

くまぎ @kumagi

@repeatedly ABA問題は「CASが成功するスレッドは1つだけだ」という前提でコードを組んだ場合に運悪く2つ以上のスレッドで値が一致して事故る現象を言うので、「TASが成功するスレッドは1つだけ」という前提で組むコードとは前提が違います。

SKS rep @repeatedly

@kumagi あーやっぱそうなのか．その辺の細かい前提が分かってなかった．

SKS rep @repeatedly

あれ，でもCASでもswapしたかどうかboolで返すような？実装によるだろうけど．

くまぎ @kumagi

@repeatedly cmpxchg8bの情報を眺めるに、成功時にZFが立って失敗時にZFがクリアされるけど、失敗時はついでに目的アドレスの値がEDX:EAXにロードされるようです。

SKS rep @repeatedly

コンセンサス問題におけるTAS / CASのスケーラビリティについてはまだまだ理解が必要

SKS rep @repeatedly

@kumagi へー．std.atomics.CASも中でそれ使ってるから，失敗した時にそれの値みればいいのか．

SKS rep @repeatedly

CASでほげほげしようと思ったらインラインアセンブラ相当の機能必須じゃね？

くまぎ @kumagi

@repeatedly asm volatile("" : : : "memory"); って書いてメモリフェンスとか必要でしょうね。boost::atomicのcasなんて成功時と失敗時に分けてメモリバリアを使い分けれるとか…。

SKS rep @repeatedly

@kumagi Boostやべぇ

SKS rep @repeatedly

D言語の場合はvolatile statementで囲いつつ，中でcore.atomic.CASとかかなぁ．いやしかしCASが必要になるということはそれ共有状態にあるということでshared修飾されているわけだから，メモリバリアは自動で貼られるはず？