プロセッサのCAS(Compare And Swap)命令に関するWikipediaの記述

質問

CAS命令についてWikipediaで調べていたところ、どうしても分からない部分があったため、質問をしています。どなたか、補足説明願えませんでしょうか(当方ハードウェアエンジニア)。
オリジナルのURL: http://ja.wikipedia.org/wiki/コンペア・アンド・スワップ

1) このようなアルゴリズムは False Positive（偽陽性）という問題（あるいは ABA問題）に対処しなければならない。古い値を読み取った後、CAS命令を実行するまでの間に、そのメモリ位置の内容が複数回書き換えられて偶然もとの古い値と同じビットパターンになっている可能性がある。CAS命令だけではこの事実を検出できない。その値はパターンは同じでも全く異なった意味かもしれない。
==> [疑問点] コンペアしているアドレスに書かれているビット列の意味が、コンペアしてない部分によって変わるかも知れない、という状況を指しているのでしょうか? そのようなことがないことが仕様上保証されれば、偽陽性は気にしなくていいのでしょうか?

2) マルチプロセッサシステムでLock-freeとWait-freeアルゴリズムを実装するのにも使われる。Maurice Herlihy(1993年)はこれが単なるリード、ライトやテスト・アンド・セットでは実装できないことを示した。
==> [疑問点]どうしてTestAndSetでLock-Free/Wait-Freeが実現できないのかがどうしても分かりません。ひるがえって、TASとCASの違いが余りよく分からないのです。

以上宜しくお願い致します。

回答No.1

rinkun

1) Load-Link/Store-Conditionalとの比較上の問題でしょうか。
　LL/SCではLLからSCまで対象アドレスを監視するのでその間に書き換えのなかったことを保証できるが、CASでは対象アドレスの値を確認するだけなので、先に参照してから書き換えが発生していないとは保証できないということですね。
　対象アドレスの現在値ではなく過去の変更履歴に依存するようなコードだと問題が発生するのでしょうか。具体的に問題の起きる例を思いつきません。
2) 実現できない理由はWikipediaの「Lock-freeとWait-freeアルゴリズム」
　から参照されている論文を読んでもらうとして
　TestAndSetとCASの違いは、前者は成功／失敗しか分からないのに対して、後者は対象アドレスにCAS命令実行直前にあった値を取得できる点ですね。書き換え失敗した場合に得られる情報量が1ビットか1ワードかの違いが出ます。
　なお、TestAndSetはもともと対象アドレスが0かテストして1をセットする形だったと思います。それでx86ではバスロックして交換命令でできたはず。