コンペア・アンド・スワップ

コンペア・アンド・スワップ（Compare-and-Swap、CAS）は、CPUの特別な命令の一種。不可分操作として、あるメモリ位置の内容と指定された値を比較し、等しければそのメモリ位置に別の指定された値を格納する。この操作の結果、置換が行われたかどうかを示す必要があり、単純な真理値を返すか、そのメモリ位置から読み込んだ内容（書き込んだ内容ではない）を返す。

CAS命令は、マルチプロセッサシステムでセマフォなどを実装するのに使われる。マルチプロセッサシステムでLock-freeとWait-freeアルゴリズムを実装するのにも使われる。

Maurice Herlihy (1993年) は、CAS命令が単なるリード、ライトやテスト・アンド・セットでは実装できないことを示した。

応用

CAS命令を利用したアルゴリズムは、一般にあるキーとなるメモリ位置を読み取り、その古い値を記憶しておく。その古い値に基づいて、新しい値を計算する。その後、CAS命令でそのメモリ位置に新しい値を格納するが、そのときにCAS命令の比較によって計算に用いた古い値が置換時にもそのまま入っていることを確認する。CAS命令が比較に失敗した場合、最初から処理をやり直す。メモリ位置を再度読み取って、値を計算し、CAS命令を再実行するのである。

このようなアルゴリズムは False Positive（偽陽性）という問題（あるいは ABA問題）に対処しなければならない。古い値を読み取った後、CAS命令を実行するまでの間に、そのメモリ位置の内容が複数回書き換えられて偶然もとの古い値と同じビットパターンになっている可能性がある。CAS命令だけではこの事実を検出できない。その値はパターンは同じでも全く異なった意味かもしれない。

CAS命令はシングルプロセッサのシステムには不要である。その場合、単に割り込みを不可にすることで不可分性が達成される。しかし、マルチプロセッサシステムでは同時に全てのプロセッサで割り込みを不可とすることは困難だし、不十分でもある。他のプロセッサでも同じメモリ位置にアクセスしようとしているかもしれない。CAS命令はそのようなプロセッサ間の衝突を防ぎ、不可分（アトミック）にメモリ位置をチェックして変更することを可能にする。

ダブル・コンペアアンドスワップ

ダブル・コンペアアンドスワップ（Double Compare-and-Swap、DCASまたはCAS2）は、CAS命令の拡張された形式。DCAS命令は2箇所のメモリ位置が指定された値であるときに両者を書き換える命令である。

Greenwald は博士論文の中で DCAS 命令の必要性を説いた。それを使うことによって Software Transactional Memory（ロックフリーな並行性制御の一種。一連のメモリへのリード/ライトをトランザクションとして不可分に実行する）を簡単に実現できるとした。最近では、Software Transactional Memory は CAS命令だけで実現できることが示されている。

DCAS命令の主な利点は双方向の線形リストをアトミック（不可分）に実装できる点である[1]。

DCAS命令は万能ではない。DCASによるLock-freeとWait-freeアルゴリズムの実装は、CAS命令を使った場合と同程度に複雑でバグを作りこみ易い。したがって今後、DCAS命令が主流となることは難しい。2006年現在、広く使われているCPUではDCAS命令はサポートされていない。モトローラは68000系のプロセッサでCAS2命令をサポートしていたが、その性能が悪かったためにあまり使われなかった[2]。現在では命令セットから省かれている。CAS命令は今もよく使われている（IA-32、SPARCなど）。

関連項目

• フェッチ・アンド・アッド
• Load-Link/Store-Conditional
• Lock-freeとWait-freeアルゴリズム

外部リンク

いずれも英文

• compare_and_swap Kernel Service
• "A Practical Nonblocking Queue Algorithm Using Compare-and-Swap" by Chien-Hua Shann, Ting-Lu Huang, Cheng Chen
• "A Nonblocking Algorithm for Shared Queues Using Compare-and-Swap" by S. Prakash, Yann Hang Lee, T. Johnson
• Description of the CAS2 assembler instruction