Double compare-and-swap とは

ダブル・コンペ・アンド・スワップ(DCASまたはCAS2)は、特定のコンカレント・プログラミング・テクニックをサポートするために提案されたアトミック・プリミティブです。 DCASは必ずしも隣接していない2つのメモリ位置をとり、それらが事前に供給された「期待値」と一致する場合にのみ新しい値を書き込みます。そのように、これははるかに一般的な比較とスワップ(CAS)操作の拡張です。
DCASは、x86 CMPXCHG16Bのような命令によって実装された倍幅の比較およびスワップ(DWCAS)と混同されることがあります。 DCASは、ここで説明するように、通常はポインタ・サイズの2つの不連続なメモリ位置を処理しますが、DWCASは2つの隣接するポインタ・サイズのメモリ位置を処理します。
彼の博士論文では、現代のハードウェアにDCASを追加することを推奨しました。これは、適用が簡単で効率的なソフトウェアトランザクションメモリ(STM)を作成するために使用できることを示しています。 Greenwaldは、DCASとCASの利点は、高次(複数項目)CASnはDCASでO(n)に実装できますが、単一CASではO(n log p)時間が必要であることです。ここで、pは競合するプロセス。
DCASの利点の1つは、比較的簡単に原子deques(すなわち、二重リンクリスト)を実装する能力です。しかしながら、より最近では、CASのみを使用して同等の特性でSTMを実施できることが示されている。しかし、一般的に、DCASは銀色の弾丸ではありません。これを使用してロックフリーおよびウェイトフリーのアルゴリズムを実装するのは、一般的にCASと同じくらい複雑でエラーが発生しやすくなります。
モトローラでは、68kシリーズの命令セットにDCASが含まれていました。しかし、他のプリミティブと比較してDCASが遅い(明らかにキャッシュ処理の問題による)ため、実際の状況では回避されていました。 2015年の時点で、DCASは本番環境の広範なCPUによってネイティブにサポートされていません。
2つ以上のアドレスへのDCASの明らかな一般化は、MCAS(マルチワードCAS)と呼ばれることもあります。 MCASはネスト可能なLL / SCによって実装できますが、そのようなプリミティブはハードウェアで直接利用できません。 MCASは、さまざまな方法で、DCASの観点からソフトウェアで実装することができます。 Trevor Brown、Faith Ellen、およびEric Ruppertは、マルチアドレスLL / SC拡張(LLX / SCXと呼ばれる)をソフトウェアに実装しています。これは、MCASよりも制限的ですが、自動コード生成を使用して最も実績のある並列バイナリ検索ツリー(実際にはクロマティックツリー)の1つであり、JDK CASベースのスキップリスト実装をわずかに凌駕しています。
一般的に、DCASは、より表現力豊かなハードウェア・トランザクション・メモリーによって提供されます。 IBM POWER8とIntel Intel TSXは、トランザクショナル・メモリーの実装を提供します。 SunのキャンセルされたRockプロセッサも同様にそれをサポートしていました。