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

ウィキペディア

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

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/10/10 17:46 UTC 版)

コンペア・アンド・スワップ（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

ウィキペディア小見出し辞書

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

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/02/11 05:42 UTC 版)

「Lock-freeとWait-freeアルゴリズム」の記事における「コンペア・アンド・スワップ」の解説

Lock-free や Wait-free アルゴリズムを作るには、CPUが専用のアトミックな命令を提供し、それを使う必要がある。最も重要なのは、コンペア・アンド・スワップ（Compare and Swap, CASと省略する）である。Java では、java.util.concurrent.atomicパッケージ内のクラスに、compareAndSetメソッドとして存在する。これは、メモリアドレス、古い値、新しい値の3つを使う。もし、メモリアドレスに保存したある値が、指定された古い値ならば、それを新しい値に置き換え、そうでない場合は、何もしない。そして、この処理が成功したかどうかをプログラムに返す。CPUはこれをアトミックに実装する必要がある。現在[いつ?]のIntelプロセッサにはこの機能がある。この機能は、メモリからデータを読み出し、変更し、書き戻すという処理を、他のスレッドがその間に同時に変更を行っていない場合にのみ行う、というアルゴリズムを可能にする。 例えば、先ほどの銀行口座の例で、別なアルゴリズムを見てみる。ATMは現在の値を読み出し、加算し、書き込む、という3ステップにおいて、3ステップ目をコンペア・アンド・スワップを使って行う。この3ステップの間に他のスレッドが値を書き換えなければ、3ステップ目のコンペア・アンド・スワップは成功する。しかし、この3ステップにおいて預金処理が同時並行で起これば、1ステップ目の読み出した金額と、3ステップ目の書き込みで「比較して交換」を使って読んだ金額が一致しないため、失敗し、ATMは1ステップ目からやり直す。全てのATMは成功するまでこの3ステップを繰り返す。このアルゴリズムは Lock-free ではあるが、Wait-free ではない。なぜなら、他のATMが預金することにより、自分のATMが何度も挑戦する必要があるからである。 Wait-Free Synchronization (1993) では、コンペア・アンド・スワップがなぜ、Wait-freeにおいて必要か証明している。