Loading article…
コンピュータサイエンスにおいて、比較交換（CAS）は、マルチスレッドで同期を実現するために使用されるアトミック命令です。メモリ位置の内容を、指定された（以前の）値と比較し、同じ場合にのみ、そのメモリ位置の内容を新しい指定された値に変更します。これは単一のアトミック操作として実行されます。アトミック性により、新しい値は最新の情報に基づいて計算されることが保証されます。その間に別のスレッドによって値が更新されていた場合、書き込みは失敗します。操作の結果は、置換が実行されたかどうかを示す必要があります。これは、単純なブール値応答（このバリアントはしばしば比較設定と呼ばれます）またはメモリ位置から読み取った値（書き込んだ値ではなく）を返すことによって、読み取った値と書き込んだ値を「交換」することによって行うことができます。
比較交換操作は、次の擬似コードのアトミック版です。ここで、* はポインタを介したアクセスを表します。[ 1 ]
関数cas(p: int 型へのポインタ、old: int 型、new: int 型)は、 *p ≠ old の場合、 falseを返します。 *p ← 新規 trueを返す
この操作は、セマフォやミューテックスなどの同期プリミティブ[ 1 ]、およびより高度なロックフリーおよび待機フリーのアルゴリズムを実装するために使用されます。モーリス・ハーリヒー（1991）は、CASがアトミック読み取り、書き込み、フェッチアンドアッドよりも多くのこれらのアルゴリズムを実装でき、かなり大きなメモリ量があれば、それらすべてを実装できることを証明しました。[ 2 ] CASは、ロードリンク/ストア条件付きと同等であり、いずれかのプリミティブの定数回の呼び出しを使用して、待機なしでもう一方のプリミティブを実装できます。[ 3 ]
CAS を中心としたアルゴリズムは通常、重要なメモリ位置を読み取り、古い値を記憶します。その古い値に基づいて、新しい値を計算します。次に、CAS を使用して新しい値をスワップしようとします。このとき、比較によって位置が古い値と等しいかどうかがチェックされます。CAS が試行の失敗を示した場合、最初からやり直す必要があります。位置を再度読み取り、新しい値を再計算し、CAS を再度試行します。CAS 操作が失敗した後にすぐに再試行するのではなく、研究者らは、マルチプロセッサ システム (多くのスレッドが特定の共有変数を常に更新している) では、CAS が失敗したスレッドが指数バックオフ(つまり、CAS を再試行する前に少し待つ) を使用すると、システム全体のパフォーマンスが向上することを発見しました。[ 4 ]
比較交換の使用例として、整数をアトミックにインクリメントまたはデクリメントするアルゴリズムを以下に示します。これは、カウンタを使用するさまざまなアプリケーションで役立ちます。関数add は、*p ← *p + aという操作をアトミックに実行し(ここでも、C と同様に*でポインタの間接参照を表します)、カウンタに格納された最終値を返します。上記のcas の擬似コードとは異なり、 cas以外の操作のシーケンスがアトミックである必要はありません。
function add(p: int型へのポインタ、a: int型) は int型を返します 完了 ← false 完了していない間 value ← *p // この操作もアトミックである必要はありません。 完了 ← cas(p, value, value + a) 戻り値 + a
このアルゴリズムでは、 *pの値がフェッチ後（またはフェッチ中）かつ CAS がストアを実行する前に変更された場合、CAS はこの事実を検知して報告し、アルゴリズムが再試行するようにします。[ 5 ]
CASベースのアルゴリズムの中には、誤検出（ABA問題）の影響を受け、その対処が必要となるものがあります。古い値が読み取られてからCASが試行されるまでの間に、他のプロセッサやスレッドがメモリ位置を2回以上変更し、古い値と一致するビットパターンを取得してしまう可能性があります。問題は、この新しいビットパターンが古い値と全く同じように見えても、実際には異なる意味を持つ場合に発生します。例えば、再利用されたアドレスであったり、ラップされたバージョンカウンタであったりする可能性があります。
この問題に対する一般的な解決策は、倍長CAS（DCAS）を使用することです。例えば、32ビットシステムでは、64ビットCASを使用できます。後半部分はカウンタを保持するために使用されます。演算の比較部分では、ポインタとカウンタの以前に読み取った値と、現在のポインタとカウンタを比較します。一致する場合、スワップが発生し、新しい値が書き込まれますが、新しい値にはインクリメントされたカウンタが含まれます。これは、ABAが発生した場合、ポインタの値は同じになりますが、カウンタが同じになる可能性は極めて低いことを意味します（32ビット値の場合、2の倍数の32演算が発生し、カウンタがラップアラウンドし、その時点でポインタの値も偶然同じになる必要があるためです）。
これとは別の方法として（DCASを持たないCPUで有効）、完全なポインタではなく、フリーリストへのインデックスを使用する方法があります。例えば、32ビットCASの場合、16ビットのインデックスと16ビットのカウンタを使用します。ただし、カウンタ長を短縮することで、現代のCPU速度でもABAが実現可能になります。
この問題を軽減するのに役立つ簡単な方法の1つは、データ構造全体に1つのABAカウンタを使用するのではなく、各データ構造要素にABAカウンタを格納することです。
より複雑ではあるものの、より効果的な解決策は、安全なメモリ解放（SMR）を実装することです。これは実質的にロックフリーのガベージコレクションです。SMRを使用する利点は、特定のポインタがデータ構造内に常に一度しか存在しないことが保証されるため、ABA問題が完全に解決されることです。（SMRを使用しない場合、データ構造内に存在しないデータ要素であっても、すべてのデータ要素に安全にアクセスできる（メモリアクセス違反が発生しない）ように、フリーリストのようなものが使用されます。SMRを使用すると、データ構造内に実際に存在する要素のみにアクセスされます。）
CASやその他のアトミック命令は、単一プロセッサシステムでは不要だと考えられることがあります。なぜなら、実行中に割り込みを無効にすることで、任意の命令シーケンスのアトミック性を実現できるからです。しかし、割り込みを無効にすることには多くの欠点があります。例えば、割り込みを無効にすることが許されるコードは、悪意を持ってCPUを独占したり、誤ってマシンを無限ループやページフォルトでハングアップさせたりしないよう、信頼できるものでなければなりません。さらに、割り込みを無効にすることは、実用的とは言えないほどコストがかかるとみなされることがよくあります。そのため、 Linuxのfutexのように、単一プロセッサマシンでのみ実行されることを想定したプログラムであっても、アトミック命令の恩恵を受けることになります。
In multiprocessor systems, it is usually impossible to disable interrupts on all processors at the same time. Even if it were possible, two or more processors could be attempting to access the same semaphore's memory at the same time, and thus atomicity would not be achieved. The compare-and-swap instruction allows any processor to atomically test and modify a memory location, preventing such multiple-processor collisions.
On server-grade multi-processor architectures of the 2010s, compare-and-swap is cheap relative to a simple load that is not served from cache. A 2013 paper points out that a CAS is only 1.15 times more expensive than a non-cached load on Intel Xeon (Westmere-EX) and 1.35 times on AMD Opteron (Magny-Cours).[6]
Compare-and-swap (and compare-and-swap-double) has been an integral part of the IBM 370 (and all successor) architectures since 1970. The operating systems that run on these architectures make extensive use of this instruction to facilitate process (i.e., system and user tasks) and processor (i.e., central processors) parallelism while eliminating, to the greatest degree possible, the "disabled spinlocks" which had been employed in earlier IBM operating systems. Similarly, the use of test-and-set was also eliminated. In these operating systems, new units of work may be instantiated "globally", into the global service priority list, or "locally", into the local service priority list, by the execution of a single compare-and-swap instruction. This substantially improved the responsiveness of these operating systems.
In the x86 (since 80486) and Itanium architectures this is implemented as the compare and exchange (CMPXCHG) instruction (on a multiprocessor the LOCK prefix must be used).
As of 2013, most multiprocessor architectures support CAS in hardware, and the compare-and-swap operation is the most popular synchronization primitive for implementing both lock-based and non-blocking concurrent data structures.[4]
The atomic counter and atomic bitmask operations in the Linux kernel typically use a compare-and-swap instruction in their implementation. The SPARC-V8 and PA-RISC architectures are two of the very few recent architectures that do not support CAS in hardware; the Linux port to these architectures uses a spinlock.[7]
多くのCコンパイラは、C11<stdatomic.h>関数[ 8 ] 、その特定のCコンパイラの非標準C拡張機能[ 9 ]、または比較交換命令を使用してアセンブリ言語で直接記述された関数を呼び出すことによって、比較交換をサポートしています。
以下のC言語関数は、指定されたメモリ位置の古い値を返す比較交換型の基本的な動作を示しています。ただし、このバージョンでは、実際の比較交換操作が保証する重要なアトミック性は提供されません。
int compare_and_swap ( int * reg , int oldval , int newval ) { ATOMIC (); int old_reg_val = * reg ; if ( old_reg_val == oldval ) * reg = newval ; END_ATOMIC (); return old_reg_val ; }old_reg_valcompare_and_swapは常に返されますが、操作後にテストして と一致するかどうかを確認できます。異なる場合、別のプロセスが競合してreg 値を から変更することにoldval成功したことを意味します。compare_and_swapoldval
例えば、選挙プロトコルを実装する際に、各プロセスがcompare_and_swap自身のPID（= newval）に対して結果をチェックするようにすることができます。勝利したプロセスは、compare_and_swap初期の非PID値（例えばゼロ）を返します。敗北したプロセスには、勝利したPIDを返します。
これは、Intelソフトウェアマニュアル第2A巻に記載されているロジックです。
bool Compare_and_swap ( int * accum , int * dest , int newval ) { if ( * accum == * dest ) { * dest = newval ; trueを返します。} else { * accum = * dest ; falseを返します。} }CASは単一のポインタサイズのメモリ位置で動作するのに対し、ほとんどのロックフリーおよび待機フリーのアルゴリズムは複数の位置を変更する必要があるため、いくつかの拡張機能が実装されています。
java.util.concurrent.atomic、さまざまなクラスで「compareAndSet」を実装しています。